A linear algorithm for string reconstruction in the reverse complement equivalence model

详细信息	查看全文 | 推荐本文 |

• 作者：Ferdinando Cicalese^a ; ^{cicalese@dia.unisa.it} ; Pé ; ter L. Erd艖s^b ; ^elp@renyi.hu ; Zsuzsanna Liptá ; k^c ; ¹ ; ^{zsuzsa@cebitec.uni-bielefeld.de}
• 关键词：String reconstruction ; Reverse complement ; String algorithms ; Subsequences ; Subwords ; Combinatorics on words
• 刊名：Journal of Discrete Algorithms
• 出版年：2012
• 期刊代码：10_15708667
• 类别：mt
• 出版时间：July, 2012
• 卷：14
• 期：Complete
• 页码：37-54
• 文件大小：353 K

摘要

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) .