Erdös, Péter L. ;
Ligeti, Péter ;
Sziklai, Péter ;
Torney, David C.
Subwords in reverse-complement order
Abstract
We examine finite words over an alphabet $Gamma={a,ar{a};
b,ar{b}}$ of pairs of letters, where each word $w_1w_2...w_t$
is identical with its {it reverse complement}
$ar{w_t}...ar{w_2}ar{w_1}$ (where $ar{ar{a}}=a,
ar{ar{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.
BibTeX - Entry
@InProceedings{erds_et_al:DSP:2006:785,
author = {P{\'e}ter L. Erd{\"o}s and P{\'e}ter Ligeti and P{\'e}ter Sziklai and David C. Torney},
title = {Subwords in reverse-complement order},
booktitle = {Combinatorial and Algorithmic Foundations of Pattern and Association Discovery},
year = {2006},
editor = {Rudolf Ahlswede and Alberto Apostolico and Vladimir I. Levenshtein},
number = {06201},
series = {Dagstuhl Seminar Proceedings},
ISSN = {1862-4405},
publisher = {Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2006/785},
annote = {Keywords: Reverse complement order, Reconstruction of words, Microarray experiments}
}
|
Keywords: |
|
Reverse complement order, Reconstruction of words, Microarray experiments |
|
Seminar: |
|
06201 - Combinatorial and Algorithmic Foundations of Pattern and Association Discovery
|
|
Documenttype: |
|
InProceedings |
|
Issue date: |
|
2006 |
|
Date of publication: |
|
07.11.2006 |
