Abstract | ||
---|---|---|
Biological 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.We 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.We 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. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1186/1471-2105-13-S10-S16 | BMC Bioinformatics |
Keywords | Field | DocType |
bioinformatics,microarrays,algorithms | Biological network,Computer science,Biological computation,Systems biology,Theoretical computer science,Bioinformatics,Computational genomics,Gene regulatory network | Journal |
Volume | Issue | ISSN |
13 Suppl 10 | S-10 | 1471-2105 |
Citations | PageRank | References |
13 | 0.52 | 11 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Wen-Chieh Chang | 1 | 119 | 7.15 |
Sudheer Vakati | 2 | 24 | 3.98 |
Roland Krause | 3 | 70 | 10.08 |
Oliver Eulenstein | 4 | 505 | 52.71 |