PMID- 15308541
OWN - NLM
STAT- MEDLINE
DCOM- 20050308
LR  - 20130520
IS  - 1367-4803 (Print)
IS  - 1367-4803 (Linking)
VI  - 21
IP  - 1
DP  - 2005 Jan 1
TI  - Protein structure alignment by deterministic annealing.
PG  - 51-62
AB  - MOTIVATION: 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.
FAU - Chen, Luonan
AU  - Chen L
AD  - Department of Electrical Engineering and Electronics, Osaka Sangyo University, 
      Osaka 574-8530, Japan. chen@elec.osaka-sandai.ac.jp
FAU - Zhou, Tianshou
AU  - Zhou T
FAU - Tang, Yun
AU  - Tang Y
LA  - eng
PT  - Journal Article
DEP - 20040812
PL  - England
TA  - Bioinformatics
JT  - Bioinformatics (Oxford, England)
JID - 9808944
RN  - 0 (Proteins)
SB  - IM
MH  - *Algorithms
MH  - Amino Acid Sequence
MH  - Computer Simulation
MH  - Models, Chemical
MH  - *Models, Molecular
MH  - Molecular Sequence Data
MH  - *Protein Conformation
MH  - Proteins/analysis/*chemistry
MH  - Sequence Alignment/*methods
MH  - Sequence Analysis, Protein/*methods
MH  - Sequence Homology, Amino Acid
MH  - Software
EDAT- 2004/08/17 10:00
MHDA- 2005/03/09 09:00
CRDT- 2004/08/17 10:00
PHST- 2004/08/17 10:00 [pubmed]
PHST- 2005/03/09 09:00 [medline]
PHST- 2004/08/17 10:00 [entrez]
AID - bth467 [pii]
AID - 10.1093/bioinformatics/bth467 [doi]
PST - ppublish
SO  - Bioinformatics. 2005 Jan 1;21(1):51-62. doi: 10.1093/bioinformatics/bth467. Epub 
      2004 Aug 12.