کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431629 | 688598 | 2015 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The complexity of string partitioning
ترجمه فارسی عنوان
پیچیدگی رشته تقسیم کردن یک ؟؟
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 32, May 2015, Pages 24–43
Journal: Journal of Discrete Algorithms - Volume 32, May 2015, Pages 24–43
نویسندگان
Anne Condon, Ján Maňuch, Chris Thachuk,