{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T05:51:26Z","timestamp":1768456286965,"version":"3.49.0"},"reference-count":40,"publisher":"Oxford University Press (OUP)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005,4,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Side-chain positioning is a central component of homology modeling and protein design. In a common formulation of the problem, the backbone is fixed, side-chain conformations come from a rotamer library, and a pairwise energy function is optimized. It is NP-complete to find even a reasonable approximate solution to this problem. We seek to put this hardness result into practical context.<\/jats:p>\n               <jats:p>Results: We present an integer linear programming (ILP) formulation of side-chain positioning that allows us to tackle large problem sizes. We relax the integrality constraint to give a polynomial-time linear programming (LP) heuristic. We apply LP to position side chains on native and homologous backbones and to choose side chains for protein design. Surprisingly, when positioning side chains on native and homologous backbones, optimal solutions using a simple, biologically relevant energy function can usually be found using LP. On the other hand, the design problem often cannot be solved using LP directly; however, optimal solutions for large instances can still be found using the computationally more expensive ILP procedure. While different energy functions also affect the difficulty of the problem, the LP\/ILP approach is able to find optimal solutions. Our analysis is the first large-scale demonstration that LP-based approaches are highly effective in finding optimal (and successive near-optimal) solutions for the side-chain positioning problem.<\/jats:p>\n               <jats:p>Availability: The source code for generating the ILP given a file of pairwise energies between rotamers is available online at http:\/\/compbio.cs.princeton.edu\/scplp<\/jats:p>\n               <jats:p>Contact: \u00a0msingh@cs.princeton.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/bti144","type":"journal-article","created":{"date-parts":[[2004,11,17]],"date-time":"2004-11-17T03:23:11Z","timestamp":1100661791000},"page":"1028-1039","source":"Crossref","is-referenced-by-count":165,"title":["Solving and analyzing side-chain positioning problems using linear and integer programming"],"prefix":"10.1093","volume":"21","author":[{"given":"Carleton L.","family":"Kingsford","sequence":"first","affiliation":[{"name":"Department of Computer Science and the Lewis-Sigler Institute for Integrative Genomics, Princeton University Princeton, NJ 08544, USA"}]},{"given":"Bernard","family":"Chazelle","sequence":"additional","affiliation":[{"name":"Department of Computer Science and the Lewis-Sigler Institute for Integrative Genomics, Princeton University Princeton, NJ 08544, USA"}]},{"given":"Mona","family":"Singh","sequence":"additional","affiliation":[{"name":"Department of Computer Science and the Lewis-Sigler Institute for Integrative Genomics, Princeton University Princeton, NJ 08544, USA"}]}],"member":"286","published-online":{"date-parts":[[2004,11,16]]},"reference":[{"key":"2023013107270920100_B1","doi-asserted-by":"crossref","unstructured":"Althaus, E., Kohlbacher, O., Lenhof, H.-P., M\u00fcller, P. 2000A combinatorial approach to protein docking with flexible side-chains. Proceedings of the 4th Annual International Conference on Computational Molecular Biology , New York, NY  ACM Press,  pp. 15\u201324","DOI":"10.1145\/332306.332319"},{"key":"2023013107270920100_B2","unstructured":"Bahadur, K.C.D., Akutsu, T., Tomita, E., Seki, T. 2004Protein side-chain packing problem: a maximum edge-weight clique algorithmic approach. Proceedings of the Second Conference on Asia-Pacific Bioinformatics , Darlinghurst, Australia  Australian Computer Society Inc.,  pp. 191\u2013200"},{"key":"2023013107270920100_B3","doi-asserted-by":"crossref","unstructured":"Bower, M.J., Cohen, F.E., Dunbrack, R.L., Jr. 1997Prediction of protein side-chain rotamers from a backbone-dependent rotamer library: a homology modeling tool. J. Mol. Biol.2671268\u20131282","DOI":"10.1006\/jmbi.1997.0926"},{"key":"2023013107270920100_B4","doi-asserted-by":"crossref","unstructured":"Canutescu, A.A., Shelenkov, A.A., Dunbrack, R.L., Jr. 2003A graph-theory algorithm for rapid protein side-chain prediction. Protein Sci.122001\u20132014","DOI":"10.1110\/ps.03154503"},{"key":"2023013107270920100_B5","doi-asserted-by":"crossref","unstructured":"Chazelle, B., Kingsford, C., Singh, M. 2004A semidefinite-programming approach to side-chain positioning with new rounding strategies. INFORMS J. Comput.16380\u2013392","DOI":"10.1145\/778348.778360"},{"key":"2023013107270920100_B6","doi-asserted-by":"crossref","unstructured":"Dahiyat, B.I. and Mayo, S.L. 1997De novo protein design: fully automated sequence selection. Science27882\u201387","DOI":"10.1126\/science.278.5335.82"},{"key":"2023013107270920100_B7","doi-asserted-by":"crossref","unstructured":"Desmet, J., De Maeyer, M., Hazes, B., Lasters, I. 1992The dead-end elimination theorem and its use in protein side-chain positioning. Nature356539\u2013542","DOI":"10.1038\/356539a0"},{"key":"2023013107270920100_B8","doi-asserted-by":"crossref","unstructured":"Desmet, J., De Maeyer, M., Lasters, I. 1994The \u2018dead-end elimination\u2019 theorem as a new approach to the side-chain packing problem. In Merz, K. and LeGrand, S. (Eds.). The Protein Folding Problem and Tertiary Structure Prediction , Boston, MA, USA  Birkh\u00e4user,  pp. 307\u2013337","DOI":"10.1007\/978-1-4684-6831-1_10"},{"key":"2023013107270920100_B9","doi-asserted-by":"crossref","unstructured":"Dunbrack, R.L., Jr. and Karplus, M. 1993Backbone-dependent rotamer library for proteins: application to side-chain prediction. J. Mol. Biol.230543\u2013574","DOI":"10.1006\/jmbi.1993.1170"},{"key":"2023013107270920100_B10","doi-asserted-by":"crossref","unstructured":"Eriksson, O., Zhou, Y., Elofsson, A. 2001Side chain-positioning as an integer programming problem. Proceedings of 1st Workshop on Algorithms in BioInformatics , Denmark  BRICS, University of Aarhus,  pp. 129\u2013141","DOI":"10.1007\/3-540-44696-6_10"},{"key":"2023013107270920100_B11","unstructured":"Fourer, R., Gay, D.M., Kernighan, B.W. AMPL A Modeling Language for Mathematical Programming2002, Pacific Grove, CA  Brooks\/Cole Publishing Company"},{"key":"2023013107270920100_B12","doi-asserted-by":"crossref","unstructured":"Goldstein, R.F. 1994Efficient rotamer elimination applied to protein side-chains and related spin glasses. Biophys. J66,  pp. 1335\u20131340","DOI":"10.1016\/S0006-3495(94)80923-3"},{"key":"2023013107270920100_B13","unstructured":"Gordon, D.B., Hom, G., Mayo, S., Pierce, N. 2002Exact rotamer optimization for protein design. J. Comput. Chem.24232\u2013243"},{"key":"2023013107270920100_B14","doi-asserted-by":"crossref","unstructured":"Gordon, D.B. and Mayo, S.L. 1998Radical performance enhancements for combinatorial optimization algorithms based on the dead-end elimination theorem. J. Comput. Chem.191505\u20131514","DOI":"10.1002\/(SICI)1096-987X(199810)19:13<1505::AID-JCC7>3.0.CO;2-U"},{"key":"2023013107270920100_B15","doi-asserted-by":"crossref","unstructured":"Harbury, P.B., Plecs, J.J., Tidor, B., Alber, T., Kim, P.S. 1998High-resolution protein design with backbone freedom. Science2821462\u20131467","DOI":"10.1126\/science.282.5393.1462"},{"key":"2023013107270920100_B16","unstructured":"Holm, L.S. and Sander, C. 1991Database algorithm for generating protein backbone and side-chain coordinates from a Calpha trace: application to model building and detection of coordinate errors. J. Mol. Biol.218183\u2013194"},{"key":"2023013107270920100_B17","unstructured":"ILOG CPLEX. 2000ILOG CPLEX 7.1"},{"key":"2023013107270920100_B18","doi-asserted-by":"crossref","unstructured":"Jones, T.A. and Kleywegt, G.J. 1999CASP3 comparative modeling evaluation. Proteins3730\u201346","DOI":"10.1002\/(SICI)1097-0134(1999)37:3+<30::AID-PROT6>3.0.CO;2-S"},{"key":"2023013107270920100_B19","doi-asserted-by":"crossref","unstructured":"Klepeis, J.L., Floudas, C.A., Morikis, D., Tsokos, C.G., Argyropoulos, E., Spruce, L., Lambris, J.D. 2003Integrated computational and experimental approach for lead optimization and design of compstatin variants with improved activity. J. Am. Chem. Soc.1258422\u20138423","DOI":"10.1021\/ja034846p"},{"key":"2023013107270920100_B20","unstructured":"Kohlbacher, O. and Lenhof, H.-P. 2000BALL\u2014rapid software prototyping in computational molecular biology. Bioinformatics16815\u2013824"},{"key":"2023013107270920100_B21","doi-asserted-by":"crossref","unstructured":"Lasters, I., De Maeyer, M., Desmet, J. 1995Enhanced dead-end elimination in the search for the global minimum energy conformation of a collection of protein side chains. Protein Eng.8815\u2013822","DOI":"10.1093\/protein\/8.8.815"},{"key":"2023013107270920100_B22","unstructured":"Leach, A.R. and Lemon, A.P. 1998Exploring the conformational space of protein side chains using dead-end elimination and the A* algorithm. Proteins33227\u2013239"},{"key":"2023013107270920100_B23","unstructured":"Lee, C. 1994Predicting protein mutant energetics by self-consistent ensemble optimization. J. Mol. Biol.236918\u2013939"},{"key":"2023013107270920100_B24","unstructured":"Lee, C. and Subbiah, S. 1991Prediction of protein side-chain conformation by packing optimization. J. Mol. Biol.217373\u2013388"},{"key":"2023013107270920100_B25","doi-asserted-by":"crossref","unstructured":"Lilien, R.H., Stevens, B.W., Anderson, A.C., Donald, B.R. 2004A novel ensemble-based scoring and search algorithm for protein redesign, and its application to modify the substrate specificity of the gramicidin synthetase a phenylalanine adenylation enzyme. Proceedings of the 8th Annual International Conference on Computational Molecular Biology , New York, NY  ACM Press,  pp. 46\u201357","DOI":"10.1145\/974614.974622"},{"key":"2023013107270920100_B26","unstructured":"Looger, L.L., Dwyer, M.A., Smith, J.J., Hellinga, H.W. 2003Computational design of receptor and sensor proteins with novel functions. Nature423185\u2013190"},{"key":"2023013107270920100_B27","doi-asserted-by":"crossref","unstructured":"Looger, L.L. and Hellinga, H.W. 2001Generalized dead-end elimination algorithms make large-scale protein side-chain structure prediction tractable: implications for protein design and structural genomics. J. Mol. Biol.307429\u2013445","DOI":"10.1006\/jmbi.2000.4424"},{"key":"2023013107270920100_B28","doi-asserted-by":"crossref","unstructured":"Malakauskas, S.M. and Mayo, S.L. 1998Design, structure and stability of a hyperthermophilic protein variant. Nat. Struct. Biol.5470\u2013475","DOI":"10.1038\/nsb0698-470"},{"key":"2023013107270920100_B29","unstructured":"Martin, A.C.R. 2001Profit program version 2.2"},{"key":"2023013107270920100_B30","unstructured":"McLachlan, A.D. 1982Rapid comparison of protein structures. Acta Crystallogr.A38871\u2013873"},{"key":"2023013107270920100_B31","unstructured":"Nicholls, A., Sharp, K.A., Honig, B. 1991Protein folding and association: insights from the interfacial and thermodynamic properties of hydrocarbons. Proteins11281\u2013296"},{"key":"2023013107270920100_B32","unstructured":"Park, S., Yang, X., Saven, J.G. 2004Advances in computational protein design. Curr. Opin. Struct. Biol.14487\u2013494"},{"key":"2023013107270920100_B33","doi-asserted-by":"crossref","unstructured":"Petrey, D., Xiang, Z., Tang, C., Xie, L., Gimpelev, M., Mitros, T., Soto, C., Goldsmith-Fischman, S., Kernytsky, A., Schlessinger, A., et al. 2003Using multiple structure alignments, fast model building and energetic analysis in fold recognition and homology modeling. Proteins53430\u2013435","DOI":"10.1002\/prot.10550"},{"key":"2023013107270920100_B34","unstructured":"Pierce, N.A. and Winfree, E. 2002Protein design is NP-hard. Protein Eng.15779\u2013782"},{"key":"2023013107270920100_B35","unstructured":"Ponder, J.W. and Richards, F.M. 1987Tertiary templates for proteins: use of packing criteria in the enumeration of allowed sequences for different structural classes. J. Mol. Biol.193775\u2013791"},{"key":"2023013107270920100_B36","unstructured":"Samudrala, R. and Moult, J. 1998A graph-theoretic algorithm for comparative modeling of protein structure. J. Mol. Biol.279287\u2013302"},{"key":"2023013107270920100_B37","unstructured":"Summers, N. and Karplus, M. 1989Construction of side-chains in homology modeling: application to the C-terminal lobe of rhizopuspepsin. J. Mol. Biol.210785\u2013811"},{"key":"2023013107270920100_B38","doi-asserted-by":"crossref","unstructured":"Thompson, J.D., Higgins, D.G., Gibson, T.J. 1994Clustal W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, positions-specific gap penalties and weight matrix choice. Nucleic Acids Res.224673\u20134680","DOI":"10.1093\/nar\/22.22.4673"},{"key":"2023013107270920100_B39","doi-asserted-by":"crossref","unstructured":"Ventura, S. and Serrano, L. 2004Designing proteins from the inside out. Proteins561\u201310","DOI":"10.1002\/prot.20142"},{"key":"2023013107270920100_B40","doi-asserted-by":"crossref","unstructured":"Xiang, Z. and Honig, B. 2001Extending the accuracy limits of prediction for side-chain conformations. J. Mol. Biol.311421\u2013430","DOI":"10.1006\/jmbi.2001.4985"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/7\/1028\/48966796\/bioinformatics_21_7_1028.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/7\/1028\/48966796\/bioinformatics_21_7_1028.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T10:25:50Z","timestamp":1675160750000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/21\/7\/1028\/269065"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,11,16]]},"references-count":40,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2005,4,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bti144","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2005,4,1]]},"published":{"date-parts":[[2004,11,16]]}}}