Protein structure alignment by deterministic annealing.
BACKGROUND
Protein structure alignment is one of the most important computational problems in molecular biology and plays a key role in protein structure prediction, fold family classification, motif finding, phylogenetic tree reconstruction and so on. From the viewpoint of computational complexity, a pairwise structure alignment is also a NP-hard problem, in contrast to the polynomial time algorithm for a pairwise sequence alignment.


RESULTS
We propose a method for solving the structure alignment problem in an accurate manner at the amino acid level, based on a mean field annealing technique. We define the structure alignment as a mixed integer-programming (MIP) problem. By avoiding complicated combinatorial computation and exploiting the special structure of the continuous partial problem, we transform the MIP into a reduced non-linear continuous optimization problem (NCOP) with a much simpler form. To optimize the reduced NCOP, a mean field annealing procedure is adopted with a modified Potts model, whose solution is generally identical to that of the MIP. There is no 'soft constraint' in our mean field model and all constraints are automatically satisfied throughout the annealing process, thereby not only making the optimization more efficient but also eliminating many unnecessary parameters that depend on problems and usually require careful tuning. A number of benchmark examples are tested by the proposed method with comparisons to several existing approaches.
Department of Electrical Engineering and Electronics, Osaka Sangyo University, Osaka 574-8530, Japan. chen@elec.osaka-sandai.ac.jp
Luonan
L
Chen
Tianshou
T
Zhou
Yun
Y
Tang
D000465:Algorithms; D000595:Amino Acid Sequence; D003198:Computer Simulation; D008956:Models, Chemical; D008958:Models, Molecular; D008969:Molecular Sequence Data; D011487:Protein Conformation; D011506:Proteins / Q000032:analysis / Q000737:chemistry*; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D017386:Sequence Homology, Amino Acid; D012984:Software
D011506:Proteins