Subwords in Reverse-Complement Order

摘要

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