NETAL: a new graph-based method for global alignment of protein-protein interaction networks
NETAL: a new graph-based method for global alignment of protein-protein interaction networks
复制标题
DOI：
10.1093/bioinformatics/btt202
复制
发表时间：
2013-07-01
期刊：
影响因子：
5.8
通讯作者：
Arab, Seyed Shahriar
中科院分区：
文献类型：
--
作者：
Neyshabur, Behnam;Khadem, Ahmadreza;Arab, Seyed Shahriar
动机：蛋白质之间的相互作用以及由此产生的这种相互作用的网络在细胞生物学中起着核心作用。排列这些网络为我们提供了重要的信息，例如保守的复合物和进化关系。虽然已经有几个出版物上的蛋白质网络的全球比对，但是，没有一个提出的方法能够产生一个高度保守和有意义的比对。此外，目前的算法的时间复杂性，使他们不可能使用多个大型networks.Results：我们提出了一种新的算法的蛋白质-蛋白质相互作用网络的全局比对。它使用基于比对评分矩阵的贪婪方法，该矩阵来自输入网络的生物和拓扑信息，以找到最佳的全局网络比对。NETAL在几个测量方面优于其他全局比对方法，例如边缘正确性，最大公共连接子图和比对蛋白质之间的公共基因本体论术语的数量。由于NETAL算法的运行时间远小于其他现有的方法，因此NETAL算法可以很容易地扩展为多序列比对算法。此外，NETAL在性能方面优于所有其他现有算法，因此NETAL的短运行时间允许我们将其实现为蛋白质相互作用网络全局对齐的第一个服务器。
Motivation: The interactions among proteins and the resulting networks of such interactions have a central role in cell biology. Aligning these networks gives us important information, such as conserved complexes and evolutionary relationships. Although there have been several publications on the global alignment of protein networks; however, none of proposed methods are able to produce a highly conserved and meaningful alignment. Moreover, time complexity of current algorithms makes them impossible to use for multiple alignment of several large networks together.Results: We present a novel algorithm for the global alignment of protein-protein interaction networks. It uses a greedy method, based on the alignment scoring matrix, which is derived from both biological and topological information of input networks to find the best global network alignment. NETAL outperforms other global alignment methods in terms of several measurements, such as Edge Correctness, Largest Common Connected Subgraphs and the number of common Gene Ontology terms between aligned proteins. As the running time of NETAL is much less than other available methods, NETAL can be easily expanded to multiple alignment algorithm. Furthermore, NETAL overpowers all other existing algorithms in term of performance so that the short running time of NETAL allowed us to implement it as the first server for global alignment of protein-protein interaction networks.