Alignments with non-overlapping moves, inversions and tandem duplications in O(n4) time

Abstract Sequence alignment is a central problem in bioinformatics. The classical dynamic programming algorithm aligns two sequences by optimizing over possible insertions, deletions and substitutions. However, other evolutionary events can be ob-served, such as inversions, tandem duplications or moves (transpositions). It has been established that the extension of the problem to move operations is NP-complete. Pre-vious work has shown that an extension restricted to non-overlapping inversions can be solved in O(n3) with a restricted scoring scheme. In this paper, we show that the alignment problem extended to non-overlapping moves can be solved in O(n5) for general scoring schemes, O(n4 logn) for concave scoring schemes and O(n4) for re-stricted scoring schemes. Furthermore, we show that the alignment problem extended to non-overlapping moves, inversions and tandem duplications can be solved with the same time complexities. Finally, an example of an alignment with non-overlapping moves is provided