کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431641 | 688602 | 2012 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A linear algorithm for string reconstruction in the reverse complement equivalence model
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A linear algorithm for string reconstruction in the reverse complement equivalence model A linear algorithm for string reconstruction in the reverse complement equivalence model](/preview/png/431641.png)
چکیده انگلیسی
In the reverse complement equivalence model, it is not possible to distinguish a string from its reverse complement. We show that one can still reconstruct a string of length n, up to reverse complement, using a linear number of subsequence queries of bounded length. We first give the proof for strings over a binary alphabet, and then extend it to arbitrary finite alphabets. A simple information theoretic lower bound proves the number of queries to be asymptotically tight. Furthermore, our result is optimal w.r.t. the bound on the query length given in Erdős et al. (2006) [6].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 14, July 2012, Pages 37–54
Journal: Journal of Discrete Algorithms - Volume 14, July 2012, Pages 37–54
نویسندگان
Ferdinando Cicalese, Péter L. Erdős, Zsuzsanna Lipták,