The Tandem Duplication Distance Is NP-Hard

DOI10.4230/LIPICS.STACS.2020.15MaRDI QIDQ5874286zbMATH OpenOpenAlexFDO

Authors Manuel Lafond, Binhai Zhu, Peng Zou

Publication date 7 February 2023

Full work available at URL https://doi.org/10.4230/LIPIcs.STACS.2020.15

zbMATH Keywords

formal languagestandem duplicationtext processingcomputational genomicsFPT algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Computing the tandem duplication distance is NP-hard
• The tandem duplication distance problem is hard over bounded alphabets
• An exact and polynomial distance-based algorithm to reconstruct single copy tandem duplication trees
• An exact and polynomial distance-based algorithm to reconstruct single copy tandem duplication trees
• Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats
• Approximation algorithms for reconstructing the duplication history of tandem repeats
• The combinatorics of tandem duplication
• Duplication Distance to the Root for Binary Sequences
• Heuristics for reversal distance between genomes with duplicated genes

This page was built for publication: The Tandem Duplication Distance Is NP-Hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874286)