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 ABSTRACTThree 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 MajorAlgorithms*Models, Biological*Protein Folding*MinorComputational Biology/methodsProtein Structure, TertiarySequence Analysis, Protein © Copyright Policy - open-access Related In: Results  -  Collection License 1 - License 2 getmorefigures.php?uid=PMC4016602&req=5 .flowplayer { width: px; height: px; } Figure 2: Crossing between binding edges; this situation is forbidden in a valid conformation. In this figure crossing between binding edges is illustrated. Notice that, this situation is forbidden in a valid conformation. Mentions: Definition Let p = p1 ... pt be an HP string of length t and let G = (V, E) be a lattice. An embedding of p into G is a mapping function f: {1, ..., t} → V from the positions of the string to the vertices of the lattice. It assigns adjacent positions in p to adjacent vertices in G, (f(i), f(i + 1)) ∈ E for all 1 ≤ i ≤ t - 1. The edges (f(i), f (i + 1)) ∈ E for 1 ≤ i ≤ t - 1 are called binding edges. An embedding of p into G is called a conformation, if no two binding edges cross each other (see Figure 2).

Protein folding in HP model on hexagonal lattices with diagonals.

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

Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC4016602&req=5

Figure 2: Crossing between binding edges; this situation is forbidden in a valid conformation. In this figure crossing between binding edges is illustrated. Notice that, this situation is forbidden in a valid conformation.
Mentions: Definition Let p = p1 ... pt be an HP string of length t and let G = (V, E) be a lattice. An embedding of p into G is a mapping function f: {1, ..., t} → V from the positions of the string to the vertices of the lattice. It assigns adjacent positions in p to adjacent vertices in G, (f(i), f(i + 1)) ∈ E for all 1 ≤ i ≤ t - 1. The edges (f(i), f (i + 1)) ∈ E for 1 ≤ i ≤ t - 1 are called binding edges. An embedding of p into G is called a conformation, if no two binding edges cross each other (see Figure 2).

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