Protein folding in HP model on hexagonal lattices with diagonals

BMC Bioinformatics

Proceedings

ASM Shohidull Islam¹  M Sohel Rahman¹  Dipan Lal Shaw²  Masud Hasan³ 

[1]AℓEDA Group, CSE, BUET, Bangladesh

[2]Department of CSE, BUET, 1000, Dhaka, Bangladesh

[3]AℓEDA Group, CSE, BUET, Bangladesh

[4]Department of CSE, BUET, 1000, Dhaka, Bangladesh

[5]Department of CSE, BRAC University, Dhaka, Bangladesh

[6]Department of CSE, BUET, 1000, Dhaka, Bangladesh

[7]Department of Computer Science, College of Computer Science and Engineering, Taibah University, Madina Munawwarah, Saudi Arabia

关键词: bioinformatics;    approximation algorithms;    protein folding;    lattice model;    HP model;    hexagonal lattice;   

DOI  :  10.1186/1471-2105-15-S2-S7

来源: Springer

【 摘 要 】

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

【 授权许可】

Unknown   
© Shaw et al.; licensee BioMed Central Ltd. 2014. This article is published under license to BioMed Central Ltd. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. The Creative Commons Public Domain Dedication waiver (http://creativecommons.org/publicdomain/zero/1.0/) applies to the data made available in this article, unless otherwise stated.