The Tandem Duplication Distance Is NP-Hard

DOI10.4230/LIPICS.STACS.2020.15OpenAlexW3013736025MaRDI QIDQ5874286FDOQ5874286

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

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

zbMATH Keywords

formal languagestandem duplicationtext processingcomputational genomicsFPT algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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)