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 C1αC_1^\alpha shift of one spin system with the Ci−1αC_{i-1}^\alpha shift of another spin system or the comparison of the C1βC_1^\beta and Ci−1βC_{i-1}^\beta 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 CαC^\alpha , CβC^\beta , CO, H(NOE). Here, CO means C′C' . Each subscore is calculated by

∑s1∑s2f(Δ),\sum_{s1} \sum_{s2} f(\Delta), where ∑s1\sum_{s1} and ∑s2\sum_{s2} sum over all the spin comparisons, and f(Δ)f(\Delta) 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:

rel_score′=(1−sdc)×rel_score+sdc×score1→2density1→Σ,rel\_score' = (1 - sdc) \times rel\_score + \frac{sdc \times score_{1 \rightarrow 2}}{density_{1 \rightarrow \Sigma}}, where rel_scorerel\_score is the base score of the pair of spins 1 and 2, rel_score′rel\_score' is the density-compensated score, sdcsdc is a user-defined input parameter, and density1→Σdensity_{1 \rightarrow \Sigma} 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:

rel_score′=(1−asb)×rel_score_unlabeled+asb×rel_score_labeled,rel\_score' = (1 - asb) \times rel\_score\_unlabeled + asb \times rel\_score\_labeled, where rel_score′rel\_score' is the modified score, asbasb is a user-defined input parameter, rel_score_unlabeledrel\_score\_unlabeled is the spin pair score without spin labeling, and rel_score_labeledrel\_score\_labeled is the spin pair score considering labeling.

Equation Interpretation
CαC\alpha Consider only spin system pairs with compatible CαC\alpha (ignore other spins).
H×CαH \times C\alpha Consider only spin system pairs with compatible CαC\alpha s and H xpeaks (NOESY) in common.
H×Cα×CβH \times C\alpha \times C\beta Consider only spin system pairs with compatible CαC\alpha s, compatible CβC\beta s, and H xpeaks in common.
Cα×(H+Cβ)C\alpha \times (H + C\beta) Consider only spin system pairs with compatible CαC\alpha s and either compatible CβC\beta s or H xpeaks in common.
H&CαH \& C\alpha Consider only spin system pairs with compatible CαC\alpha s and H xpeaks in common.
HCαH \ C\alpha Consider only spin system pairs with compatible CαC\alpha s or H xpeaks in common.
H&CαH \& C\alpha Consider only spin system pairs with compatible CαC\alpha s or H xpeaks in common, but especially favor those with both.
Cα2×(H+Cβ+CO)C\alpha^2 \times (H + C\beta + CO) Consider only spin system pairs with stringently compatible CαC\alpha s and at least one of the following: H xpeaks in common, compatible CβC\beta s, or compatible COCO 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 ( CαC^\alpha and H(NOE)H(NOE) ) 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:

rel_score′=(1−ob)×rel_score_labeled+ob×rel_score_labeled+offset,rel\_score' = (1 - ob) \times rel\_score\_labeled + ob \times rel\_score\_labeled+offset, where rel_score′rel\_score' is the new labeled score component, obob is a user-defined control parameter, rel_score_labeledrel\_score\_labeled is the spin pair score considering the presence of labels but ignoring offsets, and rel_score_labeled+offsetrel\_score\_labeled+offset 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 “ CαC^\alpha ” in “ Ci−1αC_{i-1}^\alpha ”). It modifies the spin pair score to the following equation:

rel_score′=(1−aab)×rel_score_labeled+aab×rel_score_labeled+same,rel\_score' = (1 - aab) \times rel\_score\_labeled + aab \times rel\_score\_labeled+same, where rel_score′rel\_score' is the new labeled score component, aabaab is a user-defined control parameter, rel_score_labeledrel\_score\_labeled is the spin pair score considering the presence of labels but ignoring the atomic assignment, and rel_score_labeled+samerel\_score\_labeled+same 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

fragmentScore=[score_ref(ss1,res1)×…×score_ref(ssn,resn)]1/n,(44.1)fragmentScore = [score\_ref(ss_1, res_1) \times \dots \times score\_ref(ss_n, res_n)]^{1/n}, \quad (44.1) where nn is the number of spin systems in the fragment, ssiss_i are the spin systems of the hypothetical fragment, resires_i are the residue points in the protein sequence, and scoreref(ssx,resy)score_{ref}(ss_x, res_y) is the relative score of spin system xx against residue position yy 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:

scoreA→B′=(1−sdb)×scoreA→B+sdb×[scoreA→B×(scoreA→B−scoreA→?)],score'_{A \rightarrow B} = (1 - sdb) \times score_{A \rightarrow B} + sdb \times [score_{A \rightarrow B} \times (score_{A \rightarrow B} - score_{A \rightarrow ?})], where scoreA→Bscore_{A \rightarrow B} is the score of spin system “A” →\rightarrow spin system “B” before score delta biasing, scoreA→?score_{A \rightarrow ?} is the next best score for spin system “A”, score?→Bscore_{? \rightarrow B} is the next best score for spin system BB , and sdbsdb 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

score′=score×rb#ofRepeat,score' = score \times rb^{\#of Repeat}, where rbrb is a user-defined input parameter between 0 and 1, and #ofRepeat\#of Repeat is the number of times the spin system’s link partner has been detected.

Random Factor Bias The random factor bias is defined by

score′=(1−rfb)×score+rfb×score×randomFactorexp×randAmp,score' = (1 - rfb) \times score + rfb \times score \times random Factor^{exp} \times rand Amp, where rfbrfb is a user-defined weighting factor representing the percentage of the base priority prime score multiplied by the random factor, expexp is a user-defined exponent, and randAmprand Amp 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.