Predicting protein interactions via parsimonious network history inference.
Predicting protein interactions via parsimonious network history inference.
复制标题
通过简约的网络历史推断来预测蛋白质相互作用。
DOI：
10.1093/bioinformatics/btt224
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Kingsford,Carl
中科院分区：
文献类型：
--
作者：
Patro,Rob;Kingsford,Carl
动机：蛋白质-蛋白质相互作用的网络水平进化历史的重建提供了一个原则性的方法来关联当今几个网络中的相互作用。在这里，我们提出了一个一般的框架，推断这样的历史，并展示它如何可以用来确定什么样的相互作用存在于祖先的网络，目前的相互作用，我们可能会期望存在的基础上进化的证据和信息现存的网络包含有关的顺序祖先的蛋白质duplications.Results：我们的框架特征的空间可能吝啬的网络的历史。它产生了一个结构，可以用来找到与历史相关的许多事件的概率。该框架是基于有向超图制定的动态规划，我们扩展到列举许多最佳和接近最佳的解决方案。该算法适用于重建祖先之间的相互作用bZIP转录因子，插补失踪的bZIP和蛋白质之间的相互作用，从五个疱疹病毒，并确定相对蛋白质的重复顺序在bZIP家族。我们的方法比现有的方法更准确地重建祖先的相互作用。在交叉验证测试中，我们发现我们的方法分别将bZIP和疱疹网络的前2%和17%的可能边缘中的大多数当前相互作用排除在外，使其成为边缘插补的竞争方法。它还估计相对bZIP蛋白质的重复顺序，仅使用相互作用数据和系统发育树拓扑结构，这是显着相关的基于序列的estimation.Availability：该算法是在C++实现，是开源的，可在http://www.cs.cmu.edu/ckingsf/software/parana2.Contact:robp@cs.cmu.edu或carlk@cs.cmu. edu补充信息：补充数据可在Bioinformaticsonline。
Motivation:Reconstruction of the network-level evolutionary history of protein–protein interactions provides a principled way to relate interactions in several present-day networks. Here, we present a general framework for inferring such histories and demonstrate how it can be used to determine what interactions existed in the ancestral networks, which present-day interactions we might expect to exist based on evolutionary evidence and what information extant networks contain about the order of ancestral protein duplications.Results:Our framework characterizes the space of likely parsimonious network histories. It results in a structure that can be used to find probabilities for a number of events associated with the histories. The framework is based on a directed hypergraph formulation of dynamic programming that we extend to enumerate many optimal and near-optimal solutions. The algorithm is applied to reconstructing ancestral interactions among bZIP transcription factors, imputing missing present-day interactions among the bZIPs and among proteins from five herpes viruses, and determining relative protein duplication order in the bZIP family. Our approach more accurately reconstructs ancestral interactions than existing approaches. In cross-validation tests, we find that our approach ranks the majority of the left-out present-day interactions among the top 2 and 17% of possible edges for the bZIP and herpes networks, respectively, making it a competitive approach for edge imputation. It also estimates relative bZIP protein duplication orders, using only interaction data and phylogenetic tree topology, which are significantly correlated with sequence-based estimates.Availability:The algorithm is implemented in C++, is open source and is available at http://www.cs.cmu.edu/ckingsf/software/parana2.Contact:robp@cs.cmu.edu or carlk@cs.cmu.eduSupplementary information:Supplementary data are available atBioinformaticsonline.