Convergent algorithms for protein structural alignment.
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.
Martínez
Leandro
L
Institute of Chemistry, State University of Campinas, Campinas, SP, Brazil. leandromartinez98@gmail.com
Andreani
Roberto
R
Martínez
José Mario
JM
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*
D011506:Proteins
Acta Crystallogr D Biol Crystallogr. 2004 Dec;60(Pt 12 Pt 1):2256-68
15572779
J Mol Biol. 2005 Mar 4;346(4):1173-88
15701525
Proteins. 2005 Feb 15;58(3):618-27
15609341
Curr Opin Struct Biol. 2004 Feb;14(1):70-5
15102452
Protein Sci. 1998 Feb;7(2):445-56
9521122
Nucleic Acids Res. 2000 Jan 1;28(1):235-42
10592235
Acta Crystallogr D Biol Crystallogr. 1996 Jul 1;52(Pt 4):842-57
15299650
Curr Biol. 1993 Mar;3(3):141-8
15335781
Curr Opin Struct Biol. 2006 Jun;16(3):393-8
16678402
Proc Natl Acad Sci U S A. 2003 Mar 4;100(5):2386-90
12606708
J Mol Biol. 1993 Sep 5;233(1):123-38
8377180
Proc Natl Acad Sci U S A. 2004 Aug 17;101(33):12201-6
15304646
Bioinformatics. 2000 Jun;16(6):566-7
10980157
Proc Natl Acad Sci U S A. 2005 Aug 30;102(35):12332-7
16109767
Proc Natl Acad Sci U S A. 2005 Apr 19;102(16):5641-2
15827120
BMC Bioinformatics. 2006 Dec 18;7 Suppl 5:S5
17254310
Proteins. 2004 Dec 1;57(4):702-10
15476259
Proc Natl Acad Sci U S A. 2005 Mar 8;102(10):3651-6
15705717
J Mol Biol. 1970 Mar;48(3):443-53
5420325
Protein Eng. 1998 Sep;11(9):739-47
9796821
Science. 1996 Aug 2;273(5275):595-603
8662544
Nucleic Acids Res. 2005 Apr 22;33(7):2302-9
15849316
Proteins. 1999 Dec 1;37(4):554-64
10651271
J Mol Biol. 2000 Aug 18;301(3):665-78
10966776