{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T08:48:46Z","timestamp":1790758126379,"version":"4.1.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2006,7]]},"abstract":"<jats:p>This article studies the protein side-chain packing problem using the tree-decomposition of a protein structure. To obtain fast and accurate protein side-chain packing, protein structures are modeled using a geometric neighborhood graph, which can be easily decomposed into smaller blocks. Therefore, the side-chain assignment of the whole protein can be assembled from the assignment of the small blocks. Although we will show that the side-chain packing problem is still<jats:italic>NP<\/jats:italic>-hard, we can achieve a tree-decomposition-based globally optimal algorithm with time complexity of<jats:italic>O<\/jats:italic>(<jats:italic>Nn<\/jats:italic><jats:sub><jats:italic>rot<\/jats:italic><\/jats:sub><jats:sup><jats:italic>tw<\/jats:italic>+ 1)<\/jats:sup>and several polynomial-time approximation schemes (PTAS), where<jats:italic>N<\/jats:italic>is the number of residues contained in the protein,<jats:italic>n<\/jats:italic><jats:sub><jats:italic>rot<\/jats:italic><\/jats:sub>the average number of rotamers for each residue, and<jats:italic>tw<\/jats:italic>=<jats:italic>O<\/jats:italic>(<jats:italic>N<\/jats:italic><jats:sup>2\/3<\/jats:sup>log<jats:italic>N<\/jats:italic>) the treewidth of the protein structure graph. Experimental results indicate that after Goldstein dead-end elimination is conducted,<jats:italic>n<\/jats:italic><jats:sub><jats:italic>rot<\/jats:italic><\/jats:sub>is very small and<jats:italic>tw<\/jats:italic>is equal to 3 or 4 most of the time. Based on the globally optimal algorithm, we developed a protein side-chain assignment program TreePack, which runs up to 90 times faster than SCWRL 3.0, a widely-used side-chain packing program, on some large test proteins in the SCWRL benchmark database and an average of five times faster on all the test proteins in this database. There are also some real-world instances that TreePack can solve but that SCWRL 3.0 cannot. The TreePack program is available at http:\/\/ttic.uchicago.edu\/~jinbo\/TreePack.htm.<\/jats:p>","DOI":"10.1145\/1162349.1162350","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"533-557","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":73,"title":["Fast and accurate algorithms for protein side-chain packing"],"prefix":"10.1145","volume":"53","author":[{"given":"Jinbo","family":"Xu","sequence":"first","affiliation":[{"name":"Toyota Technological Institute at Chicago and Massachusetts Institute of Technology, Chicago, IL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bonnie","family":"Berger","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Akutsu T. 1997. NP-hardness results for protein side-chain packing. In Genome Informatics 8 S. Miyano and T. Takagi Eds. 180--186.]] Akutsu T. 1997. NP-hardness results for protein side-chain packing. In Genome Informatics 8 S. Miyano and T. Takagi Eds. 180--186.]]"},{"key":"e_1_2_1_2_1","volume-title":"Biocomputing: Proceedings of 1996 Pacific Symposium.]]","author":"Alexandrov N.","unstructured":"Alexandrov , N. , Nussinov , R. , and Zimmer , R . 1996. Fast protein fold recognition via sequence to structure alignment and contact capacity potentials . In Biocomputing: Proceedings of 1996 Pacific Symposium.]] Alexandrov, N., Nussinov, R., and Zimmer, R. 1996. Fast protein fold recognition via sequence to structure alignment and contact capacity potentials. In Biocomputing: Proceedings of 1996 Pacific Symposium.]]"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence (UAI '01)","author":"Amir E.","year":"2001","unstructured":"Amir , E. 2001 . Efficient approximation for triangulation of minimum treewdith . In Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence (UAI '01) . 7--15.]] Amir, E. 2001. Efficient approximation for triangulation of minimum treewdith. In Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence (UAI '01). 7--15.]]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293348"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Bach F. and Jordan M. 2002. Thin junction trees. In Advances in Neural Information Processing Systems (NIPS) T. Dietterich S. Becker and Z. Ghahramani Eds. Vol. 14. 569--574.]] Bach F. and Jordan M. 2002. Thin junction trees. In Advances in Neural Information Processing Systems (NIPS) T. Dietterich S. Becker and Z. Ghahramani Eds. Vol. 14. 569--574.]]","DOI":"10.7551\/mitpress\/1120.003.0078"},{"key":"e_1_2_1_7_1","volume-title":"Lecture Notes in Computer Science","volume":"2880","author":"Berry A.","unstructured":"Berry , A. , Heggernes , P. , and Simonet , G . 2003. The minimum degree heuristic and the minimal triangulation process . In Lecture Notes in Computer Science , vol. 2880 . Springer-Verlag, New York, 58--70.]] Berry, A., Heggernes, P., and Simonet, G. 2003. The minimum degree heuristic and the minimal triangulation process. In Lecture Notes in Computer Science, vol. 2880. Springer-Verlag, New York, 58--70.]]"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"1268","DOI":"10.1006\/jmbi.1997.0926","article-title":"Prediction of protein side-chain rotamers from a backbone-dependent rotamer library: A new homology modeling tool","volume":"267","author":"Bower M.","year":"1997","unstructured":"Bower , M. , Cohen , F. , and Dunbrack , jr., R. L. 1997 . Prediction of protein side-chain rotamers from a backbone-dependent rotamer library: A new homology modeling tool . J. Mol. Biol. 267 , 1268 -- 1282 .]] Bower, M., Cohen, F., and Dunbrack, jr., R. L. 1997. Prediction of protein side-chain rotamers from a backbone-dependent rotamer library: A new homology modeling tool. J. Mol. Biol. 267, 1268--1282.]]","journal-title":"J. Mol. Biol."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"2001","DOI":"10.1110\/ps.03154503","article-title":"A graph-theory algorithm for rapid protein side-chain prediction","volume":"12","author":"Canutescu A.","year":"2003","unstructured":"Canutescu , A. , Shelenkov , A. , and Dunbrack , jr., R. L. 2003 . A graph-theory algorithm for rapid protein side-chain prediction . Prot. Sci. 12 , 2001 -- 2014 .]] Canutescu, A., Shelenkov, A., and Dunbrack, jr., R. L. 2003. A graph-theory algorithm for rapid protein side-chain prediction. Prot. Sci. 12, 2001--2014.]]","journal-title":"Prot. Sci."},{"key":"e_1_2_1_10_1","unstructured":"Chazelle B. Kingsford C. and Singh M. 2004. A semidefinite programming approach to side-chain positioning with new rounding strategies. INFORMS J. Comput. Special Issue in Computational Molecular Biology\/Bioinformatics 86--94.]] 10.1287\/ijoc.1040.0096 Chazelle B. Kingsford C. and Singh M. 2004. A semidefinite programming approach to side-chain positioning with new rounding strategies. INFORMS J. Comput. Special Issue in Computational Molecular Biology\/Bioinformatics 86--94.]] 10.1287\/ijoc.1040.0096"},{"key":"e_1_2_1_11_1","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 J.","year":"1992","unstructured":"Desmet , J. , Maeyer , M. D. , Hazes , B. , and Laster , I. 1992 . The dead-end elimination theorem and its use in protein side-chain positioning . Nature 356 , 539 -- 542 .]] Desmet, J., Maeyer, M. D., Hazes, B., and Laster, I. 1992. The dead-end elimination theorem and its use in protein side-chain positioning. Nature 356, 539--542.]]","journal-title":"Nature"},{"key":"e_1_2_1_12_1","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. Protein","volume":"48","author":"Desmet J.","year":"2002","unstructured":"Desmet , J. , Spriet , J. , and Laster , I. 2002 . Fast and accurate side-chain topology and energy refinement (faster) as a new method for protein structure optimization. Protein : Struct. Funct. Gen. 48 , 31 -- 43 .]] Desmet, J., Spriet, J., and Laster, I. 2002. Fast and accurate side-chain topology and energy refinement (faster) as a new method for protein structure optimization. Protein: Struct. Funct. Gen. 48, 31--43.]]","journal-title":"Struct. Funct. Gen."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 2nd Asia Pacific Bioinformatics Conference. 191--200","author":"Dukka K.","unstructured":"Dukka , K. , Tomita , E. , Suzuki , J. , and Akutsu , T . 2004. Protein side-chain packing problem: a maximum common edge-weight clique algorithmic approach . In Proceedings of the 2nd Asia Pacific Bioinformatics Conference. 191--200 .]] Dukka, K., Tomita, E., Suzuki, J., and Akutsu, T. 2004. Protein side-chain packing problem: a maximum common edge-weight clique algorithmic approach. In Proceedings of the 2nd Asia Pacific Bioinformatics Conference. 191--200.]]"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1002\/(SICI)1097-0134(1999)37:3+<81::AID-PROT12>3.0.CO;2-R","article-title":"Comparative modeling of CASP3 targets using PSI-BLAST and SCWRL. Protein","volume":"3","author":"Dunbrack","year":"1999","unstructured":"Dunbrack Jr ., R. L. 1999 . Comparative modeling of CASP3 targets using PSI-BLAST and SCWRL. Protein : Struct. Funct. Gen. 3 , 81 -- 87 .]] Dunbrack Jr., R. L. 1999. Comparative modeling of CASP3 targets using PSI-BLAST and SCWRL. Protein: Struct. Funct. Gen. 3, 81--87.]]","journal-title":"Struct. Funct. Gen."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"1661","DOI":"10.1002\/pro.5560060807","article-title":"Bayesian statistical analysis of protein side-chain rotamer preferences","volume":"6","author":"Dunbrack","year":"1997","unstructured":"Dunbrack Jr ., R. L., and Cohen , F. 1997 . Bayesian statistical analysis of protein side-chain rotamer preferences . Protein Sci. 6 , 1661 -- 1681 .]] Dunbrack Jr., R. L., and Cohen, F. 1997. Bayesian statistical analysis of protein side-chain rotamer preferences. Protein Sci. 6, 1661--1681.]]","journal-title":"Protein Sci."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 1st International Workshop on Algorithms in Bioinformatics. Springer-Verlag","author":"Eriksson O.","unstructured":"Eriksson , O. , Zhou , Y. , and Elofsson , A . 2001. Side chain-positioning as an integer programming problem . In Proceedings of the 1st International Workshop on Algorithms in Bioinformatics. Springer-Verlag , New York, 128--141.]] Eriksson, O., Zhou, Y., and Elofsson, A. 2001. Side chain-positioning as an integer programming problem. In Proceedings of the 1st International Workshop on Algorithms in Bioinformatics. Springer-Verlag, New York, 128--141.]]"},{"key":"e_1_2_1_17_1","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 R.","year":"1994","unstructured":"Goldstein , R. 1994 . Efficient rotamer elimination applied to protein side-chains and related spin glasses . Biophys. J. 66 , 1335 -- 1340 .]] Goldstein, R. 1994. Efficient rotamer elimination applied to protein side-chains and related spin glasses. Biophys. J. 66, 1335--1340.]]","journal-title":"Biophys. J."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0022-2836(91)90883-8","article-title":"Database algorithm for generating protein backbone and sidechain coordinates from a ca trace: Application to model building and detection of coordinate errors","volume":"218","author":"Holm L.","year":"1991","unstructured":"Holm , L. , and Sander , C. 1991 . Database algorithm for generating protein backbone and sidechain coordinates from a ca trace: Application to model building and detection of coordinate errors . J. Mol. Biol. 218 , 183 -- 194 .]] Holm, L., and Sander, C. 1991. Database algorithm for generating protein backbone and sidechain coordinates from a ca trace: Application to model building and detection of coordinate errors. J. Mol. Biol. 218, 183--194.]]","journal-title":"J. Mol. Biol."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979223842X"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1006\/jmbi.1999.2583","article-title":"GenTHREADER: An efficient and reliable protein fold recognition method for genomic sequences","volume":"287","author":"Jones D.","year":"1999","unstructured":"Jones , D. 1999 . GenTHREADER: An efficient and reliable protein fold recognition method for genomic sequences . J. Mol. Biol. 287 , 797 -- 815 .]] Jones, D. 1999. GenTHREADER: An efficient and reliable protein fold recognition method for genomic sequences. J. Mol. Biol. 287, 797--815.]]","journal-title":"J. Mol. Biol."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1006\/jmbi.2000.3741","article-title":"Enhanced genome annotation using structural profiles in the program 3D-PSSM","volume":"299","author":"Kelley L.","year":"2000","unstructured":"Kelley , L. , MacCallum , R. , and Sternberg , M. 2000 . Enhanced genome annotation using structural profiles in the program 3D-PSSM . J. Mol. Biol. 299 , 2, 499 -- 520 .]] Kelley, L., MacCallum, R., and Sternberg, M. 2000. Enhanced genome annotation using structural profiles in the program 3D-PSSM. J. Mol. Biol. 299, 2, 499--520.]]","journal-title":"J. Mol. Biol."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti144"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1093\/bioinformatics\/16.9.815","article-title":"BALL---Rapid software prototyping in computational molecular biology","volume":"16","author":"Kohlbacher O.","year":"2000","unstructured":"Kohlbacher , O. , and Lenhof , H. 2000 . BALL---Rapid software prototyping in computational molecular biology . Bioinformatics 16 , 9, 815 -- 824 .]] Kohlbacher, O., and Lenhof, H. 2000. BALL---Rapid software prototyping in computational molecular biology. Bioinformatics 16, 9, 815--824.]]","journal-title":"Bioinformatics"},{"key":"e_1_2_1_24_1","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&ast; algorithm. Protein","volume":"33","author":"Leach A.","year":"1998","unstructured":"Leach , A. , and Lemon , A. 1998 . Exploring the conformational space of protein side chains using dead-end elimination and the A&ast; algorithm. Protein : Struct. Funct. Gen. 33 , 227 -- 239 .]] Leach, A., and Lemon, A. 1998. Exploring the conformational space of protein side chains using dead-end elimination and the A&ast; algorithm. Protein: Struct. Funct. Gen. 33, 227--239.]]","journal-title":"Struct. Funct. Gen."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1016\/0022-2836(91)90550-P","article-title":"Prediction of protein side-chain conformation by packing optimization","volume":"217","author":"Lee C.","year":"1991","unstructured":"Lee , C. , and Subbiah , S. 1991 . Prediction of protein side-chain conformation by packing optimization . J. Mol. Biol. 217 , 373 -- 388 .]] Lee, C., and Subbiah, S. 1991. Prediction of protein side-chain conformation by packing optimization. J. Mol. Biol. 217, 373--388.]]","journal-title":"J. Mol. Biol."},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1093\/bioinformatics\/16.12.1105","article-title":"Saturated blast: Detecting distant homology using automated multiple intermediate sequence blast search","volume":"16","author":"Li W.","year":"2000","unstructured":"Li , W. , Pio , F. , Pawlowski , K. , and Godzik , A. 2000 . Saturated blast: Detecting distant homology using automated multiple intermediate sequence blast search . Bioinformatics 16 , 1105 -- 1110 .]] Li, W., Pio, F., Pawlowski, K., and Godzik, A. 2000. Saturated blast: Detecting distant homology using automated multiple intermediate sequence blast search. Bioinformatics 16, 1105--1110.]]","journal-title":"Bioinformatics"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1110\/ps.24902","article-title":"side-chain modelling with an optimized scoring function","volume":"11","author":"Liang S.","year":"2002","unstructured":"Liang , S. , and Grishin , N. 2002 . side-chain modelling with an optimized scoring function . Protein Sci. 11 , 322 -- 331 .]] Liang, S., and Grishin, N. 2002. side-chain modelling with an optimized scoring function. Protein Sci. 11, 322--331.]]","journal-title":"Protein Sci."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/256292.256294"},{"key":"e_1_2_1_29_1","first-page":"S5","article-title":"Critical assessment of methods on protein structure prediction (CASP)-round IV. Proteins","volume":"45","author":"Moult J.","year":"2001","unstructured":"Moult , J. , Fidelis , F. , Zemla , A. , and Hubbard , T. 2001 . Critical assessment of methods on protein structure prediction (CASP)-round IV. Proteins : Struct. Funct. Gen. 45 , S5 (Dec.), 2--7.]] Moult, J., Fidelis, F., Zemla, A., and Hubbard, T. 2001. Critical assessment of methods on protein structure prediction (CASP)-round IV. Proteins: Struct. Funct. Gen. 45, S5 (Dec.), 2--7.]]","journal-title":"Struct. Funct. Gen."},{"key":"e_1_2_1_30_1","first-page":"S6","article-title":"Critical assessment of methods on protein structure prediction (CASP)-round V. Proteins: Struct","volume":"53","author":"Moult J.","year":"2003","unstructured":"Moult , J. , Fidelis , F. , Zemla , A. , and Hubbard , T. 2003 . Critical assessment of methods on protein structure prediction (CASP)-round V. Proteins: Struct ., Funct. Gen. 53 , S6 (Oct.), 334--339.]] Moult, J., Fidelis, F., Zemla, A., and Hubbard, T. 2003. Critical assessment of methods on protein structure prediction (CASP)-round V. Proteins: Struct., Funct. Gen. 53, S6 (Oct.), 334--339.]]","journal-title":"Funct. Gen."},{"key":"e_1_2_1_31_1","first-page":"S3","article-title":"Critical assessment of methods on protein structure prediction (CASP)-round III. Proteins","volume":"37","author":"Moult J.","year":"1999","unstructured":"Moult , J. , Hubbard , T. , Fidelis , F. , and Pedersen , J. 1999 . Critical assessment of methods on protein structure prediction (CASP)-round III. Proteins : Struct. Funct. Gen. 37 , S3 (Dec.), 2--6.]] Moult, J., Hubbard, T., Fidelis, F., and Pedersen, J. 1999. Critical assessment of methods on protein structure prediction (CASP)-round III. Proteins: Struct. Funct. Gen. 37, S3 (Dec.), 2--6.]]","journal-title":"Struct. Funct. Gen."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 2nd CGC Workshop on Computational Geometry.]]","author":"Mount D.","unstructured":"Mount , D. , and Arya , S . 1997. ANN: A library for approximate nearest neighbor searching . In Proceedings of the 2nd CGC Workshop on Computational Geometry.]] Mount, D., and Arya, S. 1997. ANN: A library for approximate nearest neighbor searching. In Proceedings of the 2nd CGC Workshop on Computational Geometry.]]"},{"key":"e_1_2_1_33_1","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 N.","year":"2002","unstructured":"Pierce , N. , and Winfree , E. 2002 . Protein design is NP-hard . Protein Engi. 15 , 10, 779 -- 782 .]] Pierce, N., and Winfree, E. 2002. Protein design is NP-hard. Protein Engi. 15, 10, 779--782.]]","journal-title":"Protein Engi."},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","article-title":"Graph minors. II. Algorithmic aspects of tree-width","volume":"7","author":"Robertson N.","year":"1986","unstructured":"Robertson , N. , and Seymour , P. 1986 . Graph minors. II. Algorithmic aspects of tree-width . J. Algorithms 7 , 309 -- 322 .]] Robertson, N., and Seymour, P. 1986. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7, 309--322.]]","journal-title":"J. Algorithms"},{"key":"e_1_2_1_35_1","article-title":"Comparative protein modelling by satisfaction of spatial restraints","author":"Sali A.","year":"1993","unstructured":"Sali , A. , and Blundell , T. 1993 . Comparative protein modelling by satisfaction of spatial restraints . J. Mol. Biol., 779--815.]] Sali, A., and Blundell, T. 1993. Comparative protein modelling by satisfaction of spatial restraints. J. Mol. Biol., 779--815.]]","journal-title":"J. Mol. Biol., 779--815.]]"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","first-page":"991","DOI":"10.1093\/protein\/11.11.991","article-title":"Determinants of side chain conformational preferences in protein structures","volume":"11","author":"Samudrala R.","year":"1998","unstructured":"Samudrala , R. , and Moult , J. 1998 . Determinants of side chain conformational preferences in protein structures . Protein Engi. 11 , 991 -- 997 .]] Samudrala, R., and Moult, J. 1998. Determinants of side chain conformational preferences in protein structures. Protein Engi. 11, 991--997.]]","journal-title":"Protein Engi."},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1006\/jmbi.2001.4762","article-title":"FUGUE: Sequence-structure homology recognition using environment-specific substitution tables and structure-dependent gap penalties","volume":"310","author":"Shi J.","year":"2001","unstructured":"Shi , J. , Tom , L. B. , and Kenji , M. 2001 . FUGUE: Sequence-structure homology recognition using environment-specific substitution tables and structure-dependent gap penalties . J. Mol. Biol. 310 , 243 -- 257 .]] Shi, J., Tom, L. B., and Kenji, M. 2001. FUGUE: Sequence-structure homology recognition using environment-specific substitution tables and structure-dependent gap penalties. J. Mol. Biol. 310, 243--257.]]","journal-title":"J. Mol. Biol."},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","first-page":"785","DOI":"10.1016\/0022-2836(89)90109-5","article-title":"Construction of side-chains in homology modelling: Application to the c-terminal lobe of rhizopuspepsin","volume":"210","author":"Summers N.","year":"1989","unstructured":"Summers , N. , and Karplus , M. 1989 . Construction of side-chains in homology modelling: Application to the c-terminal lobe of rhizopuspepsin . J. Mol. Biol. 210 , 785 -- 811 .]] Summers, N., and Karplus, M. 1989. Construction of side-chains in homology modelling: Application to the c-terminal lobe of rhizopuspepsin. J. Mol. Biol. 210, 785--811.]]","journal-title":"J. Mol. Biol."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth232"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1006\/jmbi.2001.4865","article-title":"Extending the accuracy limits of prediction for side-chain conformations","volume":"311","author":"Xiang Z.","year":"2001","unstructured":"Xiang , Z. , and Honig , B. 2001 . Extending the accuracy limits of prediction for side-chain conformations . J. Mol. Biol. 311 , 421 -- 430 .]] Xiang, Z., and Honig, B. 2001. Extending the accuracy limits of prediction for side-chain conformations. J. Mol. Biol. 311, 421--430.]]","journal-title":"J. Mol. Biol."},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1142\/S0219720003000186","article-title":"RAPTOR: optimal protein threading by linear programming","volume":"1","author":"Xu J.","year":"2003","unstructured":"Xu , J. , Li , M. , Kim , D. , and Xu , Y. 2003 a. RAPTOR: optimal protein threading by linear programming . Journal of Bioinformatics and Computational Biology 1 , 1, 95 -- 117 .]] Xu, J., Li, M., Kim, D., and Xu, Y. 2003a. RAPTOR: optimal protein threading by linear programming. Journal of Bioinformatics and Computational Biology 1, 1, 95--117.]]","journal-title":"Journal of Bioinformatics and Computational Biology"},{"key":"e_1_2_1_42_1","volume-title":"Biocomputing: Proceedings of the 2003 Pacific Symposium","author":"Xu J.","unstructured":"Xu , J. , Li , M. , Lin , G. , Kim , D. , and Xu , Y . 2003b. Protein threading by linear programming . In Biocomputing: Proceedings of the 2003 Pacific Symposium . Hawaii, USA, 264--275.]] Xu, J., Li, M., Lin, G., Kim, D., and Xu, Y. 2003b. Protein threading by linear programming. In Biocomputing: Proceedings of the 2003 Pacific Symposium. Hawaii, USA, 264--275.]]"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1089\/cmb.1998.5.597","article-title":"An efficient computational method for globally optimal threadings","volume":"5","author":"Xu Y.","year":"1998","unstructured":"Xu , Y. , Xu , D. , and Uberbacher , E. 1998 . An efficient computational method for globally optimal threadings . J. Comput. Biol. 5 , 3, 597 -- 614 .]] Xu, Y., Xu, D., and Uberbacher, E. 1998. An efficient computational method for globally optimal threadings. J. Comput. Biol. 5, 3, 597--614.]]","journal-title":"J. Comput. Biol."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1162349.1162350","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,7]],"date-time":"2024-02-07T18:00:19Z","timestamp":1707328819000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1162349.1162350"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["10.1145\/1162349.1162350"],"URL":"https:\/\/doi.org\/10.1145\/1162349.1162350","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,7]]},"assertion":[{"value":"2006-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}