{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,31]],"date-time":"2026-07-31T03:23:34Z","timestamp":1785468214925,"version":"3.56.0"},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T00:00:00Z","timestamp":1560470400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"French Agence Nationale de la Recherche","award":["ANR-16-C40-0028"],"award-info":[{"award-number":["ANR-16-C40-0028"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Motivation<\/jats:title><jats:p>Structure-based computational protein design (CPD) plays a critical role in advancing the field of protein engineering. Using an all-atom energy function, CPD tries to identify amino acid sequences that fold into a target structure and ultimately perform a desired function. The usual approach considers a single rigid backbone as a target, which ignores backbone flexibility. Multistate design (MSD) allows instead to consider several backbone states simultaneously, defining challenging computational problems.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>We introduce efficient reductions of positive MSD problems to Cost Function Networks with two different fitness definitions and implement them in the Pompd (Positive Multistate Protein design) software. Pompd is able to identify guaranteed optimal sequences of positive multistate full protein redesign problems and exhaustively enumerate suboptimal sequences close to the MSD optimum. Applied to nuclear magnetic resonance and back-rubbed X-ray structures, we observe that the average energy fitness provides the best sequence recovery. Our method outperforms state-of-the-art guaranteed computational design approaches by orders of magnitudes and can solve MSD problems with sizes previously unreachable with guaranteed algorithms.<\/jats:p><\/jats:sec><jats:sec><jats:title>Availability and implementation<\/jats:title><jats:p>https:\/\/forgemia.inra.fr\/thomas.schiex\/pompd as documented Open Source.<\/jats:p><\/jats:sec><jats:sec><jats:title>Supplementary information<\/jats:title><jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p><\/jats:sec>","DOI":"10.1093\/bioinformatics\/btz497","type":"journal-article","created":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T11:09:37Z","timestamp":1560251377000},"page":"122-130","source":"Crossref","is-referenced-by-count":24,"title":["Positive multistate protein design"],"prefix":"10.1093","volume":"36","author":[{"given":"Jelena","family":"Vucinic","sequence":"first","affiliation":[{"name":"LISBP, Universit\u00e9 de Toulouse, CNRS, INRA, INSA , 31400 Toulouse, France"},{"name":"MIAT, Universit\u00e9 de Toulouse , INRA, 31326 Castanet-Tolosan Cedex, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Simoncini","sequence":"additional","affiliation":[{"name":"LISBP, Universit\u00e9 de Toulouse, CNRS, INRA, INSA , 31400 Toulouse, France"},{"name":"IRIT UMR 5505-CNRS, Universit\u00e9 de Toulouse , 31042 Cedex 9, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manon","family":"Ruffini","sequence":"additional","affiliation":[{"name":"LISBP, Universit\u00e9 de Toulouse, CNRS, INRA, INSA , 31400 Toulouse, France"},{"name":"MIAT, Universit\u00e9 de Toulouse , INRA, 31326 Castanet-Tolosan Cedex, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sophie","family":"Barbe","sequence":"additional","affiliation":[{"name":"LISBP, Universit\u00e9 de Toulouse, CNRS, INRA, INSA , 31400 Toulouse, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Schiex","sequence":"additional","affiliation":[{"name":"MIAT, Universit\u00e9 de Toulouse , INRA, 31326 Castanet-Tolosan Cedex, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2019,6,14]]},"reference":[{"key":"2023013109495456100_btz497-B1","doi-asserted-by":"crossref","first-page":"3031","DOI":"10.1021\/acs.jctc.7b00125","article-title":"The Rosetta all-atom energy function for macromolecular modeling and design","volume":"13","author":"Alford","year":"2017","journal-title":"J. Chem. Theory Comput"},{"key":"2023013109495456100_btz497-B2","doi-asserted-by":"crossref","first-page":"904","DOI":"10.1002\/jcc.21375","article-title":"An efficient algorithm for multistate protein design based on faster","volume":"31","author":"Allen","year":"2010","journal-title":"J. Comput. Chem"},{"key":"2023013109495456100_btz497-B3","doi-asserted-by":"crossref","first-page":"19838","DOI":"10.1073\/pnas.1012985107","article-title":"Experimental library screening demonstrates the successful application of computational protein design to large structural ensembles","volume":"107","author":"Allen","year":"2010","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023013109495456100_btz497-B4","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.artint.2014.03.005","article-title":"Computational protein design as an optimization problem","volume":"212","author":"Allouche","year":"2014","journal-title":"Artif. Intell"},{"key":"2023013109495456100_btz497-B5","doi-asserted-by":"crossref","first-page":"1154","DOI":"10.1021\/ja054718w","article-title":"Computational design of a single amino acid sequence that can switch between two distinct protein folds","volume":"128","author":"Ambroggio","year":"2006","journal-title":"J. Am. Chem. Soc"},{"key":"2023013109495456100_btz497-B6","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1002\/jcc.21988","article-title":"Durandal: fast exact clustering of protein decoys","volume":"33","author":"Berenger","year":"2012","journal-title":"J. Comput. Chem"},{"key":"2023013109495456100_btz497-B7","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1093\/nar\/28.1.235","article-title":"The protein data bank","volume":"28","author":"Berman","year":"2000","journal-title":"Nucleic Acids Res"},{"key":"2023013109495456100_btz497-B8","doi-asserted-by":"crossref","first-page":"689","DOI":"10.1093\/bioinformatics\/btq007","article-title":"PyRosetta: a script-based interface for implementing molecular modeling algorithms using Rosetta","volume":"26","author":"Chaudhury","year":"2010","journal-title":"Bioinformatics"},{"key":"2023013109495456100_btz497-B9","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1016\/j.artint.2010.02.001","article-title":"Soft arc consistency revisited","volume":"174","author":"Cooper","year":"2010","journal-title":"Artif. Intell"},{"key":"2023013109495456100_btz497-B10","doi-asserted-by":"crossref","first-page":"1241","DOI":"10.1002\/pro.2128","article-title":"Multistate approaches in computational protein design","volume":"21","author":"Davey","year":"2012","journal-title":"Protein Sci"},{"key":"2023013109495456100_btz497-B11","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/978-1-4939-6637-0_7","volume-title":"Computational Protein Design","author":"Davey","year":"2017"},{"key":"2023013109495456100_btz497-B12","doi-asserted-by":"crossref","first-page":"1280.","DOI":"10.1038\/nchembio.2503","article-title":"Rational design of proteins that exchange on functional timescales","volume":"13","author":"Davey","year":"2017","journal-title":"Nat. Chem. Biol"},{"key":"2023013109495456100_btz497-B13","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/j.str.2005.10.007","article-title":"The backrub motion: how protein backbone shrugs when a sidechain dances","volume":"14","author":"Davis","year":"2006","journal-title":"Structure"},{"key":"2023013109495456100_btz497-B14","doi-asserted-by":"crossref","first-page":"e1000393.","DOI":"10.1371\/journal.pcbi.1000393","article-title":"A correspondence between solution-state dynamics of an individual protein and the sequence and conformational diversity of its family","volume":"5","author":"Friedland","year":"2009","journal-title":"PLoS Comput. Biol"},{"key":"2023013109495456100_btz497-B15","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1089\/cmb.2015.0188","article-title":"Comets (constrained optimization of multistate energies by tree search): a provable and efficient protein design algorithm to optimize binding affinity and specificity with respect to sequence","volume":"23","author":"Hallen","year":"2016","journal-title":"J. Comput. Biol"},{"key":"2023013109495456100_btz497-B16","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.jmb.2004.09.029","article-title":"A simple physical model for the prediction and design of protein\u2013DNA interactions","volume":"344","author":"Havranek","year":"2004","journal-title":"J. Mol. Biol"},{"key":"2023013109495456100_btz497-B17","doi-asserted-by":"crossref","first-page":"e164.","DOI":"10.1371\/journal.pcbi.0030164","article-title":"Design of multi-specificity in protein interfaces","volume":"3","author":"Humphris","year":"2007","journal-title":"PLoS Comput. Biol"},{"key":"2023013109495456100_btz497-B18","doi-asserted-by":"crossref","first-page":"1777","DOI":"10.1016\/j.str.2008.09.012","article-title":"Prediction of protein\u2013protein interface sequence diversity using flexible backbone computational protein design","volume":"16","author":"Humphris","year":"2008","journal-title":"Structure"},{"key":"2023013109495456100_btz497-B19","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/s10601-016-9245-y","article-title":"Multi-language evaluation of exact solvers in graphical model discrete optimization","volume":"21","author":"Hurley","year":"2016","journal-title":"Constraints"},{"key":"2023013109495456100_btz497-B20","doi-asserted-by":"crossref","first-page":"i811","DOI":"10.1093\/bioinformatics\/bty564","article-title":"iCFN: an efficient exact algorithm for multistate protein design","volume":"34","author":"Karimi","year":"2018","journal-title":"Bioinformatics"},{"key":"2023013109495456100_btz497-B21","doi-asserted-by":"crossref","first-page":"e1005600.","DOI":"10.1371\/journal.pcbi.1005600","article-title":"Rosetta: MSF: a modular framework for multi-state computational protein design","volume":"13","author":"L\u00f6ffler","year":"2017","journal-title":"PLoS Comput. Biol"},{"key":"2023013109495456100_btz497-B22","first-page":"171","volume-title":"Methods in Enzymology","author":"Negron","year":"2013"},{"key":"2023013109495456100_btz497-B23","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1107\/S205225251801480X","article-title":"Computational design of symmetrical eight-bladed \u03b2-propeller proteins","volume":"6","author":"Noguchi","year":"2019","journal-title":"IUCrJ"},{"key":"2023013109495456100_btz497-B24","doi-asserted-by":"crossref","first-page":"779","DOI":"10.1093\/protein\/15.10.779","article-title":"Protein design is np-hard","volume":"15","author":"Pierce","year":"2002","journal-title":"Protein Eng"},{"key":"2023013109495456100_btz497-B25","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/j.jmb.2004.12.019","article-title":"Energy functions for protein design: adjustment with protein\u2013protein complex affinities, models for the unfolded state, and negative design of solubility and specificity","volume":"347","author":"Pokala","year":"2005","journal-title":"J. Mol. Biol"},{"key":"2023013109495456100_btz497-B26","volume-title":"Handbook of Constraint Programming","author":"Rossi","year":"2006"},{"key":"2023013109495456100_btz497-B27","first-page":"631","article-title":"Valued constraint satisfaction problems: hard and easy problems","volume-title":"Proceedings of the 14th IJCAI, Montr\u00e9al, Canada","author":"Schiex","year":"1995"},{"key":"2023013109495456100_btz497-B28","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1016\/j.str.2011.03.019","article-title":"A smoothed backbone-dependent rotamer library for proteins derived from adaptive kernel density estimates and regressions","volume":"19","author":"Shapovalov","year":"2011","journal-title":"Structure"},{"key":"2023013109495456100_btz497-B29","doi-asserted-by":"crossref","first-page":"5980","DOI":"10.1021\/acs.jctc.5b00594","article-title":"Guaranteed discrete energy optimization on large protein design problems","volume":"11","author":"Simoncini","year":"2015","journal-title":"J. Chem. Theory Comput"},{"key":"2023013109495456100_btz497-B30","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1145\/3205455.3205626","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference","author":"Simoncini","year":"2018"},{"key":"2023013109495456100_btz497-B31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","article-title":"The polynomial-time hierarchy","volume":"3","author":"Stockmeyer","year":"1976","journal-title":"Theor. Comput. Sci"},{"key":"2023013109495456100_btz497-B32","doi-asserted-by":"crossref","first-page":"2129","DOI":"10.1093\/bioinformatics\/btt374","article-title":"A new framework for computational protein design through cost function network optimization","volume":"29","author":"Traor\u00e9","year":"2013","journal-title":"Bioinformatics"},{"key":"2023013109495456100_btz497-B33","doi-asserted-by":"crossref","first-page":"1048","DOI":"10.1002\/jcc.24290","article-title":"Fast search algorithms for computational protein design","volume":"37","author":"Traor\u00e9","year":"2016","journal-title":"J. Comput. Chem"},{"key":"2023013109495456100_btz497-B34","doi-asserted-by":"crossref","first-page":"2122","DOI":"10.1002\/jcc.20661","article-title":"Dead-end elimination for multistate protein design","volume":"28","author":"Yanover","year":"2007","journal-title":"J. Comput. Chem"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btz497\/28924811\/btz497.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/1\/122\/48981701\/bioinformatics_36_1_122.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/1\/122\/48981701\/bioinformatics_36_1_122.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,19]],"date-time":"2024-07-19T14:44:21Z","timestamp":1721400261000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/36\/1\/122\/5519117"}},"subtitle":[],"editor":[{"given":"Arne","family":"Elofsson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2019,6,14]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btz497","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,1,1]]},"published":{"date-parts":[[2019,6,14]]}}}