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(nm2 + 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(k2mG+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.

Bernardini, G., Pisanti, N., Pissis, S., Rosone, G. (2017). Pattern matching on elastic-degenerate text with errors. In String Processing and Information Retrieval (pp.74-90). Springer Verlag [10.1007/978-3-319-67428-5_7].

Pattern matching on elastic-degenerate text with errors

Bernardini, G;
2017

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(nm2 + 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(k2mG+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.
Si
paper
Uncertain sequences, Elastic-degenerate strings, Degenerate strings, Pan-genome, Pattern matching
English
International Symposium on String Processing and Information Retrieval, SPIRE 2017 26-29 September
9783319674278
https://link.springer.com/chapter/10.1007%2F978-3-319-67428-5_7
Bernardini, G., Pisanti, N., Pissis, S., Rosone, G. (2017). Pattern matching on elastic-degenerate text with errors. In String Processing and Information Retrieval (pp.74-90). Springer Verlag [10.1007/978-3-319-67428-5_7].
Bernardini, G; Pisanti, N; Pissis, S; Rosone, G
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/204939
Citazioni
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 6
Social impact