Biomedical Engineering Reference
In-Depth Information
Multiple sequence alignment, in which three or more sequences must be aligned, is useful in finding
conserved regulatory patterns in nucleotide sequences and for identifying structural and functional
domains in protein families. Unfortunately, multiple sequence alignment is much more challenging
than single pairwise alignment. For nucleotide sequences, the problem appears as:
J) TCAGAGCGAGA
K) ATCCGGCCCGGCAGCGAGA
L) CAAAATTCAGAGCGAGA
M) ATCCGCAGAGCCCGGGGAGA
N) CCCGGCAGCGAGA
0) ATCCGTTTTTTTTTGAGA
Instead of simply considering gaps, inexact matches, and global-versus-local alignment for a pair of
sequences, multiple sequences must be considered—in this example, six sequences. Of course, in an
actual multiple sequence alignment, each sequence may consist of several hundred characters,
making manual gap insertions and other non-computational methods infeasible. Although most of the
following discussion deals with single pairwise alignment, multiple alignment is an area of active
research in bioinformatics because of the computational challenges involved.
Computational Methods
Fortunately, a variety of computational methods is available for sequence alignment, whether single,
multiple, global, or local. A sampling of major computational approaches to pattern matching and
sequence alignment is listed in
Table 8-2
.
Table 8-2. Computational Methods of Sequence Alignment.
Bayesian Methods
Dot Matrix
Dynamic Programming
Genetic Algorithms
Hidden Markov Models
Neural Networks
Scoring Matrices
Word-Based Techniques
Of the methods listed in
Table 8-2
, word-based techniques, followed by dynamic programming
methods, are used most often. The popularity of word-based techniques is in part because of the
ready availability of Web-based tools that use these methods, such as Fast Alignment (FASTA) and
Basic Local Alignment and Search Tool (BLAST). Similarly, dynamic programming techniques, such as
the Smith-Waterman algorithm, while computationally expensive, are also popular because of free
access to Web-based tools. Dot matrix methods, once a mainstay of manual and computer-enabled
sequence alignment, have become less popular since the advent of BLAST and its derivatives.
