|
HELP
CENTER
Alignment Scores
and Search Algorithms:
1. Alignment Scores
2. Alignment Algorithms
1. Alignment Scores:
The higher the score ... the better the alignment.
| |
A Substitution Score is chosen for each
aligned pair of letters. The set of these scores is called the
substitution matrix. The matrix scores highly identical
matches of bases, and also gives 'better' scores to alignments
of non-identical bases that are similiar in some way, and a 'worse'
score to pairs that are very dissimilar. This system can preserve
alignments based on function by identifying, for example, sections
of the two sequences that are similarly hydrophobic, even if
not identical in sequence. |
| |
A gap scoring system (affine
gap costs) is used to chose scores for 'gaps'. A gap
is one or more adjacent nulls in one sequence aligned with letters
in the other sequence. Ideally, the gap scoring system charges
a large initial penality for the existence of a gap, and smaller
penalities for each individual residue. This takes into account
that each mutational event can insert or delete multiple residues
at a time - the bulk of the gap cost penalty is for the existence
of the mutation itself, not the length. |
| |
The alignment score is the sum of
the scores specified for each of the aligned pairs of letters,
and letters with nulls, in the alignment. The higher the alignment
score, the better the alignment. |
Top of Page
2. Alignment Algorithms:
Once a scoring system is defined, an algorithm is needed for
locating the optimal (i.e. highest scoring) alignments of two
sequences.
a. Dynamic Programming Algorithms
Needleman and Wunsch ("Global" Alignment)
Uses a global alignment algorithm, meaning that:
| |
a. the full sequence must be aligned . |
| |
b. gaps at the end of the sequence are
penalized as much as internal gaps. |
Smith-Waterman ("Local" Alignment)
Example and Explanation of Smith-Waterman
Algorithm
Uses a local alignment algorithm, meaning that:
|
a. it searches for both full and partial
sequence matches . |
| |
b. gaps at the end of the sequence essentially
have a penalty of zero. |
|
Note:
Global alignment methods give the optimal end to end
alignment between two sequences.
However, homologous sequences may share similarity only in
a sub-region of the sequence. In trying to choose the optimal
end-to-end alignment, global alignments can fail to pick up local
homology. Local alignment methods will return alignments
with high scoring regional homology.
|
Top of Page
b. BLAST
Program Search Strategy:
|
Step
1. Rapid exact-match searches identifies promising
regions |
| |
Step
2. Smith-Waterman
algorithm implemented on this restricted set of alignments |
This heuristic search strategy is 10-100 times faster than
the complete Smith-Waterman, although less accurate. Thus, BLAST
sacrifices the guarentee of optimality in local alignments for
a significant improvement in runtime.
Top of Page
HELP
CENTER
|
