Exploring biological interaction networks with tailored weighted quasi-bicliques.
Exploring biological interaction networks with tailored weighted quasi-bicliques.
复制标题
DOI：
10.1186/1471-2105-13-s10-s16
复制
发表时间：
2012-06-25
影响因子：
3
通讯作者：
Eulenstein O
中科院分区：
文献类型：
--
作者：
Chang WC;Vakati S;Krause R;Eulenstein O
生物网络提供了对基因及其产物的功能表征、DNA-蛋白质相互作用的表征、调控机制的识别以及其他生物学任务的基本见解。由于实验和生物学的复杂性，它们的计算开发面临着许多算法挑战。我们引入了新的加权拟biclique问题，以确定生物网络中的功能模块时，表示为二分图。与以往的拟biclique问题不同，我们使用边加权的拟biclique包含生物相互作用水平。虽然我们证明了我们的问题是NP难的，我们还描述了IP配方计算精确的解决方案，为中等规模的网络。我们使用模拟和经验数据验证我们的IP解决方案的有效性。模拟结果显示了较高的准biclique召回率，经验数据证实了我们的加权准biclique在提取特征和恢复生物网络中缺失的相互作用的能力。
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.