SGShay Golan

Shay Golan

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Shay Golan has a total of 24 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • String problems in the congested clique model

    by Shay Golan, Matan Kraus

  • Open Access

    GreedyMini: generating low-density DNA minimizers

    by Shay Golan, Ido Tziony, Matan Kraus, Yaron Orenstein, Arseny Shur

    Motivation: Minimizers are the most popular k-mer selection scheme in algorithms and data structures analyzing high-throughput sequencing (HTS) data. In a minimizer scheme, the smallest k-mer by some predefined order is selected as the representative of a sequence window containing w consecutive k-mers, which results in overlapping windows often selecting the same k-mer. Minimizers that achieve the lowest frequency of selected k-mers over a random DNA sequence, termed the expected density, are desired for improved performance of HTS analyses. Yet, no method to date exists to generate minimizers that achieve minimum expected density. Moreover, for k and w values used by common HTS algorithms and data structures, there is a gap between densities achieved by existing selection schemes and the theoretical lower bound. Results: We developed GreedyMini, a toolkit of methods to generate minimizers with low expected or particular density, to improve minimizers, to extend minimizers to larger alphabets, k, and w, and to measure the expected density of a given minimizer efficiently. We demonstrate over various combinations of k and w values, including those of popular HTS methods, that GreedyMini can generate DNA minimizers that achieve expected densities very close to the lower bound, and both expected and particular densities much lower compared to existing selection schemes. Moreover, we show that GreedyMini’s k-mer rank-retrieval time is comparable to common k-mer hash functions. We expect GreedyMini to improve the performance of many HTS algorithms and data structures and advance the research of k-mer selection schemes. Availability and implementation: The toolkit, its source code, and precomputed minimizers for a variety of (k,w) pairs are available via https://github.com/OrensteinLab/GreedyMini.


  • Open Access

    GreedyMini: Generating low-density DNA minimizers

    by Shay Golan, Ido Tziony, Matan Kraus, Yaron Orenstein, Arseny Shur

    Minimizers is the most popular k -mer selection scheme in algorithms and data structures analyzing high-throughput sequencing (HTS) data. In a minimizers scheme, the smallest k -mer by some predefined order is selected as the representative of a sequence window containing w consecutive k -mers, which results in overlapping windows often selecting the same k -mer. Minimizers that achieve the lowest frequency of selected k -mers over a random DNA sequence, termed the expected density, are desired for improved performance of HTS analyses. Yet, no method to date exists to generate minimizers that achieve minimum expected density. Moreover, for k and w values used by common HTS algorithms and data structures there is a gap between the densities achieved by existing selection schemes and a recent theoretical lower bound. Here, we present GreedyMini , a toolkit of methods to generate minimizers with low expected or particular density, to improve minimizers, to extend minimizers to larger alphabets, k , and w , and to measure the expected density of a given minimizer efficiently. We demonstrate over various combinations of k and w values, including those of popular HTS methods, that GreedyMini can generate DNA minimizers that achieve expected densities very close to the lower bound, and both expected and particular densities much lower compared to existing selection schemes. Additionally, we show that the k -mer rank-retrieval time by GreedyMini is comparable to that of common k -mer hash functions. We expect GreedyMini to improve the performance of many HTS algorithms and data structures and advance the research of k -mer selection schemes.


  • Burst Edit Distance

    by Itai Boneh, Shay Golan, Avivit Levy, Ely Porat, B. Riva Shalom


  • Open Access

    An Improved Algorithm for The k -Dyck Edit Distance Problem

    by Dvir Fried, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat, Tatiana Starikovskaya

    A Dyck sequence is a sequence of opening and closing parentheses (of various types) that is balanced. The Dyck edit distance of a given sequence of parentheses S is the smallest number of edit operations (insertions, deletions, and substitutions) needed to transform S into a Dyck sequence. We consider the threshold Dyck edit distance problem, where the input is a sequence of parentheses S and a positive integer k , and the goal is to compute the Dyck edit distance of S only if the distance is at most k , and otherwise report that the distance is larger than k . Backurs and Onak [PODS’16] showed that the threshold Dyck edit distance problem can be solved in O ( n + k 16 ) time. In this work, we design new algorithms for the threshold Dyck edit distance problem which costs O ( n + k 4.544184 ) time with high probability or O ( n + k 4.853059 ) deterministically. Our algorithms combine several new structural properties of the Dyck edit distance problem, a refined algorithm for fast (min, +) matrix product, and a careful modification of ideas used in Valiant’s parsing algorithm.


  • Open Access

    Approximating text-to-pattern Hamming distances

    by Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat

    We revisit a fundamental problem in string matching: given a pattern of length m and a text of length n, both over an alphabet of size σ, compute the Hamming distance (i.e., the number of mismatches) between the pattern and the text at every location. Several randomized (1+ε)-approximation algorithms have been proposed in the literature (e.g., by Karloff (Inf. Proc. Lett., 1993), Indyk (FOCS 1998), and Kopelowitz and Porat (SOSA 2018)), with running time of the form O(ε−O(1)nlognlogm), all using fast Fourier transform (FFT). We describe a simple randomized (1+ε)-approximation algorithm that is faster and does not need FFT. Combining our approach with additional ideas leads to numerous new results (all Monte-Carlo randomized) in different settings: (1) We design the first truly linear-time approximation algorithm for constant ; the running time is O(ε−2n). In fact, the time bound can be made slightly sublinear in n if the alphabet size σ is small (by using bit packing tricks). (2) We apply our approximation algorithms to design a faster exact algorithm computing all Hamming distances up to a threshold k; its runtime of O(n + min(nk√logm/√m,nk2/m)) improves upon previous results by logarithmic factors and is linear for k≤ √m. (3) We alternatively design approximation algorithms with better ε-dependence, by using fast rectangular matrix multiplication. In fact, the time bound is O(npolylogn) when the pattern is sufficiently long, i.e., m≥ ε−c for a specific constant c. Previous algorithms with the best ε-dependence require O(ε−1npolylogn) time. (4) When k is not too small, we design a truly sublinear-time algorithm to find all locations with Hamming distance approximately (up to a constant factor) less than k, in time O((n/kΩ(1)+occ)no(1)) time, where occ is the output size. The algorithm leads to a property tester for pattern matching that costs O((δ−1/3n2/3 + δ−1n/m) n) time and, with high probability, returns true if an exact match exists and false if the Hamming distance is more than δ m at every location. (5) We design a streaming algorithm that approximately computes the Hamming distance for all locations with the distance approximately less than k, using O(ε−2√kn) space. Previously, streaming algorithms were known for the exact problem with O(kn) space (which is tight up to the polylogn factor) or for the approximate problem with O(ε−O(1)√mpolylogn) space. For the special case of k=m, we improve the space usage to O(ε−1.5√mpolylogn).


  • Open Access

    Time-Space Tradeoffs for Finding a Long Common Substring

    by Stav Ben-Nun, Shay Golan, Tomasz Kociumaka, Matan Kraus

    We consider the problem of finding, given two documents of total length $n$, a longest string occurring as a substring of both documents. This problem, known as the Longest Common Substring (LCS) problem, has a classic $O(n)$-time solution dating back to the discovery of suffix trees (Weiner, 1973) and their efficient construction for integer alphabets (Farach-Colton, 1997). However, these solutions require $\Theta(n)$ space, which is prohibitive in many applications. To address this issue, Starikovskaya and Vildh{\o}j (CPM 2013) showed that for $n^{2/3} \le s \le n^{1-o(1)}$, the LCS problem can be solved in $O(s)$ space and $O(\frac{n^2}{s})$ time. Kociumaka et al. (ESA 2014) generalized this tradeoff to $1 \leq s \leq n$, thus providing a smooth time-space tradeoff from constant to linear space. In this paper, we obtain a significant speed-up for instances where the length $L$ of the sought LCS is large. For $1 \leq s \leq n$, we show that the LCS problem can be solved in $O(s)$ space and $\tilde{O}(\frac{n^2}{L\cdot s}+n)$ time. The result is based on techniques originating from the LCS with Mismatches problem (Flouri et al., 2015; Charalampopoulos et al., CPM 2018), on space-efficient locally consistent parsing (Birenzwige et al., SODA 2020), and on the structure of maximal repetitions (runs) in the input documents.

  • Open Access

    The Streaming k-Mismatch Problem: Tradeoffs between Space and Total Time

    by Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat

    We revisit the $k$-mismatch problem in the streaming model on a pattern of length $m$ and a streaming text of length $n$, both over a size-$\sigma$ alphabet. The current state-of-the-art algorithm for the streaming $k$-mismatch problem, by Clifford et al. [SODA 2019], uses $\tilde O(k)$ space and $\tilde O\big(\sqrt k\big)$ worst-case time per character. The space complexity is known to be (unconditionally) optimal, and the worst-case time per character matches a conditional lower bound. However, there is a gap between the total time cost of the algorithm, which is $\tilde O(n\sqrt k)$, and the fastest known offline algorithm, which costs $\tilde O\big(n + \min\big(\frac{nk}{\sqrt m},\sigma n\big)\big)$ time. Moreover, it is not known whether improvements over the $\tilde O(n\sqrt k)$ total time are possible when using more than $O(k)$ space. We address these gaps by designing a randomized streaming algorithm for the $k$-mismatch problem that, given an integer parameter $k\le s \le m$, uses $\tilde O(s)$ space and costs $\tilde O\big(n+\min\big(\frac {nk^2}m,\frac{nk}{\sqrt s},\frac{\sigma nm}s\big)\big)$ total time. For $s=m$, the total runtime becomes $\tilde O\big(n + \min\big(\frac{nk}{\sqrt m},\sigma n\big)\big)$, which matches the time cost of the fastest offline algorithm. Moreover, the worst-case time cost per character is still $\tilde O\big(\sqrt k\big)$.