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.
