Protein folding in HP model on hexagonal prism lattice with diagonals

Abstract

The protein folding problem consist in nding the primary structure or native conformation of a protein from its amino acid sequence. It is one of the most studied computational problems in Bioinformatics and Computational Biology. Since, this is NP-hard problem, a number of simpli ed models have been proposed in literature to capture the essential properties of this problem. An important class of simpli ed models are known as the lattice models. Lattice models have been proven to be extremely useful tools for reasoning about the complexity of the protein folding problems. Hydrophobic-Polar (HP) model is one of the lattice models where the main force in the folding process is the hydrophobic-hydrophobic force. In this thesis, we introduce the hexagonal prism lattice with diagonals, that solve some long standing problems of other lattices for protein folding, e.g. parity problem. We present two novel approximation algorithms to solve the protein folding problem in the hexagonal prism lattice with diagonals in HP model. For any given HP string, our rst algorithm (Algorithm HelixArrangement) achieves an approximation ratio of 2. Our second algorithm (Algorithm LayerArrangement) achieves a 9 7 approximation ratio. Furthermore, we incorporate the concept of weighted contact which has biological motivation. Considering weighted contact we analyse our two algorithms as well as a previous algorithm on a different lattice. Finally, we implement our approximation algorithms and conducted experiments on benchmarks datasets.