Degenerate String Comparison and Applications

Abstract : A generalised degenerate string (GD string) S^ is a sequence of n sets of strings of total size N, where the ith set contains strings of the same length k_i but this length can vary between different sets. We denote the sum of these lengths k_0, k_1,...,k_{n-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,n^2}N)-time algorithm for computing all palindromes in S^. Furthermore, we show a similar conditional lower bound for computing maximal palindromes in S^. Finally, proof-of-concept experimental results are presented using real protein datasets.
Type de document :
Communication dans un congrès
WABI 2018 - 18th Workshop on Algorithms in Bioinformatics, Aug 2018, Helsinki, Finland. 113, pp.1-14, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. 〈10.4230/LIPIcs.WABI.2018.21〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01964706
Contributeur : Marie-France Sagot <>
Soumis le : dimanche 23 décembre 2018 - 12:07:01
Dernière modification le : jeudi 7 février 2019 - 16:31:39

Fichier

LIPIcs-WABI-2018-21.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Mai Alzamel, Lorraine Ayad, Giulia Bernardini, Roberto Grossi, Costas Iliopoulos, et al.. Degenerate String Comparison and Applications. WABI 2018 - 18th Workshop on Algorithms in Bioinformatics, Aug 2018, Helsinki, Finland. 113, pp.1-14, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. 〈10.4230/LIPIcs.WABI.2018.21〉. 〈hal-01964706〉

Partager

Métriques

Consultations de la notice

6

Téléchargements de fichiers

81