Link to bioRxiv paper: http://biorxiv.org/cgi/content/short/2022.10.27.513881v1?rss=1

Authors: Fan, J., Khan, J., Pibiri, G. E., Patro, R.

Abstract: The reference indexing problem for k-mers is to pre-process a collection of reference genomic sequences [R] so that the position of all occurrences of any queried k-mer can be rapidly identified. An efficient and scalable solution to this problem is fundamental for many tasks in bioinformatics. In this work, we introduce the spectrum preserving tiling (SPT), a general representation of [R] that specifies how a set of tiles repeatedly occur to spell out the constituent reference sequences in [R]. By encoding the order and positions where tiles occur, SPTs enable the implementation and analysis of a general class of modular indexes. An index over a SPT decomposes the reference indexing problem for k-mers into: (1) a k-mer-to-tile mapping; and (2) a tile-to-occurrence mapping. Recently introduced work to construct and compactly index k-mer-sets can be used to efficiently implement the k-mer-to-tile mapping. However, implementing the tile-to-occurrence mapping remains prohibitively costly in terms of space. As reference collections become large, the space requirements of the tile-to-occurrence mapping dominates that of the k-mer-to-tile mapping since the former depends on the amount of total sequence while the latter depends on the number of unique k-mers in [R]. To address this, we introduce a class of sampling schemes for SPTs that trade off speed to reduce the size of the tile-to-reference mapping. We implement a practical index with these sampling schemes in the tool: pufferfish2. When indexing 30,000 bacterial genomes, pufferfish2 reduces the size of the tile-to-occurrence mapping from 86.3G to 34.6G while incurring only a 3.6x slowdown when querying k-mers from a sequenced readset. Availability: pufferfish2 implemented in Rust and available at https://github.com/COMBINE-lab/pufferfish2 .

Copy rights belong to original authors. Visit the link for more info

Podcast created by Paper Player, LLC