Related Experiment Video
Updated: Feb 14, 2026
03:53
Author Spotlight: Advancements in Multiplex Detection of Respiratory Viruses
Published on: November 10, 2023
2.0K
Squeakr: an exact and approximate k-mer counting system.
Prashant Pandey1, Michael A Bender1, Rob Johnson1,2
1Department of Computer Science, Stony Brook University, Stony Brook, NY 11790, USA.
Bioinformatics (Oxford, England)
|February 15, 2018
Summary
Squeakr, a new system using counting quotient filters, efficiently represents k-mer multisets for high-throughput sequencing data. It offers faster counting and querying, improving downstream bioinformatics analyses.
Area of Science:
- Bioinformatics
- Computational Biology
- Data Structures
Background:
- k-mer-based algorithms are crucial for high-throughput sequencing data analysis.
- Existing methods use diverse k-mer representations and data structures, leading to inefficiencies.
- Tasks include k-mer counting, error correction, assembly, and quantification.
Purpose of the Study:
- To introduce Squeakr (Simple Quotient filter-based Exact and Approximate Kmer Representation), a novel system for k-mer counting and multiset representation.
- To leverage the counting quotient filter for efficient and accurate k-mer data handling.
- To demonstrate Squeakr's utility in downstream bioinformatics applications.
Main Methods:
- Developed Squeakr based on the counting quotient filter, an approximate membership query data structure.
- Implemented a system for k-mer counting and multiset representation.
- Evaluated Squeakr's performance against state-of-the-art methods for counting and querying workloads.
Main Results:
- Squeakr achieves 2×-4.3× speedup in counting and querying compared to state-of-the-art methods.
- It utilizes 1.5×-4.3× less memory, demonstrating significant memory efficiency.
- Squeakr provides order-of-magnitude faster point queries for k-mer abundance and supports dynamic k-mer operations.
Conclusions:
- Squeakr offers an efficient, memory-saving solution for representing and querying k-mer multisets.
- Its performance advantages make it suitable for various high-throughput sequencing data analysis tasks.
- The system's capabilities facilitate downstream analyses like de Bruijn graph traversal.
Related Concept Videos
01:08Fisher's Exact Test
1.2K
Fisher's exact test is a statistical significance test widely used to analyze 2x2 contingency tables, particularly in situations where sample sizes are small. Unlike the chi-squared test, which approximates P-values and assumes minimum expected frequencies of at least five in each cell, Fisher's exact test calculates the exact probability (P-value) of observing the data or more extreme results under the null hypothesis. This feature makes it especially valuable when the assumptions of...
1.2K
01:24Approximate Integration
59
In many practical and theoretical contexts, the exact value of a definite integral may be inaccessible. This limitation typically arises when the antiderivative of a function is either unknown or cannot be expressed in a closed mathematical form. Alternatively, it can occur when a function is defined not by a formula but by a finite set of empirical data points, such as those collected during experiments. In these cases, approximate integration techniques provide a valuable solution.One of the...
59
01:26Linearization and Approximation
77
Linearization is a mathematical technique used to approximate complex, nonlinear functions with simpler linear models in the vicinity of a chosen reference point. The method is based on the idea that, although a function may be difficult to evaluate exactly, its behavior near a specific input value can often be closely approximated by the tangent line at that point. This approach is particularly useful when small deviations from a known value are involved.Consider the square root function, for...
77
01:29Application of Linearization and Approximation
105
A drone flying through complex terrain often relies on more than one sensing method to estimate small changes in altitude. Along with direct measurements, air pressure provides a useful indirect indicator of vertical movement. Atmospheric pressure decreases as altitude increases, and this relationship is commonly described using an exponential model. Although accurate, converting pressure measurements into altitude values requires calculations that are too complex to perform repeatedly during...
105
01:28Accuracy, limits, and approximation
1.3K
Accuracy, limits, and approximations are common in many fields, especially in engineering calculations. These concepts are imperative for ensuring that a given value is as close as possible to its true value.
Accuracy is defined as the closeness of the measured value to the true or actual value. In engineering mechanics, repeated measurements are taken during theoretical or experimental analyses to ensure that the result is precise and accurate.
The accuracy of any solution is based on the...
Accuracy is defined as the closeness of the measured value to the true or actual value. In engineering mechanics, repeated measurements are taken during theoretical or experimental analyses to ensure that the result is precise and accurate.
The accuracy of any solution is based on the...
1.3K
01:26Linear Approximation in Frequency Domain
393
Linear systems are characterized by two main properties: superposition and homogeneity. Superposition allows the response to multiple inputs to be the sum of the responses to each individual input. Homogeneity ensures that scaling an input by a scalar results in the response being scaled by the same scalar.
In contrast, nonlinear systems do not inherently possess these properties. However, for small deviations around an operating point, a nonlinear system can often be approximated as linear....
In contrast, nonlinear systems do not inherently possess these properties. However, for small deviations around an operating point, a nonlinear system can often be approximated as linear....
393