Python Programming for Biology: Bioinformatics and Beyond

Progressive pairing

The general multiple-alignment problem might not be solvable in an optimal mathematical

sense,  but  there  are  nonetheless  means  for  getting  very  good  (and  hence  scientifically

useful)  solutions  quickly.  The  way  that  this  is  done  considers  that  the  sequences  being

aligned  have  arisen  from  a  divergent,  branching  evolutionary  process.  Thus,  rather  than

optimising the alignment of each sequence with all of the others, many methods attempt to

join sequences into an alignment in the order of their similarity to one another; this is the

progressive  pairing  approach.  The  alignment  process  can  thus  be  broken  down  into

discrete stages: the building of a family tree for the input sequences and then the creation

of the overall multiple alignment, by progressively pairing alignments of smaller numbers

of  sequences  in  the  same  order  as  the  branches  of  the  family  tree  join  (often  done  in  a

weighted manner depending on the lengths of the tree branches).

The  tricky  problem  of  building  (phylogenetic)  trees  is  discussed  later  in

Chapter  14

.

Initially  we  will  make  only  crude  multiple-sequence  alignments  by  joining  sequences  in

the input (arbitrary) order. Nevertheless you can use later Python examples to make family

trees and thus employ a better order for combining alignments. There are of course other

approaches  that  can  be  taken  to  generate  multiple  alignments,  aside  or  on  top  of  the

progressive pairing approach. However, many of these are slower and more specialised for

increased  accuracy.  Usually  these  more  rigorous  approaches  will  not  give  answers  too

dissimilar  to  solutions  from  progressive  pairing;  indeed  one  common  speed-up  trick  for

more exhaustive searches is to restrict the search for optimal solutions to only routes that

lie near the initial, quick solution.