A Novel Branch-and-Bound Algorithm for the Protein Folding Problem in the 3D HP Model

Hsin Hung Chou, Ching Tien Hsu, Li Hsuan Chen, Yue Cheng Lin, Sun Yuan Hsieh

研究成果: Article同行評審

摘要

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) lattice 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 lattice HP model. For 10 48-monomer benchmark sequences, our proposed algorithm finds the lowest energies so far within comparable computation times than previous methods.

原文English
文章編號8794636
頁(從 - 到)455-462
頁數8
期刊IEEE/ACM Transactions on Computational Biology and Bioinformatics
18
發行號2
DOIs
出版狀態Published - 2021 三月 1

All Science Journal Classification (ASJC) codes

  • 生物技術
  • 遺傳學
  • 應用數學

指紋

深入研究「A Novel Branch-and-Bound Algorithm for the Protein Folding Problem in the 3D HP Model」主題。共同形成了獨特的指紋。

引用此