  As high-throughput sequencers become standard equipment outside of sequencing
centers, there is an increasing need for efficient methods for pre-processing
and primary analysis. While a vast literature proposes methods for HTS data
analysis, we argue that significant improvements can still be gained by
exploiting expensive pre-processing steps which can be amortized with savings
from later stages. We propose a method to accelerate and improve read mapping
based on an initial clustering of possibly billions of high-throughput
sequencing reads, yielding clusters of high stringency and a high degree of
overlap. This clustering improves on the state-of-the-art in running time for
small datasets and, for the first time, makes clustering high-coverage human
libraries feasible. Given the efficiently computed clusters, only one
representative read from each cluster needs to be mapped using a traditional
readmapper such as BWA, instead of individually mapping all reads. On human
reads, all processing steps, including clustering and mapping, only require
11%-59% of the time for individually mapping all reads, achieving speed-ups for
all readmappers, while minimally affecting mapping quality. This accelerates a
highly sensitive readmapper such as Stampy to be competitive with a fast
readmapper such as BWA on unclustered reads.
