title: Local optimization for global alignment of protein interaction networks.
abstract: We propose a novel algorithm, PISwap, for computing global pairwise alignments of protein interaction networks, based on a local optimization heuristic that has previously demonstrated its effectiveness for a variety of other NP-hard problems, such as the Traveling Salesman Problem. Our algorithm begins with a sequence-based network alignment and then iteratively adjusts the alignment by incorporating network structure information. It has a worst-case pseudo-polynomial running-time bound and is very efficient in practice. It is shown to produce improved alignments in several well-studied cases. In addition, the flexible nature of this algorithm makes it suitable for different applications of network alignments. Finally, this algorithm can yield interesting insights into the evolutionary history of the compared species.
authors.affiliation: Department of Mathematics and Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, USA. leonidus@csail.mit.edu
authors.forename: Leonid
authors.initials: L
authors.lastname: Chindelevitch
authors.forename: Chung-Shou
authors.initials: CS
authors.lastname: Liao
authors.forename: Bonnie
authors.initials: B
authors.lastname: Berger
mesh_terms: D000465:Algorithms; D000818:Animals; D029742:Caenorhabditis elegans Proteins / Q000737:chemistry / Q000235:genetics / Q000378:metabolism; D019295:Computational Biology; D029721:Drosophila Proteins / Q000737:chemistry / Q000235:genetics / Q000378:metabolism; D019143:Evolution, Molecular; D008957:Models, Genetic; D060066:Protein Interaction Maps / Q000235:genetics; D029701:Saccharomyces cerevisiae Proteins / Q000737:chemistry / Q000235:genetics / Q000378:metabolism; D016415:Sequence Alignment
chemical_list: D029742:Caenorhabditis elegans Proteins; D029721:Drosophila Proteins; D029701:Saccharomyces cerevisiae Proteins