Limits...
Protein folding in HP model on hexagonal lattices with diagonals.

Shaw D, Shohidull Islam AS, Sohel Rahman M, Hasan M - BMC Bioinformatics (2014)

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.

View Article: PubMed Central - HTML - PubMed

ABSTRACT
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.

Show MeSH
Folding of HP string H4P4H6PH5P2H4P2H4P4H12 by the Algorith ImprovedChainArrangement. This figure aids in understanding the folding by Algorithm ImprovedChainArrangement.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
getmorefigures.php?uid=PMC4016602&req=5

Figure 10: Folding of HP string H4P4H6PH5P2H4P2H4P4H12 by the Algorith ImprovedChainArrangement. This figure aids in understanding the folding by Algorithm ImprovedChainArrangement.

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.


Protein folding in HP model on hexagonal lattices with diagonals.

Shaw D, Shohidull Islam AS, Sohel Rahman M, Hasan M - BMC Bioinformatics (2014)

Folding of HP string H4P4H6PH5P2H4P2H4P4H12 by the Algorith ImprovedChainArrangement. This figure aids in understanding the folding by Algorithm ImprovedChainArrangement.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
Show All Figures
getmorefigures.php?uid=PMC4016602&req=5

Figure 10: Folding of HP string H4P4H6PH5P2H4P2H4P4H12 by the Algorith ImprovedChainArrangement. This figure aids in understanding the folding by Algorithm ImprovedChainArrangement.
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.

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.

View Article: PubMed Central - HTML - PubMed

ABSTRACT
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.

Show MeSH