ogMapper improves speed and memory for short-sequencing read mapping using a novel guided sparse genome index

Short DNA-read sequencing has become an everyday essential tool in research and clinical setting. Read mapping is a crucial step that consumes large amounts of memory and CPU time, limiting the hardware required and ultimately restricting its applications. The memory required for the genome index can be approximated as βG, where G is the genome size and β is a factor that depends on the implementation. For example, β ≈ 10 for bwa-mem2 or β ≈ 1.9 for minimap2. Here, an indexing strategy is presented in which β can be even less than 1, commonly around 0.5. The indexing strategy relies on "guides," a deterministic, sequence-based pattern for key selection that allows the search to directly access key occurrences. The C++ implementation, available on GitHub as ogMapper (oriGen mapper), is faster than current methods on the T2T human genome, with a negligible reduction in the percentage of reads mapped, and shows memory usage less than 3 GiB even with multiple mapping threads. ogMapper can be used for DNA-Seq reads and has been tested on macOS X, Linux, and Android systems. The ogMapper code is available on GitHub at https://github.com/vtrevino/ogmapper, including installation, compilation, and running instructions. Using sequencing data from simulations and well-characterized samples from Genome in a Bottle, we demonstrate the capabilities of ogMapper by comparing it with other short-read mappers and analyzing possible downstream effects using three variant callers.