Skip to Main content Skip to Navigation
Conference papers

Maximal Repetitions and Application to DNA sequences

Mathieu Giraud 1 Gregory Kucherov 2
2 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper we describe an implementation of Main-Kolpakov-Kucherov algorithm \cite{KolpakovKucherovFOCS99} of linear-time search for maximal repetitions in sequences. We first present a theoretical background and sketch main components of the method. We also discuss how the method can be generalized to finding approximate repetitions. Then we discuss implementation decisions and present test examples of running the programs on real DNA data.
Document type :
Conference papers
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Thursday, October 19, 2006 - 9:11:58 AM
Last modification on : Friday, February 4, 2022 - 3:31:28 AM
Long-term archiving on: : Wednesday, March 29, 2017 - 12:59:20 PM


  • HAL Id : inria-00107854, version 1



Mathieu Giraud, Gregory Kucherov. Maximal Repetitions and Application to DNA sequences. Journées Ouvertes : Biologie, Informatique et Mathématiques - JOBIM'2000, 2000, Montpellier/France, pp.165--172. ⟨inria-00107854⟩



Record views


Files downloads