A generalised degenerate string (GD string) Š is a sequence of n sets of strings of total size N, where the ith set contains strings of the same length ki but this length can vary between different sets. We denote the sum of these lengths k0, k1, . . . , kn-1 by W. This type of uncertain sequence can represent, for example, a gapless multiple sequence alignment of width W in a compact form. Our first result in this paper is an O(N+M)-time algorithm for deciding whether the intersection of two GD strings of total sizes N and M, respectively, over an integer alphabet, is non-empty. This result is based on a combinatorial result of independent interest: although the intersection of two GD strings can be exponential in the total size of the two strings, it can be represented in only linear space. A similar result can be obtained by employing an automata-based approach but its cost is alphabet-dependent. We then apply our string comparison algorithm to compute palindromes in GD strings. We present an O(min{W, n2}N)-time algorithm for computing all palindromes in Š. Furthermore, we show a similar conditional lower bound for computing maximal palindromes in Š. Finally, proof-of-concept experimental results are presented using real protein datasets.

Alzamel, M., Ayad, L., Bernardini, G., Grossi, R., Iliopoulos, C., Pisanti, N., et al. (2018). Degenerate string comparison and applications. In WABI 2018. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing [10.4230/LIPIcs.WABI.2018.21].

Degenerate string comparison and applications

Bernardini, G;
2018

Abstract

A generalised degenerate string (GD string) Š is a sequence of n sets of strings of total size N, where the ith set contains strings of the same length ki but this length can vary between different sets. We denote the sum of these lengths k0, k1, . . . , kn-1 by W. This type of uncertain sequence can represent, for example, a gapless multiple sequence alignment of width W in a compact form. Our first result in this paper is an O(N+M)-time algorithm for deciding whether the intersection of two GD strings of total sizes N and M, respectively, over an integer alphabet, is non-empty. This result is based on a combinatorial result of independent interest: although the intersection of two GD strings can be exponential in the total size of the two strings, it can be represented in only linear space. A similar result can be obtained by employing an automata-based approach but its cost is alphabet-dependent. We then apply our string comparison algorithm to compute palindromes in GD strings. We present an O(min{W, n2}N)-time algorithm for computing all palindromes in Š. Furthermore, we show a similar conditional lower bound for computing maximal palindromes in Š. Finally, proof-of-concept experimental results are presented using real protein datasets.
Si
paper
Degenerate strings; Elastic-degenerate strings; Generalised degenerate strings; Palindromes; String comparison;
Degenerate strings, Elastic-degenerate strings, Generalised degenerate strings, Palindromes, String comparison
English
18th International Workshop on Algorithms in Bioinformatics, WABI 2018
9783959770828
Alzamel, M., Ayad, L., Bernardini, G., Grossi, R., Iliopoulos, C., Pisanti, N., et al. (2018). Degenerate string comparison and applications. In WABI 2018. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing [10.4230/LIPIcs.WABI.2018.21].
Alzamel, M; Ayad, L; Bernardini, G; Grossi, R; Iliopoulos, C; 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/204941
Citazioni
  • Scopus 10
  • ???jsp.display-item.citation.isi??? ND
Social impact