Computing the Tandem Duplication Distance is NP-Hard
From MaRDI portal
Publication:5020832
DOI10.1137/20M1356257zbMath1483.68504arXiv1906.05266OpenAlexW4206496492MaRDI QIDQ5020832
Peng Zou, Manuel Lafond, Binhai Zhu
Publication date: 7 January 2022
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1906.05266
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Genetics and epigenetics (92D10) Algorithms on strings (68W32) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Tandem Duplications, Segmental Duplications and Deletions, and Their Applications, Permutation-constrained common string partitions with applications
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- On regularity of languages generated by copying systems
- Approximation algorithms for reconstructing the duplication history of tandem repeats
- On the regularity of languages on a binary alphabet generated by copying systems
- Uniformly bounded duplication languages
- Linear time algorithms for finding and representing all the tandem repeats in a string
- Bound-decreasing duplication system
- The Capacity of String-Duplication Systems
- Sorting by Transpositions Is Difficult
- 2726. A problem on strings of beads
- On the tandem duplication-random loss model of genome rearrangement
- Closure of Language Classes Under Bounded Duplication
- Algorithms on Strings, Trees and Sequences
- Capacity and Expressiveness of Genomic Tandem Duplication
- Duplication Distance to the Root for Binary Sequences
- Reducibility among Combinatorial Problems
- Aspects of Molecular Computing
