Integrated simultaneous analysis of different biomedical data types with exact weighted bi-cluster editing

More Information | Back to archive
Full Text of this article Full article [PDF] (907,46 kB)
doi doi:10.2390/biecoll-jib-2012-197
submission May 16, 2012
published July 17, 2012
NCBI PubMed PubMed ID 22802138

Peng Sun, Jiong Guo and Jan Baumbach

Correspondence should be addressed to:
Peng Sun
Computational Systems Biology group, Max Planck Institute for Informatics, Campus E1.4, 66123 Saarbr├╝cken, Germany


The explosion of biological data has largely influenced the focus of today’s biology research. Integrating and analysing large quantity of data to provide meaningful insights has become the main challenge to biologists and bioinformaticians. One major problem is the combined data analysis of data from different types, such as phenotypes and genotypes. This data is modelled as bi-partite graphs where nodes correspond to the different data points, mutations and diseases for instance, and weighted edges relate to associations between them. Bi-clustering is a special case of clustering designed for partitioning two different types of data simultaneously. We present a bi-clustering approach that solves the NP-hard weighted bi-cluster editing problem by transforming a given bi-partite graph into a disjoint union of bi-cliques. Here we contribute with an exact algorithm that is based on fixed-parameter tractability. We evaluated its performance on artificial graphs first. Afterwards we exemplarily applied our Java implementation to data of genome-wide association studies (GWAS) data aiming for discovering new, previously unobserved geno-to-pheno associations. We believe that our results will serve as guidelines for further wet lab investigations. Generally our software can be applied to any kind of data that can be modelled as bi-partite graphs. To our knowledge it is the fastest exact method for weighted bi-cluster editing problem.


Peng Sun, Jiong Guo and Jan Baumbach. Integrated simultaneous analysis of different biomedical data types with exact weighted bi-cluster editing. Journal of Integrative Bioinformatics, 9(2):197, 2012. Online Journal:
imprint | sitemap | credits | top