A Branch and Bound Algorithm for the Protein Folding Problem in the HP Lattice Model
Open Access
- 1 January 2005
- journal article
- research article
- Published by Oxford University Press (OUP) in Genomics, Proteomics and Bioinformatics
- Vol. 3 (4), 225-230
- https://doi.org/10.1016/s1672-0229(05)03031-7
Abstract
A branch and bound algorithm is proposed for the two-dimensional protein folding problem in the HP lattice model. In this algorithm, the benefit of each possible location of hydrophobic monomers is evaluated and only promising nodes are kept for further branching at each level. The proposed algorithm is compared with other well-known methods for 10 benchmark sequences with lengths ranging from 20 to 100 monomers. The results indicate that our method is a very efficient and promising tool for the protein folding problem.Keywords
Funding Information
- National Natural Science Foundation of China (10471051)
- National Basic Research Program (973 Program) of China (2004CB318000)
This publication has 16 references indexed in Scilit:
- Personification algorithm for protein folding problem: Im-provements in PERMChinese Science Bulletin, 2004
- Guided simulated annealing method for optimization problemsPhysical Review E, 2003
- Growth algorithms for lattice heteropolymers at low temperaturesThe Journal of Chemical Physics, 2003
- Protein Folding in the Hydrophobic-Hydrophilic (HP) Model is NP-CompleteJournal of Computational Biology, 1998
- On the Complexity of Protein FoldingJournal of Computational Biology, 1998
- Robust Proofs of NP-Hardness for Protein Folding: General Lattices and Energy PotentialsJournal of Computational Biology, 1997
- Principles of protein folding — A perspective from simple exact modelsProtein Science, 1995
- Genetic Algorithms for Protein Folding SimulationsJournal of Molecular Biology, 1993
- REDUCED REPRESENTATION MODEL OF PROTEIN-STRUCTURE PREDICTION - STATISTICAL POTENTIAL AND GENETIC ALGORITHMSProtein Science, 1993
- Theory for the folding and stability of globular proteinsBiochemistry, 1985