On the number of elements to reorder when ...
Type de document :
Article dans une revue scientifique: Article original
Titre :
On the number of elements to reorder when updating a suffix array
Auteur(s) :
Léonard, Martine [Auteur]
Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes [LITIS]
Mouchard, Laurent [Auteur]
Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes [LITIS]
Salson, Mikael [Auteur correspondant]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Bioinformatics and Sequence Analysis [BONSAI]
Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes [LITIS]
Mouchard, Laurent [Auteur]
Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes [LITIS]
Salson, Mikael [Auteur correspondant]

Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Bioinformatics and Sequence Analysis [BONSAI]
Titre de la revue :
Journal of Discrete Algorithms
Pagination :
87-99
Éditeur :
Elsevier
Date de publication :
2012-02
ISSN :
1570-8667
Discipline(s) HAL :
Informatique [cs]/Bio-informatique [q-bio.QM]
Sciences du Vivant [q-bio]/Bio-Informatique, Biologie Systémique [q-bio.QM]
Informatique [cs]/Algorithme et structure de données [cs.DS]
Informatique [cs]/Traitement du texte et du document
Sciences du Vivant [q-bio]/Bio-Informatique, Biologie Systémique [q-bio.QM]
Informatique [cs]/Algorithme et structure de données [cs.DS]
Informatique [cs]/Traitement du texte et du document
Résumé en anglais : [en]
Recently new algorithms appeared for updating the Burrows-Wheeler transform or the suffix array, when the text they index is modified. These algorithms proceed by reordering entries and the number of such reordered entries ...
Lire la suite >Recently new algorithms appeared for updating the Burrows-Wheeler transform or the suffix array, when the text they index is modified. These algorithms proceed by reordering entries and the number of such reordered entries may be as high as the length of the text. However, in practice, these algorithms are faster for updating the Burrows-Wheeler transform or the suffix array than the fastest reconstruction algorithms. In this article we focus on the number of elements to be reordered for real-life texts. We show that this number is related to LCP values and that, on average, L_ave entries are reordered, where L_ave denotes the average LCP value, defined as the average length of the longest common prefix between two consecutive sorted suffixes. Since we know little about the LCP distribution for real-life texts, we conduct experiments on a corpus that consists of DNA sequences and natural language texts. The results show that apart from texts containing large repetitions, the average LCP value is close to the one expected on a random text.Lire moins >
Lire la suite >Recently new algorithms appeared for updating the Burrows-Wheeler transform or the suffix array, when the text they index is modified. These algorithms proceed by reordering entries and the number of such reordered entries may be as high as the length of the text. However, in practice, these algorithms are faster for updating the Burrows-Wheeler transform or the suffix array than the fastest reconstruction algorithms. In this article we focus on the number of elements to be reordered for real-life texts. We show that this number is related to LCP values and that, on average, L_ave entries are reordered, where L_ave denotes the average LCP value, defined as the average length of the longest common prefix between two consecutive sorted suffixes. Since we know little about the LCP distribution for real-life texts, we conduct experiments on a corpus that consists of DNA sequences and natural language texts. The results show that apart from texts containing large repetitions, the average LCP value is close to the one expected on a random text.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.inria.fr/inria-00636066/document
- Accès libre
- Accéder au document
- https://doi.org/10.1016/j.jda.2011.01.002
- Accès libre
- Accéder au document
- https://doi.org/10.1016/j.jda.2011.01.002
- Accès libre
- Accéder au document
- https://hal.inria.fr/inria-00636066/document
- Accès libre
- Accéder au document
- https://doi.org/10.1016/j.jda.2011.01.002
- Accès libre
- Accéder au document
- https://doi.org/10.1016/j.jda.2011.01.002
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- LMS10.pdf
- Accès libre
- Accéder au document
- j.jda.2011.01.002
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- LMS10.pdf
- Accès libre
- Accéder au document