Network archaeology: uncovering ancient networks from present-day interactions.
Network archaeology: uncovering ancient networks from present-day interactions.
复制标题
DOI：
10.1371/journal.pcbi.1001119
复制
发表时间：
2011-04
影响因子：
4.3
通讯作者：
Kingsford C
中科院分区：
文献类型：
--
作者：
Navlakha S;Kingsford C
什么样的蛋白质在早已灭绝的酵母祖先中相互作用？随着时间的推移，蛋白质复合物的不同成员是如何组装在一起的？我们回答这些问题的能力受到无法获得祖先蛋白质-蛋白质相互作用（PPI）网络的限制。为了克服这一限制，我们提出了几种新的算法来重建当今网络的增长历史。我们的基于似然的方法通过在时间上向后应用假设的增长模型来找到图的可能先前状态。这种方法保留了节点身份，以便可以跟踪各个节点的历史记录。使用这种方法，我们估计蛋白质的年龄在酵母PPI网络，是在很好的协议与基于序列的估计年龄和蛋白质复合物的结构特征。此外，通过比较几种不同增长模型（互补性重复突变，森林火灾和优先连接）的推断历史的质量，我们提供了额外的证据，证明基于重复的模型比旨在模仿社交网络增长的模型更好地捕捉了PPI网络增长的许多特征。从重建的历史中，我们对现存和祖先相互作用的到达时间进行了建模，并预测随着时间的推移，复合物会显着重新连接，并且新的边缘往往会在现有复合物中形成。我们还假设每个蛋白质重复率的分布，跟踪网络聚类系数的变化，并预测现存蛋白质之间的旁系同源关系，这些蛋白质可能与单独使用序列推断的关系互补。最后，我们推断模型的合理参数，从而预测各种进化事件的相对概率。这些算法的成功表明，酵母PPI的部分历史是以其现在的形式编码的。关于当今交互网络的许多问题可以通过跟踪网络如何随时间变化来回答。我们提出了一套算法来揭示一个近似的节点和边缘的变化历史的网络时，只给出了一个现今的网络和一个合理的增长模型，它演变。我们的方法通过寻找高可能性的先前配置来跟踪现有网络。仅使用拓扑结构，我们可以估计蛋白质的年龄，并可以识别蛋白质复制的锚节点。我们重建的历史还使我们能够研究网络的拓扑性质如何随着时间的推移而变化，以及相互作用和模块如何演变。此外，我们提供了另一条证据线，表明酵母PPI进化的主要特征最好由基于复制的模型捕获。对推断出的古代网络的研究是动态网络分析的一个新应用，可以揭示驱动细胞机制的进化原理。这里介绍的算法也可能对研究其他古老的、不可用的网络有用。
What proteins interacted in a long-extinct ancestor of yeast? How have different members of a protein complex assembled together over time? Our ability to answer such questions has been limited by the unavailability of ancestral protein-protein interaction (PPI) networks. To overcome this limitation, we propose several novel algorithms to reconstruct the growth history of a present-day network. Our likelihood-based method finds a probable previous state of the graph by applying an assumed growth model backwards in time. This approach retains node identities so that the history of individual nodes can be tracked. Using this methodology, we estimate protein ages in the yeast PPI network that are in good agreement with sequence-based estimates of age and with structural features of protein complexes. Further, by comparing the quality of the inferred histories for several different growth models (duplication-mutation with complementarity, forest fire, and preferential attachment), we provide additional evidence that a duplication-based model captures many features of PPI network growth better than models designed to mimic social network growth. From the reconstructed history, we model the arrival time of extant and ancestral interactions and predict that complexes have significantly re-wired over time and that new edges tend to form within existing complexes. We also hypothesize a distribution of per-protein duplication rates, track the change of the network's clustering coefficient, and predict paralogous relationships between extant proteins that are likely to be complementary to the relationships inferred using sequence alone. Finally, we infer plausible parameters for the model, thereby predicting the relative probability of various evolutionary events. The success of these algorithms indicates that parts of the history of the yeast PPI are encoded in its present-day form. Many questions about present-day interaction networks could be answered by tracking how the network changed over time. We present a suite of algorithms to uncover an approximate node-by-node and edge-by-edge history of changes of a network when given only a present-day network and a plausible growth model by which it evolved. Our approach tracks the extant network backwards in time by finding high-likelihood previous configurations. Using topology alone, we show we can estimate protein ages and can identify anchor nodes from which proteins have duplicated. Our reconstructed histories also allow us to study how topological properties of the network have changed over time and how interactions and modules may have evolved. Further, we provide another line of evidence indicating that major features of the evolution of the yeast PPI are best captured by a duplication-based model. The study of inferred ancient networks is a novel application of dynamic network analysis that can unveil the evolutionary principles that drive cellular mechanisms. The algorithms presented here will likely also be useful for investigating other ancient, unavailable networks.
登录
查看更多内容
影响因子：
5.6
作者：
Bar-Ilan, Judit;Mat-Hassan, Mazlita;Levene, Mark
通讯作者：
Levene, Mark
DOI：
10.1073/pnas.0901910106
发表时间：
2009-07-21
影响因子：
11.1
作者：
Ahmed, Amr;Xing, Eric P.
通讯作者：
Xing, Eric P.
影响因子：
64.8
作者：
Gavin, AC;Aloy, P;Superti-Furga, G
通讯作者：
Superti-Furga, G
影响因子：
2.4
作者：
Callaway, DS;Hopcroft, JE;Strogatz, SH
通讯作者：
Strogatz, SH
DOI：
10.1093/bioinformatics/btn640
发表时间：
2009-02-01
期刊：
Bioinformatics (Oxford, England)
影响因子：
--
作者：
Huang H;Bader JS
通讯作者：
Bader JS