Protein folding in HP model on hexagonal lattices with diagonals.
Bottom Line: Since, this is a hard problem, a number of simplified models have been proposed in literature to capture the essential properties of this problem.In this paper we introduce the hexagonal lattices with diagonals to handle the protein folding problem considering the well researched HP model.We give two approximation algorithms for protein folding on this lattice.
Three dimensional structure prediction of a protein from its amino acid sequence, known as protein folding, is one of the most studied computational problem in bioinformatics and computational biology. Since, this is a hard problem, a number of simplified models have been proposed in literature to capture the essential properties of this problem. In this paper we introduce the hexagonal lattices with diagonals to handle the protein folding problem considering the well researched HP model. We give two approximation algorithms for protein folding on this lattice. Our first algorithm is a 5/3-approximation algorithm, which is based on the strategy of partitioning the entire protein sequence into two pieces. Our next algorithm is also based on partitioning approaches and improves upon the first algorithm.
License 1 - License 2
Mentions: In this paper, we introduce the hexagonal lattices with diagonals for protein folding. The motivation for introducing hexagonal lattice comes from the secondary structure of a protein as follows. The secondary structure of a protein suggests that, in real protein folding, sharp turn does not occur frequently. Hexagonal model alleviates this sharp turn problem . On the other hand, in the square lattice HP model there is a serious shortcoming, namely, the parity problem as follows. Due to a grid structure in a square lattice, contact can be established between two hydrophobic atoms only if they both are either on even positions or on odd positions of the sequence. To address this parity problem, we came up with the idea of this new lattice model, i.e., hexagonal lattice model with diagonals. In this model contacts may exist through diagonals (see Figure 1). Notably, these issues have also been partially alleviated in square lattice with diagonals and triangular lattice. To this end, our new model opens a new avenue for further research for this long standing problem. We present two novel approximation algorithms for protein folding on this lattice. Our first algorithm is a -approximation algorithm for k > 10 where k is the number of sequences of H's in the HP string. This algorithm is based on a strategy of partitioning the entire protein sequence into two pieces. Our second algorithm partitions the HP string into four pieces and employs the idea of the first algorithm on the two halves. This gives a better approximation ratio of for k > 22. The latter result is applicable to HP strings where all the sequences of H's are of even length greater than two. The expected approximation ratio of this algorithm would be for n > 260 when both odd and even length sequences of H's having length greater than two are allowed. Here, n is the number of total H's in the HP string. We also present the idea of folding HP strings with sequences of H having length less than two. Notably, in the literature the best approximation ratio for the hexagonal lattice is 6, which is due to , and that for the square lattice with diagonals is . Clearly, the approximation ratio of our algorithm is better than the above results.