|
|||||
|
|
Subwords in Reverse-Complement Order |
|
| Authors: | Péter L Erd?s Péter Ligeti Péter Sziklai David C Torney |
| Institution: | 1. A. Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, P.O. Box 127, H-1364, Hungary 2. Department of Computer Science, E?tv?s University, Pázmány Péter sétány 1/C, H-1117, Budapest, Hungary 3. Theoretical Biology and Biophysics, Mailstop K710, Los Alamos National Laboratory, Los Alamos, New Mexico, 87545, USA |
| Abstract: | We examine finite words over an alphabet
of pairs of letters, where each word w1w2 ... wt is identified with its reverse complement
where (
). 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.
Received October 19, 2005 |
| Keywords: | 05D05 68R15 |
| 本文献已被 SpringerLink 等数据库收录！ | |