ITIdo Tziony

Ido Tziony

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

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Ido Tziony has a total of 39 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Generating Minimum-Density Minimizers

    by Arseny Shur, Ido Tziony, Yaron Orenstein

  • Open Access

    CROP: a feature-independent context-aware method for CRISPR-Cas9 frameshift prediction.

    by Ido Tziony, Yaron Orenstein

    The CRISPR-Cas9 complex has revolutionized genome-editing technologies. By designing a 20 nt-long guide RNA, a Cas9 nuclease can be guided to cleave almost any genomic target site (followed by NGG). The cleavage induces double-stranded DNA breaks, which are then repaired by cellular pathways. Accurate CRISPR-Cas9 repair-outcome prediction is essential for designing guide RNAs with desired genomic effects, such as gene knockout. A central challenge is quantifying the rate of frameshifts, i.e. repair-outcomes that lead to a change in the local length that is not a multiple of three. Previous methods for frameshift-rate prediction were trained on only a few experimental or cellular contexts, mostly relied on manually defined microhomology features, and were limited by sparse features and class labels. We developed CROP, a feature-independent context-aware repair-outcome prediction method. By aggregating specific repair outcomes as Δlength classes, CROP overcomes class sparsity. We designed CROP to work with variable input sequence lengths and output classes to utilize multiple datasets simultaneously. We benchmarked CROP against state-of-the-art repair-outcome prediction methods over 18 datasets, which we curated and standardized from various studies. Across all datasets, CROP outperformed all competing methods in frameshift-rate prediction. We performed cross-experiment and cross-cellular frameshift-rate predictions to investigate the generalizability of repair mechanisms. Finally, we show that CROP learned microhomology principles from raw sequences without explicit feature engineering, establishing an end-to-end architecture for CRISPR-Cas9 repair-outcome prediction that learns from multiple datasets. CROP is available at https://github.com/OrensteinLab/CROP.

  • Open Access

    10-minimizers: a promising class of constant-space minimizers

    by Arseny Shur, Ido Tziony, Yaron Orenstein

    Minimizers are sampling schemes which are ubiquitous in almost any high-throughput sequencing analysis. Assuming a fixed alphabet of size σ , a minimizer is defined by two positive integers k, w and a linear order ρ on k -mers. A sequence is processed by a sliding window algorithm that chooses in each window of length w + k − 1 its minimal k -mer with respect to ρ . A key characteristic of a minimizer is its density, which is the expected frequency of chosen k -mers among all k -mers in a random infinite σ -ary sequence. Minimizers of smaller density are preferred as they produce smaller samples, which lead to reduced runtime and memory usage in downstream applications. Recent studies developed methods to generate minimizers with optimal and near-optimal densities, but they require to explicitly store k -mer ranks in Ω (2 k ) space. While constant-space minimizers exist, and some of them are proven to be asymptotically optimal, no constant-space minimizers was proven to guarantee lower density compared to a random minimizer in the non-asymptotic regime, and many minimizer schemes suffer from long k -mer key-retrieval times due to complex computation. In this paper, we introduce 10-minimizers, which constitute a class of minimizers with promising properties. First, we prove that for every k > 1 and every w ≥ k − 2, a random 10-minimizer has, on expectation, lower density than a random minimizer. This is the first provable guarantee for a class of minimizers in the non-asymptotic regime. Second, we present spacers, which are particular 10-minimizers combining three desirable properties: they are constant-space, low-density, and have small k -mer key-retrieval time. In terms of density, spacers are competitive to the best known constant-space minimizers; in certain ( k, w ) regimes they achieve the lowest density among all known (not necessarily constant-space) minimizers. Notably, we are the first to benchmark constant-space minimizers in the time spent for k -mer key retrieval, which is the most fundamental operation in many minimizers-based methods. Our empirical results show that spacers can retrieve k -mer keys in competitive time (a few seconds per genome-size sequence, which is less than required by random minimizers), for all practical values of k and w . We expect 10-minimizers to improve minimizers-based methods, especially those using large window sizes. We also propose the k -mer key-retrieval benchmark as a standard objective for any new minimizer scheme.

  • Open Access

    Generating minimum-density minimizers

    by Arseny Shur, Ido Tziony, Yaron Orenstein

    Minimizers are sampling schemes which are ubiquitous in almost any high-throughput sequencing analysis. Assuming a fixed alphabet of size σ , a minimizer is defined by two positive integers k, w and a linear order ρ on k -mers. A sequence is processed by a sliding window algorithm that chooses in each window of length w + k − 1 its minimal k -mer with respect to ρ . A key characteristic of a minimizer is its density, which is the expected frequency of chosen k -mers among all k -mers in a random infinite σ -ary sequence. Minimizers of smaller density are preferred as they produce smaller samples, which lead to reduced runtime and memory usage in downstream applications. While the hardness of finding a minimizer of minimum density for given input parameters ( σ, k, w ) is unknown, it has a huge search space of ( σ k )! and there is no known algorithm apart from a trivial brute-force search. In this paper, we tackle the minimum density problem for minimizers. We first formulate this problem as an ILP of size Θ ( wσ w + k ), which has worst-case solution time that is doubly-exponential in ( k + w ) under standard complexity assumptions. Our experiments show that an ILP solver terminates with an optimal solution only for very small k and w . We then present our main method, called OptMini, which computes an optimal minimizer in time and thus is capable of processing large w values. In experiments, OptMini works much faster than the runtime predicts due to several additional tricks shrinking the search space without harming optimality. We use OptMini to compute minimum-density minimizers for ( σ, k ) ∈ {(2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (4, 2)} and w ∈ [2, 3 σ k ], with the exception of certain w -ranges for k = 6 and the single case of k = 5, w = 2. Finally, we derive conclusions and insights regarding the density values as a function of w , patterns in optimal minimizer orders, and the relation between minimum-size universal hitting sets and minimum-density minimizers.

  • Open Access

    CROP: A feature-independent context-aware method for CRISPR-Cas9 frameshift prediction

    by Ido Tziony, Yaron Orenstein

    Motivation: The CRISPR-Cas9 complex has revolutionized genome-editing technologies. By designing a 20 nt-long guide RNA, a Cas9 nuclease can be guided to cleave almost any genomic target site (followed by NGG). The cleavage induces double-stranded DNA breaks, which are then repaired by cellular pathways. Accurate CRISPR-Cas9 repair-outcome prediction is essential for designing guide RNAs with desired genomic effects, such as gene knockout. A central challenge is quantifying the rate of frameshifts, i.e. repair-outcomes that lead to a change in the local length that is not a multiplicity of 3. Previous methods for frameshift-rate prediction were trained on only few experimental or cellular contexts, mostly rely on manually defined microhomology features, and are limited by sparse features and class labels. Results: We developed CROP, the first feature-independent context-aware repair-outcome prediction method. By aggregating specific repair outcomes as Δlength classes, CROP overcomes class sparsity. We designed CROP to work with variable input sequence lengths and output classes in order to utilize multiple datasets simultaneously. We benchmarked CROP against state-of-the-art repair-outcome prediction methods over 18 datasets, which we curated and standardized from various studies. Across all datasets, CROP outperformed all competing methods in frameshift-rate prediction. We performed cross-experiment and cross-cellular frameshift predictions to investigate the generalizability of repair mechanisms. Finally, we show that CROP learned microhomology principles from raw sequences without explicit feature engineering, establishing the first end-to-end architecture for CRISPR-Cas9 repair-outcome prediction which learns from multiple datasets. Availability and implementation: CROP is available at https://github.com/OrensteinLab/CROP .

  • Open Access

    Inferring binding specificities of human transcription factors with the wisdom of crowds

    by Nikita Gryzunov, Dmitry Penzar, Vasilii Kamenets, Valery Vyaltsev, Ivan Kozin, Irina A. Eliseeva, Vladimir Nozdrin, Ilya E. Vorontsov, Sergey Bushuev, Vadim Strekalovskikh, et al.

    DNA motif discovery and, particularly, computational modeling of transcription factor binding motifs, has been a mecca of algorithmic bioinformatics for several decades. Here, we report the results of the largest open community challenge in Inferring BInding Specificities (IBIS), where participants all over the world were invited to construct binding specificity models from multi-assay experimental data for poorly studied human transcription factors. The submissions were rigorously tested against a rich held-out dataset. Benchmarking demonstrated a consistent advantage of properly designed deep learning models over traditional positional weight matrices and other machine learning methods. Yet, the positional weight matrices displayed a surprisingly strong performance out of the box, being only slightly behind the best deep learning models. A post-challenge assessment of a selection of other deep learning methods further solidified this finding. IBIS highlights the power of benchmarking in finding adequate DNA motif representations, emphasizes the pros and cons of various machine learning methods applied to DNA motif modeling, and establishes a rich dataset, benchmarking protocols, and computational framework for a fair cross-platform evaluation of future models of transcription factor binding motifs in DNA sequences.


  • 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

    FiSSC: Finding smallest sequence covers to sets of degenerate reads with applications to RNA editing

    by Ido Tziony, Jonathan Mandl, Kobi Shapira, Eli Eisenberg, Ely Porat, Yaron Orenstein

    High-throughput sequencing (HTS) is the most established technique to measure transcript abundance. HTS reads often contain uncertain or low-quality base calls that introduce ambiguity in determining the underlying sequence. In many applications, these unresolved nucleotides are handled by looking at the consensus sequence of all HTS reads. However, this approach is not applicable where sequence heterogeneity is of biological relevance. To gauge the biological complexity of a set of HTS reads in face of unresolved base calls, one may apply the parsimony principle, i.e., find a smallest set of sequences that cover all ambiguous reads. But, no method to date solves this problem optimally. Here, we present FiSSC, a new method to find a smallest sequence cover of a set of ambiguous reads. We first prove that the problem is NP-hard. We then present filtering steps that preserve optimal solution size, and an integer-linear-programming formulation, which together form FiSSC. We tested FiSSC on A-to-I RNA editing datasets with binary ambiguities. FiSSC outperformed all baseline methods and achieved optimal results in all but one dataset. We expect FiSSC to advance the study of sequence variation and biological complexity of ambiguous reads in various biological domains.

  • 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.