Erdős, Péter and Ligeti, Péter and Sziklai, Péter and Torney, D. C.
(2006)
*Subwords in reverse-complement order.*
ANNALS OF COMBINATORICS, 10 (4).
pp. 415-430.
ISSN 0218-0006

Text
ELSzT-AoC06.pdf Restricted to Repository staff only Download (196kB) | Request a copy |

## Abstract

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

Item Type: | Article |
---|---|

Uncontrolled Keywords: | Reconstruction of words; Levenshtein distance; DNA codes; combinatorics of words |

Subjects: | Q Science / természettudomány > QA Mathematics / matematika |

SWORD Depositor: | MTMT SWORD |

Depositing User: | MTMT SWORD |

Date Deposited: | 06 Feb 2014 03:39 |

Last Modified: | 06 Feb 2014 03:39 |

URI: | http://real.mtak.hu/id/eprint/9916 |

### Actions (login required)

Edit Item |