O'Reilly logo

Python for Bioinformatics by Kinser

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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’ ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required