Subwords in reverse-complement order

Erdős, Péter and Ligeti, Péter and Sziklai, Péter and Torney, D. C. (2006) Subwords in reverse-complement order. ANNALS OF COMBINATORICS, 10 (4). pp. 415-430. ISSN 0218-0006

[img] Text
Restricted to Repository staff only

Download (196kB) | Request a copy


We examine finite words over an alphabet Gamma = {a; (a) over bar; b, (b) over bar} of pairs of letters, where each word w(1)w(2)(...)w(t) is identified with its reverse complement (w) over bar (...)(t)(w) over bar (2)(w) over bar (1) where (where <(a)double over bar > = a; <(b)double over bar > = b). We seek the smallest k such that every word of length n, composed from G, is uniquely determined by the set of its subwords of length up to k. Our almost sharp result (k similar to 2n/3) is an analogue of a classical result for "normal" words. This problem has its roots in bioinformatics.

Item Type: Article
Uncontrolled Keywords: Reconstruction of words; Levenshtein distance; DNA codes; combinatorics of words
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Depositing User: MTMT SWORD
Date Deposited: 06 Feb 2014 03:39
Last Modified: 06 Feb 2014 03:39

Actions (login required)

Edit Item Edit Item