Efficiency of Learned Indexes on Genome Spectra

Area of Science:

• Bioinformatics
• Computational Biology
• Data Structures

Background:

• Bioinformatic tools rely on data structures for genomic k-mers.
• Efficient data structures must leverage inherent data patterns.
• Learned indexes offer efficient k-mer multiset rank approximation but lack predictive performance analysis.

Purpose of the Study:

• Develop a novel measure for piecewise-linear approximability of data.
• Introduce Canonical Piecewise Linear approximability (CaPLa) to predict data structure performance.
• Analyze the variability of genomic k-mer patterns.

Main Methods:

• Developed CaPLa based on power-law model deviations.
• Proved CaPLa properties and created an efficient computation algorithm.
• Applied CaPLa to predict space bounds for real-world data structures.

Main Results:

• CaPLa accurately predicts space bounds for data structures on genomic data.
• Empirical analysis of over 500 genomes shows significant CaPLa variation across the tree of life and within genomes.
• Identified factors contributing to genomic k-mer multisets differing from random ones.

Conclusions:

• CaPLa is a robust measure for predicting data structure performance on genomic k-mers.
• Genomic k-mer patterns exhibit substantial variability, impacting data structure efficiency.
• CaPLa provides insights into optimizing bioinformatics tools for diverse genomic datasets.