The complexity of string partitioning

DOI10.1016/j.jda.2014.11.002zbMath1328.68324OpenAlexW1553958932WikidataQ115180473 ScholiaQ115180473MaRDI QIDQ2343298

Anne Condon, Chris Thachuk, Ján Maňuch

Publication date: 4 May 2015

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2014.11.002

zbMATH Keywords

NP-completenessfactor-freeprefix-freesuffix-freecollision-aware oligo designequality-freegene synthesisstring partitioning

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Genetics and epigenetics (92D10) Algorithms on strings (68W32)

Related Items (4)

Computing equality-free and repetitive string factorisations ⋮ The Maximum Equality-Free String Factorization Problem: Gaps vs. No Gaps ⋮ String factorisations with maximum or minimum dimension ⋮ Novel phylogenetic network distances based on cherry picking

Cites Work

• Unnamed Item
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• \((1+\varepsilon)\)-approximation of sorting by reversals and transpositions.
• A simpler and faster 1.5-approximation algorithm for sorting by transpositions
• Minimum common string partition problem: hardness and approximations
• Sorting Strings by Reversals and by Transpositions
• The Complexity of String Partitioning
• Complexity of a Collision-Aware String Partition Problem and Its Relation to Oligo Design for Gene Synthesis
• An Eulerian path approach to DNA fragment assembly
• Mapping the genome
• Polynomial-time algorithm for computing translocation distance between genomes

This page was built for publication: The complexity of string partitioning