|
A tandem duplication in a string takes a substring and inserts another copy of
it right beside it. Given two strings, we want to find a shortest sequence of
tandem duplications that transform the shorter string into the longer one, or
recognize that no such sequence exists. The problem, in particular with short tandem duplications, is of interest in genomics, and a number of complexity
results are known. First we improve a recent simple XP algorithm. However, our
main technical contributions are an FPT algorithm, where the parameter is the
difference of lengths of the two given strings, and a polynomial kernel.
|
