2026-07-20T11:27:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9323 2024-03-06T10:44:02Z ddc:004 open_access

Degenerate String Comparison and Applications Alzamel, Mai Ayad, Lorraine A. K. Bernardini, Giulia Grossi, Roberto Iliopoulos, Costas S. Pisanti, Nadia Pissis, Solon P. Rosone, Giovanna degenerate strings generalised degenerate strings elastic-degenerate strings string comparison palindromes 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mai Alzamel and Lorraine A. K. Ayad and Giulia Bernardini and Roberto Grossi and Costas S. Iliopoulos and Nadia Pisanti and Solon P. Pissis and Giovanna Rosone 2018 Is Part Of LIPIcs, Volume 113, 18th International Workshop on Algorithms in Bioinformatics (WABI 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2018.21 urn:nbn:de:0030-drops-93236 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2018.21 eng https://creativecommons.org/licenses/by/3.0/legalcode