Large a polynomial-time nuclear vector replacement algorithm for automated NMR resonance assignments

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Large a polynomial-time nuclear vector replacement algorithm for automated NMR resonance assignments

Full text

Pdf (2.14 MB)

Source

Annual Conference on Research in Computational Molecular Biology archive
Proceedings of the seventh annual international conference on Research in computational molecular biology table of contents

Berlin, Germany

Pages: 176 - 187

Year of Publication: 2003

ISBN:1-58113-635-8

Authors

Christopher James Langmead	Dartmouth University, Hanover, NH
Anthony Yan	Dartmouth University, Hanover, NH
Ryan Lilien	Dartmouth University, Hanover, NH
Lincong Wang	Dartmouth University, Hanover, NH
Bruce Randall Donald	Dartmouth University, Hanover, NH

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 21, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/640075.640098 What is a DOI?

ABSTRACT

High-throughput NMR structural biology can play an important role in structural genomics. We report an automated procedure for high-throughput NMR resonance assignment for a protein of known structure, or of an homologous structure. These assignments are a prerequisite for probing protein-protein interactions, protein-ligand binding, and dynamics by NMR. Assignments are also the starting point for structure determination and refinement. A new algorithm, called Nuclear Vector Replacement (NVR) is introduced to compute assignments that optimally correlate experimentally-measured NH residual dipolar couplings (RDCs) to a given a priori whole-protein 3D structural model. The algorithm requires only uniform ¹⁵N-labelling of the protein, and processes unassigned H^N-¹⁵N HSQC spectra, H^N-¹⁵N RDCs, and sparse H^N-H^N NOE's dNNs), all of which can be acquired in a fraction of the time needed to record the traditional suite of experiments used to perform resonance assignments. NVR runs in minutes and efficiently assigns the (H^N,¹⁵N) backbone resonances as well as the dNNs of the 3D \nfif-NOESY spectrum, in O(n³) time. The algorithm is demonstrated on NMR data from a 76-residue protein, human ubiquitin, matched to four structures, including one mutant (homolog), determined either by X-ray crystallography or by different NMR experiments (without RDCs). NVR achieves an average assignment accuracy of over 90%. We further demonstrate the feasibility of our algorithm for different and larger proteins, using NMR data for hen lysozyme (129 residues, 98% accuracy) and streptococcal protein G (56 residues, 95% accuracy), matched to a variety of 3D structural models. Finally, we extend NVR to a second application, 3D structural homology detection, and demonstrate that NVR is able to identify structural homologies between proteins with remote amino acid sequences using a database of structural models.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Al-Hashimi, H.M. and Gorin, A. and Majumdar, A. and Gosser, Y. and Patel, D.J. Towards Structural Genomics of RNA: Rapid NMR Resonance Assignment and Simultaneous RNA Tertiary Structure Determination Using Residual Dipolar Couplings. J. Mol. Biol. 318 (2002), 637--649.
	2	Altschul, S.F. and Gish, W. and Miller, W. and Myers, E.W. and Lipman, D.J. Basic local alignment search tool. J. Mol. Biol. 215 (1990), 403--410.
	3	Andrec, M. and Du, P. and Levy, R.M. Protein backbone structure determination using only residual dipolar couplings from one ordering medium. J Biomol NMR 21, 4 (2001), 335--347.
	4	Annila, A. and Aitio, H. and Thulin, E. and Drakenberg. T. Recognition of protein folds via dipolar couplings. J. Biom. NMR 14 (1999), 223--230.
	5	Artymiuk, P. J. and Blake, C. C. F. and Rice, D. W. and Wilson, K. S. The Structures of the Monoclinic and Orthorhombic Forms of Hen Egg-White Lysozyme at 6 Angstroms Resolution. Acta Crystallogr B Biol Crystallogr 38 (1982), 778.
	6	Babu, C. R. and Flynn, P. F. and Wand, A. J. Validation of Protein Structure from Preparations of Encapsulated Proteins Dissolved in Low Viscosity Fluids. J.Am.Chem.Soc. 123 (2001), 2691.
	7	Bailey-Kellogg, C. and Widge, A. and Kelley III, J.J. and Berardi, M.J. and Bushweller, J.H. and Donald, B.R. The NOESY Jigsaw: automated protein secondary structure and main-chain assignment from sparse, unassigned NMR data. J Comput Biol 7, 3-4 (2000), 537--58.
	8	Saugata Basu, An Improved Algorithm for Quantifier Elimination Over Real Closed Fields, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.56, October 19-22, 1997
	9	Saugata Basu , Richard Pollack , Marie-Françoise Roy, On the combinatorial and algebraic complexity of quantifier elimination, Journal of the ACM (JACM), v.43 n.6, p.1002-1045, Nov. 1996 [doi>10.1145/235809.235813]
	10	Berman, H.M and Westbrook, J. and Feng, Z. and Gilliland, G. and Bhat, T.N. and Weissig, H. and Shindyalov, I.N. and Bourne, P.E. The Protein Data Bank. Nucl. Acids Res. 28 (2000), 235--242.
	11	Blundell, T.L. and Sibanda, B.L. and Sternberg, M.J. and Thornton, J.M. Knowledge-Based Prediction of Protein Structures and the Design of Novel Molecules. Nature 326 (1987), 347--352.
	12	Chen, Y. and Reizer, J. and Saier Jr., M. H. and Fairbrother, W. J. and Wright, P. E. Mapping of the binding interfaces of the proteins of the bacterial phosphotransferase system, HPr and IIAglc. Biochemistry 32, 1 (1993), 32--37.
	13	Chou, J.J and Gaemers, S. and Howder, B. and Louis, J.M. and Bax, A. A simple apparatus for generating stretched polyacrylamide gels, yielding uniform alignment of proteins and detergent micelles. J. Biom. NMR 21, 4 (2001), 377--82.
	14	Chou, J.J and Li, S. and Bax, A. Study of conformational rearrangement and refinement of structural homology models by the use of heteronuclear dipolar couplings. J. Biom. NMR 18 (2000), 217--227.
	15	Cornilescu, G. and Marquardt, J. L. and Ottiger, M. and Bax, A. Validation of Protein Structure from Anisotropic Carbonyl Chemical Shifts in a Dilute Liquid Crystalline Phase. J.Am.Chem.Soc. 120 (1998), 6836--6837.
	16	Cuff, J.A. and Clamp, M.E. and Siddiqui, A.S. and Finlay, M. and Barton, G.J. Jpred: A Consensus Secondary Structure Prediction Server. Bioinformatics 14 (1998), 892--893.
	17	Delaglio, F. and Kontaxis, G. and Bax, A. Protein structure determination using molecular fragment replacement and NMR dipolar couplings. J. Am. Chem. Soc 122 (2000), 2142--2143.
	18	Diamond, R. Real-space refinement of the structure of hen egg-white lysozyme. J Mol. Biol. 82 (1974), 371--391.
	19	Fejzo, J. and Lepre, C.A. and Peng, J.W. and Bemis, G.W. and Ajay and Murcko, M.A. and Moore, J.M. The SHAPES strategy: An NMR-based approach for lead generation in drug discovery. Chem. and Biol. 6 (1999), 755--769.
	20	Fetrow, J.S. and Bryant, S.H. New Programs for Protein Tertiary Structure Prediction. Bio/Technology 11 (1993), 479--484.
	21	Fiaux, J. and Bertelsen, E. B. and Horwich, A. L. and Wuthrich, K. NMR analysis of a 900K GroEL-GroES complex. Nature 418 (2002), 207--211.
	22	Fowler, C.A. and Tian, F. and Al-Hashimi, H. M. and Prestegard, J. H. Rapid Determination of Protein Folds Using Residual Dipolar Couplings. J. Mol. Bio 304, 3 (2000), 447--460.
	23	Gallagher, T. and Alexander, P. and Bryan, P. and Gilliland, G. L. Two crystal structures of the B1 immunoglobulin-binding domain of streptococcal protein G and comparison with NMR. Biochemistry 33 (1994), 4721--4729.
	24	Girard, E. and Chantalat, L. and Vicat, J. and Kahn, R. Gd-HPDO3A, a Complex to Obtain High-Phasing-Power Heavy Atom Derivatives for SAD and MAD Experiments: Results with Tetragonal Hen Egg-White Lysozyme. Acta Crystallogr D Biol Crystallogr. 58 (2001), 1--9.
	25	Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
	26	Greer, J. Comparative Modeling of Homologous Proteins. . Meth. Enzymol. 202 (1991), 239--252.
	27	D. Yu. Grigor'ev, Complexity of deciding Tarski algebra, Journal of Symbolic Computation, v.5 n.1-2, p.65-108, February/April 1988 [doi>10.1016/S0747-7171(88)80006-3]
	28	D. Yu. Grigor'ev , N. N. Vorobjov, Solving systems of polynomial inequalities in subexponential time, Journal of Symbolic Computation, v.5 n.1-2, p.37-64, February/April 1988 [doi>10.1016/S0747-7171(88)80005-1]
	29	Gronenborn, A. M. and Filpula, D. R. and Essig, N. Z. and Achari, A. and Whitlow, M. and Wingfield, P. T. and Clore, G. M. A novel, highly stable fold of the immunoglobulin binding domain of streptococcal protein G. Science 253 (1991), 657.
	30	Harris, R. The Ubiquitin NMR Resource Page. BBSRC Bloomsbury Center for Structural Biology http://www.biochem.ucl.ac.uk/bsm/nmr/ubq/index.html, 2002.
	31	Hus, J.C. and Marion, D. and Blackledge, M. De novo Determination of Protein Structure by NMR using Orientational and Long-range Order Restraints. J. Mol. Bio 298, 5 (2000), 927--936.
	32	Hus, J.C. and Propmers, J. and Bruschweiler, R. Assignment strategy for proteins of known structure. J. Mag. Res 157 (2002), 119--125.
	33	Hus, J.C. and Propmers, J. and Bruschweiler, R. Assignment strategy for proteins of known structure. J. Mag. Res 157 (2002), 119--125.
	34	Johnson, M.S. and Srinivasan, N. and Sowdhamini, R. and Blundell, T.L. Knowledge-Based Protein Modeling. Mol. Biochem. 29 (1994), 1--68.
	35	Kuhn, H.W. Hungarian method for the assignment problem. Nav. Res. Logist. Quarterly 2 (1955), 83--97.
	36	Kullback, S. and Leibler, R. A. On Information and Sufficiency. Annals of Math. Stats. 22 (1951), 79--86.
	37	Kurinov, I. V. and Harrison, R. W. The influence of temperature on lysozyme crystals - structure and dynamics of protein and water. Acta Crystallogr D Biol Crystallogr 51 (1995), 98--109.
	38	Kuszewski, J. and Gronenborn, A. M. and Clore, G. M. Improving the Packing and Accuracy of NMR Structures with a Pseudopotential for the Radius of Gyration. J. Am. Chem. Soc. 121 (1999), 2337--2338.
	39	Lathrop, R.H. and Smith, T.F. Global Optimum Protein Threading with Gapped Alignment and Empirical Pair Score Functions. J. Mol. Biol. 255 (1996), 641--665.
	40	Lim, K. and Nadarajah, A. and Forsythe, E. L. and Pusey, M. L. Locations of bromide ions in tetragonal lysozyme crystals. Acta Crystallogr D Biol Crystallogr. 54 (1998), 899--904.
	41	Losonczi, J.A. and Andrec, M. and Fischer, W.F. and Prestegard J.H. Order matrix analysis of residual dipolar couplings using singular value decomposition. J Magn Reson 138, 2 (1999), 334--42.
	42	Meiler, J. and Peti, W. and Griesinger, C. DipoCoup: A versatile program for 3D-structure homology comparison based on residual dipolar couplings and pseudocontact shifts. J. Biom. NMR 17 (2000), 283--294.
	43	Mueller, G.A. and Choy, W.Y. and Yang, D. and Forman-Kay, J.D. and Venters, R.A. and Kay, L.E. Global Folds of Proteins with Low Densities of NOEs Using Residual Dipolar Couplings: Application to the 370-Residue Maltodextrin-binding Protein. J. Mol. Biol. 300 (2000), 197--212.
	44	National Institute of General Medical Sciences. The Protein Structure Initiative. The National Institute of General Medical Sciences, 2002. URL: http://www.nigms.nih.gov/funding/psi.html.
	45	Oki, H. and Matsuura, Y. and Komatsu, H. and Chernov, A. A. Refined structure of orthorhombic lysozyme crystallized at high temperature: correlation between morphology and intermolecular contacts. Acta Crystallogr D Biol Crystallogr. 55 (1999), 114.
	46	Osapay, K. and Case,D.A. A new analysis of proton chemical shifts in proteins. J. Am. Chem. Soc. 113 (1991), 9436--9444.
	47	Palmer III, A. G. Probing Molecular Motion By NMR. Current Opinion in Structural Biology 7 (1997), 732--737.
	48	Pearlman, D.A. and Case, D.A. and Caldwell, J.W. and Ross, W.S. and Cheatham, T.E. and DeBolt, S. and Ferguson, D. and Seibel, G. and Kollman, P. AMBER, a package of computer programs for applying molecular mechanics, normal mode analysis, molecular dynamics and free energy calculations to simulate the structures and energies of molecules. Comp. Phy. Comm. 91 (1995), 1--41.
	49	Ramage, R. and Green, J. and Muir, T. W. and Ogunjobi, O. M. and Love, S. and Shaw, K. Synthetic, structural and biological studies of the ubiquitin system: the total chemical synthesis of ubiquitin. J. Biochem 299 (1994), 151--158.
	50	Ramirez, B.E. and Bax, A. Modulation of the alignment tensor of macromolecules dissolved in a dilute liquid crystalline medium. J. Am. Chem. Soc. 120 (1998), 9106--9107.
	51	Rohl, C.A and Baker, D. De Novo Determination of Protein Backbone Structure from Residual Dipolar Couplings Using Rosetta. J. Am. Chem. Soc. 124, 11 (2002), 2723--2729.
	52	Rossman, M.G. and Blow, D.M. The detection of sub-units within the crystallographic asymmetric unit. Acta Crystallogr 15 (1962), 24--31.
	53	Sali, A. and Overington, J.P. and Johnson, M.S. and Blundell, T.L. From Comparisons of Protein Sequences and Structures to Protein Modelling and Design. Trends Biochem. Sci. 15 (1990), 235--240.
	54	Saupe, A. Recent Results in the field of liquid crystals. Angew. Chem. 7 (1968), 97--112.
	55	Schneider, D.M. and Dellwo, M.J. and Wand, A. J. Fast Internal Main-Chain Dynamics of Human Ubiquitin. Biochemistry 31, 14 (1992), 3645--3652.
	56	Schwalbe, H. and Grimshaw, S. B. and Spencer, A. and Buck, M. and Boyd, J. and Dobson, C. M. and Redfield, C. and Smith, L. J. A Refined Solution Structure of Hen Lysozyme Determined Using Residual Dipolar Coupling Data. Protein Sci. 10 (2001), 677--688.
	57	Shuker, S. B. and Hajduk, P. J. and Meadows, R. P. and Fesik, S. W. Discovering high affinity ligands for proteins: SAR by NMR. Science 274 (1996), 1531--1534.
	58	Tian, F. and Valafar, H. and Prestegard, J. H. A Dipolar Coupling Based Strategy for Simultaneous Resonance Assignment and Structure Determination of Protein Backbones. J. Am. Chem. Soc. 123 (2001), 11791--11796.
	59	Tjandra, N. and Bax, A. Direct Measurement of Distances and Angles in Biomolecules by NMR in a Dilute Liquid Crystalline Medium. Science 278 (1997), 1111--1114.
	60	Vaney, M. C. and Maignan, S. and Ries-Kautt, M. and Ducruix, A. High-resolution structure (1.33 angstrom) of a HEW lysozyme tetragonal crystal grown in the APCF apparatus. Data and structural comparison with a crystal grown under microgravity from SpaceHab-01 mission. Acta Crystallogr D Biol Crystallogr 52 (1996), 505--517.
	61	Vijay-Kumar, S. and Bugg, C. E. and Cook, W. J. Structure of ubiquitin refined at 1.8 A resolution. J Mol. Biol. 194 (1987), 531--544.
	62	Weber, P. L. and Brown, S. C. and Mueller, L. Sequential 1H NMR Assignments and Secondary Structure Identification of Human Ubiquitin. Biochemistry 26 (1987), 7282--7290.
	63	Wedemeyer, W. J. and Rohl, C. A. and Scheraga, H. A. Exact solutions for chemical bond orientations from residual dipolar couplings. J. Biom. NMR 22 (2002), 137--151.
	64	Wishart, D.S. and Watson, M.S. and Boyko, R.F. and Sykes, B.D. Automated 1H and 13C Chemical Shift Prediction Using the BioMagResBank. J.Biomol. NMR 10 (1997), 329--336.
	65	Wuthrich, K. Protein recognition by NMR. Nat. Struct. Biol 7, 3 (2000), 188--189.
	66	Ying Xu , Dong Xu , Oakley H. Crawford , J. Ralph Einstein , Engin Serpersu, Protein structure determination using protein threading and sparse NMR data (extended abstract), Proceedings of the fourth annual international conference on Computational molecular biology, p.299-307, April 2000, Tokyo, Japan [doi>10.1145/332306.332568]
	67	Zweckstetter, M. and Bax, A. Single-step determination of protein substructures using dipolar couplings: aid to structural genomics. J Am Chem Soc 123, 38 (2001), 9490--1.

CITED BY 2

	Michael A. Erdmann, Protein similarity from knot theory and geometric convolution, Proceedings of the eighth annual international conference on Resaerch in computational molecular biology, p.195-204, March 27-31, 2004, San Diego, California, USA
	Xiang Wan , Guohui Lin, CISA: Combined NMR Resonance Connectivity Information Determination and Sequential Assignment, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.4 n.3, p.336-348, July 2007