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

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Article number8794636
Pages (from-to)455-462
Number of pages8
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume18
Issue number2
DOIs
Publication statusPublished - 2021 Mar 1

All Science Journal Classification (ASJC) codes

  • Biotechnology
  • Genetics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A Novel Branch-and-Bound Algorithm for the Protein Folding Problem in the 3D HP Model'. Together they form a unique fingerprint.

Cite this