Longest repeated motif with a block of don't cares

Maxime Crochemore; Costas S. Iliopoulos; Manal Mohamed; Marie-France Sagot

Longest repeated motif with a block of don't cares

Maxime Crochemore ^{1, 2} Costas S. Iliopoulos ² Manal Mohamed ² Marie-France Sagot ³

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

2 Department of Computer Science [London]

3 Baobab

PEGASE - Département PEGASE [LBBE]

Abstract : We introduce an algorithm for extracting all longest repeats with k don’t cares from a given sequence. Such repeats are composed of two parts separated by a block of k don’t care symbols. The algorithm uses suffix trees to fulfill this task and relies on the ability to answer the lowest common ancestor queries in constant time. It requires O(n log n) time in the worst-case.

Document type :

Conference papers

Domain :

Computer Science [cs] / Data Structures and Algorithms [cs.DS]

Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00619983
Contributor : Maxime Crochemore <>
Submitted on : Friday, December 18, 2015 - 9:32:47 AM
Last modification on : Thursday, April 18, 2019 - 2:43:26 PM
Long-term archiving on : Saturday, March 19, 2016 - 11:40:40 AM

LATIN2004.pdf

Files produced by the author(s)

Longest repeated motif with a block of don't cares

File

Identifiers

Collections

Citation

Export

Metrics

385

79

Contact

Longest repeated motif with a block of don't cares

File

Identifiers

Collections

Citation

Export

Share

Metrics

385

79

Contact