2024/02/11 by Md. Hasin Abrar, Paul Medvedev · 1 voice
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Algebra and Logic #DNA and Biological Computing #Rough Sets and Fuzzy Logic
paper · pdf · doi:10.1101/2024.02.08.579510
openalex publication_date 2024/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Abstract Motivation Understanding structural properties of k -mer multisets is crucial to designing space-efficient indices to query them. A potentially novel source of structure can be found in the rank function of a k -mer multiset. In particular, the rank function of a k -mer multiset can be approximated by a piece-wise linear function with very few segments. Such an approximation was shown to speed up suffix array queries and sequence alignment. However, a more comprehensive study of the structure of rank functions of k -mer multisets and their potential applications is lacking. Results We study a measure of a k -mer multiset complexity, which we call the PLA-complexity. The PLA-complexity is the number of segments necessary to approximate the rank function of a k -mer multiset with a piece-wise linear function so that the maximum error is bounded by a predefined threshold. We describe, implement, and evaluate the PLA-index, which is able to construct, compact, and query a piece-wise linear approximation of the k -mer rank function. We examine the PLA-complexity of more than 500 genome spectra and several other genomic multisets. Finally, we show how the PLA-index can be applied to several downstream applications to improve on existing methods: speeding up suffix array queries, decreasing the index memory of a short-read aligner, and decreasing the space of a direct access table of k -mer ranks. Availability The software and reproducibility information is freely available at https://github.com/medvedevgroup/pla-index