Efficiency of Learned Indexes on Genome Spectra
Md Hasin Abrar1, Paul Medvedev1,2,3, Giorgio Vinciguerra4
1Department of Computer Science and Engineering, Penn State, University Park, PA, USA.
Lipics : Leibniz International Proceedings in Informatics
|April 15, 2026
Summary
We introduce CaPLa, a new measure for data structure performance on genomic k-mers. CaPLa predicts efficiency by analyzing data patterns, improving bioinformatics tool design for large datasets.
Area of Science:
- Bioinformatics
- Computational Biology
- Data Structures
Background:
- Genomic data structures rely on patterns in k-mer multisets for efficiency.
- Learned indexes approximate data functions but lack predictive theoretical analysis.
- Practical performance of learned indexes is hard to predict from worst-case analysis.
Purpose of the Study:
- Develop a novel measure, CaPLa, for piecewise-linear approximability of genomic k-mer multisets.
- Enable accurate prediction of space bounds for bioinformatics data structures.
- Understand the variability of data patterns across genomes.
Main Methods:
- Introduced CaPLa (Canonical Piecewise Linear approximability) based on power-law models and deviations.
- Developed an efficient algorithm for CaPLa computation.
- Analyzed over 500 genomes using CaPLa to assess its predictive power and variability.
Main Results:
- CaPLa accurately predicts space bounds for data structures on real genomic data.
- Empirical analysis revealed wide variation in CaPLa across the tree of life and within genomes.
- Identified factors contributing to the non-random nature of genomic k-mer multisets.
Conclusions:
- CaPLa provides a robust measure for predicting the performance of learned indexes on genomic data.
- Understanding k-mer multiset approximability is crucial for efficient bioinformatics tool development.
- Genomic data exhibits unique patterns that CaPLa effectively quantifies.
Related Concept Videos
02:54Evolutionary Relationships through Genome Comparisons
7.3K
Genome comparison is one of the excellent ways to interpret the evolutionary relationships between organisms. The basic principle of genome comparison is that if two species share a common feature, it is likely encoded by the DNA sequence conserved between both species. The advent of genome sequencing technologies in the late 20th century enabled scientists to understand the concept of conservation of domains between species and helped them to deduce evolutionary relationships across diverse...
7.3K
02:05Gene Evolution - Fast or Slow?
8.4K
The genomes of eukaryotes are punctuated by long stretches of sequence which do not code for proteins or RNAs. Although some of these regions do contain crucial regulatory sequences, the vast majority of this DNA serves no known function. Typically, these regions of the genome are the ones in which the fastest change, in evolutionary terms, is observed, because there is typically little to no selection pressure acting on these regions to preserve their sequences.
In contrast, regions which code...
In contrast, regions which code...
8.4K
01:29Modern Molecular Taxonomy
868
Advancements in molecular biology have revolutionized the identification and characterization of bacteria, with multiple methods leveraging DNA sequencing for enhanced precision. As sequencing technologies improve and costs decline, these approaches are increasingly used in clinical, environmental, and evolutionary studies.Multilocus Sequence Typing (MLST) examines several housekeeping genes, essential chromosomal genes encoding cellular functions, to distinguish strains. Approximately...
868
02:51Multi-species Conserved Sequences
5.0K
Next-generation sequencing technologies have created large genomic databases of a variety of animals and plants. Ever since the human genome project was completed, scientists studied the genome of primates, mammals, and other phylogenetically distant living beings. Such large-scale studies have provided new insights into the evolutionary relationship between organisms.
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved...
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved...
5.0K
01:02¹H NMR: Interpreting Distorted and Overlapping Signals
1.8K
Spin systems where the difference in chemical shifts of the coupled nuclei is greater than ten times J are called first-order spin systems. These nuclei are weakly coupled, and their chemical shifts and coupling constant can generally be estimated from the well-separated signals in the spectrum.
As Δν decreases and the signals move closer, the doublets appear increasingly distorted. The intensities of the inner lines increase at the cost of those of the outer lines as the signals are...
As Δν decreases and the signals move closer, the doublets appear increasingly distorted. The intensities of the inner lines increase at the cost of those of the outer lines as the signals are...
1.8K
03:00Next-generation Sequencing
102.0K
The first human genome sequencing project cost $2.7 billion and was declared complete in 2003, after 15 years of international cooperation and collaboration between several research teams and funding agencies. Today, with the advent of next-generation sequencing technologies, the cost and time of sequencing a human genome have dropped over 100 fold.
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features....
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features....
102.0K