TY - GEN

T1 - An efficient genetic algorithm for predicting protein tertiary structures in the 2D HP model

AU - Bui, Thang N.

AU - Sundarraj, Gnanasekaran

PY - 2005

Y1 - 2005

N2 - Given the amino acid sequence of a protein, predicting its tertiary structure is known as the protein folding problem. This problem has been widely studied under the HP model in which each amino acid is classified, based on its hydrophobicity, as an H (hydrophobic or non-polar) or a P (hydrophilic or polar). Conformation of a protein in the HP model is embedded as a self-avoiding walk in either a two-dimensional or a three-dimensional lattice. The protein folding problem in the HP model is to find a lowest energy conformation. This problem is known to be NP-hard in both two-dimensional and three-dimensional square lattices. In this paper, we present an efficient genetic algorithm for the protein folding problem under the HP model in the two-dimensional square lattice. A special feature of this algorithm is its usage of secondary structures, that the algorithm evolves, as building blocks for the conformation. Experimental results on benchmark sequences show that the algorithm performs very well against existing evolutionary algorithms and Monte Carlo algorithms.

AB - Given the amino acid sequence of a protein, predicting its tertiary structure is known as the protein folding problem. This problem has been widely studied under the HP model in which each amino acid is classified, based on its hydrophobicity, as an H (hydrophobic or non-polar) or a P (hydrophilic or polar). Conformation of a protein in the HP model is embedded as a self-avoiding walk in either a two-dimensional or a three-dimensional lattice. The protein folding problem in the HP model is to find a lowest energy conformation. This problem is known to be NP-hard in both two-dimensional and three-dimensional square lattices. In this paper, we present an efficient genetic algorithm for the protein folding problem under the HP model in the two-dimensional square lattice. A special feature of this algorithm is its usage of secondary structures, that the algorithm evolves, as building blocks for the conformation. Experimental results on benchmark sequences show that the algorithm performs very well against existing evolutionary algorithms and Monte Carlo algorithms.

UR - http://www.scopus.com/inward/record.url?scp=32444434801&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=32444434801&partnerID=8YFLogxK

U2 - 10.1145/1068009.1068072

DO - 10.1145/1068009.1068072

M3 - Conference contribution

AN - SCOPUS:32444434801

SN - 1595930108

SN - 9781595930101

T3 - GECCO 2005 - Genetic and Evolutionary Computation Conference

SP - 385

EP - 392

BT - GECCO 2005 - Genetic and Evolutionary Computation Conference

A2 - Beyer, H.G.

A2 - O'Reilly, U.M.

A2 - Arnold, D.

A2 - Banzhaf, W.

A2 - Blum, C.

A2 - Bonabeau, E.W.

A2 - Cantu-Paz, E.

A2 - Dasgupta, D.

A2 - Deb, K.

A2 - et al, al

T2 - GECCO 2005 - Genetic and Evolutionary Computation Conference

Y2 - 25 June 2005 through 29 June 2005

ER -