DagSemProc.06201.10.pdf
- Filesize: 185 kB
- 8 pages
Document
Subwords in reverse-complement order
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 6201
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2006-11-07
Cite As Get BibTex
Péter L. Erdös, Péter Ligeti, Péter Sziklai, and David C. Torney. Subwords in reverse-complement order. In Combinatorial and Algorithmic Foundations of Pattern and Association Discovery. Dagstuhl Seminar Proceedings, Volume 6201, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
https://doi.org/10.4230/DagSemProc.06201.10
Abstract
We examine finite words over an alphabet $Gamma={a,bar{a};b,bar{b}}$ of pairs of letters, where each word $w_1w_2...w_t$ is identical with its {it reverse complement} $bar{w_t}...bar{w_2}bar{w_1}$ (where $bar{bbar{a}}=a,bar{bar{b}}=b$). We seek the smallest $k$ such that every word of length $n,$ composed from $Gamma$, is uniquely determined by the set of its subwords of length up to $k$. Our almost sharp result ($ksim 2n/3$) is an analogue of a classical result for ``normal'' words.
This classical problem originally was posed by M.P. Sch"utzenberger and I. Simon, and gained a considerable interest for several researchers, foremost by Vladimir Levenshtein.
Our problem has its roots in bioinformatics.
Subject Classification
Keywords
- Reverse complement order
- Reconstruction of words
- Microarray experiments
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads