Scalable global alignment for multiple biological networks

BMC Bioinformatics

Proceedings

Srinivasan Parthasarathy¹  Yu-Keng Shih¹ 

[1] Department of Computer Science and Engineering, Ohio State University, Columbus, OH, USA;

关键词: Similarity Score;    Priority Queue;    Network Alignment;    High Similarity Score;    Functional Orthologs;   

DOI  :  10.1186/1471-2105-13-S3-S11

来源: Springer

【 摘 要 】

BackgroundAdvances in high-throughput technology has led to an increased amount of available data on protein-protein interaction (PPI) data. Detecting and extracting functional modules that are common across multiple networks is an important step towards understanding the role of functional modules and how they have evolved across species. A global protein-protein interaction network alignment algorithm attempts to find such functional orthologs across multiple networks.ResultsIn this article, we propose a scalable global network alignment algorithm based on clustering methods and graph matching techniques in order to detect conserved interactions while simultaneously attempting to maximize the sequence similarity of nodes involved in the alignment. We present an algorithm for multiple alignments, in which several PPI networks are aligned. We empirically evaluated our algorithm on three real biological datasets with 6 different species and found that our approach offers a significant benefit both in terms of quality as well as speed over the current state-of-the-art algorithms.ConclusionComputational experiments on the real datasets demonstrate that our multiple network alignment algorithm is a more efficient and effective algorithm than the state-of-the-art algorithm, IsoRankN. From a qualitative standpoint, our approach also offers a significant advantage over IsoRankN for the multiple network alignment problem.

【 授权许可】

CC BY   
© Shih and Parthasarathy; licensee BioMed Central Ltd. 2012