Multiple Optimisation Alignment Exact Algorithms

Multiple Optimisation Alignment [MOA] is the second of 10 lectures on Biological Sequence Analysis [BSA], I will give at the ANU,  in September to November 2018.     BSA is a huge field since sequences are presently so abundant.  POA is the starting point of sequence analysis (first paper 1970) and most other methods are in one way or another derived from the techniques first developed from pairwise alignment.

In this lecture I will discuss exact algorithms to align more than two sequences.  An algorithm for aligning n sequences related by a phylogeny was first published in 1973 by David Sankoff when indels had length 1.  This has since been generalized to longer insertion-deletions with a gap-cost g_k=ab*k. Accellerations to the basic algorithm has been proposed.  Variants of parametric alignment proposed by Kececioglu finding an alignment that has properties as close to a set of bench marks are discussed.