Fundamentals of Bioinformatics - Ogurtsov A.N. 2013

Methods of Bioinformatic Analysis
Sequence Alignment Algorithms
Approximate Methods for Rapid Database Searching

According to standard practice, genes from a new genome are compared against all sequences in a database.

Heuristic Methods are typically used first; while they can perform well and quickly when Searching for Similar sequences, they may fall short of exact methods when searching for highly distant relationships.

In practice, heuristic methods yield satisfactory results in many cases where the query sequence is sufficiently similar to one or more database sequences, making them the logical first choice.

A typical heuristic approach selects a small integer k and finds all substrings of length k in the query sequence that also appear in any database sequence.

Such a short identical sequence is referred to as a "word" or "k-tuple".

In mathematics, a tuple denotes a sequence of a finite number of elements. In certain programming languages, a tuple is a specialized data Structure. For instance, in Python, a tuple differs from a list in that it is immutable.

The word "tuple" itself Functions as a generalized "suffix" within a series of words of increasing length: single, double, triple, quadruple, quintuple, sextuple, septuple, octuple, ..., n-tuple, ...

A candidate sequence is a database sequence that contains A large number of matching k-tuples.

Next, for the selected set of candidate sequences, bounded optimal alignment calculations are performed with time and space constraints, involving matrix traversals within diagonals that contain numerous matching k-tuple sets.

Word-based or k-tuple methods, as implemented in programs like FASTA and BLAST, are exceptionally fast, enabling a complete database scan to identify the candidate sequence that yields the best alignment with the query sequence.

The FASTA and BLAST algorithms are heuristic—that is, based on empirical machine programming methods where solutions are found using empirically established rules and feedback loops to refine the results.

The core operation in database searching is aligning the query sequence with each candidate sequence from the database. Since heuristic methods accomplish this task significantly faster, they are preferred over algorithmic dynamic programming methods.

The FASTA program delivers both high sensitivity and rapid similarity searching. This sensitivity is achieved through optimized local alignment algorithms and substitution matrix analysis implemented within the program.

First, FASTA generates a list of tuple-words selected from the pair of compared sequences. A word consists of a string of 3–6 NUCLEOTIDES or 2–3 Amino Acids, and these tuple-words must be non-overlapping. The program then matches the tuple-words and tallies the matches.

Much like constructing a dot plot and calculating a dot matrix score, FASTA selects the variants with the maximum number of words on a diagonal, identifies the match with the highest possible score, and labels the result (the word match) as element #1. If this maximum score is sufficiently high, the program proceeds to the second tier.

At the second tier, the program searches for neighboring approximate matches for each top-scoring word match. If the score is satisfactory, FASTA links the short segments of element #1, builds a longer dot matrix diagonal from them, and calculates the score incorporating gaps and penalty scoring.

The best score from the second tier is known as the initn score. FASTA stores the initn scores calculated for all comparisons between the query sequence and the target sequences. Once all database sequences have been screened, those yielding the highest initn scores are used to construct a local alignment (via the Smith-Waterman algorithm) with the highest possible optimal score.

The FASTA format is widely adopted in numerous Multiple Sequence Alignment programs.