Approximation Algorithms for Protein Folding in the Hydrophobic-Polar Model on 3D Hexagonal Prism Lattice

In this article, we study approximation algorithms for the protein folding problem in the hydrophobic-polar (HP) model on three-dimensional (3D) hexagonal prism lattice. We present two approximation algorithms based on previous work on two-dimensional (2D) square, 3D cubic, and 2D hexagonal lattice HP models. The first algorithm produces folds in which the H-H contacts are mainly on or between the hexagonal planes, and has approximation ratio [Formula: see text]. While in the folds produced by the second algorithm, the H-H contacts are mainly on or between the zigzag square planes. The theoretical approximation ratio bound of the second algorithm is no less than [Formula: see text], although no better than the first algorithm, it may perform much better for specific instances in practice.