Python Programming for Biology: Bioinformatics and Beyond

Dynamic programming

The  dynamic  programming  algorithm,  which  we  commonly  use  to  align  pairs  of

sequences,  is  based  on  the  idea  that  if  your  big  problem  can  be  broken  down  into  local

sub-problems  that  occur  repeatedly,  then  the  solution  to  each  sub-problem  only  needs  to

be calculated once. In terms of sequence alignment the big problem is to find the highest-

scoring  arrangement  and  the  local  sub-problems  involve  smaller  sub-alignments.  For  a

simple abstract example imagine a problem where you wanted to find the quickest overall

route  from  point  A  to  point  H,  where  you  had  to  travel  via  various  intermediate  points

(you  could  imagine  that  each  point  represents  a  town  and  travelling  represents  a  train

ride).  The  arrangement  of  the  points  is  as  shown  in

Figure  12.4

,  such  that  at  each

intermediate stage you have to go through one of two points.