Fundamentals of Bioinformatics - Ogurtsov A.N. 2013

Methods of Bioinformatic Analysis
Multiple Sequence Alignment
Methods for Multiple Alignment

To date, various Methods have been developed that allow Multiple Sequence Alignment of known Proteins to be used for identifying related sequences during database searches. These methods are implemented as software tools, the most prominent being Profiles, PSI-BLAST (Position-Specific Iterated BLAST), and Hidden Markov Models (HMMs).

Profiles. As a rule, proteins with similar Functions share a common, identical motif in their Structure. Therefore, motif prediction is far more useful than searching for global similarities in primary protein sequences. Proteins with similar or comparable functions are very likely descendants of a common ancestral protein. Quite often, their sequences (especially motifs) exhibit significant similarity. Multiple sequence alignment typically enables the detection of related Protein Families. This type of multiple sequence alignment is referred to as a profile.

A profile (or weight matrix) is a positional scoring table that summarizes information from a full sequence alignment. Profiles indicate which residues may occupy specific positions; which positions are conserved versus degenerate; and which positions or regions accommodate insertions. In addition to data derived from alignment, the scoring system may incorporate evolutionary weights and structural analysis results.

In the literature, the terms profile, pattern, Position Weight Matrix (PWM), and Position-Specific Weight Matrix (PSWM, or Position-Specific Scoring Matrix, PSSM) are used almost interchangeably.

A profile reveals regular combinations present in a multiple alignment of homologous sequences. These combinations are of great significance.

✵ They allow for more accurate alignments of distantly related sequences.

✵ Sets of highly conserved residues suggest their involvement in the Active Site and help determine protein function.

✵ Conserved patterns facilitate the identification of other similar sequences.

✵ Conserved patterns can be used to classify subfamilies within a set of homologs.

✵ Sets of residues that show low conservation and contain insertions and deletions are highly likely to correspond to loops on the protein surface. This information has been useful in vaccine development, as these regions are strong candidates for stimulating The production of Antibodies that effectively bind to native structures.

✵ Structure Prediction Methods Based on multiple sequence alignment are more robust than those relying on single-sequence analysis. For instance, Homology modeling fundamentally depends on generating a correct sequence alignment.

To use profiles for identifying homologs, a given sequence must be compared against the database sequences presented in the alignment table, assigning higher weights to conserved positions compared to variable ones.

If a specific region of a protein chain is known to be strictly conserved, the Procedure should require the mandatory presence of that motif.

At the same time, an overly stringent requirement for this operation could lead to missing interesting distant relatives, so a degree of tolerance must be allowed.

As a quantitative measure of conservation, each position in the aligned sequence table is associated with a probability distribution of Amino Acids.

For example, for the alignment

Class="center">

one can construct the weight matrix

the elements of which represent the weight of a given amino acid for each Column of the alignment.

Several methods are used to construct such a matrix. First, the representativeness of a profile increases with the number of sequences included in the alignment.

Second, one accounts for the substitution weight of a given amino acid i with any other observed amino acid using amino acid Substitution Matrices, such as PAM250 or BLOSUM62. In this case, amino acid i can be assigned a value

In effect, the vector of values for the amino acids is the product of the substitution matrix and the residue frequency vector.

This scheme distributes values among the observed amino acids, weighted according to substitution probabilities. An amino acid in the query sequence receives a higher score either if it appears frequently at that position in the query, or if it has a high probability of arising via mutation from residues typical of that position. In other words, a combination of the observed sample and Background amino acid frequencies is used as The amino acid distribution.

This approach is more efficient for detecting distant relatives when using a limited set of known sequences.

The algorithm that implements the search for the optimal alignment between a query sequence and a profile across all possible alignments is a generalization of the dynamic programming method for pairwise sequence alignment.

The drawback of a simple profile is that multiple sequence alignment must be performed beforehand and is incorporated in a fixed form.

An alternative is to use the PSI-BLAST program and hidden Markov models (HMMs), whose computational (and predictive) power increases with the growing size of Databases.

PSI-BLAST. PSI-BLAST is a program that searches databases for sequences similar to a query. It is a generalized version of the BLAST program.

The BLAST program (and its variants) independently compares each database entry with the query sequence.

The first step of the BLAST algorithm is to search for word-tuples of a set length W with a score exceeding a certain threshold T. The value of W is typically 3 for protein sequences and 11 for nucleic acid sequences. Initially, BLAST (similar to the FASTA algorithm (see section 8.4)) selects a word-tuple from the query sequence and proceeds to extend it in both directions by matching it against the target sequence while simultaneously calculating match and mismatch scores, as well as gap opening and extension penalties. Word extension continues until a certain limit S is reached. BLAST extends individual pairs of matching words until the total alignment score drops from its maximum value down to a certain threshold; As a result, the program outputs pairs of high-scoring segments.

BLAST is a heuristic search algorithm implemented in various programs of the suite (see section 4.3).

BLASTP compares a query Amino Acid Sequence against subject sequences from a protein database.

BLASTN compares a query nucleotide sequence against subject sequences from a nucleotide sequence database.

BLASTX compares the results of a six-frame conceptual Translation (Six-Frame Translation or 6-Frame Translation) of both DNA strands of a nucleotide query sequence against the contents of a protein sequence database.

TBLASTN compares a query protein sequence against sequences from a nucleotide sequence database dynamically translated in all six reading frames (both strands).

TBLASTX compares the six-frame translation products of a nucleotide query sequence with the six-frame translation products of sequences from a nucleotide sequence database.

PSI-BLAST compares a query amino acid sequence against subject sequences from protein databases.

The PSI-BLAST program begins by performing a pairwise comparison of each database entry with the query sequence. It then constructs a local multiple sequence alignment of the sequences retrieved from the initial query and subsequently searches the database using this multiple alignment.

The process is then repeated (a new multiple alignment is built from the resulting set of candidates), and the results are refined over several iterations until a specified number of cycles is exhausted or until the procedure converges, meaning that the results of two consecutive queries match.

The reason behind The Development of the BLAST program was that full-scale dynamic programming methods are not fast enough for exhaustive searches in large databases. A database often contains sequences very similar to the query sequence. Less accurate but faster programs are fully capable of identifying close matches, which is what is required in the majority of cases.

For example, if There is a need to find mouse protein homologs in The Human Genome, the degree of similarity will likely be high, and faster methods will be well-suited for solving this task.

However, when searching for human protein homologs in C. elegans or Yeast, the differences will be more subtle, and therefore a program with a higher degree of accuracy is required.

The method underlying the BLAST program is, generally speaking, similar to dot matrix analysis, which reveals regions of high local similarity. For each database entry, short contiguous segments matching short contiguous segments of the query sequence are checked (using an amino acid substitution matrix), but without gaps. Fixed-length segments are rapidly identified using lookup tables (hash tables).

A lookup table is a data structure (typically an array or associative array) used to replace runtime computations with a simple indexing operation. Speed gains are achieved because performing a simple memory lookup requires significantly less machine time than executing complex calculations. Examples of lookup tables include trigonometric tables or logarithm tables (such as Bradis tables), which were widely used prior to the mass production of scientific calculators.

Once the BLAST program identifies a suitable region, it attempts to extend it. Some versions of the program allow for gaps. The output provides the program's set of local segment alignments.

The PSI-BLAST program, which utilizes iterative sequence searching, is much more efficient than BLAST when exploring more distant evolutionary relationships. PSI-BLAST accurately identifies three times as many homologs as BLAST in regions where identity falls below 30%. Consequently, this method is exceptionally well-suited for whole-Genome Analysis. PSI-BLAST is able to identify Protein domains of known structure for 39% of M. genitalium genes, 24% of yeast genes, and 21% of C. elegans genes.

The only more efficient sequence-based method is the hidden Markov model approach.