Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
431629 | Journal of Discrete Algorithms | 2015 | 20 Pages |
Abstract
Given a string w over a finite alphabet Σ and an integer K, can w be partitioned into strings of length at most K, such that there are no collisions? We refer to this question as the string partition problem and show it is NP-complete for various definitions of collision and for a number of interesting restrictions including |Σ|=2|Σ|=2. This establishes the hardness of an important problem in contemporary synthetic biology, namely, oligo design for gene synthesis.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Anne Condon, Ján Maňuch, Chris Thachuk,