Computer Science and Artificial Intelligence Laboratory and Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA, Department of Computer Science and Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu 30013, Taiwan.
Bioinformatics. 2013 Nov 1;29(21):2765-73. doi: 10.1093/bioinformatics/btt486. Epub 2013 Sep 17.
The global alignment of protein interaction networks is a widely studied problem. It is an important first step in understanding the relationship between the proteins in different species and identifying functional orthologs. Furthermore, it can provide useful insights into the species' evolution.
We propose a novel algorithm, PISwap, for optimizing global pairwise alignments of protein interaction networks, based on a local optimization heuristic that has previously demonstrated its effectiveness for a variety of other intractable problems. PISwap can begin with different types of network alignment approaches and then iteratively adjust the initial alignments by incorporating network topology information, trading it off for sequence information. In practice, our algorithm efficiently refines other well-studied alignment techniques with almost no additional time cost. We also show the robustness of the algorithm to noise in protein interaction data. In addition, the flexible nature of this algorithm makes it suitable for different applications of network alignment. This algorithm can yield interesting insights into the evolutionary dynamics of related species.
Our software is freely available for non-commercial purposes from our Web site, http://piswap.csail.mit.edu/.
bab@csail.mit.edu or csliao@ie.nthu.edu.tw.
Supplementary data are available at Bioinformatics online.
蛋白质相互作用网络的全局比对是一个广泛研究的问题。它是理解不同物种中蛋白质之间关系和识别功能同源物的重要第一步。此外，它还可以为物种进化提供有用的见解。
我们提出了一种新的算法 PISwap，用于优化蛋白质相互作用网络的全局成对比对，该算法基于一种局部优化启发式算法，该算法已被证明在许多其他棘手问题上非常有效。PISwap 可以从不同类型的网络比对方法开始，然后通过整合网络拓扑信息，在序列信息上进行交换，迭代调整初始比对。在实践中，我们的算法可以有效地改进其他经过充分研究的比对技术，几乎不需要额外的时间成本。我们还展示了该算法对蛋白质相互作用数据中噪声的鲁棒性。此外，该算法的灵活性使其适用于网络比对的不同应用。该算法可以为相关物种的进化动态提供有趣的见解。
我们的软件可免费用于非商业用途，请访问我们的网站 http://piswap.csail.mit.edu/。
bab@csail.mit.edu 或 csliao@ie.nthu.edu.tw。
补充数据可在 Bioinformatics 在线获取。
