{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T06:07:39Z","timestamp":1791266859844,"version":"4.1.0"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2005,2,14]],"date-time":"2005-02-14T00:00:00Z","timestamp":1108339200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0\/"},{"start":{"date-parts":[[2005,2,14]],"date-time":"2005-02-14T00:00:00Z","timestamp":1108339200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0\/"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                        <jats:title>Background<\/jats:title>\n                        <jats:p>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 <jats:italic>ab-initio<\/jats:italic> 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 (<jats:italic>NP<\/jats:italic>-hard) combinatorial problem of predicting a protein's conformation from its amino acid sequence under a widely studied, conceptually simple model \u2013 the 2-dimensional (2D) and 3-dimensional (3D) hydrophobic-polar (HP) model.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Results<\/jats:title>\n                        <jats:p>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.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Conclusions<\/jats:title>\n                        <jats:p>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.<\/jats:p>\n                     <\/jats:sec>","DOI":"10.1186\/1471-2105-6-30","type":"journal-article","created":{"date-parts":[[2005,2,15]],"date-time":"2005-02-15T07:25:23Z","timestamp":1108452323000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":174,"title":["An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem"],"prefix":"10.1186","volume":"6","author":[{"given":"Alena","family":"Shmygelska","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Holger H","family":"Hoos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,2,14]]},"reference":[{"key":"355_CR1","volume-title":"Tech rep., 91-016, Dip Elettronica, Politecnico di Milano, Italy","author":"M Dorigo","year":"1991","unstructured":"Dorigo M, Maniezzo V, Colorni A: Positive feedback as a search strategy. Tech rep., 91\u2013016, Dip Elettronica, Politecnico di Milano, Italy 1991."},{"key":"355_CR2","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1109\/3477.484436","volume":"26","author":"M Dorigo","year":"1996","unstructured":"Dorigo M, Maniezzo V, Colorni A: The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B 1996, 26: 29\u201341. 10.1109\/3477.484436","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics-Part B"},{"key":"355_CR3","volume-title":"New Ideas in Optimization","author":"M Dorigo","year":"1999","unstructured":"Dorigo M, Di Caro G: New Ideas in Optimization. In New Ideas in Optimization. Edited by: Corne D, Dorigo M, Glover F. McGraw-Hill; 1999."},{"issue":"2","key":"355_CR4","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1162\/106454699568728","volume":"5","author":"M Dorigo","year":"1999","unstructured":"Dorigo M, Di Caro G, Gambardella LM: Ant Algorithms for Discrete Optimization. Artificial Life 1999, 5(2):137\u2013172. 10.1162\/106454699568728","journal-title":"Artificial Life"},{"key":"355_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/b99492","volume-title":"Ant Colony Optimization","author":"M Dorigo","year":"2004","unstructured":"Dorigo M, St\u00fctzle T: Ant Colony Optimization. The MIT Press; 2004."},{"key":"355_CR6","first-page":"40","volume-title":"Proc of the 3rd Intl Workshop on Ant Algorithms, ANTS LNCS 2463","author":"A Shmygelska","year":"2002","unstructured":"Shmygelska A, Hernandez R, Hoos HH: An Ant Colony Optimization Algorithm for the 2D HP Protein Folding Problem. In Proc of the 3rd Intl Workshop on Ant Algorithms, ANTS LNCS 2463. Springer Verlag; 2002:40\u201352."},{"key":"355_CR7","first-page":"400","volume-title":"Proc of the 16th Canadian Conference on Artificial Intelligence, LNCS 2671","author":"A Shmygelska","year":"2003","unstructured":"Shmygelska A, Hoos HH: An Improved Ant Colony Optimisation Algorithm for the 2D HP Protein Folding Problem. In Proc of the 16th Canadian Conference on Artificial Intelligence, LNCS 2671. Springer Verlag; 2003:400\u201317."},{"issue":"6","key":"355_CR8","doi-asserted-by":"publisher","first-page":"1183","DOI":"10.1007\/BF02460703","volume":"55","author":"R Unger","year":"1993","unstructured":"Unger R, Moult J: Finding the lowest Free-Energy Conformation of a protein is an NP-hard problem \u2013 Proof and Implications. Bull Math Biol 1993, 55(6):1183\u20131198.","journal-title":"Bull Math Biol"},{"key":"355_CR9","doi-asserted-by":"publisher","first-page":"3986","DOI":"10.1021\/ma00200a030","volume":"22","author":"KF Lau","year":"1989","unstructured":"Lau KF, Dill KA: lattice statistical mechanics model of the conformation and sequence space of proteins. Macromolecules 1989, 22: 3986\u20133997. 10.1021\/ma00200a030","journal-title":"Macromolecules"},{"key":"355_CR10","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1146\/annurev.bb.06.060177.001055","volume":"6","author":"FM Richards","year":"1977","unstructured":"Richards FM: Areas, volumes, packing, and protein structures. Annu Rev Biophys Bioeng 1977, 6: 151\u2013176. 10.1146\/annurev.bb.06.060177.001055","journal-title":"Annu Rev Biophys Bioeng"},{"key":"355_CR11","first-page":"353","volume-title":"Proc of Engineering of Intelligent Systems","author":"N Krasnogor","year":"1998","unstructured":"Krasnogor N, Pelta D, Lopez PM, Mocciola P, de la Canal E: Genetic algorithms for the protein folding problem: a critical view. In Proc of Engineering of Intelligent Systems. Edited by: Alpaydin C. ICSC Academic Press; 1998:353\u2013360."},{"key":"355_CR12","first-page":"1596","volume-title":"Proc of the Genetic and Evolutionary Computation conference","author":"N Krasnogor","year":"1999","unstructured":"Krasnogor N, Hart WE, Smith J, Pelta DA: Protein structure prediction with evolutionary algorithms. Proc of the Genetic and Evolutionary Computation conference 1999, 1596\u20131601."},{"key":"355_CR13","first-page":"574","volume-title":"Proc of the 6th Intl Conf Genetic Algorithms","author":"AWP Patton","year":"1995","unstructured":"Patton AWP, Goldman E: A standard GA approach to native protein conformation prediction. In Proc of the 6th Intl Conf Genetic Algorithms. Morgan Kaufmann Publishers; 1995:574\u2013581."},{"key":"355_CR14","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1006\/jmbi.1993.1258","volume":"231","author":"R Unger","year":"1993","unstructured":"Unger R, Moult J: Genetic algorithms for protein folding simulations. J of Mol Biol 1993, 231: 75\u201381. 10.1006\/jmbi.1993.1258","journal-title":"J of Mol Biol"},{"key":"355_CR15","first-page":"581","volume-title":"Proc of the 5th Intl Conf on Genetic Algorithms","author":"R Unger","year":"1993","unstructured":"Unger R, Moult J: A genetic algorithm for three dimensional protein folding simulations. In Proc of the 5th Intl Conf on Genetic Algorithms. Morgan Kaufmann Publishers; 1993:581\u2013588."},{"key":"355_CR16","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1002\/(SICI)1097-0134(19980701)32:1<52::AID-PROT7>3.0.CO;2-G","volume":"32","author":"U Bastolla","year":"1998","unstructured":"Bastolla U, Fravenkron H, Gestner E, Grassberger P, Nadler W: Testing a New Monte Carlo algorithm for the protein folding problem. Proteins 1998, 32: 52\u201366.","journal-title":"Proteins"},{"key":"355_CR17","first-page":"27","volume-title":"Condensed Materials Archive","author":"G Chikenji","year":"1999","unstructured":"Chikenji G, Kikuchi M, Iba Y: Multi-Self-Overlap Ensemble for protein folding: ground state search and thermodynamics. Condensed Materials Archive 1999, 27."},{"key":"355_CR18","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1063\/1.1522710","volume":"118","author":"HP Hsu","year":"2003","unstructured":"Hsu HP, Mehra V, Nadler W, Grassberger P: Growth Algorithm for Lattice Heteropolymers at Low Temperatures. J Chem Phys 2003, 118: 444\u201351. 10.1063\/1.1522710","journal-title":"J Chem Phys"},{"issue":"7","key":"355_CR19","doi-asserted-by":"publisher","first-page":"3374","DOI":"10.1063\/1.1387478","volume":"115","author":"F Liang","year":"2001","unstructured":"Liang F, Wong WH: Evolutionary Monte Carlo for protein folding simulations. J Chem Phys 2001, 115(7):3374\u20133380. 10.1063\/1.1387478","journal-title":"J Chem Phys"},{"issue":"11","key":"355_CR20","doi-asserted-by":"publisher","first-page":"8644","DOI":"10.1063\/1.463383","volume":"97","author":"EM O'Toole","year":"1992","unstructured":"O'Toole EM, Panagiotopoulos AZ: Monte Carlo simulation of folding transitions of simple model proteins using a chain growth algorithm. J Chem Phys 1992, 97(11):8644\u20138652. 10.1063\/1.463383","journal-title":"J Chem Phys"},{"issue":"6","key":"355_CR21","doi-asserted-by":"publisher","first-page":"2418","DOI":"10.1063\/1.473791","volume":"106","author":"R Ramakrishnan","year":"1997","unstructured":"Ramakrishnan R, Ramachandran B, Pekny JF: A dynamic Monte Carlo algorithm for exploration of dense conformational spaces in heteropolymers. J Chem Phys 1997, 106(6):2418\u20132424. 10.1063\/1.473791","journal-title":"J Chem Phys"},{"key":"355_CR22","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1038\/369248a0","volume":"369","author":"A Sali","year":"1994","unstructured":"Sali A, Shakhnovich E, Karplus M: How does a protein fold? Nature 1994, 369: 248\u2013251. 10.1038\/369248a0","journal-title":"Nature"},{"key":"355_CR23","doi-asserted-by":"publisher","first-page":"1942","DOI":"10.1073\/pnas.90.5.1942","volume":"90","author":"KA Dill","year":"1993","unstructured":"Dill KA, Fiebig KM, Chan HS: Cooperativity in Protein-Folding Kinetics. Proc Natl Acad Sci USA 1993, 90: 1942\u20131946.","journal-title":"Proc Natl Acad Sci USA"},{"key":"355_CR24","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1002\/pro.5560050118","volume":"5","author":"L Toma","year":"1996","unstructured":"Toma L, Toma S: Contact interactions method: A new algorithm for protein folding simulations. Protein Sci 1996, 5: 147\u2013153.","journal-title":"Protein Sci"},{"key":"355_CR25","doi-asserted-by":"publisher","first-page":"2037","DOI":"10.1002\/pro.5560051010","volume":"5","author":"T Beutler","year":"1996","unstructured":"Beutler T, Dill K: A fast conformational search strategy for finding low energy structures of model proteins. Protein Sci 1996, 5: 2037\u20132043.","journal-title":"Protein Sci"},{"key":"355_CR26","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1073\/pnas.92.1.146","volume":"92","author":"K Yue","year":"1995","unstructured":"Yue K, Dill KA: Forces of Tertiary Structural Organization in Globular Proteins. Proc Natl Acad Sci USA 1995, 92: 146\u2013150.","journal-title":"Proc Natl Acad Sci USA"},{"key":"355_CR27","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/978-3-540-24599-5_5","volume-title":"Proc XIX Intl Conf on Logic Programming","author":"R Backofen","year":"2003","unstructured":"Backofen R, Will S: A Constraint-Based Approach to Structure Prediction for Simplified Protein Models that Outperforms Other Existing Methods. Proc XIX Intl Conf on Logic Programming 2003, 49\u201371."},{"key":"355_CR28","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0021-9991(77)90121-8","volume":"23","author":"GM Torrie","year":"1977","unstructured":"Torrie GM, Valleau JP: Nonphysical sampling distributions in MC free energy estimation: Umbrella sampling. J Comput Phys 1977, 23: 187\u2013199. 10.1016\/0021-9991(77)90121-8","journal-title":"J Comput Phys"},{"issue":"12","key":"355_CR29","doi-asserted-by":"publisher","first-page":"5065","DOI":"10.1063\/1.1289533","volume":"113","author":"D Gront","year":"2000","unstructured":"Gront D, Kolinski A, Skolnick J: Comparison of three Monte Carlo conformational search strategies for a proteinlike homopolymer model: Folding thermodynamics and identification of low-energy structures. J Chem Phys 2000, 113(12):5065\u20135071. 10.1063\/1.1289533","journal-title":"J Chem Phys"},{"issue":"14","key":"355_CR30","doi-asserted-by":"publisher","first-page":"6664","DOI":"10.1063\/1.1555847","volume":"118","author":"A Mitsutake","year":"2003","unstructured":"Mitsutake A, Sugita Y, Okamoto Y: Replica-exchange multicanonical and multicanonical replica-exchange Monte Carlo simulations of peptides. I. Formulation and benchmark test. J Chem Phys 2003, 118(14):6664\u20136675. 10.1063\/1.1555847","journal-title":"J Chem Phys"},{"key":"355_CR31","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1103\/PhysRevLett.68.9","volume":"68","author":"BA Berg","year":"1992","unstructured":"Berg BA, Neuhaus T: Multicanonical ensemble: A new approach to simulate first-order phase transitions. Phys Rev Lett 1992, 68: 9\u201312. 10.1103\/PhysRevLett.68.9","journal-title":"Phys Rev Lett"},{"key":"355_CR32","first-page":"98","volume-title":"Monte Carlo Approach to Biopolymers and Protein Folding","author":"A Irb\u00e4ck","year":"1998","unstructured":"Irb\u00e4ck A: Dynamic-parameter algorithms for protein folding. In Monte Carlo Approach to Biopolymers and Protein Folding. Edited by: Grassberger P, Barkema GT, Nadler W,. World Scientific, Singapore; 1998:98\u2013109."},{"key":"355_CR33","first-page":"92","volume-title":"Proc of the 5th Pacific Symposium on Biocomputing","author":"R Backofen","year":"2000","unstructured":"Backofen R, Will S, Clote P: Algorithmic approach to quantifying the hydrophobic force contribution in protein folding. Proc of the 5th Pacific Symposium on Biocomputing 2000, 92\u2013103."},{"key":"355_CR34","first-page":"021113-1","volume":"68","author":"HP Hsu","year":"2003","unstructured":"Hsu HP, Mehra V, Nadler W, Grassberger P: Growth-based Optimisation Algorithm for Lattice Heteropolymers. Phys Rev E 2003, 68: 021113\u20131-021113\u20134.","journal-title":"Phys Rev E"},{"key":"355_CR35","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF02703680","volume":"27","author":"T Nandi","year":"2002","unstructured":"Nandi T, B-Rao C, Ramachandran S: Comparative Genomics using Data Mining tools. J Bioscience 2002, 27: 15\u201325.","journal-title":"J Bioscience"},{"issue":"9","key":"355_CR36","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1016\/S0968-0004(00)89080-5","volume":"20","author":"R Sayle","year":"1995","unstructured":"Sayle R, Milner-White EJ: RASMOL \u2013 Biomolecular Graphics for All. Trends Biochem Sci 1995, 20(9):374\u2013376. 10.1016\/S0968-0004(00)89080-5","journal-title":"Trends Biochem Sci"},{"key":"355_CR37","volume-title":"Protein Folding","author":"TE Creighton","year":"1992","unstructured":"Creighton TE: Protein Folding. W H Freeman and Company; 1992."},{"key":"355_CR38","doi-asserted-by":"publisher","first-page":"985","DOI":"10.1006\/jmbi.1998.1645","volume":"277","author":"KW Plaxco","year":"1998","unstructured":"Plaxco KW, Simons KT, Baker D: Contact order, transition state placement and the refolding rates of single domainproteins. J Mol Biol 1998, 277: 985\u2013994. 10.1006\/jmbi.1998.1645","journal-title":"J Mol Biol"},{"key":"355_CR39","first-page":"238","volume-title":"Proc of the 14th Conference on Uncertainty in Artificial Intelligence","author":"HH Hoos","year":"1998","unstructured":"Hoos HH, St\u00fctzle T: On the empirical evaluation of Las Vegas algorithms. In Proc of the 14th Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann Publishers; 1998:238\u2013245."},{"key":"355_CR40","doi-asserted-by":"publisher","first-page":"1614","DOI":"10.1006\/jmbi.1994.1110","volume":"235","author":"A Sali","year":"1994","unstructured":"Sali A, Shakhnovich E, Karplus M: Kinetics of protein folding \u2013 A lattice model study of the requirements for folding tothe native state. J Mol Biol 1994, 235: 1614\u20131636. 10.1006\/jmbi.1994.1110","journal-title":"J Mol Biol"},{"issue":"8","key":"355_CR41","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1016\/S0167-739X(00)00043-1","volume":"16","author":"T St\u00fctzle","year":"2000","unstructured":"St\u00fctzle T, Hoos HH: MAX-MIN Ant System. Future Generation Computer Systems 2000, 16(8):889\u2013914. 10.1016\/S0167-739X(00)00043-1","journal-title":"Future Generation Computer Systems"},{"key":"355_CR42","volume-title":"Stochastic Local Search: Foundations and Applications","author":"HH Hoos","year":"2004","unstructured":"Hoos HH, St\u00fctzle T: Stochastic Local Search: Foundations and Applications. Morgan Kaufmann Publishers \/Elsevier; 2004."},{"key":"355_CR43","first-page":"356","volume-title":"Proc of the Applications of Artificial Intelligence Conf","author":"A Parkes","year":"1996","unstructured":"Parkes A, Walser JP: Tuning Local Search for Satisfiability Testing. In Proc of the Applications of Artificial Intelligence Conf. MIT Press; 1996:356\u2013362."},{"key":"355_CR44","unstructured":"HP Benchmarks[http:\/\/www.cs.sandia.gov\/tech_reports\/compbio\/tortilla-hp-benchmarks.html]"},{"key":"355_CR45","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0303-2647(98)00090-2","volume":"50","author":"R Konig","year":"1999","unstructured":"Konig R, Dandekar T: Improving Genetic Algorithms for Protein Folding simulations by systematic crossover. Biosystems 1999, 50: 17\u201325. 10.1016\/S0303-2647(98)00090-2","journal-title":"Biosystems"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-30.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/1471-2105-6-30\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-30.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T12:05:43Z","timestamp":1728302743000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-6-30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,2,14]]},"references-count":45,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2005,12]]}},"alternative-id":["355"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-6-30","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,2,14]]},"assertion":[{"value":"16 July 2004","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 February 2005","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 February 2005","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"30"}}