title: An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem.
abstract: BACKGROUND
  The protein folding problem is a fundamental problems in computational molecular biology and biochemical physics. Various optimisation methods have been applied to formulations of the ab-initio folding problem that are based on reduced models of protein structure, including Monte Carlo methods, Evolutionary Algorithms, Tabu Search and hybrid approaches. In our work, we have introduced an ant colony optimisation (ACO) algorithm to address the non-deterministic polynomial-time hard (NP-hard) combinatorial problem of predicting a protein's conformation from its amino acid sequence under a widely studied, conceptually simple model - the 2-dimensional (2D) and 3-dimensional (3D) hydrophobic-polar (HP) model.
  
  
  RESULTS
  We present an improvement of our previous ACO algorithm for the 2D HP model and its extension to the 3D HP model. We show that this new algorithm, dubbed ACO-HPPFP-3, performs better than previous state-of-the-art algorithms on sequences whose native conformations do not contain structural nuclei (parts of the native fold that predominantly consist of local interactions) at the ends, but rather in the middle of the sequence, and that it generally finds a more diverse set of native conformations.
  
  
  CONCLUSIONS
  The application of ACO to this bioinformatics problem compares favourably with specialised, state-of-the-art methods for the 2D and 3D HP protein folding problem; our empirical results indicate that our rather simple ACO algorithm scales worse with sequence length but usually finds a more diverse ensemble of native states. Therefore the development of ACO algorithms for more complex and realistic models of protein structure holds significant promise.
authors.affiliation: Department of Computer Science, University of British Columbia, Vancouver, Canada. oshmygel@cs.ubc.ca <oshmygel@cs.ubc.ca>
authors.forename: Alena
authors.initials: A
authors.lastname: Shmygelska
authors.forename: Holger H
authors.initials: HH
authors.lastname: Hoos
mesh_terms: D000465:Algorithms; D020816:Amino Acid Motifs; D000595:Amino Acid Sequence; D019295:Computational Biology / Q000379:methods*; D016208:Databases, Factual; D019143:Evolution, Molecular; D008954:Models, Biological; D008956:Models, Chemical; D008958:Models, Molecular; D015233:Models, Statistical; D008962:Models, Theoretical; D008968:Molecular Conformation; D009010:Monte Carlo Method; D011487:Protein Conformation; D011489:Protein Denaturation; D017510:Protein Folding; D011506:Proteins / Q000737:chemistry*; D040901:Proteomics / Q000379:methods*; D012984:Software; D013997:Time Factors
chemical_list: D011506:Proteins