Degenerate String Comparison and Applications

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.