Comparing Degenerate Strings

Issue title: A Mosaic of Computational Topics: from Classical to Novel, Special Issue Dedicated to Jetty Kleijn on the Occasion of Her 65th Birthday

Guest editors: Maurice ter Beek, Maciej Koutny and Grzegorz Rozenberg

Article type: Research Article

Authors: Alzamel, Mai^{a; *} | Ayad, Lorraine A.K.^b | Bernardini, Giulia^c | Grossi, Roberto^d | Iliopoulos, Costas S.^e | Pisanti, Nadia^{f; †} | Pissis, Solon P.^g | Rosone, Giovanna^h

Affiliations: [a] Department of Informatics, King’s College London, UK. mai.alzamel@kcl.ac.uk | [b] Department of Informatics, King’s College London, UK. lorraine.ayad@kcl.ac.uk | [c] DISCo, University of Milano - Bicocca, Italy. giulia.bernardini@unimib.it | [d] Department of Computer Science, University of Pisa, Italy. grossi@di.unipi.it | [e] Department of Informatics, King’s College London, UK. costas.iliopoulos@kcl.ac.uk | [f] Department of Computer Science, University of Pisa, Italy. pisanti@di.unipi.it | [g] Life Sciences and Health research group, CWI Amsterdam, the Netherlands. solon.pissis@cwi.nl | [h] Department of Computer Science, University of Pisa, Italy. giovanna.rosone@unipi.it

Correspondence: [†] Address for correspondence: Department of Computer Science, University of Pisa, Italy

Note: [*] Also works: Department of Computer Science, King Saud University, KSA

Abstract: Uncertain sequences are compact representations of sets of similar strings. They highlight common segments by collapsing them, and explicitly represent varying segments by listing all possible options. A generalized degenerate string (GD string) is a type of uncertain sequence. Formally, a 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 by W the sum of these lengths k0, k1, . . . , kn-1. Our main result is an 𝒪(N + M)-time algorithm for deciding whether two GD strings of total sizes N and M, respectively, over an integer alphabet, have a non-empty intersection. 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 linear space. We then apply our string comparison tool to devise a simple algorithm for computing all palindromes in Ŝ in 𝒪(min{W, n2}N)-time. We complement this upper bound by showing a similar conditional lower bound for computing maximal palindromes in Ŝ. We also show that a result, which is essentially the same as our string comparison linear-time algorithm, can be obtained by employing an automata-based approach.

Keywords: degenerate strings, generalized degenerate strings, elastic-degenerate strings, string comparison, palindromes

DOI: 10.3233/FI-2020-1947

Journal: Fundamenta Informaticae, vol. 175, no. 1-4, pp. 41-58, 2020