Protein Structure and Function. Application of Bioinformatics Methods - John Rigden 2014

Fold recognition
“Threading”
Heuristic alignment rules

Since the threading problem is formally unsolvable (NP-hard), numerous heuristic rules have been developed to enable highly sensitive Selection of potential alignments while searching for a sub-optimal solution within a reasonable computational time. One approach relies on imposing constraints on gap Location and size. The core idea is that gaps are permitted only in the most probable Regions of the template Structure, such as between conserved Secondary structure elements (Madej et al. 1995). Another approach is known as the "frozen approximation" (Fig. 2.3, left) (Westhead et al. 1995). As noted above, the main challenge in calculating the alignment score of a specific residue relative to its position in the template structure is that the alignment of all other residues—that is, the environment of the residue in question—must be known. Since this environment is unknown, the fixed approximation assumes it to be identical to the template sequence environment. This elegant and straightforward solution serves as an excellent approximation when the query sequence closely resembles the template sequence. However, this method fails when significant differences exist between the sequences—which is precisely the case of interest here.

A more refined version of the fixed approximation was developed by Skolnick and Kihara (Skolnick and Kihara 2000) and is termed the "unfrozen approximation" (Fig. 2.3, right). In this case, the residue environment is derived not from the template structure itself, but from an initial trial alignment of the query sequence against the template structure, obtained using classical profile-based alignment Methods. This ensures that at least the local environment of the target residue is based on the correct sequence. Nevertheless, the reliability of the resulting energy values heavily depends on the quality of the initial alignment, which, as we recall, was the original problem. To reduce this dependence on the initial alignment, the process is repeated iteratively, each time aligning the sequence by incorporating the threading score contributions obtained from the previous iterations.

Class="center">

Fig. 2.3. (For the color version of the figure, see the insert.) Schematic representation of threading. Left: Frozen approximation: here, residue M of the query sequence is pre-aligned against residue V of the template structure. The empirical potential for residue M is then evaluated within the environment of residues G, L, and F, taken directly from the native template structure. Right: Unfrozen approximation. A trial alignment is performed first, using techniques such as profile alignment. The environment of residue M is now defined by its surroundings in the trial alignment. Shaded areas indicate residues of the original template.

A rather sophisticated approach, developed by Jones et al. (Jones et al. 1992) and named "double dynamic programming," is implemented in the THREADER program. The effectiveness of this approach was demonstrated in early CASP evaluations. Although a full Description of the technique is beyond The Scope of this chapter, the general idea is to align a single position in the query sequence with a single position in the template structure. A conventional alignment algorithm is then used to align the remaining part of the sequence, optimizing the potential relative to this fixed position. The optimal alignment found in this manner is subsequently added to the scoring matrix. The process is repeated for every possible pair of sequence and structure residues (or at least for a significant subset of pairs), with information on the optimal alignment recorded each time in a secondary scoring matrix. Finally, the secondary scoring matrix is used to generate the final alignment, which incorporates the maximum possible number of accumulated optimal alignments. It is precisely because of this two-level alignment Procedure that the method is called double dynamic programming. Originally, The method was designed to break down the threading problem into numerous smaller tasks whose combined solutions yielded a definitive answer. This concept has since been repeatedly employed in many of the methods described below.

The Gibbs sampling algorithm was applied to the threading problem by Bryant (Bryant 1996). In this approach, a random alignment is generated in the first step. At each step of the algorithm, a core secondary structure element C is chosen at random, all possible alternative alignments are generated for it, a score S is calculated for each new alignment, and a new alignment is then selected with a probability proportional to exp(-S/kT), where k is the Boltzmann constant and T is the system's virtual "Temperature." Each new iteration involves using a newly selected random core element as the alignment target. A simulated annealing protocol is employed, whereby the system temperature is slowly decreased over time. Using a high temperature initially ensures that low-scoring alignments are sampled just as frequently as high-scoring ones. This is appropriate for the Cytology/cytology/16.html">Early stages of modeling, as the probability of stumbling upon a complete, high-quality alignment purely by chance is extremely low. However, as the temperature drops, the probability of accepting low-scoring alignments gradually decreases, and the system "settles" into a globally low-energy alignment. Simulated annealing is widely used to solve optimization problems in bioinformatics and other fields. While the method does not guarantee finding the global optimum, it is characterized by high speed and efficiency.

The "divide and conquer" threading algorithm (Xu et al. 1998) repeatedly splits the structure into substructures, solves the alignment problem for each, and combines the resulting solutions to find the global optimum. Similarly, in the branch-and-bound search algorithm (Lathrop and Smith 1996), the threading search space is recursively divided into smaller subspaces, the most promising subspace is selected and further subdivided. In The final stage, the best selected subspace contains only a single alignment, which represents the global optimum. Finding the global optimum is extremely time-consuming; therefore, a version of the program tentatively named "Always Ready!" (Lathrop 1999) was developed, which quickly yields a fairly accurate approximation. The longer the program runs, the more precise the results become, eventually returning the alignment corresponding to the global optimum.

Another closely related approach is protein threading via linear programming (Xu et al. 2003). Linear programming is a general method used to solve complex problems subject to various constraints. In threading, such constraints often include the notion that aligning a specific region of the query sequence with the structure implies a corresponding alignment of the subsequent (or preceding) PARTS OF THE sequence with the respective parts of the structure. Such constraints, functioning more as logical variables than continuous ones, can be collectively formulated as an integer programming problem. These problems are often solved by treating them less stringently as continuous linear programming problems, followed by the application of a branch-and-bound model.

This Overview of selected threading methods demonstrates the wide array of tools from physics, mathematics, and computer science that have been applied to this challenging problem over the past 15-20 years. Nevertheless, no single method has emerged as clearly superior to the others in this field. Despite the availability of highly efficient and accurate sequence-structure alignment Methods based on Energy Functions, the energy function itself remains the "weak link" and the primary cause of limited performance.