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 H2P6H4P2H3P3H5P5H3 by Algorithm ChainArrangement. This figure aids in understanding the folding by Algorithm ChainArrangement.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 7: Folding of HP string H2P6H4P2H3P3H5P5H3 by Algorithm ChainArrangement. This figure aids in understanding the folding by Algorithm ChainArrangement.

Mentions: In this section, we present two novel approximation algorithms for the problem. The idea of the first algorithm is to arrange all H's occurring in the input string along the two chains. We arrange the H's in the prefix of the string up to the -th H on the left chain and arrange the rest of those on the right one (see Figure 7). Then we arrange the P's between H's outside these two chains. The arrangements of the P-runs along the side-arms of the two chains are shown in Figure 7. The arrangement in the left (right) chain can be further divided into four regions, namely, the left region, the right region, the up region and the down region (see Figure 8 and Figure 9). Now we formally present our algorithm in the form of Algorithm ChainArrangement.


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 H2P6H4P2H3P3H5P5H3 by Algorithm ChainArrangement. This figure aids in understanding the folding by Algorithm ChainArrangement.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 7: Folding of HP string H2P6H4P2H3P3H5P5H3 by Algorithm ChainArrangement. This figure aids in understanding the folding by Algorithm ChainArrangement.
Mentions: In this section, we present two novel approximation algorithms for the problem. The idea of the first algorithm is to arrange all H's occurring in the input string along the two chains. We arrange the H's in the prefix of the string up to the -th H on the left chain and arrange the rest of those on the right one (see Figure 7). Then we arrange the P's between H's outside these two chains. The arrangements of the P-runs along the side-arms of the two chains are shown in Figure 7. The arrangement in the left (right) chain can be further divided into four regions, namely, the left region, the right region, the up region and the down region (see Figure 8 and Figure 9). Now we formally present our algorithm in the form of Algorithm ChainArrangement.

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