A biclustering algorithm for extracting bit-patterns from binary datasets

• Published in: Bioinformatics 2011-10, Vol.27 (19), p.2738-2745
• Main Authors: Rodriguez-Baena, Domingo S., Perez-Pulido, Antonio J., Aguilar−Ruiz, Jesus S.
• Format: Article
• Language: English
• Subjects: Algorithms; Biological and medical sciences; Central Nervous System Neoplasms - embryology; Central Nervous System Neoplasms - genetics; Cluster Analysis; Computational Biology - methods; Data Mining - methods; Databases, Factual; Fundamental and applied biological sciences. Psychology; Gene Expression; General aspects; Humans; Information Storage and Retrieval; Mathematics in biology. Statistical analysis. Models. Metrology. Data processing in biology (general aspects); Oligonucleotide Array Sequence Analysis; Software
• ISSN: 1367-4803; 1460-2059; 1367-4811
• DOI: 10.1093/bioinformatics/btr464

Motivation: Binary datasets represent a compact and simple way to store data about the relationships between a group of objects and their possible properties. In the last few years, different biclustering algorithms have been specially developed to be applied to binary datasets. Several approaches based on matrix factorization, suffix trees or divide-and-conquer techniques have been proposed to extract useful biclusters from binary data, and these approaches provide information about the distribution of patterns and intrinsic correlations. Results: A novel approach to extracting biclusters from binary datasets, BiBit, is introduced here. The results obtained from different experiments with synthetic data reveal the excellent performance and the robustness of BiBit to density and size of input data. Also, BiBit is applied to a central nervous system embryonic tumor gene expression dataset to test the quality of the results. A novel gene expression preprocessing methodology, based on expression level layers, and the selective search performed by BiBit, based on a very fast bit-pattern processing technique, provide very satisfactory results in quality and computational cost. The power of biclustering in finding genes involved simultaneously in different cancer processes is also shown. Finally, a comparison with Bimax, one of the most cited binary biclustering algorithms, shows that BiBit is faster while providing essentially the same results. Availability: The source and binary codes, the datasets used in the experiments and the results can be found at: http://www.upo.es/eps/bigs/BiBit.html Contact: [e-mail] Supplementary information: Supplementary data are available at Bioinformatics online.