Skip to Main content Skip to Navigation
Journal articles

Indexing gapped-factors using a tree

Pierre Peterlongo 1 Julien Allali 2 Marie-France Sagot 3 
1 SYMBIOSE - Biological systems and models, bioinformatics and sequences
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
3 HELIX - Computer science and genomics
Inria Grenoble - Rhône-Alpes, LBBE - Laboratoire de Biométrie et Biologie Evolutive - UMR 5558
Abstract : We present a data structure to index a specific kind of factors, that is of substrings, called gapped-factors. A gapped-factor is a factor containing a gap that is ignored during the indexation. The data structure presented is based on the suffix tree and indexes all the gapped-factors of a text with a fixed size of gap, and only those. The construction of this data structure is done online in linear time and space. Such a data structure may play an important role in various pattern matching and motif inference problems, for instance in text filtration.
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Pierre Peterlongo Connect in order to contact the contributor
Submitted on : Wednesday, October 24, 2007 - 12:19:38 PM
Last modification on : Saturday, June 25, 2022 - 8:29:28 PM
Long-term archiving on: : Sunday, April 11, 2010 - 11:08:06 PM


Files produced by the author(s)



Pierre Peterlongo, Julien Allali, Marie-France Sagot. Indexing gapped-factors using a tree. International Journal of Foundations of Computer Science, World Scientific Publishing, 2008, 19 (1), pp.71-87. ⟨10.1142/S0129054108005541⟩. ⟨inria-00179719⟩



Record views


Files downloads