Cicalese, F. and Erdős, Péter and Lipták, Z. (2011) Efficient reconstruction of RC-equivalent strings. LECTURE NOTES IN COMPUTER SCIENCE, 6460 L. pp. 349-362. ISSN 0302-9743
|
Text
CicaleseErdosLiptak-IWOCA2010.pdf Download (451kB) | Preview |
Abstract
In the reverse complement (RC) equivalence model, it is not possible to distinguish between a string and its reverse complement. We show that one can still reconstruct a binary string of length n, up to reverse complement, using a linear number of subsequence queries of bounded length. A simple information theoretic lower bound proves the number of queries to be tight. Our result is also optimal w.r.t. the bound on the query length given in [Erdos et al., Ann. of Comb. 2006].
| Item Type: | Article |
|---|---|
| Additional Information: | 21st International Workshop on Combinatorial Algorithms, IWOCA 2010 26 July 2010 through 28 July 2010 London |
| Uncontrolled Keywords: | Combinatorial mathematics; INFORMATION THEORY; Algorithms; Simple informations; Query lengths; LOWER BOUNDS; Equivalence models; EFFICIENT RECONSTRUCTION; Binary string |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 06 Feb 2014 05:37 |
| Last Modified: | 08 Feb 2014 08:02 |
| URI: | http://real.mtak.hu/id/eprint/9907 |
Actions (login required)
 |
Edit Item |
