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 sys-tems. Given the fact that the alignment of networks is computationally intractable, it is important tointroduce a more efficient and accurate algorithm which finds as large as possible similar areas amongnetworks. This paper proposes a new algorithm named INDEX for the global alignment of protein–proteininteraction networks. INDEX has multiple phases. First, it computes topological and biological scores ofproteins and creates the initial alignment based on the proposed matching score strategy. Using networkstopologies and aligned proteins, it then selects a set of high scoring proteins in each phase and extendsnew 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 obtaina larger common connected subgraph with a much greater number of edges compared with previousmethods. Regarding other measures such as edge correctness, symmetric substructure score, and run-time, the proposed algorithm performed considerably better than existing popular methods. Our resultsshow that INDEX can be a promising method for identifying functionally conserved interactions.Availability: The INDEX executable file is available at https://github.com/a-mir/index/.

Keywords