Python for Bioinformatics

8 Dynamic Programming

The functions discussed in the previous chapter required users to insert gaps manually into sequences. Information about where and how many gaps are needed is not generally available. A commonly executed task is to align two sequences and to determine the locations of the gaps that provide the optimal alignment. Because brute force alignment—a technique that considers all of the possibilities for the location of gaps—is no longer a viable option, the field has adopted dynamic programming as a solution.

8.1 The Problem with the Brute Force Approach

For the purposes of alignment, it is not possible to distinguish between an insertion and a deletion. Consider the following two sequences:

 

A = 'TGCGTAG'B = 'TG-GTAG'

Has a ‘C’ ...