Related Experiment Videos
Optimizing sparse and skew hashing: faster k-mer dictionaries
Giulio Ermanno Pibiri1, Rob Patro2
1DAIS, Ca' Foscari University of Venice, Venice, Italy.
Bioinformatics (Oxford, England)
|July 7, 2026
Summary
This study refines the sparse and skew hashing (SSHash) data structure for efficient k-mer representation in bioinformatics. The improved SSHash offers faster construction and querying, outperforming existing methods for bioinformatics sequence analysis.
Area of Science:
- Bioinformatics
- Computational Biology
- Data Structures
Background:
- Efficiently representing k-mers (short DNA sequences) is crucial for bioinformatics.
- Sparse and skew hashing (SSHash) offers space-effective k-mer storage with fast queries.
- SSHash is order-preserving, aiding compression of associated k-mer data.
Purpose of the Study:
- To accelerate query performance within the SSHash indexing paradigm.
- To enhance SSHash without sacrificing its space efficiency.
- To develop a simpler and faster streaming query algorithm.
Main Methods:
- Proposing a refined data structure for SSHash with optimized lookups and reduced cache misses.
- Implementing a faster algorithm for streaming lookup queries.
- Benchmarking against existing k-mer indexing structures like SBWT and FMSI.
Main Results:
- The refined SSHash demonstrates substantial performance gains in index construction and query speed.
- SSHash significantly outperforms SBWT and FMSI in both building and querying speed.
- SSHash offers competitive space efficiency compared to SBWT and is orders of magnitude faster than FMSI.
Conclusions:
- The enhanced SSHash provides superior performance for k-mer set representation and querying.
- This refined data structure is a valuable tool for bioinformatics applications requiring fast k-mer lookups.
- SSHash represents a significant advancement in efficient bioinformatics data indexing.
Related Concept Videos
01:06Skewness
The measures of central tendency calculated from a data set may not reveal much about its intrinsic distribution. If a plot is made of the data set’s values, the mean and the median may not only differ, but also the plot may have more values on one side of the central tendencies. Such a data set is said to be skewed towards that side.
The longer the tail of the plot on one side, the more skewed it is. The skewness of a data set’s values suggests that the measures of central tendency are...
The longer the tail of the plot on one side, the more skewed it is. The skewness of a data set’s values suggests that the measures of central tendency are...
01:24Microsoft Excel: Finding Central Tendency, Skew, and Kurtosis
Central tendency refers to the central point or typical value of a dataset. It summarizes the data set with a single value that represents the center of its distribution. The three main measures of central tendency are:
Mean: The arithmetic average of all data points. It is calculated by adding all the values together and dividing by the number of values. The mean is sensitive to extreme values (outliers).
Median: The middle value when the data points are arranged in ascending or descending...
Mean: The arithmetic average of all data points. It is calculated by adding all the values together and dividing by the number of values. The mean is sensitive to extreme values (outliers).
Median: The middle value when the data points are arranged in ascending or descending...
01:09Types of Skewness
If the frequency distribution of a data set is more inclined towards smaller or larger values, the distribution is said to be skewed. If data values are skewed to the right, then the distribution is called positively skewed. Conversely, if the plot is skewed to the left, the distribution is called negatively skewed.
For instance, in the middle of a pandemic, the geographical distribution of vaccine coverage may be positively skewed towards populations in the global north countries. However,...
For instance, in the middle of a pandemic, the geographical distribution of vaccine coverage may be positively skewed towards populations in the global north countries. However,...
01:26Optimization Problems
Optimization problems often involve identifying maximum or minimum values under specific constraints. A well-known example is determining the longest horizontal pipe that can be moved around a right-angled corner, where a 3-meter-wide hallway meets a 2-meter-wide hallway. This scenario, common in architectural design and industrial transport, can be understood conceptually through geometric and trigonometric reasoning.To visualize the problem, consider the pipe as a straight line that touches...
01:16Kendall's Tau Test
Kendall's tau test, also known as the Kendall rank coefficient test, is a nonparametric method for assessing association between two variables. This test is particularly useful for identifying significant correlations when the distributions of the sample and population are unknown. Developed in 1938 by the British statistician Sir Maurice George Kendall, the tau coefficient (denoted as τ) serves as a rank correlation coefficient, with values ranging from -1 to +1.
A τ value of +1 indicates that...
A τ value of +1 indicates that...
01:28Methods of Medium Optimization
Optimizing growth media enhances microbial proliferation and maximizes product yield. Statistical experimental design methodologies provide structured and reproducible approaches, offering progressively higher levels of robustness and efficiency.The One-Factor-at-a-Time (OFAT) MethodThe One-Factor-at-a-Time (OFAT) method involves adjusting a single variable while keeping all others constant. However, it cannot detect interactions between variables, often leading to suboptimal outcomes when...