Local optimization for global alignment of protein interaction networks
File(s)
Published version
Author(s)
Chindelevitch, Leonid
Liao, Chung-Shou
Berger, Bonnie
Type
Conference Paper
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.
Date Issued
2009-10-01
Date Acceptance
2009-09-14
Citation
Proceedings of the Pacific Symposium on Biocomputing, 2009, pp.123-132
ISBN
978-981-4299-47-3
Publisher
World Scientific
Start Page
123
End Page
132
Journal / Book Title
Proceedings of the Pacific Symposium on Biocomputing
Copyright Statement
© 2009 World Scientific. This paper is available open access and is licenced under a CC-BY Attribution Licence (https://creativecommons.org/licenses/by/3.0/)
License URL
Source
Pacific Symposium on Biocomputing 2010
Publication Status
Published
Start Date
2010-01-04
Finish Date
2010-01-08
Coverage Spatial
Kamuela, Hawaii