蛋白質摺疊在生物信息學和生物化學中是一個重要的問題。 其中一個被廣泛使用來處理蛋白質折疊問題的模型是HP模型。在三維的HP模型中進行蛋白質折疊的問題已經被認為是NP完全的問題，而那些被用作處理此問題的演算法大多都只是在有限的時間內尋找近似最佳解。在這篇論文中，我們提出了一個新的使用分支界定法的演算法在三維的HP模型中處理蛋白質摺疊問題，我們將我們的演算法和其他演算法比較，而我們的演算法在實驗中有非常好的成果。

The protein folding problem(PFP) is an important issue in bioinformatics and biochemical physics. One of the most widely studied models of protein folding is the hydrophobic-polar (HP) model introduced by Dill. The PFP in the three-dimensional (3D) HP model has been shown to be NP-complete; the proposed algorithms for solving the problem can therefore only find near-optimal energy structures for most long benchmark sequences within acceptable time periods. In this paper, we propose a novel algorithm based on the branch-and-bound approach to solve the PFP in the 3D HP model; our proposed algorithm is more efficient than well-known approaches in experiments conducted with benchmark protein sequences.

[1] B. Barney “Introduction to Parallel Computing,”, Lawrence Livermore National Laboratory
[2] A. Bazzoli and A.G.B. Tettamanzi, “A memetic algorithm for protein structure prediction in a 3D-Lattice HP model,” EvoWorkshops, pp. 1-10, 2004.
[3] B. Berger and F. T. Leighton, “Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete,” Journal of Computational Biology, vol. 5, pp. 27– 40, 1998.
[4] T. Beutler and K. A. Dill, “A fast conformational method: a new algorithm for protein folding simulations”, Protein Science, vol. 5, pp. 147–153, 1996.
[5] M. Chen and W. Q. Huang, “A branch and bound algorithm for the protein folding problem in the hp lattice model,” Genomics, Proteomics and Bioinformatics, vol. 3, pp. 225–230, 2005.
[6] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C.Stein. “Introduction to Algorithms,” Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.3: Depth-first search, pp. 540–549.
[7] P. Crescenzi, D. Goldman, C. Papadimitriou, A. Piccolboni, and M. Yannakakis, “On the complexity of protein folding,” Journal of Computational Biology, vol. 5, pp. 423–465, 1998.
[8] K. A. Dill, “Theory for the folding and stability of globular proteins,” Biochemistry, vol. 24, pp. 1501–1509, 1985.
[9] K. A. Dill and K. Lau, “A lattice statistical mechanics model of the conformational sequence spaces of proteins,” Macromolecules, vol. 22, pp. 3986–3997, 1989.
[10] K. A. Dill, K. M. Fiebig, and H. S. Chan, “Cooperativity in Protein-Folding Kinetics,” Proceedings of the National Academy of Sciences, vol. 90, pp. 1942– 1946, 1993.
[11] K. A. Dill, S. Bromberg, K. Yue, K. Fiebig, D. Yee, P. Thomas, and H. chan, “Principles of protein folding-a perspective from simple exact models”, Protein Science, vol. 4, pp. 561–602, 1995.
[12] C. M. Dobson, “The nature and significance of protein folding,” Mechanisms of Protein Folding, vol. 2, pp. 236–243, 2000.
[13] M. Dorigo, V. Maniezzo, and A. Colorni, “Ant system: Optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man and Cybernetics, vol. 26, pp. 29–41, 1996.
[14] M. Dorigo and L. M. Gambardella, “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 1, pp. 53–66, 1997.
[15] W. E. Hart and S. Istrail, “Robust proofs of np-hardness for protein folding:general lattices and energy potentials,” Journal of Computational Biology, vol. 4, pp. 1–22, 1997.
[16] H. P. Hsu, V. Mehra, W. Nadler, and P. Grassberger, “Growth algorithm for lattice heteropolymers at low temperatures,” Journal of Chemical Physics, vol. 118, pp. 444–451, 2003.
[17] W. Huang, Z. Lu, and H. Shi, “Growth algorithm for finding low energy configurations of simple lattice proteins.” PHYSICAL REVIEW E 72, 016704, 2005.
[18] A. Shmygelska and H. H. Hoos, “An ant colony optimization algorithm for the 2D and 3D hydrophobic polar protein folding problem,” BMC Bioinformatics, vol. 6, 2005.
[19] J. Song, J. Cheng, and T. Zheng, “Protein 3D HP model folding simulation based on ACO*,” Proceedings of the Sixth International Conference on Intelligent Systems Design and Applications, vol. 1, pp. 410–415, 2006.
[20] L. Toma and S. Toma, “Contact interaction method: a new algorithm for protein folding simulations,” Protein Science, vol. 5, pp. 147–153, 1996.
[21] D. B. West, “Introduction to Graph Theory ” second edition, 1995
[22] K. Yue and K. A. Dill, “Forces of tertiary structural organizaton in globular protein,” Proceedings of the National Academy of Sciences, vol.92, pp. 146–150, 2005.
[23] K. Yue, K. M. Fiebig, P. D. Thomas, H. S. Chan, E. I. Shakhnovich, and K. A. Dill, “A test of lattice protein folding algorithms,” Proceedings of the National Academy of Sciences, vol. 5, pp. 325–329, 1995.