"Hardness" of (multi-) sequence alignment

Align 2 sequences of length N allowing gaps.

ACCAC-ACA ACCACACA

::x::x:x: :xxxxxx:

AC-ACCATA , A-----CACCATA , etc.

2N gap positions, gap lengths of 0 to N each:

A naïve algorithm might scale by O(N2N).

For N= 3x109 this is rather large.

Now, what about kɮ sequences?

or rearrangements other than gaps?

Previous slide

Next slide

Back to first slide

View graphic version