BLAST

This is the Title of the Book, eMatter Edition

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

50

|

Chapter 3: Sequence Alignment

Dynamic Programming

Now that you’ve seen the typical approach to global and local alignment, consider

the generality of dynamic programming. The advantage of DP can be seen in the fill

phase. Each cell represents the maximum scoring alignment between the two

sequences up to that point. When you calculate the next cell, you use previously

stored values. In other words, DP is an optimizing function whose definition is

extended as the algorithm proceeds.

Algorithmic Complexity

The complexity of algorithms is often described in big-O notation, a shorthand for the

asymptotic behavior of the algorithm. For example, searching for a name in a phone

book by starting at the beginning and going name-by-name takes on average, n/2

operations, where n is the number of names in the phone book. Such a search has

O(n) time complexity (constants are dropped from the notation). It scales linearly in

time; a phone book twice as long takes twice as long to search. An approach that

scales more efficiently successively splits the phone book in half based on the alpha-

betical order. This is called a binary search and has complexity. For exam-

ple, a phone book eight times longer takes only three times longer to search. The

alignment algorithms as described have O(nm) complexity ...