DynMap: Mapping short reads to multiple related genomes

The constant advances in sequencing technology have redefined the way genome sequencing is performed. They are able to produce millions of short sequences (reads) during a single experiment, and with a much lower cost than previously possible. Due to the dramatic increase in the amount of data generated, efficient algorithms for aligning (mapping) these reads to reference genomes are in great demand, and recently, there has been ample work for publishing such algorithms. In this paper, we study a different version of this problem; mapping these reads to multiple related genomes (e.g. individuals of the same species). We present DynMap, a new practical algorithm, which employs a suitable data structure that takes into account potential inherent genomic variability (replacements, insertions, deletions) between related genomes. Therefore, if a small number of differences occurs within a reference sequence, the already mapped reads can be altered dynamically. The presented experimental results demonstrate that DynMap can match or even outperform the most popular tools in terms of sensitivity, accuracy, and speed.