Document Open Access Logo

Subwords in reverse-complement order

Authors Péter L. Erdös, Péter Ligeti, Péter Sziklai, David C. Torney

PDF

File

Thumbnail PDF
PDF
DagSemProc.06201.10.pdf
  • Filesize: 185 kB
  • 8 pages

Document Identifiers

Subject Classification

Keywords
  • Reverse complement order
  • Reconstruction of words
  • Microarray experiments

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

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

Author Details

Péter L. Erdös
Péter Ligeti
Péter Sziklai
David C. Torney
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact