{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,3]],"date-time":"2026-11-03T13:13:52Z","timestamp":1793711632231,"version":"4.6.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2008,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>The principles of protein folding and evolution pose problems of very high inherent complexity. Often these problems are tackled using simplified protein models, e.g. lattice proteins. The CPSP-tools package provides programs to solve exactly and completely the problems typical of studies using 3D lattice protein models. Among the tasks addressed are the prediction of (all) globally optimal and\/or suboptimal structures as well as sequence design and neutral network exploration.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>In contrast to stochastic approaches, which are not capable of answering many fundamental questions, our methods are based on fast, non-heuristic techniques. The resulting tools are designed for high-throughput studies of 3D-lattice proteins utilising the Hydrophobic-Polar (HP) model. The source bundle is freely available [1].<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>The CPSP-tools package is the first set of exact and complete methods for extensive, high-throughput studies of non-restricted 3D-lattice protein models. In particular, our package deals with cubic and face centered cubic (FCC) lattices.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-9-230","type":"journal-article","created":{"date-parts":[[2008,5,7]],"date-time":"2008-05-07T18:44:44Z","timestamp":1210185884000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":39,"title":["CPSP-tools \u2013 Exact and complete algorithms for high-throughput 3D lattice protein studies"],"prefix":"10.1186","volume":"9","author":[{"given":"Martin","family":"Mann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Will","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rolf","family":"Backofen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2008,5,7]]},"reference":[{"key":"2215_CR1","unstructured":"CPSP-tools[http:\/\/www.bioinf.uni-freiburg.de\/sw\/cpsp\/]"},{"key":"2215_CR2","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1093\/bioinformatics\/btm180","volume":"23","author":"E Jacob","year":"2007","unstructured":"Jacob E, Horovitz A, Unger R: Different mechanistic requirements for prokaryotic and eukaryotic chaperonins: a lattice study. Bioinformatics 2007, 23: 240\u2013248. 10.1093\/bioinformatics\/btm180","journal-title":"Bioinformatics"},{"key":"2215_CR3","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1209\/epl\/i2005-10577-0","volume":"74","author":"MT Wolfinger","year":"2006","unstructured":"Wolfinger MT, Will S, Hofacker IL, Backofen R, Stadler PF: Exploring the lower part of discrete polymer model energy landscapes. Europhysics Lett 2006, 74: 725\u2013732. 10.1209\/epl\/i2005-10577-0","journal-title":"Europhysics Lett"},{"key":"2215_CR4","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1093\/bioinformatics\/btl248","volume":"22","author":"FP Huard","year":"2006","unstructured":"Huard FP, Deane CM, Woo GR: Modelling sequential protein folding under kinetic control. Bioinformatics 2006, 22: 202\u2013210. 10.1093\/bioinformatics\/btl248","journal-title":"Bioinformatics"},{"key":"2215_CR5","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: proof and implications. Bull Math Biol 1993, 55: 1183\u20131198.","journal-title":"Bull Math Biol"},{"key":"2215_CR6","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1089\/cmb.1998.5.27","volume":"5","author":"B Berger","year":"1998","unstructured":"Berger B, Leighton T: Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete. J Comp Biol 1998, 5: 27\u201340.","journal-title":"J Comp Biol"},{"key":"2215_CR7","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-540-27801-6_18","volume-title":"Combinatorial Pattern Matching","author":"P Berman","year":"2004","unstructured":"Berman P, DasGupta B, Mubayi D, Sloan R, Tur\u00e1n G, Zhang Y: The protein sequence design problem in canonical model on 2D and 3D lattices. In Combinatorial Pattern Matching. Volume 3109. Springer; 2004:244\u2013253."},{"key":"2215_CR8","doi-asserted-by":"publisher","first-page":"021113","DOI":"10.1103\/PhysRevE.68.021113","volume":"68","author":"HP Hsu","year":"2003","unstructured":"Hsu HP, Mehra V, Nadler W, Grassberger P: Growth-based optimization algorithm for lattice heteropolymers. Phys Rev E 2003, 68: 021113. 10.1103\/PhysRevE.68.021113","journal-title":"Phys Rev E"},{"key":"2215_CR9","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 1995, 92: 146\u2013150. 10.1073\/pnas.92.1.146","journal-title":"Proc Natl Acad Sci"},{"key":"2215_CR10","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1002\/prot.10239","volume":"49","author":"H Li","year":"2002","unstructured":"Li H, Tang C, Wingreen NS: Designability of protein structures: a lattice-model study using the Miyazawa-Jernigan matrix. Proteins 2002, 49: 403\u2013412. 10.1002\/prot.10239","journal-title":"Proteins"},{"key":"2215_CR11","doi-asserted-by":"publisher","first-page":"154907","DOI":"10.1063\/1.2056545","volume":"123","author":"BP Blackburne","year":"2005","unstructured":"Blackburne BP, Hirst JD: Population dynamics simulations of functional model proteins. J Chem Phys 2005, 123: 154907\u20139. 10.1063\/1.2056545","journal-title":"J Chem Phys"},{"key":"2215_CR12","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1006\/jmbi.1995.0311","volume":"249","author":"BH Park","year":"1995","unstructured":"Park BH, Levitt M: The complexity and accuracy of discrete state models of protein structure. J Mol Biol 1995, 249: 493\u2013507. 10.1006\/jmbi.1995.0311","journal-title":"J Mol Biol"},{"key":"2215_CR13","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s10601-006-6848-8","volume":"11","author":"R Backofen","year":"2006","unstructured":"Backofen R, Will S: A constraint-based approach to fast and exact structure prediction in three-dimensional protein models. Constraints 2006, 11: 5\u201330. 10.1007\/s10601-006-6848-8","journal-title":"Constraints"},{"key":"2215_CR14","doi-asserted-by":"publisher","first-page":"3986","DOI":"10.1021\/ma00200a030","volume":"22","author":"KF Lau","year":"1989","unstructured":"Lau KF, Dill KA: A lattice statistical mechanics model of the conformational and sequence spaces of proteins. Macromolecules 1989, 22: 3986\u20133997. 10.1021\/ma00200a030","journal-title":"Macromolecules"},{"key":"2215_CR15","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1073\/pnas.022240299","volume":"99","author":"Y Cui","year":"2002","unstructured":"Cui Y, Wong WH, Bornberg-Bauer E, Chan HS: Recombinatoric exploration of novel folded structures: a heteropolymer-based model of protein evolutionary landscapes. Proc Natl Acad Sci 2002, 99: 809\u2013814. 10.1073\/pnas.022240299","journal-title":"Proc Natl Acad Sci"},{"key":"2215_CR16","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1093\/bioinformatics\/btl318","volume":"23","author":"E Jacob","year":"2007","unstructured":"Jacob E, Unger R: A tale of two tails: why are terminal residues of proteins exposed? Bioinformatics 2007, 23: 225\u2013230. 10.1093\/bioinformatics\/btl318","journal-title":"Bioinformatics"},{"key":"2215_CR17","doi-asserted-by":"publisher","first-page":"3453","DOI":"10.1063\/1.1590310","volume":"119","author":"BP Blackburne","year":"2003","unstructured":"Blackburne BP, Hirst JD: Three-dimensional functional model proteins: structure function and evolution. J Chem Phys 2003, 119: 3453\u20133460. 10.1063\/1.1590310","journal-title":"J Chem Phys"},{"key":"2215_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73086-6_12","volume-title":"On-Line Encyclopedia of Integer Sequences","author":"NJA Sloane","year":"2007","unstructured":"Sloane NJA: Number of n-step self-avoiding walks on cubic lattice. On-Line Encyclopedia of Integer Sequences 2007. [http:\/\/www.research.att.com\/~njas\/sequences\/A001412]"},{"key":"2215_CR19","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1186\/1471-2105-5-186","volume":"5","author":"A Dal Palu","year":"2004","unstructured":"Dal Palu A, Dovier A, Fogolari F: Constraint Logic Programming approach to protein structure prediction. BMC Bioinformatics 2004, 5: 186. 10.1186\/1471-2105-5-186","journal-title":"BMC Bioinformatics"},{"key":"2215_CR20","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1023\/A:1020577603762","volume":"7","author":"L Krippahl","year":"2002","unstructured":"Krippahl L, Barahona P: PSICO: Solving protein structures with constraint programming and optimization. Constraints 2002, 7: 317\u2013331. 10.1023\/A:1020577603762","journal-title":"Constraints"},{"key":"2215_CR21","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1002\/prot.10387","volume":"52","author":"L Krippahl","year":"2003","unstructured":"Krippahl L, Moura JJ, Palma PN: Modeling protein complexes with BiGGER. Proteins 2003, 52: 19\u201323. 10.1002\/prot.10387","journal-title":"Proteins"},{"key":"2215_CR22","volume-title":"Protein folding in the generalized hydrophobic-polar model on the triangular lattice","author":"SE Decatur","year":"1996","unstructured":"Decatur SE: Protein folding in the generalized hydrophobic-polar model on the triangular lattice. 1996."},{"key":"2215_CR23","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/S0032-3861(01)00427-X","volume":"43","author":"Z Bagci","year":"2002","unstructured":"Bagci Z, Jernigan RL, Bahar I: Residue coordination in proteins conforms to the closest packing of spheres. Polymer 2002, 43: 451\u2013459. 10.1016\/S0032-3861(01)00427-X","journal-title":"Polymer"},{"key":"2215_CR24","doi-asserted-by":"publisher","first-page":"79","DOI":"10.2976\/1.2739116\/10.2976\/1","volume":"1","author":"R Wroe","year":"2007","unstructured":"Wroe R, Chan HS, Bornberg-Bauer E: A structural model of latent evolutionary potentials underlying neutral networks in proteins. HFSP J 2007, 1: 79\u201387. 10.2976\/1.2739116","journal-title":"HFSP J"},{"key":"2215_CR25","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/3-540-48194-X_24","volume-title":"Proc of the 12th Annual Symposium on Combinatorial Pattern Matching","author":"R Backofen","year":"2001","unstructured":"Backofen R, Will S: Optimally Compact Finite Sphere Packings \u2013 Hydrophobic Cores in the FCC. In Proc of the 12th Annual Symposium on Combinatorial Pattern Matching. Volume 2089. Springer; 2001:257\u2013272."},{"key":"2215_CR26","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/5625.001.0001","volume-title":"Programming with Constraints: an Introduction","author":"K Marriott","year":"1998","unstructured":"Marriott K, Stuckey PJ: Programming with Constraints: an Introduction. The MIT Press; 1998."},{"key":"2215_CR27","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1002\/pro.5560010202","volume":"1","author":"D Shortle","year":"1992","unstructured":"Shortle D, Chan HS, Dill KA: Modeling the effects of mutations on the denatured states of proteins. Prot Sci 1992, 1: 201\u2013215.","journal-title":"Prot Sci"},{"key":"2215_CR28","first-page":"83","volume-title":"Proc of Workshop on Constraint Based Methods for Bioinformatics","author":"S Will","year":"2006","unstructured":"Will S, Mann M: Counting protein structures by DFS with dynamic decomposition. Proc of Workshop on Constraint Based Methods for Bioinformatics 2006, 83\u201390."},{"key":"2215_CR29","doi-asserted-by":"publisher","first-page":"1328","DOI":"10.1089\/cmb.2005.12.1328","volume":"12","author":"A Gupta","year":"2005","unstructured":"Gupta A, Manuch J, Stacho L: Structure-approximating inverse protein folding problem in the 2D HP model. J Comp Biol 2005, 12: 1328\u20131345. 10.1089\/cmb.2005.12.1328","journal-title":"J Comp Biol"},{"key":"2215_CR30","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1002\/cplx.10052","volume":"8","author":"P Schuster","year":"2002","unstructured":"Schuster P, Stadler PF: Networks in molecular evolution. Complexity 2002, 8: 34\u201342. 10.1002\/cplx.10052","journal-title":"Complexity"},{"key":"2215_CR31","unstructured":"Jmol: an open-source Java viewer for chemical structures in 3D[http:\/\/jmol.sourceforge.net\/]"},{"key":"2215_CR32","unstructured":"Gecode \u2013 generic constraint development environment[http:\/\/www.gecode.org]"},{"key":"2215_CR33","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1186\/1471-2105-6-30","volume":"6","author":"A Shmygelska","year":"2005","unstructured":"Shmygelska A, Hoos HH: An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem. BMC Bioinformatics 2005, 6: 30. 10.1186\/1471-2105-6-30","journal-title":"BMC Bioinformatics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-9-230.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T10:59:57Z","timestamp":1630493997000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-9-230"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5,7]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["2215"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-9-230","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,5,7]]},"assertion":[{"value":"18 December 2007","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2008","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2008","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"230"}}