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

Text ELSzT-AoC06.pdf Restricted to Repository staff only Download (196kB) | Request a copy

Abstract

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.

Actions (login required)

Edit Item