title: Convergent algorithms for protein structural alignment.
abstract: BACKGROUND
  Many algorithms exist for protein structural alignment, based on internal protein coordinates or on explicit superposition of the structures. These methods are usually successful for detecting structural similarities. However, current practical methods are seldom supported by convergence theories. In particular, although the goal of each algorithm is to maximize some scoring function, there is no practical method that theoretically guarantees score maximization. A practical algorithm with solid convergence properties would be useful for the refinement of protein folding maps, and for the development of new scores designed to be correlated with functional similarity.
  
  
  RESULTS
  In this work, the maximization of scoring functions in protein alignment is interpreted as a Low Order Value Optimization (LOVO) problem. The new interpretation provides a framework for the development of algorithms based on well established methods of continuous optimization. The resulting algorithms are convergent and increase the scoring functions at every iteration. The solutions obtained are critical points of the scoring functions. Two algorithms are introduced: One is based on the maximization of the scoring function with Dynamic Programming followed by the continuous maximization of the same score, with respect to the protein position, using a smooth Newtonian method. The second algorithm replaces the Dynamic Programming step by a fast procedure for computing the correspondence between C alpha atoms. The algorithms are shown to be very effective for the maximization of the STRUCTAL score.
  
  
  CONCLUSIONS
  The interpretation of protein alignment as a LOVO problem provides a new theoretical framework for the development of convergent protein alignment algorithms. These algorithms are shown to be very reliable for the maximization of the STRUCTAL score, and other distance-dependent scores may be optimized with same strategy. The improved score optimization provided by these algorithms provide means for the refinement of protein fold maps and also for the development of scores designed to match biological function. The LOVO strategy may be also used for more general structural superposition problems such as flexible or non-sequential alignments. The package is available on-line at http://www.ime.unicamp.br/~martinez/lovoalign.
authors: Institute of Chemistry, State University of Campinas, Campinas, SP, Brazil. leandromartinez98@gmail.com
authors: Leandro
authors: L
authors: Martínez
authors: Roberto
authors: R
authors: Andreani
authors: José Mario
authors: JM
authors: Martínez
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D008969:Molecular Sequence Data; D017510:Protein Folding; D011506:Proteins / Q000737:chemistry* / Q000648:ultrastructure*; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*
chemical_list: D011506:Proteins
references: Acta Crystallogr D Biol Crystallogr. 2004 Dec;60(Pt 12 Pt 1):2256-68
references: 15572779
references: J Mol Biol. 2005 Mar 4;346(4):1173-88
references: 15701525
references: Proteins. 2005 Feb 15;58(3):618-27
references: 15609341
references: Curr Opin Struct Biol. 2004 Feb;14(1):70-5
references: 15102452
references: Protein Sci. 1998 Feb;7(2):445-56
references: 9521122
references: Nucleic Acids Res. 2000 Jan 1;28(1):235-42
references: 10592235
references: Acta Crystallogr D Biol Crystallogr. 1996 Jul 1;52(Pt 4):842-57
references: 15299650
references: Curr Biol. 1993 Mar;3(3):141-8
references: 15335781
references: Curr Opin Struct Biol. 2006 Jun;16(3):393-8
references: 16678402
references: Proc Natl Acad Sci U S A. 2003 Mar 4;100(5):2386-90
references: 12606708
references: J Mol Biol. 1993 Sep 5;233(1):123-38
references: 8377180
references: Proc Natl Acad Sci U S A. 2004 Aug 17;101(33):12201-6
references: 15304646
references: Bioinformatics. 2000 Jun;16(6):566-7
references: 10980157
references: Proc Natl Acad Sci U S A. 2005 Aug 30;102(35):12332-7
references: 16109767
references: Proc Natl Acad Sci U S A. 2005 Apr 19;102(16):5641-2
references: 15827120
references: BMC Bioinformatics. 2006 Dec 18;7 Suppl 5:S5
references: 17254310
references: Proteins. 2004 Dec 1;57(4):702-10
references: 15476259
references: Proc Natl Acad Sci U S A. 2005 Mar 8;102(10):3651-6
references: 15705717
references: J Mol Biol. 1970 Mar;48(3):443-53
references: 5420325
references: Protein Eng. 1998 Sep;11(9):739-47
references: 9796821
references: Science. 1996 Aug 2;273(5275):595-603
references: 8662544
references: Nucleic Acids Res. 2005 Apr 22;33(7):2302-9
references: 15849316
references: Proteins. 1999 Dec 1;37(4):554-64
references: 10651271
references: J Mol Biol. 2000 Aug 18;301(3):665-78
references: 10966776