License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2018.21
URN: urn:nbn:de:0030-drops-93236
URL: http://drops.dagstuhl.de/opus/volltexte/2018/9323/
Go to the corresponding LIPIcs Volume Portal


Alzamel, Mai ; Ayad, Lorraine A. K. ; Bernardini, Giulia ; Grossi, Roberto ; Iliopoulos, Costas S. ; Pisanti, Nadia ; Pissis, Solon P. ; Rosone, Giovanna

Degenerate String Comparison and Applications

pdf-format:
LIPIcs-WABI-2018-21.pdf (0.5 MB)


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.

BibTeX - Entry

@InProceedings{alzamel_et_al:LIPIcs:2018:9323,
  author =	{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},
  title =	{{Degenerate String Comparison and Applications}},
  booktitle =	{18th International Workshop on Algorithms in  Bioinformatics (WABI 2018)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-082-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{113},
  editor =	{Laxmi Parida and Esko Ukkonen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9323},
  URN =		{urn:nbn:de:0030-drops-93236},
  doi =		{10.4230/LIPIcs.WABI.2018.21},
  annote =	{Keywords: degenerate strings, generalised degenerate strings, elastic-degenerate strings, string comparison, palindromes}
}

Keywords: degenerate strings, generalised degenerate strings, elastic-degenerate strings, string comparison, palindromes
Seminar: 18th International Workshop on Algorithms in Bioinformatics (WABI 2018)
Issue Date: 2018
Date of publication: 26.07.2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI