title: Optimizing a global alignment of protein interaction networks.
abstract: BACKGROUND
  The global alignment of protein interaction networks is a widely studied problem. It is an important first step in understanding the relationship between the proteins in different species and identifying functional orthologs. Furthermore, it can provide useful insights into the species' evolution.
  
  
  RESULTS
  We propose a novel algorithm, PISwap, for optimizing global pairwise alignments of protein interaction networks, based on a local optimization heuristic that has previously demonstrated its effectiveness for a variety of other intractable problems. PISwap can begin with different types of network alignment approaches and then iteratively adjust the initial alignments by incorporating network topology information, trading it off for sequence information. In practice, our algorithm efficiently refines other well-studied alignment techniques with almost no additional time cost. We also show the robustness of the algorithm to noise in protein interaction data. In addition, the flexible nature of this algorithm makes it suitable for different applications of network alignment. This algorithm can yield interesting insights into the evolutionary dynamics of related species.
  
  
  BACKGROUND
  Our software is freely available for non-commercial purposes from our Web site, http://piswap.csail.mit.edu/.
  
  
  BACKGROUND
  bab@csail.mit.edu or csliao@ie.nthu.edu.tw.
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Computer Science and Artificial Intelligence Laboratory and Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA, Department of Computer Science and Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu 30013, Taiwan.
authors.forename: Leonid
authors.initials: L
authors.lastname: Chindelevitch
authors.forename: Cheng-Yu
authors.initials: CY
authors.lastname: Ma
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; D005075:Biological Evolution; D006801:Humans; D025941:Protein Interaction Mapping / Q000379:methods*; D011506:Proteins / Q000737:chemistry; D012984:Software
chemical_list: D011506:Proteins
references.citation: Nucleic Acids Res. 2004 Jul 1;32(Web Server issue):W83-8
references.pmid: 15215356
references.citation: Bioinformatics. 2007 Jul 1;23(13):i149-58
references.pmid: 17646291
references.citation: Nucleic Acids Res. 2009 Jan;37(Database issue):D767-72
references.pmid: 18988627
references.citation: Nature. 2000 Feb 10;403(6770):623-7
references.pmid: 10688190
references.citation: Bioinformatics. 2011 May 15;27(10):1390-6
references.pmid: 21414992
references.citation: Nature. 2002 Jan 10;415(6868):141-7
references.pmid: 11805826
references.citation: Nucleic Acids Res. 2009 Jan;37(Database issue):D690-7
references.pmid: 19033362
references.citation: Nat Biotechnol. 2005 Jul;23(7):839-44
references.pmid: 16003372
references.citation: Proc Natl Acad Sci U S A. 2005 Feb 8;102(6):1974-9
references.pmid: 15687504
references.citation: Nucleic Acids Res. 2011 Jan;39(Database issue):D295-300
references.pmid: 21177658
references.citation: J Integr Bioinform. 2010 Mar 25;7(3):
references.pmid: 20375452
references.citation: Bioinformatics. 2012 Dec 1;28(23):3105-14
references.pmid: 23047556
references.citation: Proc Natl Acad Sci U S A. 2001 Apr 10;98(8):4569-74
references.pmid: 11283351
references.citation: Nucleic Acids Res. 2008 Jan;36(Database issue):D637-40
references.pmid: 18000002
references.citation: Cell. 2007 Nov 2;131(3):557-71
references.pmid: 17981122
references.citation: Proc Natl Acad Sci U S A. 2008 Sep 2;105(35):12763-8
references.pmid: 18725631
references.citation: Nucleic Acids Res. 2004 Jan 1;32(Database issue):D449-51
references.pmid: 14681454
references.citation: Bioinformatics. 2004 Dec 12;20(18):3508-15
references.pmid: 15284103
references.citation: Nat Biotechnol. 2002 Oct;20(10):991-7
references.pmid: 12355115
references.citation: Bioinformatics. 2009 Jun 15;25(12):i240-6
references.pmid: 19477994
references.citation: BMC Bioinformatics. 2013;14 Suppl 2:S12
references.pmid: 23368411
references.citation: Nat Rev Genet. 2004 Feb;5(2):101-13
references.pmid: 14735121
references.citation: Bioinformatics. 2008 Apr 15;24(8):1093-9
references.pmid: 18344248
references.citation: Nature. 2003 Mar 13;422(6928):198-207
references.pmid: 12634793
references.citation: J Comput Biol. 2009 Aug;16(8):1001-22
references.pmid: 19645599
references.citation: Nature. 2002 Jan 10;415(6868):180-3
references.pmid: 11805837
references.citation: Bioinformatics. 2009 Jun 15;25(12):i259-67
references.pmid: 19477997
references.citation: BMC Bioinformatics. 2006 May 09;7:252
references.pmid: 16684350
references.citation: Proc Natl Acad Sci U S A. 2006 Jul 18;103(29):10967-72
references.pmid: 16835301
references.citation: Curr Opin Struct Biol. 1997 Jun;7(3):422-7
references.pmid: 9204286
references.citation: Proc Natl Acad Sci U S A. 2003 Sep 30;100(20):11394-9
references.pmid: 14504397
references.citation: J Comput Biol. 2006 Mar;13(2):182-99
references.pmid: 16597234
references.citation: Bioinformatics. 2013 Apr 1;29(7):917-24
references.pmid: 23413436
references.citation: Bioinformatics. 2009 Jun 15;25(12):i253-8
references.pmid: 19477996
references.citation: J Comput Biol. 2009 Aug;16(8):989-99
references.pmid: 19624266
references.citation: Nat Genet. 1997 Jul;16(3):277-82
references.pmid: 9207794
references.citation: BMC Bioinformatics. 2010 Jan 18;11 Suppl 1:S38
references.pmid: 20122211
references.citation: Pac Symp Biocomput. 2010;:123-32
references.pmid: 19908365
references.citation: J R Soc Interface. 2010 Sep 6;7(50):1341-54
references.pmid: 20236959