2026-07-25T00:34:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8951 2024-03-06T10:42:56Z ddc:004 open_access

Dictionary Matching in Elastic-Degenerate Texts with Applications in Searching VCF Files On-line Pissis, Solon P. Retha, Ahmad on-line algorithms algorithms on strings dictionary matching elastic-degenerate string Variant Call Format An elastic-degenerate string is a sequence of n sets of strings of total length N. It has been introduced to represent multiple sequence alignments of closely-related sequences in a compact form. For a standard pattern of length m, pattern matching in an elastic-degenerate text can be solved on-line in time O(nm^2+N) with pre-processing time and space O(m) (Grossi et al., CPM 2017). A fast bit-vector algorithm requiring time O(N * ceil[m/w]) with pre-processing time and space O(m * ceil[m/w]), where w is the size of the computer word, was also presented. In this paper we consider the same problem for a set of patterns of total length M. A straightforward generalization of the existing bit-vector algorithm would require time O(N * ceil[M/w]) with pre-processing time and space O(M * ceil[M/w]), which is prohibitive in practice. We present a new on-line O(N * ceil[M/w])-time algorithm with pre-processing time and space O(M). We present experimental results using both synthetic and real data demonstrating the performance of the algorithm. We further demonstrate a real application of our algorithm in a pipeline for discovery and verification of minimal absent words (MAWs) in the human genome showing that a significant number of previously discovered MAWs are in fact false-positives when a population's variants are considered. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Solon P. Pissis and Ahmad Retha 2018 Is Part Of LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2018.16 urn:nbn:de:0030-drops-89515 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.16 eng https://creativecommons.org/licenses/by/3.0/legalcode