BLAST

This is the Title of the Book, eMatter Edition

Copyright © 2012 O’Reilly & Associates, Inc. All rights reserved.

46

|

Chapter 3: Sequence Alignment

Local Alignment: Smith-Waterman

The local alignment algorithm we describe here, the Smith-Waterman algorithm, is a

very simple modification of Needleman-Wunsch. There are only three changes:

• The edges of the matrix are initialized to 0 instead of increasing gap penalties.

• The maximum score is never less than 0, and no pointer is recorded unless the

score is greater than 0.

• The trace-back starts from the highest score in the matrix (rather than at the end

of the matrix) and ends at a score of 0 (rather than the start of the matrix).

These simple changes have a profound effect on the behavior of algorithm. Using the

same words and scoring scheme as you did in global alignment, look at the filled

matrix in Figure 3-6.

# trace-back

my $align1 = "";

my $align2 = "";

# start at last cell of matrix

my $j = length($seq1);

my $i = length($seq2);

while (1) {

last if $matrix[$i][$j]{pointer} eq "none"; # ends at first cell of matrix

if ($matrix[$i][$j]{pointer} eq "diagonal") {

$align1 .= substr($seq1, $j-1, 1);

$align2 .= substr($seq2, $i-1, 1);

$i--;

$j--;

}

elsif ($matrix[$i][$j]{pointer} eq "left") {

$align1 .= substr($seq1, $j-1, 1);

$align2 .= "-";

$j--;

}

elsif ($matrix[$i][$j]{pointer} eq "up") {

$align1 .= "-";

$align2 .= substr($seq2, $i-1, 1);

$i--; ...