Exploring biological interaction networks with tailored weighted quasi-bicliques

BMC Bioinformatics

Proceedings

Roland Krause¹  Oliver Eulenstein²  Wen-Chieh Chang²  Sudheer Vakati² 

[1] Department of Computer Science, Free University of Berlin, 14195, Berlin, Germany;Department of Computational Molecular Biology, Max Planck Institute for Molecular Genetics, 14195, Berlin, Germany;Luxembourg Centre for Systems Biology, University of Luxembourg, L-4362, Esch-sur-Alzette, Luxembourg;Department of Computer Science, Iowa State University, 50011, Ames, IA, USA;

关键词: Bipartite Graph;    Integer Program;    Edge Weight;    Biological Network;    Molecular Network;   

DOI  :  10.1186/1471-2105-13-S10-S16

来源: Springer

【 摘 要 】

BackgroundBiological networks provide fundamental insights into the functional characterization of genes and their products, the characterization of DNA-protein interactions, the identification of regulatory mechanisms, and other biological tasks. Due to the experimental and biological complexity, their computational exploitation faces many algorithmic challenges.ResultsWe introduce novel weighted quasi-biclique problems to identify functional modules in biological networks when represented by bipartite graphs. In difference to previous quasi-biclique problems, we include biological interaction levels by using edge-weighted quasi-bicliques. While we prove that our problems are NP-hard, we also describe IP formulations to compute exact solutions for moderately sized networks.ConclusionsWe verify the effectiveness of our IP solutions using both simulation and empirical data. The simulation shows high quasi-biclique recall rates, and the empirical data corroborate the abilities of our weighted quasi-bicliques in extracting features and recovering missing interactions from biological networks.

【 授权许可】

Unknown   
© Chang et al; licensee BioMed Central Ltd. 2012. This article is published under license to BioMed Central Ltd. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.