Pattern Matching on Elastic-Degenerate Text with Errors

Giulia Bernardini 1 Nadia Pisanti 2, 3 Solon Pissis 4 Giovanna Rosone 2
1 Dipartimento di Matematica [Pisa]
2 Dipartimento di Informatica [Pisa]
3 ERABLE - Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale
Inria Grenoble - Rhône-Alpes
4 Department of Informatics [King's College London]
Abstract : An elastic-degenerate string is a sequence of n sets of strings of total length N. It has been introduced to represent a multiple alignment of several closely-related sequences (e.g. pan-genome) compactly. In this representation, substrings of these sequences that match exactly are collapsed, while in positions where the sequences differ, all possible variants observed at that location are listed. The natural problem that arises is finding all matches of a deterministic pattern of length m in an elastic-degenerate text. There exists an O(nm 2 + N)-time algorithm to solve this problem on-line after a pre-processing stage with time and space O(m). In this paper, we study the same problem under the edit distance model and present an O(k 2 mG + kN)-time and O(m)-space algorithm, where G is the total number of strings in the elastic-degenerate text and k is the maximum edit distance allowed. We also present a simple O(kmG + kN)-time and O(m)-space algorithm for Hamming distance.
Keywords : uncertain strings elastic-degenerate strings degenerate strings pan-genome pattern matching
Type de document :
Communication dans un congrès
SPIRE 2017 - 24th International Symposium on String Processing and Information Retrieval, Sep 2017, Palermo, Italy. Springer, LNCS, 10508, pp.74-90, SPIRE 2017: String Processing and Information Retrieval. 〈http://pages.di.unipi.it/spire2017/〉. 〈10.1007/978-3-319-67428-5_7〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01673585
Contributeur : Marie-France Sagot <>
Soumis le : samedi 30 décembre 2017 - 17:48:50
Dernière modification le : jeudi 19 avril 2018 - 14:24:03

Fichier

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

Identifiants

Collections

INRIA | INRIA2017

Citation

Giulia Bernardini, Nadia Pisanti, Solon Pissis, Giovanna Rosone. Pattern Matching on Elastic-Degenerate Text with Errors. SPIRE 2017 - 24th International Symposium on String Processing and Information Retrieval, Sep 2017, Palermo, Italy. Springer, LNCS, 10508, pp.74-90, SPIRE 2017: String Processing and Information Retrieval. 〈http://pages.di.unipi.it/spire2017/〉. 〈10.1007/978-3-319-67428-5_7〉. 〈hal-01673585〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

48

Téléchargements de fichiers

28

Contact


archive-ouverte@inria.fr