Comparative analysis of biclustering algorithms

• DOI: 10.1145/1854776.1854814
• Publication Date: 2010-09-07T15:48:28Z
• Authors: Doruk Bozdağ; Ashwin S. Kumar; Umit V. Catalyurek
• Keywords: 0301 basic medicine; 03 medical and health sciences; 0206 medical engineering; 02 engineering and technology

Biclustering is a very popular method to identify hidden co-regulation patterns among genes. There are numerous biclustering algorithms designed to undertake this challenging task, however, a thorough comparison between these algorithms is even harder to accomplish due to lack of a ground truth and large variety in the search strategies and objectives of the algorithms. In this paper, we address this less studied, yet important problem and formally analyze several biclustering algorithms in terms of the bicluster patterns they attempt to discover. We systematically formulate the requirements for well-known patterns and show the constraints imposed by biclustering algorithms that determine their capacity to identify such patterns. We also give experimental results from a carefully designed testbed to evaluate the power of the employed search strategies. Furthermore, on a set of real datasets, we report the biological relevance of clusters identified by each algorithm.