RoSA '02 (Rouen, June 6-7, 2002)

Répétitions en tandem avec évolution
Evolutive tandem repeats

Richard GROULT
LIFAR-ABISS, Faculté des Sciences et des Techniques, Université de Rouen, 76821 MONT-SAINT-AIGNAN CEDEX, FRANCE
Joint work with M. Léonard et L. Mouchard

We present an algorithm for detecting a ``new'' type of approximate repeat in texts, named evolutive tandem repeat. An evolutive tandem repeat consists in the concatenation of a series of copies, where every copy might slightly differ from its predecessor. We are presenting in this paper a new O(l.|w|2) algorithm for computing evolutive tandem repeats in a word w, l being the length of a copy. This algorithm relies on the use of equivalence classes and graphs and has been implemented in LEDA.

Retour à la page d'accueil
Back to home page