{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:33:17Z","timestamp":1773275597104,"version":"3.50.1"},"reference-count":35,"publisher":"Oxford University Press (OUP)","issue":"13","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":3015,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Complementing its traditional role in structural studies of proteins, nuclear magnetic resonance (NMR) spectroscopy is playing an increasingly important role in functional studies. NMR dynamics experiments characterize motions involved in target recognition, ligand binding, etc., while NMR chemical shift perturbation experiments identify and localize protein\u2013protein and protein\u2013ligand interactions. The key bottleneck in these studies is to determine the backbone resonance assignment, which allows spectral peaks to be mapped to specific atoms. This article develops a novel approach to address that bottleneck, exploiting an available X-ray structure or homology model to assign the entire backbone from a set of relatively fast and cheap NMR experiments.<\/jats:p>\n               <jats:p>Results: We formulate contact replacement for resonance assignment as the problem of computing correspondences between a contact graph representing the structure and an NMR graph representing the data; the NMR graph is a significantly corrupted, ambiguous version of the contact graph. We first show that by combining connectivity and amino acid type information, and exploiting the random structure of the noise, one can provably determine unique correspondences in polynomial time with high probability, even in the presence of significant noise (a constant number of noisy edges per vertex). We then detail an efficient randomized algorithm and show that, over a variety of experimental and synthetic datasets, it is robust to typical levels of structural variation (1\u20132 AA), noise (250\u2013600%) and missings (10\u201340%). Our algorithm achieves very good overall assignment accuracy, above 80% in \u03b1-helices, 70% in \u03b2-sheets and 60% in loop regions.<\/jats:p>\n               <jats:p>Availability: Our contact replacement algorithm is implemented in platform-independent Python code. The software can be freely obtained for academic use by request from the authors.<\/jats:p>\n               <jats:p>Contact: \u00a0gopal@cs.purdue.edu; cbk@cs.dartmouth.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/btn167","type":"journal-article","created":{"date-parts":[[2008,6,27]],"date-time":"2008-06-27T07:43:13Z","timestamp":1214552593000},"page":"i205-i213","source":"Crossref","is-referenced-by-count":15,"title":["Contact replacement for NMR resonance assignment"],"prefix":"10.1093","volume":"24","author":[{"given":"Fei","family":"Xiong","sequence":"first","affiliation":[{"name":"1 Department of Computer Science, Dartmouth College, Hanover, NH 03755 and 2Department of Computer Science, Purdue University, West Lafayette, IN 47907,USA"}]},{"given":"Gopal","family":"Pandurangan","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, Dartmouth College, Hanover, NH 03755 and 2Department of Computer Science, Purdue University, West Lafayette, IN 47907,USA"}]},{"given":"Chris","family":"Bailey-Kellogg","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, Dartmouth College, Hanover, NH 03755 and 2Department of Computer Science, Purdue University, West Lafayette, IN 47907,USA"}]}],"member":"286","published-online":{"date-parts":[[2008,7,1]]},"reference":[{"key":"2023020210372922400_B1","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1089\/106652700750050934","article-title":"The NOESY jigsaw: automated protein secondary structure and main-chain assignment from sparse, unassigned NMR data","volume":"7","author":"Bailey-Kellogg","year":"2000","journal-title":"J. Comp. Biol"},{"key":"2023020210372922400_B2","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1089\/cmb.2005.12.569","article-title":"A random graph approach to NMR sequential assignment","volume":"12","author":"Bailey-Kellogg","year":"2005","journal-title":"J. Comp. Biol"},{"key":"2023020210372922400_B3","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1002\/(SICI)1096-987X(19970115)18:1<139::AID-JCC13>3.0.CO;2-H","article-title":"Garant\u2014 a general algorithm for resonance assignment of multidimensional nuclear magnetic resonance spectra","volume":"18","author":"Bartels","year":"1997","journal-title":"J. Comp. Chem"},{"key":"2023020210372922400_B4","first-page":"1","article-title":"Approximating longest directed path","volume":"32","author":"Bjorklund","year":"2003","journal-title":"Electron. Colloq. Comput. Complex."},{"key":"2023020210372922400_B5","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"Bollobas","year":"2001"},{"key":"2023020210372922400_B6","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1021\/bi00052a006","article-title":"Mapping of the binding interfaces of the proteins of the bacterial phosphotransferase system, HPr and IIAglc","volume":"32","author":"Chen","year":"1993","journal-title":"Biochemistry"},{"key":"2023020210372922400_B7","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1023\/A:1008335423527","article-title":"Completeness of NOEs in protein structures: a statistical analysis of NMR data","volume":"14","author":"Doreleijers","year":"1999","journal-title":"J. Biomol. NMR"},{"key":"2023020210372922400_B8","article-title":"Rapid protein structure detection and assignment using residual dipolar couplings","volume-title":"Technical Report CMU-CS-02-195","author":"Erdmann","year":"2002"},{"key":"2023020210372922400_B9","first-page":"166","article-title":"Finding large cycles in hamiltonian graphs","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Feder","year":"2005"},{"key":"2023020210372922400_B10","doi-asserted-by":"crossref","first-page":"1596","DOI":"10.1137\/S0097539701395486","article-title":"Approximating the longest cycle problem in sparse graphs","volume":"31","author":"Feder","year":"2002","journal-title":"SIAM J. Comput"},{"key":"2023020210372922400_B11","first-page":"407","article-title":"Finding paths and cycles of superpolylogarithmic length","volume-title":"Proceedings of the 36th ACM Symposium on the Theory of Computing (STOC)","author":"Gabow","year":"2004"},{"key":"2023020210372922400_B12","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1137\/0205049","article-title":"The planar hamiltonian circuit problem is NP-complete","volume":"5","author":"Garey","year":"1976","journal-title":"SIAM J. Comput"},{"key":"2023020210372922400_B13","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1023\/A:1008318805889","article-title":"Sequence-specific NMR assignment of proteins by global fragment mapping with program Mapper","volume":"17","author":"G\u00fcntert","year":"2000","journal-title":"J. Biomol. NMR"},{"key":"2023020210372922400_B14","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1126\/science.278.5337.497","article-title":"Drug design: discovering high-affinity ligands for proteins","volume":"278","author":"Hajduk","year":"1997","journal-title":"Science"},{"key":"2023020210372922400_B15","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1023\/B:JNMR.0000042954.99056.ad","article-title":"MARS - robust automatic backbone assignment of proteins","volume":"30","author":"Jung","year":"2004","journal-title":"J. Biomol. NMR"},{"key":"2023020210372922400_B16","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1093\/bioinformatics\/bti786","article-title":"An efficient randomized algorithm for contact-based NMR backbone resonance assignment","volume":"22","author":"Kamisetty","year":"2006","journal-title":"Bioinformatics"},{"key":"2023020210372922400_B17","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1038\/755","article-title":"Protein dynamics from NMR","volume":"5","author":"Kay","year":"1998","journal-title":"Nat. Struct. Biol"},{"key":"2023020210372922400_B18","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1023\/B:JNMR.0000019247.89110.e6","article-title":"An expectation\/maximization nuclear vector replacement algorithm for automated NMR resonance assignments","volume":"29","author":"Langmead","year":"2004","journal-title":"J. Biomol. NMR"},{"key":"2023020210372922400_B19","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1089\/1066527041410436","article-title":"A polynomial-time nuclear vector replacement algorithm for automated NMR resonance assignments","volume":"11","author":"Langmead","year":"2004","journal-title":"J. Comp. Biol"},{"key":"2023020210372922400_B20","first-page":"165","article-title":"An efficient branch-and-bound algorithm for assignment of protein backbone NMR peaks","volume-title":"Proceedings of the Computer Society Conference on Bioinformatics","author":"Lin","year":"2002"},{"key":"2023020210372922400_B21","doi-asserted-by":"crossref","first-page":"982","DOI":"10.1038\/80768","article-title":"Protein NMR spectroscopy in structural genomics","volume":"7","author":"Montelione","year":"2000","journal-title":"Nat. Struct. Biol"},{"key":"2023020210372922400_B22","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1016\/S0959-440X(99)00019-6","article-title":"Automated analysis of NMR assignments and structures for proteins","volume":"9","author":"Moseley","year":"1999","journal-title":"Curr. Opin. Struct. Biol"},{"key":"2023020210372922400_B23","doi-asserted-by":"crossref","first-page":"13293","DOI":"10.1021\/jp9606117","article-title":"Nuclear magnetic resonance studies of biopolymer dynamics","volume":"100","author":"Palmer III","year":"1996","journal-title":"J. Phys. Chem"},{"key":"2023020210372922400_B24","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/j.ipl.2005.04.001","article-title":"On a simple randomized algorithm for finding a 2-factor in sparse graphs","volume":"95","author":"Pandurangan","year":"2005","journal-title":"Inform. Process. Lett."},{"key":"2023020210372922400_B25","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0020-0190(79)90023-1","article-title":"The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two","volume":"8","author":"Plesnik","year":"1979","journal-title":"Inform. Process. Lett."},{"key":"2023020210372922400_B26","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1023\/A:1008338605320","article-title":"RESCUE: an artificial neural network tool for the NMR spectral assignment of proteins","volume":"15","author":"Pons","year":"1999","journal-title":"J. Biomol. NMR"},{"key":"2023020210372922400_B27","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1002\/jcc.10011","article-title":"Semiautomatic sequence-specific assignment of proteins based on the tertiary structure\u2013the program ST2NMR","volume":"23","author":"Pristovek","year":"2002","journal-title":"J. Comp. Chem"},{"key":"2023020210372922400_B28","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1107\/S0365110X62000067","article-title":"The detection of sub-units within the crystallographic asymmetric unit","volume":"15","author":"Rossman","year":"1962","journal-title":"Acta. Cryst"},{"key":"2023020210372922400_B29","doi-asserted-by":"crossref","first-page":"1531","DOI":"10.1126\/science.274.5292.1531","article-title":"Discovering high-affinity ligands for proteins: SAR by NMR","volume":"274","author":"Shuker","year":"1996","journal-title":"Science"},{"key":"2023020210372922400_B30","first-page":"Article 6, 1","article-title":"Model-based assignment and inference of protein backbone nuclear magnetic resonances","volume":"3","author":"Vitek","year":"2004","journal-title":"Stat. Appli. Gene. Mol. Biol."},{"key":"2023020210372922400_B31","doi-asserted-by":"crossref","first-page":"ii230","DOI":"10.1093\/bioinformatics\/bti1138","article-title":"Reconsidering complete search algorithms for protein backbone NMR assignment","volume":"21","author":"Vitek","year":"2005","journal-title":"Bioinformatics"},{"key":"2023020210372922400_B32","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/s10858-006-9027-8","article-title":"Inferential backbone assignment for sparse data","volume":"35","author":"Vitek","year":"2006","journal-title":"J. Biomol. NMR"},{"key":"2023020210372922400_B33","first-page":"403","article-title":"A hierarchical grow-and-match algorithm for backbone resonance assignments given 3D structure","volume-title":"Proceedings of IEEE Bioinformatics and Bioengineering","author":"Xiong","year":"2007"},{"key":"2023020210372922400_B34","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1145\/332306.332568","article-title":"Protein structure determination using protein threading and sparse NMR data","volume-title":"Proceedings of the Fourth Annual International Conference on Computational Molecular Biology","author":"Xu","year":"2000"},{"key":"2023020210372922400_B35","doi-asserted-by":"crossref","first-page":"592","DOI":"10.1006\/jmbi.1997.1052","article-title":"Automated analysis of protein NMR assignments using methods from artificial intelligence","volume":"269","author":"Zimmerman","year":"1997","journal-title":"J. Mol. Biol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/13\/i205\/49053272\/bioinformatics_24_13_i205.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/13\/i205\/49053272\/bioinformatics_24_13_i205.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T12:16:41Z","timestamp":1675340201000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/24\/13\/i205\/232868"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7,1]]},"references-count":35,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2008,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btn167","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2008,7,1]]},"published":{"date-parts":[[2008,7,1]]}}}