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

Fold recognition
“Threading”
Alignment search

When a potential energy function is available to evaluate a given protein model Structure, a researcher faces a challenging task: finding the Sequence-to-Structure Alignment that minimizes (or maximizes) the potential function value. Disregarding the fact that insertions and deletions naturally occur in protein sequences during evolution allows The Use of the "gaps-free threading" technique. This approach relies on simply "sliding" the sequence along the structure, evaluating every gap-free alignment in the process. While this method offers high computational speed, its major drawback is the inability to account for gaps. The insertion or deletion of even a single residue causes a reading frame shift, causing high-quality alignments to be completely overlooked under other conditions. Therefore, incorporating gaps is essential for capturing the true nature of evolutionary variations.

However, accounting for these very gaps turns a straightforward task into an NP-hard problem, for which no fast (polynomial-time) solution exists. Exhaustive searches of all possible gapped alignments for a given sequence and structure are computationally unfeasible for obvious reasons, especially when searching Databases containing thousands of structures. In standard sequence alignment, which ignores pairwise interaction contributions between any two residues within the same protein, the alignment problem can be solved efficiently via dynamic programming recursion. Yet, once various pairwise interaction contributions—such as physical potentials—are factored in, dynamic programming can no longer be applied. In classical dynamic programming, aligning a residue of the target sequence against a putative template structure is evaluated using a simple lookup table (e.g., BLOSUM or a Profile/Position Specific Scoring Matrix (PSSM); see below and Table 2.1). Conversely, when using the threading method, the alignment score of a sequence residue relative to a structural residue is determined based on how all other interacting residues in that local region have been aligned.

Class="center">Table 2.1. (a) BLOSUM scoring matrix (Seq)

(b) Simple Secondary structure scoring matrix (SS)

(c) Simple solvent accessibility scoring matrix (Solv)