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: From Equation 1 we can see that a higher value of k will give us a better approximation ratio. So, if there are many short H-runs then we will get better results. This interesting insight provides us with an idea of an improved algorithm. However, as will be discussed later, the better approximation ratio will be applicable only if every H-run is of length greater than 2. For this improved algorithm we introduce the notion of inner-left chains, outer-left chains, inner-right chains and outer-right chains as shown in Figure 10. Recall that, unlike the current algorithm, there were only two chains in our previous algorithm. The arrangement in the outer-left (outer-right) chain can be further divided into four regions, namely, the left region, the right region, the up region and the down region. The arrangement in the inner-left (inner-right) chain can be further divided into three regions, namely, the middle region, the up region and the down region (see Figure 11). We apply the following procedures. We first put an H of an H-run in the outer-left chain; the next two H's of the H-run is placed in the inner-left chain. Rest of the H's of the H-run are placed alternatively on the inner-left chain (inner-right chain) and on the outer-left chain (outer-right chain) (see Figure 10). At this point, a brief discussion on the difference between the arrangements done by the two algorithm is in order. In Algorithm ChainArrangement, we can place all P's of an HP string in the side arms. However in the current algorithm we may have to arrange some P's of an HP string in the outer-left chain or outer-right chain also (see Figure 10). The algorithm is finally presented below.