title: An efficient algorithm for pairwise local alignment of protein interaction networks.
abstract: Recently, researchers seeking to understand, modify, and create beneficial traits in organisms have looked for evolutionarily conserved patterns of protein interactions. Their conservation likely means that the proteins of these conserved functional modules are important to the trait's expression. In this paper, we formulate the problem of identifying these conserved patterns as a graph optimization problem, and develop a fast heuristic algorithm for this problem. We compare the performance of our network alignment algorithm to that of the MaWISh algorithm [Koyutürk M, Kim Y, Topkara U, Subramaniam S, Szpankowski W, Grama A, Pairwise alignment of protein interaction networks, J Comput Biol13(2):182-199, 2006.], which bases its search algorithm on a related decision problem formulation. We find that our algorithm discovers conserved modules with a larger number of proteins in an order of magnitude less time. The protein sets found by our algorithm correspond to known conserved functional modules at comparable precision and recall rates as those produced by the MaWISh algorithm.
authors.affiliation: Department of Computer Science, Guangzhou University, 230 Wai Huan Xi Road, Guangzhou Higher Education Mega Center, Guangzhou, 510006, P. R. China , Shanghai Key Laboratory of Intelligent Information Processing, Fudan University, 220 Handan Road, Yangpu District, Shanghai, 200433, P. R. China , State Key Laboratory for Novel Software Technology, Nanjing University, 22 Hankou Road, Nanjing, Jiangsu, 210093, P. R. China.
authors.forename: Wenbin
authors.initials: W
authors.lastname: Chen
authors.forename: Matthew
authors.initials: M
authors.lastname: Schmidt
authors.forename: Wenhong
authors.initials: W
authors.lastname: Tian
authors.forename: Nagiza F
authors.initials: NF
authors.lastname: Samatova
authors.forename: Shaohong
authors.initials: S
authors.lastname: Zhang
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology; D017124:Conserved Sequence; D063990:Gene Ontology / Q000706:statistics & numerical data; D006801:Humans; D025941:Protein Interaction Mapping / Q000706:statistics & numerical data; D060066:Protein Interaction Maps; D016415:Sequence Alignment / Q000706:statistics & numerical data*
keywords: Network alignment; conserved functional modules; graph optimization; graph theory