The Tandem Duplication Distance Problem Is Hard over Bounded Alphabets

A tandem duplication is an operation that converts a string \(S = AXB\) into a string \(T = AXXB.\) As they appear to be involved in genetic disorders, tandem duplications are widely studied in computational biology. Also, tandem duplication mechanisms have been recently studied in different contexts, from formal languages, to information theory, to error-correcting codes for DNA storage systems. The question of determining the complexity of computing the tandem duplication distance between two given strings was posed by (Leupold et al., 2004) and, very recently, the problem was shown to be NP-hard for the case of unbounded alphabets (Lafond et al., STACS 2020).