Maximum likelihood reconstruction of ancestral networks by integer linear programming
Maximum likelihood reconstruction of ancestral networks by integer linear programming
复制标题
DOI：
10.1093/bioinformatics/btaa931
复制
发表时间：
2021-04-15
期刊：
影响因子：
5.8
通讯作者：
Zhang，Xiuwei
中科院分区：
文献类型：
--
作者：
Rajan，Vaibhav;Zhang，Ziqi;Zhang，Xiuwei
对生物网络进化史的研究使人们能够深入了解各种生物分子过程的功能。网络生长模型，如带互补的复制突变(DMC)模型，为描述基于复制和发散的蛋白质-蛋白质相互作用(PPI)的进化提供了一种原则性的方法。结果提出了一种基于DMC模型的最大似然重构祖先网络的整数线性规划方法。我们证明了为找到最优解而设计的解的正确性。它还可以使用来自通用ILP解算器的高效启发式算法来获得在许多应用中可能有用的多个最优和接近最优解。在合成数据上的实验表明，我们的ILP比以前的方法获得更高的似然解，并且对噪声和模型失配具有很强的鲁棒性。我们在两个真实的PPI网络上评估了我们的算法，使用的蛋白质来自bZIP转录因子家族和指挥官复合体。在这两个网络上，我们的ILP解决方案的可能性更高，并与来自其他研究的独立生物学证据更好地一致。可用性和实施可在https://bitbucket.org/cdal/network-reconstruction.Supplementary信息上获得PYTHON实现补充数据可在生物信息学在线上获得。
MotivationThe study of the evolutionary history of biological networks enables deep functional understanding of various bio-molecular processes. Network growth models, such as the Duplication–Mutation with Complementarity (DMC) model, provide a principled approach to characterizing the evolution of protein–protein interactions (PPIs) based on duplication and divergence. Current methods for model-based ancestral network reconstruction primarily use greedy heuristics and yield sub-optimal solutions.ResultsWe present a new Integer Linear Programming (ILP) solution for maximum likelihood reconstruction of ancestral PPI networks using the DMC model. We prove the correctness of our solution that is designed to find the optimal solution. It can also use efficient heuristics from general-purpose ILP solvers to obtain multiple optimal and near-optimal solutions that may be useful in many applications. Experiments on synthetic data show that our ILP obtains solutions with higher likelihood than those from previous methods, and is robust to noise and model mismatch. We evaluate our algorithm on two real PPI networks, with proteins from the families of bZIP transcription factors and the Commander complex. On both the networks, solutions from our ILP have higher likelihood and are in better agreement with independent biological evidence from other studies.Availability and implementationA Python implementation is available at https://bitbucket.org/cdal/network-reconstruction.Supplementary informationSupplementary data are available atBioinformaticsonline.