Protein NMR structure determination with automated NOE assignment using the new software CANDID and the torsion angle dynamics algorithm DYANA

Combined automated NOE assignment and structure determination module (CANDID) is a new software for efficient NMR structure determination of proteins by automated assignment of the NOESY spectra. CANDID uses an iterative approach with multiple cycles of NOE cross-peak assignment and protein structure calculation using the fast DYANA torsion angle dynamics algorithm, so that the result from each CANDID cycle consists of exhaustive, possibly ambiguous NOE cross-peak assignments in all available spectra and a three-dimensional protein structure represented by a bundle of conformers. The input for the first CANDID cycle consists of the amino acid sequence, the chemical shift list from the sequence-specific resonance assignment, and listings of the cross-peak positions and volumes in one or several two, three or four-dimensional NOESY spectra. The input for the second and subsequent CANDID cycles contains the three-dimensional protein structure from the previous cycle, in addition to the complete input used for the first cycle. CANDID includes two new elements that make it robust with respect to the presence of artifacts in the input data, i.e. network-anchoring and constraint-combination, which have a key role in de novo protein structure determinations for the successful generation of the correct polypeptide fold by the first CANDID cycle. Network-anchoring makes use of the fact that any network of correct NOE cross-peak assignments forms a self-consistent set; the initial, chemical shift-based assignments for each individual NOE cross-peak are therefore weighted by the extent to which they can be embedded into the network formed by all other NOE cross-peak assignments. Constraint-combination reduces the deleterious impact of artifact NOE upper distance constraints in the input for a protein structure calculation by combining the assignments for two or several peaks into a single upper limit distance constraint, which lowers the probability that the presence of an artifact peak will influence the outcome of the structure calculation. CANDID test calculations were performed with NMR data sets of four proteins for which high-quality structures had previously been solved by interactive protocols, and they yielded comparable results to these reference structure determinations with regard to both the residual constraint violations, and the precision and accuracy of the atomic coordinates. The CANDID approach has further been validated by de novo NMR structure determinations of four additional proteins. The experience gained in these calculations shows that once nearly complete sequence-specific resonance assignments are available, the automated CANDID approach results in greatly enhanced efficiency of the NOESY spectral analysis. The fact that the correct fold is obtained in cycle 1 of a de novo structure calculation is the single most important advance achieved with CANDID, when compared with previously proposed automated NOESY assignment methods that do not use network-anchoring and constraint-combination.     

Automated combined assignment of NOESY spectra and three-dimensional protein structure determination

A procedure for automated protein structure determination is presented that is based on an iterative procedure during which the NOESY peak list assignment and the structure calculation are performed simultaneously. The input consists of a list of NOESY peak positions and a list of chemical shifts as obtained from sequence-specific resonance assignment. For the present applications of this approach the previously introduced NOAH routine was implemented in the distance geometry program DIANA. As an illustration, experimental 2D and 3D NOESY cross-peak lists of six proteins have been analyzed, for which complete sequence-specific ¹H assignments are available for the polypeptide backbone and the amino acid side chains. The automated method assigned 70–90% of all NOESY cross peaks, which is on average 10% less than with the interactive approach, and only between 0.8% and 2.4% of the automatically assigned peaks had a different assignment than in the corresponding manually assigned peak lists. The structures obtained with NOAH/DIANA are in close agreement with those from manually assigned peak lists, and with both approaches the residual constraint violations correspond to high-quality NMR structure determinations. Systematic comparisons of the bundles of conformers that represent corresponding automatically and interactively determined structures document the absence of significant bias in either approach, indicating that an important step has been made towards automation of structure determination from NMR spectra.     

Computational assignment of protein backbone NMR peaks by efficient bounding and filtering

NMR resonance assignment is one of the key steps in solving an NMR protein structure. The assignment process links resonance peaks to individual residues of the target protein sequence, providing the prerequisite for establishing intra- and inter-residue spatial relationships between atoms. The assignment process is tedious and time-consuming, which could take many weeks. Though there exist a number of computer programs to assist the assignment process, many NMR labs are still doing the assignments manually to ensure quality. This paper presents a new computational method based on the combination of a suite of algorithms for automating the assignment process, particularly the process of backbone resonance peak assignment. We formulate the assignment problem as a constrained weighted bipartite matching problem. While the problem, in the most general situation, is NP-hard, we present an efficient solution based on a branch-and-bound algorithm with effective bounding techniques using two recently introduced approximation algorithms. We also devise a greedy filtering algorithm for reducing the search space. Our experimental results on 70 instances of (pseudo) real NMR data derived from 14 proteins demonstrate that the new solution runs much faster than a recently introduced (exhaustive) two-layer algorithm and recovers more correct peak assignments than the two-layer algorithm. Our result demonstrates that integrating different algorithms can achieve a good tradeoff between backbone assignment accuracy and computation time.     

Reliability of exclusively NOESY-based automated resonance assignment and structure determination of proteins

Protein structure determination by NMR can in principle be speeded up both by reducing the measurement time on the NMR spectrometer and by a more efficient analysis of the spectra. Here we study the reliability of protein structure determination based on a single type of spectra, namely nuclear Overhauser effect spectroscopy (NOESY), using a fully automated procedure for the sequence-specific resonance assignment with the recently introduced FLYA algorithm, followed by combined automated NOE distance restraint assignment and structure calculation with CYANA. This NOESY-FLYA method was applied to eight proteins with 63–160 residues for which resonance assignments and solution structures had previously been determined by the Northeast Structural Genomics Consortium (NESG), and unrefined and refined NOESY data sets have been made available for the Critical Assessment of Automated Structure Determination of Proteins by NMR project. Using only peak lists from three-dimensional ¹³C- or ¹⁵N-resolved NOESY spectra as input, the FLYA algorithm yielded for the eight proteins 91–98 % correct backbone and side-chain assignments if manually refined peak lists are used, and 64–96 % correct assignments based on raw peak lists. Subsequent structure calculations with CYANA then produced structures with root-mean-square deviation (RMSD) values to the manually determined reference structures of 0.8–2.0 Å if refined peak lists are used. With raw peak lists, calculations for 4 proteins converged resulting in RMSDs to the reference structure of 0.8–2.8 Å, whereas no convergence was obtained for the four other proteins (two of which did already not converge with the correct manual resonance assignments given as input). These results show that, given high-quality experimental NOESY peak lists, the chemical shift assignments can be uncovered, without any recourse to traditional through-bond type assignment experiments, to an extent that is sufficient for calculating accurate three-dimensional structures.     

Influence of the completeness of chemical shift assignments on NMR structures obtained with automated NOE assignment

Reliable automated NOE assignment and structure calculation on the basis of a largely complete, assigned input chemical shift list and a list of unassigned NOESY cross peaks has recently become feasible for routine NMR protein structure calculation and has been shown to yield results that are equivalent to those of the conventional, manual approach. However, these algorithms rely on the availability of a virtually complete list of the chemical shifts. This paper investigates the influence of incomplete chemical shift assignments on the reliability of NMR structures obtained with automated NOESY cross peak assignment. The program CYANA was used for combined automated NOESY assignment with the CANDID algorithm and structure calculations with torsion angle dynamics at various degrees of completeness of the chemical shift assignment which was simulated by random omission of entries in the experimental ¹H chemical shift lists that had been used for the earlier, conventional structure determinations of two proteins. Sets of structure calculations were performed choosing the omitted chemical shifts randomly among all assigned hydrogen atoms, or among aromatic hydrogen atoms. For comparison, automated NOESY assignment and structure calculations were performed with the complete experimental chemical shift but under random omission of NOESY cross peaks. When heteronuclear-resolved three-dimensional NOESY spectra are available the current CANDID algorithm yields in the absence of up to about 10% of the experimental ¹H chemical shifts reliable NOE assignments and three-dimensional structures that deviate by less than 2 Å from the reference structure obtained using all experimental chemical shift assignments. In contrast, the algorithm can accommodate the omission of up to 50% of the cross peaks in heteronuclear- resolved NOESY spectra without producing structures with a RMSD of more than 2 Å to the reference structure. When only homonuclear NOESY spectra are available, the algorithm is slightly more susceptible to missing data and can tolerate the absence of up to about 7% of the experimental ¹H chemical shifts or of up to 30% of the NOESY peaks.Abbreviations: BmPBP^A – Bombyx mori pheromone binding protein form A; CYANA – combined assignment and dynamics algorithm for NMR applications; NMR – nuclear magnetic resonance; NOE – nuclear Overhauser effect; NOESY – NOE spectroscopy; RMSD – root-mean-square deviation; WmKT – Williopsis mrakii killer toxin     

RNA tertiary structure determination: NOE pathways construction by tabu search

MOTIVATION: Liquid state nuclear magnetic resonance (NMR) spectroscopy has now been well established as a method for RNA tertiary structure determination. Most of the steps involved in the determination of RNA molecules are performed using computer programs. They however, do not apply to resonance assignment being the starting point of the whole procedure. We propose a tabu search algorithm as a tool for automating this step. Nuclear overhause effect (NOE) pathway, which determines the assignment, is constructed during an analysis of possible connections between resonances within aromatic/anomeric region of two-dimensional NOESY spectrum resulting from appropriate NMR experiment. RESULTS: Computational tests demonstrate the superior performance of the tabu search algorithm as compared with the exact enumerative approach and genetic procedure applied to the experimental and simulated spectral data for RNA molecules. AVAILABILITY: The software package can be obtained upon request from Marta Szachniuk.     

An automated assignment-free Bayesian approach for accurately identifying proton contacts from NOESY data

The identification of proton contacts from NOE spectra remains the major bottleneck in NMR protein structure calculations. We describe an automated assignment-free system for deriving proton contact probabilities from NOESY peak lists that can be viewed as a quantitative extension of manual assignment techniques. Rather than assigning contacts to NOESY crosspeaks, a rigorous Bayesian methodology is used to transform initial proton contact probabilities derived from a set of 2992 protein structures into posterior probabilities using the observed crosspeaks as evidence. Given a target protein, the Bayesian approach is used to derive probabilities for all possible proton contacts. We evaluated the accuracy of this approach at predicting proton contacts on 60 ¹⁵N separated NOESY and ¹³C separated NOESY datasets simulated from experimentally determined NMR structures and compared it to CYANA, an established method for proton constraint assignment. On average, at the highest confidence level, our method accurately identifies 3.16/3.17 long range contacts per residue and 12.11/12.18 interresidue proton contacts per residue. These accuracies represent a significant increase over the performance of CYANA on the same data set. On a difficult real dataset that is publicly available, the coverage is lower but our method retains its advantage in accuracy over CANDID/CYANA. The algorithm is publicly available via the Protinfo NMR webserver .     

Automatic NOESY assignment in CS-RASREC-Rosetta

We have developed an approach for simultaneous structure calculation and automatic Nuclear Overhauser Effect (NOE) assignment to solve nuclear magnetic resonance (NMR) structures from unassigned NOESY data. The approach, autoNOE-Rosetta, integrates Resolution Adapted Structural RECombination (RASREC) Rosetta NMR calculations with algorithms for automatic NOE assignment. The method was applied to two proteins in the 15–20 kDa size range for which both, NMR and X-ray data, is available. The autoNOE-Rosetta calculations converge for both proteins and yield accurate structures with an RMSD of 1.9 Å to the X-ray reference structures. The method greatly expands the radius of convergence for automatic NOE assignment, and should be broadly useful for NMR structure determination.     

Determination of a high precision structure of a novel protein, Linum usitatissimum trypsin inhibitor (LUTI), using computer-aided assignment of NOESY cross-peaks

The solution structure of a novel 69 residue proteinase inhibitor, Linum usitatissimum trypsin inhibitor (LUTI), was determined using a method based on computer aided assignment of nuclear Overhauser enhancement spectroscopy (NOESY) data. The approach applied uses the program NOAH/DYANA for automatic assignment of NOESY cross-peaks. Calculations were carried out using two unassigned NOESY peak lists and a set of determined dihedral angle restraints. In addition, hydrogen bonds involving amide protons were identified during calculations using geometrical criteria and values of HN temperature coefficients. Stereospecific assignment of beta-methylene protons was carried out using a standard procedure based on nuclear Overhauser enhancement intensities and 3J(alpha)(beta) coupling constants. Further stereospecific assignment of methylene protons and diastereotopic methyl groups were established upon structure-based method available in the program GLOMSA and chemical shift calculations. The applied algorithm allowed us to assign 1968 out of 2164 peaks (91%) derived from NOESY spectra recorded in H2O and 2H2O. The final experimental data input consisted of 1609 interproton distance restraints, 88 restraints for 44 hydrogen bonds, 63 torsion angle restraints and 32 stereospecifically assigned methylene proton pairs and methyl groups. The algorithm allowed the calculation of a high precision protein structure without the laborious manual assignment of NOESY cross-peaks. For the 20 best conformers selected out of 40 refined ones in the program CNS, the calculated average pairwise rmsd values for residues 3 to 69 were 0.38 A (backbone atoms) and 1.02 A (all heavy atoms). The three-dimensional LUTI structure consists of a mixed parallel and antiparallel beta-sheet, a single alpha-helix and shows the fold of the potato 1 family of proteinase inhibitors. Compared to known structures of the family, LUTI contains Arg and Trp residues at positions P6' and P8', respectively, instead of two Arg residues, involved in the proteinase binding loop stabilization. A consequence of the ArgTrp substitution at P8' is a slightly more compact conformation of the loop relative to the protein core.     

SANE (Structure Assisted NOE Evaluation): An automated model-based approach for NOE assignment

A reliable automated approach for assignment of NOESY spectra would allow more rapid determination of protein structures by NMR. In this paper we describe a semi-automated procedure for complete NOESY assignment (SANE, Structure Assisted NOE Evaluation), coupled to an iterative procedure for NMR structure determination where the user is directly involved. Our method is similar to ARIA [Nilges et al. (1997) J. Mol. Biol., 269, 408–422], but is compatible with the molecular dynamics suites AMBER and DYANA. The method is ideal for systems where an initial model or crystal structure is available, but has also been used successfully for ab initio structure determination. Use of this semi-automated iterative approach assists in the identification of errors in the NOE assignments to short-cut the path to an NMR solution structure.     

An efficient randomized algorithm for contact-based NMR backbone resonance assignment

MOTIVATION: Backbone resonance assignment is a critical bottleneck in studies of protein structure, dynamics and interactions by nuclear magnetic resonance (NMR) spectroscopy. A minimalist approach to assignment, which we call 'contact-based', seeks to dramatically reduce experimental time and expense by replacing the standard suite of through-bond experiments with the through-space (nuclear Overhauser enhancement spectroscopy, NOESY) experiment. In the contact-based approach, spectral data are represented in a graph with vertices for putative residues (of unknown relation to the primary sequence) and edges for hypothesized NOESY interactions, such that observed spectral peaks could be explained if the residues were 'close enough'. Due to experimental ambiguity, several incorrect edges can be hypothesized for each spectral peak. An assignment is derived by identifying consistent patterns of edges (e.g. for alpha-helices and beta-sheets) within a graph and by mapping the vertices to the primary sequence. The key algorithmic challenge is to be able to uncover these patterns even when they are obscured by significant noise. RESULTS: This paper develops, analyzes and applies a novel algorithm for the identification of polytopes representing consistent patterns of edges in a corrupted NOESY graph. Our randomized algorithm aggregates simplices into polytopes and fixes inconsistencies with simple local modifications, called rotations, that maintain most of the structure already uncovered. In characterizing the effects of experimental noise, we employ an NMR-specific random graph model in proving that our algorithm gives optimal performance in expected polynomial time, even when the input graph is significantly corrupted. We confirm this analysis in simulation studies with graphs corrupted by up to 500% noise. Finally, we demonstrate the practical application of the algorithm on several experimental beta-sheet datasets. Our approach is able to eliminate a large majority of noise edges and to uncover large consistent sets of interactions. AVAILABILITY: Our algorithm has been implemented in the platform-independent Python code. The software can be freely obtained for academic use by request from the authors.     

RDC derived protein backbone resonance assignment using fragment assembly

Experimental residual dipolar couplings (RDCs) in combination with structural models have the potential for accelerating the protein backbone resonance assignment process because RDCs can be measured accurately and interpreted quantitatively. However, this application has been limited due to the need for very high-resolution structural templates. Here, we introduce a new approach to resonance assignment based on optimal agreement between the experimental and calculated RDCs from a structural template that contains all assignable residues. To overcome the inherent computational complexity of such a global search, we have adopted an efficient two-stage search algorithm and included connectivity data from conventional assignment experiments. In the first stage, a list of strings of resonances (CA-links) is generated via exhaustive searches for short segments of sequentially connected residues in a protein (local templates), and then ranked by the agreement of the experimental ¹³C_α chemical shifts and ¹⁵N-¹H RDCs to the predicted values for each local template. In the second stage, the top CA-links for different local templates in stage I are combinatorially connected to produce CA-links for all assignable residues. The resulting CA-links are ranked for resonance assignment according to their measured RDCs and predicted values from a tertiary structure. Since the final RDC ranking of CA-links includes all assignable residues and the assignment is derived from a “global minimum”, our approach is far less reliant on the quality of experimental data and structural templates. The present approach is validated with the assignments of several proteins, including a 42 kDa maltose binding protein (MBP) using RDCs and structural templates of varying quality. Since backbone resonance assignment is an essential first step for most of biomolecular NMR applications and is often a bottleneck for large systems, we expect that this new approach will improve the efficiency of the assignment process for small and medium size proteins and will extend the size limits assignable by current methods for proteins with structural models.     

Blind testing of routine, fully automated determination of protein structures from NMR data

The protocols currently used for protein structure determination by nuclear magnetic resonance (NMR) depend on the determination of a large number of upper distance limits for proton-proton pairs. Typically, this task is performed manually by an experienced researcher rather than automatically by using a specific computer program. To assess whether it is indeed possible to generate in a fully automated manner NMR structures adequate for deposition in the Protein Data Bank, we gathered 10 experimental data sets with unassigned nuclear Overhauser effect spectroscopy (NOESY) peak lists for various proteins of unknown structure, computed structures for each of them using different, fully automatic programs, and compared the results to each other and to the manually solved reference structures that were not available at the time the data were provided. This constitutes a stringent "blind" assessment similar to the CASP and CAPRI initiatives. This study demonstrates the feasibility of routine, fully automated protein structure determination by NMR.     

Protein NMR structure determination with automated NOE-identification in the NOESY spectra using the new software ATNOS

Novel algorithms are presented for automated NOESY peak picking and NOE signal identification in homonuclear 2D and heteronuclear-resolved 3D [¹H,¹H]-NOESY spectra during de novoprotein structure determination by NMR, which have been implemented in the new software ATNOS (automated NOESY peak picking). The input for ATNOS consists of the amino acid sequence of the protein, chemical shift lists from the sequence-specific resonance assignment, and one or several 2D or 3D NOESY spectra. In the present implementation, ATNOS performs multiple cycles of NOE peak identification in concert with automated NOE assignment with the software CANDID and protein structure calculation with the program DYANA. In the second and subsequent cycles, the intermediate protein structures are used as an additional guide for the interpretation of the NOESY spectra. By incorporating the analysis of the raw NMR data into the process of automated de novoprotein NMR structure determination, ATNOS enables direct feedback between the protein structure, the NOE assignments and the experimental NOESY spectra. The main elements of the algorithms for NOESY spectral analysis are techniques for local baseline correction and evaluation of local noise level amplitudes, automated determination of spectrum-specific threshold parameters, the use of symmetry relations, and the inclusion of the chemical shift information and the intermediate protein structures in the process of distinguishing between NOE peaks and artifacts. The ATNOS procedure has been validated with experimental NMR data sets of three proteins, for which high-quality NMR structures had previously been obtained by interactive interpretation of the NOESY spectra. The ATNOS-based structures coincide closely with those obtained with interactive peak picking. Overall, we present the algorithms used in this paper as a further important step towards objective and efficient de novoprotein structure determination by NMR.     

PACES: Protein sequential assignment by computer-assisted exhaustive search

A crucial step in determining solution structures of proteins using nuclear magnetic resonance (NMR) spectroscopy is the process of sequential assignment, which correlates backbone resonances to corresponding residues in the primary sequence of a protein, today, typically using data from triple-resonance NMR experiments. Although the development of automated approaches for sequential assignment has greatly facilitated this process, the performance of these programs is usually less satisfactory for large proteins, especially in the cases of missing connectivity or severe chemical shift degeneracy. Here, we report the development of a novel computer-assisted method for sequential assignment, using an algorithm that conducts an exhaustive search of all spin systems both for establishing sequential connectivities and then for assignment. By running the program iteratively with user intervention after each cycle, ambiguities in the assignments can be eliminated efficiently and backbone resonances can be assigned rapidly. The efficiency and robustness of this approach have been tested with 27 proteins of sizes varying from 76 amino acids to 723 amino acids, and with data of varying qualities, using experimental data for three proteins, and published assignments modified with simulated noise for the other 24. The complexity of sequential assignment with regard to the size of the protein, the completeness of NMR data sets, and the uncertainty in resonance positions has been examined.Supplementary material to this paper is available in electronic form at http://dx.doi.org/10.1023/A:1023589029301     

Probabilistic Identification of Spin Systems and their Assignments including Coil–Helix Inference as Output (PISTACHIO)

We present a novel automated strategy (PISTACHIO) for the probabilistic assignment of backbone and sidechain chemical shifts in proteins. The algorithm uses peak lists derived from various NMR experiments as input and provides as output ranked lists of assignments for all signals recognized in the input data as constituting spin systems. PISTACHIO was evaluate00000000d by comparing its performance with raw peak-picked data from 15 proteins ranging from 54 to 300 residues; the results were compared with those achieved by experts analyzing the same datasets by hand. As scored against the best available independent assignments for these proteins, the first-ranked PISTACHIO assignments were 80–100% correct for backbone signals and 75–95% correct for sidechain signals. The independent assignments benefited, in a number of cases, from structural data (e.g. from NOESY spectra) that were unavailable to PISTACHIO. Any number of datasets in any combination can serve as input. Thus PISTACHIO can be used as datasets are collected to ascertain the current extent of secure assignments, to identify residues with low assignment probability, and to suggest the types of additional data needed to remove ambiguities. The current implementation of PISTACHIO, which is available from a server on the Internet, supports input data from 15 standard double- and triple-resonance experiments. The software can readily accommodate additional types of experiments, including data from selectively labeled samples. The assignment probabilities can be carried forward and refined in subsequent steps leading to a structure. The performance of PISTACHIO showed no direct dependence on protein size, but correlated instead with data quality (completeness and signal-to-noise). PISTACHIO represents one component of a comprehensive probabilistic approach we are developing for the collection and analysis of protein NMR data.Electronic Supplementary Material Electronic Supplementary material is available for this article at and accessible for authorised users.     

MAP-XSII: an improved program for the automatic assignment of methyl resonances in large proteins

NMR studies of large proteins have gathered much interest in recent years, especially after methyl-transverse relaxation optimized spectroscopy was successfully applied to systems as large as ~1 MDa in molecular weight. However, to fully take advantage of these spectra, there is a need for convenient and robust methods for making resonance assignments rapidly. Here, we present an improved version of our program MAP-XS (methyl assignment prediction from X-ray structure) for the automatic assignment of methyl peaks, based on nuclear Overhauser effects (NOE) correlations and chemical shifts together with available structures. No manual analysis of the NOE data is needed in this new version, which helps to further accelerate the assignment process. A refined algorithm as well as more efficient sampling produces results from single runs of MAP-XSII using unanalyzed NOE data are comparable to those achieved by the old version using manually curated data with every NOE peak correctly attributed to the two related methyl peaks; in addition, checking the results from multiple parallel runs against each other provides an effective mechanism for getting rid of the wrong assignments while keeping the correct ones, which significantly improves the reliability of final assignments. The new program is tested against three different proteins and delivers ~95 % correct assignments; positive results are also achieved for tests using different cut-off distances for NOEs, structures of lower resolutions, and ambiguous residue types.     

Automated Protein NMR Structure Determination Using Wavelet De-noised NOESY Spectra

A major time-consuming step of protein NMR structure determination is the generation of reliable NOESY cross peak lists which usually requires a significant amount of manual interaction. Here we present a new algorithm for automated peak picking involving wavelet de-noised NOESY spectra in a process where the identification of peaks is coupled to automated structure determination. The core of this method is the generation of incremental peak lists by applying different wavelet de-noising procedures which yield peak lists of a different noise content. In combination with additional filters which probe the consistency of the peak lists, good convergence of the NOESY-based automated structure determination could be achieved. These algorithms were implemented in the context of the ARIA software for automated NOE assignment and structure determination and were validated for a polysulfide-sulfur transferase protein of known structure. The procedures presented here should be commonly applicable for efficient protein NMR structure determination and automated NMR peak picking. Electronic supplementary material Electronic supplementary material is available for this article at and accessible for authorised users.