Biomedical subjects

Ramgopal R Mettu

Publications and source records attributed to Ramgopal R Mettu.

3 recordsLinked to original sources

PubMed2006

A polynomial-time algorithm for de novo protein backbone structure determination from nuclear magnetic resonance data.

We describe an efficient algorithm for protein backbone structure determination from solution Nuclear Magnetic Resonance (NMR) data. A key feature of our algorithm is that it finds the conformation and orientation of secondary structure elements as well as the global fold in polynomial time. This is the first polynomial-time algorithm for de novo high-resolution biomacromolecular structure determination using experimentally recorded data from either NMR spectroscopy or X-ray crystallography. Previous algorithmic formulations of this problem focused on using local distance restraints from NMR (e.g., nuclear Overhauser effect [NOE] restraints) to determine protein structure. This approach has been shown to be NP-hard, essentially due to the local nature of the constraints. In practice, approaches such as molecular dynamics and simulated annealing, which lack both combinatorial precision and guarantees on running time and solution quality, are used routinely for structure determination. We show that residual dipolar coupling (RDC) data, which gives global restraints on the orientation of internuclear bond vectors, can be used in conjunction with very sparse NOE data to obtain a polynomial-time algorithm for structure determination. Furthermore, an implementation of our algorithm has been applied to six different real biological NMR data sets recorded for three proteins. Our algorithm is combinatorially precise, polynomialtime, and uses much less NMR data to produce results that are as good or better than previous approaches in terms of accuracy of the computed structure as well as running time.

Algorithms↗

PubMed2005

High-throughput inference of protein-protein interfaces from unassigned NMR data.

SUMMARY: We cast the problem of identifying protein-protein interfaces, using only unassigned NMR spectra, into a geometric clustering problem. Identifying protein-protein interfaces is critical to understanding inter- and intra-cellular communication, and NMR allows the study of protein interaction in solution. However it is often the case that NMR studies of a protein complex are very time-consuming, mainly due to the bottleneck in assigning the chemical shifts, even if the apo structures of the constituent proteins are known. We study whether it is possible, in a high-throughput manner, to identify the interface region of a protein complex using only unassigned chemical shifts and residual dipolar coupling (RDC) data. We introduce a geometric optimization problem where we must cluster the cells in an arrangement on the boundary of a 3-manifold, where the arrangement is induced by a spherical quadratic form [corrected] The arrangement is induced by a spherical quadratic form, which in turn is parameterized by a SO(3)xR2. We show that this formalism derives directly from the physics of RDCs. We present an optimal algorithm for this problem that runs in O(n3 log n) time for an n-residue protein. We then use this clustering algorithm as a subroutine in a practical algorithm for identifying the interface region of a protein complex from unassigned NMR data. We present the results of our algorithm on NMR data for seven proteins from five protein complexes, and show that our approach is useful for high-throughput applications in which we seek to rapidly identify the interface region of a protein complex. AVAILABILITY: Contact authors for source code.

Algorithms↗

PubMed2005

An algebraic geometry approach to protein structure determination from NMR data.

Our paper describes the first provably-efficient algorithm for determining protein structures de novo, solely from experimental data. We show how the global nature of a certain kind of NMR data provides quantifiable complexity-theoretic benefits, allowing us to classify our algorithm as running in polynomial time. While our algorithm uses NMR data as input, it is the first polynomial-time algorithm to compute high-resolution structures de novo using any experimentally-recorded data, from either NMR spectroscopy or X-Ray crystallography. Improved algorithms for protein structure determination are needed, because currently, the process is expensive and time-consuming. For example, an area of intense research in NMR methodology is automated assignment of nuclear Overhauser effect (NOE) restraints, in which structure determination sits in a tight inner-loop (cycle) of assignment/refinement. These algorithms are very time-consuming, and typically require a large cluster. Thus, algorithms for protein structure determination that are known to run in polynomial time and provide guarantees on solution accuracy are likely to have great impact in the long-term. Methods stemming from a technique called "distance geometry embedding" do come with provable guarantees, but the NP-hardness of these problem formulations implies that in the worst case these techniques cannot run in polynomial time. We are able to avoid the NP-hardness by (a) some mild assumptions about the protein being studied, (b) the use of residual dipolar couplings (RDCs) instead of a dense network of NOEs, and (c) novel algorithms and proofs that exploit the biophysical geometry of (a) and (b), drawing on a variety of computer science, computational geometry, and computational algebra techniques. In our algorithm, RDC data, which gives global restraints on the orientation of internuclear bond vectors, is used in conjunction with very sparse NOE data to obtain a polynomial-time algorithm for protein structure determination. An implementation of our algorithm has been applied to 6 different real biological NMR data sets recorded for 3 proteins. Our algorithm is combinatorially precise, polynomial-time, and uses much less NMR data to produce results that are as good or better than previous approaches in terms of accuracy of the computed structure as well as running time. In practice approaches such as restrained molecular dynamics and simulated annealing, which lack both combinatorial precision and guarantees on running time and solution quality, are commonly used. Our results show that by using a different "slice" of the data, an algorithm that is polynomial time and that has guarantees about solution quality can be obtained. We believe that our techniques can be extended and generalized for other structure-determination problems such as computing side-chain conformations and the structure of nucleic acids from experimental data.

Algorithms↗