The complexity of string partitioning
The complexity of string partitioning
复制标题
字符串分区的复杂性
DOI：
10.1007/978-3-642-31265-6_13
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Chris Thachuk
中科院分区：
文献类型：
--
作者：
A. Condon;Ján Manuch;Chris Thachuk
给定一个有限字母表Σ上的字符串w和一个整数K，是否可以将w分割成至多K个长度的字符串，使得没有冲突？我们将这个问题称为字符串划分问题，并证明了对于碰撞的各种定义和一些有趣的限制，包括|Σ|=2，它是NP完全的。这确立了当代合成生物学中的一个重要问题的难度，即用于基因合成的寡聚设计。
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. This establishes the hardness of an important problem in contemporary synthetic biology, namely, oligo design for gene synthesis.