International Conference Papers

Permanent URI for this collectionhttp://dl.cerist.dz/handle/CERIST/4

Browse

Filters

2017 - 20182

Settings

Subject: search.filters.subject.Matching statistics

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Fast matching statistics in small space
    (Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018-06-27) Belazzougui, Djamal; Cunial, Fabio; Denas, Olgert
    Computing the matching statistics of a string S with respect to a string T on an alphabet of size sigma is a fundamental primitive for a number of large-scale string analysis applications, including the comparison of entire genomes, for which space is a pressing issue. This paper takes from theory to practice an existing algorithm that uses just O(|T|log{sigma}) bits of space, and that computes a compact encoding of the matching statistics array in O(|S|log{sigma}) time. The techniques used to speed up the algorithm are of general interest, since they optimize queries on the existence of a Weiner link from a node of the suffix tree, and parent operations after unsuccessful Weiner links. Thus, they can be applied to other matching statistics algorithms, as well as to any suffix tree traversal that relies on such calls. Some of our optimizations yield a matching statistics implementation that is up to three times faster than a plain version of the algorithm, depending on the similarity between S and T. In genomic datasets of practical significance we achieve speedups of up to 1.8, but our fastest implementations take on average twice the time of an existing code based on the LCP array. The key advantage is that our implementations need between one half and one fifth of the competitor's memory, and they approach comparable running times when S and T are very similar.
  • Thumbnail Image
    Item
    Fast Label Extraction in the CDAWG
    (Springer, 2017-09-06) Belazzougui, Djamal; Cunial, Fabio
    The compact directed acyclic word graph (CDAWG) of a string T of length n takes space proportional just to the number e of right extensions of the maximal repeats of T, and it is thus an appealing index for highly repetitive datasets, like collections of genomes from similar species, in which e grows significantly more slowly than n. We reduce from O(m log ⁡log⁡ n) to O(m) the time needed to count the number of occurrences of a pattern of length m, using an existing data structure that takes an amount of space proportional to the size of the CDAWG. This implies a reduction from O(m log log n+occ) to O(m+occ) in the time needed to locate all the occocc occurrences of the pattern. We also reduce from O(k log ⁡log ⁡n) to O(k) the time needed to read the k characters of the label of an edge of the suffix tree of T, and we reduce from O(m log ⁡log ⁡n) to O(m) the time needed to compute the matching statistics between a query of length m and T, using an existing representation of the suffix tree based on the CDAWG. All such improvements derive from extracting the label of a vertex or of an arc of the CDAWG using a straight-line program induced by the reversed CDAWG.