The Complexity of String Partitioning

DOI10.1007/978-3-642-31265-6_13MaRDI QIDQ2904489zbMATH OpenOpenAlexFDO

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

Publication date 14 August 2012

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.2201

Mathematics Subject Classification ID

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

Abstract: Given a string $w$ over a finite alphabet $Sigma$ and an integer $K$, can $w$ be partitioned into strings of length at most $K$, such that there are no emph{collisions}? We refer to this question as the emph{string partition} problem and show it is NP-complete for various definitions of collision and for a number of interesting restrictions including $|Sigma|=2$. This establishes the hardness of an important problem in contemporary synthetic biology, namely, oligo design for gene synthesis.

Recommendations

• The complexity of string partitioning
• Exponential and polynomial time algorithms for the minimum common string partition problem
• The combinatorial complexity of a finite string
• Minimum common string partition problem: hardness and approximations
• Algorithms and Computation
• On the kernelization complexity of string problems
• On the kernelization complexity of string problems
• Crochemore's partitioning on weighted strings and applications
• Minimum common string partition revisited
• Minimum common string partition revisited

Cited in

(4)

• Complexity of a Collision-Aware String Partition Problem and Its Relation to Oligo Design for Gene Synthesis
• The complexity of string partitioning
• Separating strings with small automata
• Computing equality-free string factorisations

This page was built for publication: The Complexity of String Partitioning

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