Prague Stringology Conference 2023
Tandem Duplication Parameterized by the Length Difference
| Abstract: |
| 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. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |