New Algorithms for Multiple Sequence Alignment
Paul Horton
We have developed two new exact algorithms for gapless multiple alignment
of DNA sequences. Unlike previous exact algorithms, for sufficiently
short motifs, the complexity of our algorithms do not grow
exponentially in the number of sequences. One algorithm, which assumes
a class of scoring functions which includes the information theoretic
entry scoring function, is polynomial in the number
of sequences although it is exponential in the width of the motifs to
be aligned. The other algorithm is super exponential in the width of
the motif but linear in the number of sequences for a very general
class of scoring functions.
Real World Computing Partnership