Local optimization for global alignment of protein interaction networks.
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.
Chindelevitch
Leonid
L
Department of Mathematics and Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, USA. leonidus@csail.mit.edu
Liao
Chung-Shou
CS
Berger
Bonnie
B
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
D029742:Caenorhabditis elegans Proteins; D029721:Drosophila Proteins; D029701:Saccharomyces cerevisiae Proteins