RoSA '02 (Rouen, June 6-7, 2002)
Répétitions en tandem avec évolution
Evolutive tandem repeats
Richard GROULT
Richard.Groult@univ-rouen.fr
http://ric.jalix.org
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