Mir Abolfazl, Naghibzadeh Mahmoud, Saadati Nayyereh
Department of Computer Software Engineering, Mashhad Branch, Islamic Azad University, Mashhad, Iran.
Department of Computer Engineering, Ferdowsi University of Mashhad, Mashhad, Iran.
Biosystems. 2017 Dec;162:24-34. doi: 10.1016/j.biosystems.2017.08.005. Epub 2017 Aug 30.
High-throughput methods have provided us with a large amount of data pertaining to protein-protein interaction networks. The alignment of these networks enables us to better understand biological systems. Given the fact that the alignment of networks is computationally intractable, it is important to introduce a more efficient and accurate algorithm which finds as large as possible similar areas among networks. This paper proposes a new algorithm named INDEX for the global alignment of protein-protein interaction networks. INDEX has multiple phases. First, it computes topological and biological scores of proteins and creates the initial alignment based on the proposed matching score strategy. Using networks topologies and aligned proteins, it then selects a set of high scoring proteins in each phase and extends new alignments around them until final alignment is obtained. Proposing a new alignment strategy, detailed consideration of matching scores, and growth of the alignment core has led INDEX to obtain a larger common connected subgraph with a much greater number of edges compared with previous methods. Regarding other measures such as edge correctness, symmetric substructure score, and runtime, the proposed algorithm performed considerably better than existing popular methods. Our results show that INDEX can be a promising method for identifying functionally conserved interactions.
The INDEX executable file is available at https://github.com/a-mir/index/.
高通量方法为我们提供了大量与蛋白质-蛋白质相互作用网络相关的数据。这些网络的比对能让我们更好地理解生物系统。鉴于网络比对在计算上难以处理，引入一种更高效、准确的算法很重要，该算法能在网络中找到尽可能大的相似区域。本文提出了一种名为INDEX的新算法，用于蛋白质-蛋白质相互作用网络的全局比对。INDEX有多个阶段。首先，它计算蛋白质的拓扑和生物学得分，并基于所提出的匹配得分策略创建初始比对。然后，利用网络拓扑和已比对的蛋白质，在每个阶段选择一组高分蛋白质，并围绕它们扩展新的比对，直到获得最终比对。提出新的比对策略、详细考虑匹配得分以及比对核心的扩展，使得INDEX与先前方法相比，能获得一个更大的具有更多边的公共连通子图。在诸如边正确性、对称子结构得分和运行时间等其他指标方面，所提出的算法比现有的流行方法表现得好得多。我们的结果表明，INDEX可能是一种识别功能保守相互作用的有前景的方法。
INDEX可执行文件可在https://github.com/a-mir/index/获取。
