Chapter 44Autolink: An Algorithm for Automated NMR Resonance Assignment
This chapter discusses Autolink, an heuristic stochastic algorithm for automated NMR resonance assignment [1]. This advanced lecture is designed to expose the reader to the large number of parameters and thresholds that must typically be chosen in current NMR data analysis algorithms. Choosing these parameters is nontrivial, and modern machine-learning techniques, such as support vector machines and graphical models, offer great promise for their systematic and automatic incorporation.
Algorithm Overview
Spin System A spin system is defined as a group of coupled resonances, measured as crosspeaks in the NMR spectra.
Link There is a link between two spin systems if their corresponding residues are adjacent in the protein sequence.
Fragment A fragment is a set of two or more linked spin systems.
The Assignment Problem In an NMR resonance assignment problem, we are given spin systems of a protein sequence, and must find an optimal mapping from spin systems to residues of the sequence.
Overview of Autolink Figure 44.1 shows an overview of Autolink. The input data are spin systems obtained from CARA [2]. All possible spin system pairings are considered and a “fitness” score is computed for each pair. A pair of spin systems and their fitness score form a “link hypothesis.” Each fitness score consists of several subscores representing specific resonance comparisons, such as the comparison of shift of one spin system with the shift of another spin system or the comparison of the and shifts of spin systems. All link hypotheses form a list of potential spin system links, called the “priority list,” which is regarded as the input of the next step, “hypothesis evaluation/reevaluation” cycles. In hypothesis evaluation/reevaluation cycles, some link hypotheses are accepted for the assignment of their spin systems to some regions of the protein sequence, and some link hypotheses are rejected from the candidate list. Next, the link hypotheses fitness scores are modified by factors that depend on the acceptance or rejection of other link hypotheses. The process repeats until convergence, that is, until none of the remaining link hypotheses can be accepted.
Figure 44.1 An overview of Autolink [1]. Reprinted with permission from Elsevier.
Spin System Pair Scoring
The spin system pairing fitness score is a measurement of how likely each spin system pairing corresponds to adjacent spin systems within the protein. As shown in figure 44.2 (plate 45), each spin system pair score consists of several subscores according to different user-selected types, such as , , CO, H(NOE). Here, CO means . Each subscore is calculated by
where and sum over all the spin comparisons, and is a user-defined function describing a mathematical comparison of spin systems.
In addition, each spin pair score is biased according to several user-controlled functions to interpret spin density, overlap, the labeling of each spin, the atom name in each atom label, and the offset in spin label. All these biases will be described in the following section.
Spin Density Bias
The spin density bias is used to account for the fact that uncommon chemical shifts are generally more valuable for determining spin systems linkages than those spins with relatively common ppm values. Spin pair scores are modified according to the following formula:
where is the base score of the pair of spins 1 and 2, is the density-compensated score, is a user-defined input parameter, and is called the spin density, which denotes the average base score of spin 1 with all spins.
Assigned Spin Bias
The assigned spin bias is used to account for the assignment of ambiguous spins. It is considered by the following formula:
where is the modified score, is a user-defined input parameter, is the spin pair score without spin labeling, and is the spin pair score considering labeling.
| Equation | Interpretation |
|---|---|
| Consider only spin system pairs with compatible (ignore other spins). | |
| Consider only spin system pairs with compatible s and H xpeaks (NOESY) in common. | |
| Consider only spin system pairs with compatible s, compatible s, and H xpeaks in common. | |
| Consider only spin system pairs with compatible s and either compatible s or H xpeaks in common. | |
| Consider only spin system pairs with compatible s and H xpeaks in common. | |
| Consider only spin system pairs with compatible s or H xpeaks in common. | |
| Consider only spin system pairs with compatible s or H xpeaks in common, but especially favor those with both. | |
| Consider only spin system pairs with stringently compatible s and at least one of the following: H xpeaks in common, compatible s, or compatible s. |
Figure 44.2 (plate 45) The spin system pairing scoring. (a) Diagram of spin-system pair scoring. The spins of both spin systems (represented here by crosspeaks in spectra) are compared using a user-defined scoring function. Spin comparisons are signified by lines connecting relevant points in the NMR spectra. Model subscoring functions are plotted in gold at the top of the figure. The subscores are calculated by adding together all of the relevant comparison scores of each spin of one spin system (ss1) with each spin of another spin system (ss2). After the individual subscore types ( and ) are shown here) are calculated, they are then combined to form an overall spin-system pair score. The manner in which they are combined is determined by a user-defined scoring equation. The overall scores are recorded in the ‘priority list.’ (b) Examples of scoring equations and literal interpretation. The left column shows examples of valid scoring equations demonstrating the quasi-operators ‘&&,’ ‘i,’’ and ‘&|.’’ ‘xpeak’’ = crosspeak. The right column describes the operations of the scoring equations [1]. Reprinted with permission from Elsevier.
Offset Bias
The offset bias is used to interpret the uncertainty in the intra-or interresidue correlation. It modifies the spin pair score to the following formula:
where is the new labeled score component, is a user-defined control parameter, is the spin pair score considering the presence of labels but ignoring offsets, and is the spin pair score considering offsets.
Atomic Assignment Bias
The atomic assignment bias is used to consider the ambiguity in the atomic assignment (i.e., the “ ” in “ ”). It modifies the spin pair score to the following equation:
where is the new labeled score component, is a user-defined control parameter, is the spin pair score considering the presence of labels but ignoring the atomic assignment, and is the spin pair score considering the atomic assignment.
Overall Spin System Pair Scoring
All the preceding subscores are combined to form an overall score for each spin system pair based on a heuristic, fuzzy-logic approach (see section 2.3.6 in Masse and Keller [1] for more details). Next, these combined scores are sorted in terms of their values and stored in the priority list.
Hypothesis Evaluation/Reevaluation Cycles
In the hypothesis evaluation/reevaluation cycles, a “base priority prime list” is first calculated based on the existing spin system residue assignment. Then a “relative priority prime list” is formed by modifying the base list with biasing potentials (relative biasing, random biasing, and repetition biasing). After that, some best spin system link hypotheses are accepted and some worst spin system links are deleted. Such a process is repeated until convergence, as shown in figure 44.1. There is no guarantee that the algorithm converges, nor on the time complexity, soundness, or solution accuracy.
Calculation of the Base Priority Prime List
The base priority prime list is created by considering how well the fragment from the acceptance of each hypothesis would match positions of the protein sequence. The fitness of each fragment is calculated by
where is the number of spin systems in the fragment, are the spin systems of the hypothetical fragment, are the residue points in the protein sequence, and is the relative score of spin system against residue position in the protein sequence. An example in figure 44.3 (plate 46) illustrates the computation of fitness of a fragment assigned to some region of the protein sequence.
Figure 44.3 (plate 46) The computation of fitness of a fragment. Matching of spin system fragments to the protein sequence proceeds in two stages, (a) individual spin system–sequence matching, and (b) fragment–sequence matching. (a) Each spin system of each fragment is first fit, using fuzzy logic, to each residue position of the protein sequence. In this diagram, comparison of a single spin system (ss11) to each position of the protein sequence is signified by solid black lines. The fit scores for each spin system are then scaled to a range of 0–1. The final fitting scores for each spin system to the protein sequence are shown here in rows 1, 2, and 3, in the ‘Relative spin system residue fit scores’ boxes. (b) Fragment–sequence fitting. Fragment scores are calculated as the geometric average of the single spin system relative fits for consecutive positions within the protein sequence [1]. Reprinted with permission from Elsevier.
Calculation of the Relative Priority Prime List
Score Delta Bias Each spin system pair score is biased according to the next best hypothesis in the list, as shown in the following formula:
where is the score of spin system “A” spin system “B” before score delta biasing, is the next best score for spin system “A”, is the next best score for spin system , and is a user-defined control parameter between 0 and 1.
Repeat Bias The repeat bias is used to avoid loops of the Autolink program. Autolink uses a counter to remember how many times a particular spin system has been linked to another spin system. The repeat bias is defined by
where is a user-defined input parameter between 0 and 1, and is the number of times the spin system’s link partner has been detected.
Random Factor Bias The random factor bias is defined by
where is a user-defined weighting factor representing the percentage of the base priority prime score multiplied by the random factor, is a user-defined exponent, and is a parameter that controls the magnitude of the random factor’s effect.
Evaluation of the Relative Priority Prime List Autolink divides the linking/unlinking process into several rounds, and a maximum number of added/deleted links is defined for each round. During each round, Autolink evaluates the spin system link hypotheses by computing the base priority prime list and subsequently the relative priority prime list, and then accepts a user-defined number of hypotheses at the top of the list. However, Autolink does not accept links that would preclude a higher ranking link in the list. After each linking round, the priority prime lists are recalculated and the worst scoring links are removed.
Linking/unlinking rounds are repeated until either a user-defined number of rounds is reached, or the number of remaining spin system link hypotheses is below a user-defined threshold.
Spin System Fragment Assignment Initially, all of the fragments from previous linking/unlinking cycles are unassigned. All fragment are scored by equation (44.1) against the protein sequence and sorted in terms of that score. The fragment with the highest priority and only one fitting sequence position is assigned first. After the first fragment is assigned, each fragment is rescored against the remaining unassigned parts of the protein sequence, and again, the highest priority fragment matching only one sequence position is assigned. Such a procedure is repeated until no fragments can be unambiguously assigned to the protein sequence.
References
- [1] J. E. Masse and R. Keller. AutoLink: Automated sequential resonance assignment of biopolymers from NMR data by relative-hypothesis-prioritization-based simulated logic. Journal of Magnetic Resonance 174;1(2005 May):133–151.
- [2] R. Keller and K. Wuthrich. Computer-aided resonance assignment (CARA). Available at: http://www.nmr.ch.