Cicalese, F. and Erdős, Péter and Lipták, Z. (2012) A linear algorithm for string reconstruction in the reverse complement equivalence model. JOURNAL OF DISCRETE ALGORITHMS, 14. pp. 37-54. ISSN 1570-8667
|
Text
CEL-JDA11.pdf Download (443kB) | Preview |
Abstract
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 Erdos et al. (2006) [6].
| Item Type: | Article |
|---|---|
| Additional Information: | Selected papers from the 21st International Workshop on Combinatorial Algorithms (IWOCA 2010) |
| Uncontrolled Keywords: | Algorithms; INFORMATION THEORY; Subwords; Subsequences; String reconstruction; String algorithms; Reverse complement; Combinatorics on words |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 06 Feb 2014 05:48 |
| Last Modified: | 08 Feb 2014 07:57 |
| URI: | http://real.mtak.hu/id/eprint/9904 |
Actions (login required)
 |
Edit Item |
