{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T01:54:11Z","timestamp":1767837251890,"version":"3.49.0"},"reference-count":59,"publisher":"Oxford University Press (OUP)","issue":"17","license":[{"start":{"date-parts":[[2018,9,9]],"date-time":"2018-09-09T00:00:00Z","timestamp":1536451200000},"content-version":"vor","delay-in-days":8,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1546278"],"award-info":[{"award-number":["CCF-1546278"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000057","name":"National Institute of General Medical Sciences","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000057","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["R35GM124952"],"award-info":[{"award-number":["R35GM124952"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Texas A&M AgriLife"},{"name":"Plant Bioinformatics Graduate Training Program"},{"DOI":"10.13039\/100019038","name":"Texas A&M High Performance Research Computing","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100019038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Multistate protein design addresses real-world challenges, such as multi-specificity design and backbone flexibility, by considering both positive and negative protein states with an ensemble of substates for each. It also presents an enormous challenge to exact algorithms that guarantee the optimal solutions and enable a direct test of mechanistic hypotheses behind models. However, efficient exact algorithms are lacking for multistate protein design.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We have developed an efficient exact algorithm called interconnected cost function networks (iCFN) for multistate protein design. Its generic formulation allows for a wide array of applications such as stability, affinity and specificity designs while addressing concerns such as global flexibility of protein backbones. iCFN treats each substate design as a weighted constraint satisfaction problem (WCSP) modeled through a CFN; and it solves the coupled WCSPs using novel bounds and a depth-first branch-and-bound search over a tree structure of sequences, substates, and conformations. When iCFN is applied to specificity design of a T-cell receptor, a problem of unprecedented size to exact methods, it drastically reduces search space and running time to make the problem tractable. Moreover, iCFN generates experimentally-agreeing receptor designs with improved accuracy compared with state-of-the-art methods, highlights the importance of modeling backbone flexibility in protein design, and reveals molecular mechanisms underlying binding specificity.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>https:\/\/shen-lab.github.io\/software\/iCFN<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Supplementary information<\/jats:title>\n                  <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/bty564","type":"journal-article","created":{"date-parts":[[2018,7,7]],"date-time":"2018-07-07T06:00:37Z","timestamp":1530943237000},"page":"i811-i820","source":"Crossref","is-referenced-by-count":20,"title":["iCFN: an efficient exact algorithm for multistate protein design"],"prefix":"10.1093","volume":"34","author":[{"given":"Mostafa","family":"Karimi","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering and TEES-AgriLife Center for Bioinformatics and Genomic Systems Engineering, Texas A&M University, College Station, USA"}]},{"given":"Yang","family":"Shen","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering and TEES-AgriLife Center for Bioinformatics and Genomic Systems Engineering, Texas A&M University, College Station, USA"}]}],"member":"286","published-online":{"date-parts":[[2018,9,8]]},"reference":[{"key":"2023061313502740100_bty564-B1","first-page":"840","article-title":"Computational protein design as a cost function network optimization problem","volume-title":"Principles and Practice of Constraint Programming, Number 7514 in Lecture Notes in Computer Science","author":"Allouche","year":"2012"},{"key":"2023061313502740100_bty564-B2","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":"2023061313502740100_bty564-B3","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":"2023061313502740100_bty564-B4","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1126\/science.aaf8818","article-title":"Accurate design of megadalton-scale two-component icosahedral protein complexes","volume":"353","author":"Bale","year":"2016","journal-title":"Science"},{"key":"2023061313502740100_bty564-B5","article-title":"Virtual arc consistency for weighted CSP","volume-title":"Proceedings of the 23rd National Conference on Artificial Intelligence","author":"Cooper","year":"2008"},{"key":"2023061313502740100_bty564-B6","article-title":"Optimal soft arc consistency","volume-title":"Proceedings of the 20th International Joint Conference on Artificial Intelligence","author":"Cooper","year":"2007"},{"key":"2023061313502740100_bty564-B7","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1038\/356539a0","article-title":"The dead-end elimination theorem and its use in protein side-chain positioning","volume":"356","author":"Desmet","year":"1992","journal-title":"Nature"},{"key":"2023061313502740100_bty564-B8","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/978-1-4684-6831-1_10","article-title":"The \u2018dead-end elimination\u2019 theorem: a new approach to the side-chain packing problem","volume-title":"The Protein Folding Problem and Tertiary Structure Prediction","author":"Desmet","year":"1994"},{"key":"2023061313502740100_bty564-B9","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1002\/prot.10131","article-title":"Fast and accurate side-chain topology and energy refinement (faster) as a new method for protein structure optimization","volume":"48","author":"Desmet","year":"2002","journal-title":"Proteins: Structure, Function, and Bioinformatics"},{"key":"2023061313502740100_bty564-B10","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1006\/jmbi.1993.1170","article-title":"Backbone-dependent rotamer library for proteins. Application to side-chain prediction","volume":"230","author":"Dunbrack","year":"1993","journal-title":"J. Mol. Biol."},{"key":"2023061313502740100_bty564-B11","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1006\/jmbi.1993.1331","article-title":"A method to configure protein side-chains from\u00a0the main-chain trace in homology modelling","volume":"231","author":"Eisenmenger","year":"1993","journal-title":"J. Mol. Biol."},{"key":"2023061313502740100_bty564-B12","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1146\/annurev.bb.17.060188.002315","article-title":"Conformational substates in proteins","volume":"17","author":"Frauenfelder","year":"1988","journal-title":"Annu. Rev. Biophys. Biophys. Chem."},{"key":"2023061313502740100_bty564-B13","doi-asserted-by":"crossref","first-page":"i214","DOI":"10.1093\/bioinformatics\/btn168","article-title":"A computational framework to empower probabilistic protein design","volume":"24","author":"Fromer","year":"2008","journal-title":"Bioinformatics"},{"key":"2023061313502740100_bty564-B14","doi-asserted-by":"crossref","first-page":"e1002335","DOI":"10.1371\/journal.pcbi.1002335","article-title":"Protein design using continuous rotamers","volume":"8","author":"Gainza","year":"2012","journal-title":"PLoS Comput. Biol."},{"key":"2023061313502740100_bty564-B15","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/B978-0-12-394292-0.00005-9","article-title":"OSPREY: protein design with ensembles, flexibility, and provable algorithms","volume":"523","author":"Gainza","year":"2013","journal-title":"Methods Enzymol."},{"key":"2023061313502740100_bty564-B16","doi-asserted-by":"crossref","first-page":"i185","DOI":"10.1093\/bioinformatics\/btm197","article-title":"Dead-end elimination with backbone flexibility","volume":"23","author":"Georgiev","year":"2007","journal-title":"Bioinformatics"},{"key":"2023061313502740100_bty564-B17","first-page":"530","article-title":"A novel minimized dead-end elimination criterion and its application to protein redesign in a hybrid scoring and search algorithm for computing partition functions over molecular ensembles","volume-title":"Research in Computational Molecular Biology, Number 3909 in Lecture Notes in Computer Science","author":"Georgiev","year":"2006"},{"key":"2023061313502740100_bty564-B18","first-page":"84","article-title":"Existential arc consistency: getting closer to full arc consistency in weighted csps","volume-title":"In Proceedings of the 19th IJCAI","author":"Givry","year":"2005"},{"key":"2023061313502740100_bty564-B19","doi-asserted-by":"crossref","first-page":"1335","DOI":"10.1016\/S0006-3495(94)80923-3","article-title":"Efficient rotamer elimination applied to protein side-chains and related spin glasses","volume":"66","author":"Goldstein","year":"1994","journal-title":"Biophys. J."},{"key":"2023061313502740100_bty564-B20","doi-asserted-by":"crossref","first-page":"1505","DOI":"10.1002\/(SICI)1096-987X(199810)19:13<1505::AID-JCC7>3.0.CO;2-U","article-title":"Radical performance enhancements for combinatorial optimization algorithms based on the dead-end elimination theorem","volume":"19","author":"Gordon","year":"1998","journal-title":"J. Comput. Chem."},{"key":"2023061313502740100_bty564-B21","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1038\/nature07885","article-title":"Design of protein-interaction specificity gives selective bZIP-binding peptides","volume":"458","author":"Grigoryan","year":"2009","journal-title":"Nature"},{"key":"2023061313502740100_bty564-B22","first-page":"122","article-title":"Comets (constrained optimization of multistate energies by tree search): a provable and efficient algorithm to optimize binding affinity and specificity with respect to sequence","volume-title":"Research in Computational Molecular Biology, Number 9029 in Lecture Notes in Computer Science","author":"Hallen","year":"2015"},{"key":"2023061313502740100_bty564-B23","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1002\/prot.24150","article-title":"Dead-End Elimination with Perturbations (\u2018DEEPer\u2019): a provable protein design algorithm with continuous sidechain and backbone flexibility","volume":"81","author":"Hallen","year":"2013","journal-title":"Proteins"},{"key":"2023061313502740100_bty564-B24","doi-asserted-by":"crossref","first-page":"1462","DOI":"10.1126\/science.282.5393.1462","article-title":"High-resolution protein design with backbone freedom","volume":"282","author":"Harbury","year":"1998","journal-title":"Science"},{"key":"2023061313502740100_bty564-B25","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybernet."},{"key":"2023061313502740100_bty564-B26","doi-asserted-by":"crossref","first-page":"4967","DOI":"10.1073\/pnas.79.16.4967","article-title":"Conformational substates in a protein: structure and dynamics of metmyoglobin at 80\u2009K","volume":"79","author":"Hartmann","year":"1982","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023061313502740100_bty564-B27","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1038\/nsb877","article-title":"Automated design of specificity in molecular recognition","volume":"10","author":"Havranek","year":"2003","journal-title":"Nat. Struct. Biol."},{"key":"2023061313502740100_bty564-B28","doi-asserted-by":"crossref","first-page":"1923","DOI":"10.1002\/jcc.21188","article-title":"Rotamer optimization for protein design through MAP estimation and problem-size reduction","volume":"30","author":"Hong","year":"2009","journal-title":"J. Comput. Chem."},{"key":"2023061313502740100_bty564-B29","doi-asserted-by":"crossref","first-page":"1387","DOI":"10.1126\/science.1152692","article-title":"De\u00a0novo computational design of retro-aldol enzymes","volume":"319","author":"Jiang","year":"2008","journal-title":"Science"},{"key":"2023061313502740100_bty564-B30","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1002\/pro.5560030405","article-title":"De\u00a0novo protein design using pairwise potentials and a genetic algorithm","volume":"3","author":"Jones","year":"1994","journal-title":"Protein Sci."},{"key":"2023061313502740100_bty564-B31","doi-asserted-by":"crossref","first-page":"1028","DOI":"10.1093\/bioinformatics\/bti144","article-title":"Solving and analyzing side-chain positioning problems using linear and integer programming","volume":"21","author":"Kingsford","year":"2005","journal-title":"Bioinformatics"},{"key":"2023061313502740100_bty564-B32","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1038\/nsmb749","article-title":"Computational redesign of protein-protein interaction specificity","volume":"11","author":"Kortemme","year":"2004","journal-title":"Nat. Struct. Mol. Biol."},{"key":"2023061313502740100_bty564-B33","doi-asserted-by":"crossref","first-page":"1364","DOI":"10.1126\/science.1089427","article-title":"Design of a novel globular protein fold with atomic-level accuracy","volume":"302","author":"Kuhlman","year":"2003","journal-title":"Science"},{"key":"2023061313502740100_bty564-B34","first-page":"48","article-title":"Node and Arc Consistency in Weighted CSP","volume-title":"Proceedings of the 18th National Conference on Artificial Intelligence","author":"Larrosa","year":"2002"},{"key":"2023061313502740100_bty564-B35","first-page":"239","article-title":"In the quest of the best form of local consistency for weighted CSP","volume-title":"Proceedings of the 18th International Joint Conference on Artificial Intelligence, IJCAI\u201903","author":"Larrosa","year":"2003"},{"key":"2023061313502740100_bty564-B36","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.artint.2004.05.004","article-title":"Solving weighted CSP by maintaining arc consistency","volume":"159","author":"Larrosa","year":"2004","journal-title":"Artif. Intell."},{"key":"2023061313502740100_bty564-B37","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1002\/(SICI)1097-0134(19981101)33:2<227::AID-PROT7>3.0.CO;2-F","article-title":"Exploring the conformational space of protein side chains using dead-end elimination and the A* algorithm","volume":"33","author":"Leach","year":"1998","journal-title":"Proteins"},{"key":"2023061313502740100_bty564-B38","doi-asserted-by":"crossref","first-page":"e20937","DOI":"10.1371\/journal.pone.0020937","article-title":"A generic program for multistate protein design","volume":"6","author":"Leaver-Fay","year":"2011","journal-title":"PLoS One"},{"key":"2023061313502740100_bty564-B39","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1016\/B978-0-12-381270-4.00019-6","article-title":"ROSETTA3: an object-oriented software suite for the simulation and design of macromolecules","volume":"487","author":"Leaver-Fay","year":"2011","journal-title":"Methods Enzymol."},{"key":"2023061313502740100_bty564-B40","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1038\/nbt1336","article-title":"Computational design of antibody-affinity improvement beyond in\u00a0vivo maturation","volume":"25","author":"Lippow","year":"2007","journal-title":"Nat. Biotechnol."},{"key":"2023061313502740100_bty564-B41","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":"Loffler","year":"2017","journal-title":"PLoS Comput. Biol."},{"key":"2023061313502740100_bty564-B42","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/B978-0-12-394292-0.00008-4","article-title":"Multistate protein design using CLEVER and CLASSY","volume":"523","author":"Negron","year":"2013","journal-title":"Methods Enzymol."},{"key":"2023061313502740100_bty564-B43","first-page":"230","article-title":"Triangle-based consistencies for cost function networks","volume-title":"Constraints","author":"Nguyen","year":"2017"},{"key":"2023061313502740100_bty564-B44","doi-asserted-by":"crossref","first-page":"e1003478","DOI":"10.1371\/journal.pcbi.1003478","article-title":"Computational design of the affinity and specificity of a therapeutic T cell receptor","volume":"10","author":"Pierce","year":"2014","journal-title":"PLoS Comput. Biol."},{"key":"2023061313502740100_bty564-B45","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":"2023061313502740100_bty564-B46","doi-asserted-by":"crossref","first-page":"999","DOI":"10.1002\/1096-987X(200008)21:11<999::AID-JCC9>3.0.CO;2-A","article-title":"Conformational splitting: a more powerful criterion for dead-end elimination","volume":"21","author":"Pierce","year":"2000","journal-title":"J. Comput. Chem."},{"key":"2023061313502740100_bty564-B47","doi-asserted-by":"crossref","first-page":"1859","DOI":"10.1002\/prot.24870","article-title":"Fast gap-free enumeration of conformations and sequences for protein design","volume":"83","author":"Roberts","year":"2015","journal-title":"Proteins"},{"key":"2023061313502740100_bty564-B48","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1038\/nature06879","article-title":"Kemp elimination catalysts by computational enzyme design","volume":"453","author":"Rothlisberger","year":"2008","journal-title":"Nature"},{"key":"2023061313502740100_bty564-B49","first-page":"631","article-title":"Valued constraint satisfaction problems: hard and easy\u00a0problems","volume-title":"Proceedings of the 14th International\u00a0Joint Conference on Artificial Intelligence - Volume 1, IJCAI\u201995","author":"Schiex","year":"1995"},{"key":"2023061313502740100_bty564-B50","doi-asserted-by":"crossref","first-page":"e1004300","DOI":"10.1371\/journal.pcbi.1004300","article-title":"Design of protein multi-specificity using an independent sequence search reduces the barrier to low energy sequences","volume":"11","author":"Sevy","year":"2015","journal-title":"PLoS Comput. Biol."},{"key":"2023061313502740100_bty564-B51","doi-asserted-by":"crossref","first-page":"2129","DOI":"10.1002\/prot.24404","article-title":"Improved flexible refinement of protein docking in CAPRI rounds 22\u201327","volume":"81","author":"Shen","year":"2013","journal-title":"Proteins"},{"key":"2023061313502740100_bty564-B52","doi-asserted-by":"crossref","first-page":"2433","DOI":"10.1021\/cb400468c","article-title":"Testing the substrate-envelope hypothesis with designed pairs of compounds","volume":"8","author":"Shen","year":"2013","journal-title":"ACS Chem. Biol."},{"key":"2023061313502740100_bty564-B53","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1002\/prot.24730","article-title":"Molecular mechanisms and design principles for promiscuous inhibitors to avoid drug resistance: lessons learned from HIV-1 protease inhibition","volume":"83","author":"Shen","year":"2015","journal-title":"Proteins"},{"key":"2023061313502740100_bty564-B54","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":"2023061313502740100_bty564-B55","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":"2023061313502740100_bty564-B56","doi-asserted-by":"crossref","first-page":"2581","DOI":"10.1093\/bioinformatics\/bty092","article-title":"Cost function network-based design of protein-protein interactions: predicting changes in binding affinity","volume":"34","author":"Viricel","year":"2018","journal-title":"Bioinformatics"},{"key":"2023061313502740100_bty564-B57","first-page":"1457","article-title":"Approximate inference and protein-folding","volume-title":"Proceedings of the 15th International Conference on Neural Information Processing Systems","author":"Yanover","year":"2002"},{"key":"2023061313502740100_bty564-B58","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."},{"key":"2023061313502740100_bty564-B59","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1089\/cmb.2015.0212","article-title":"Computational protein design using AND\/OR branch-and-bound search","volume":"23","author":"Zhou","year":"2016","journal-title":"J. Comput. Biol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/17\/i811\/50582390\/bioinformatics_34_17_i811.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/17\/i811\/50582390\/bioinformatics_34_17_i811.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T13:52:55Z","timestamp":1686664375000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/34\/17\/i811\/5093221"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,1]]},"references-count":59,"journal-issue":{"issue":"17","published-print":{"date-parts":[[2018,9,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bty564","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2018,9,1]]},"published":{"date-parts":[[2018,9,1]]}}}