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
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.
Type de document :
Article dans une revue
International Journal of Foundations of Computer Science, World Scientific Publishing, 2007
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00179719
Contributeur : Pierre Peterlongo <>
Soumis le : mercredi 24 octobre 2007 - 12:19:38
Dernière modification le : mercredi 16 mai 2018 - 11:23:05
Document(s) archivé(s) le : dimanche 11 avril 2010 - 23:08:06

Fichier

biFactorTree_IJFCS_erratum.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00179719, version 1

Citation

Pierre Peterlongo, Julien Allali, Marie-France Sagot. Indexing gapped-factors using a tree. International Journal of Foundations of Computer Science, World Scientific Publishing, 2007. 〈inria-00179719〉

Partager

Métriques

Consultations de la notice

423

Téléchargements de fichiers

113