PLA-complexity of k-mer multisets

MotivationUnderstanding 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. ResultsWe 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. AvailabilityThe software and reproducibility information is freely available at https://github.com/medvedevgroup/pla-index