Item

Abstract

Motivation: Sequencing capacity is currently growing more rapidly
than CPU speed, leading to an analysis bottleneck in many genome
projects. Alignment-free sequence analysis methods tend to be
more efficient than their alignment-based counterparts. They may,
therefore, be important in the long run for keeping sequence analysis
abreast with sequencing.
Results: We derive and implement an alignment-free estimator of
the number of pairwise mismatches, πm. Our implementation of πm,
pim, is based on an enhanced suffix array and inherits the superior
time and memory efficiency of this data structure. Simulations
demonstrate that πm is accurate if mutations are distributed randomly
along the chromosome. While real data often deviates from this ideal,
πm remains useful for identifying regions of low genetic diversity using
a sliding window approach. We demonstrate this by applying it to the
complete genomes of 37 strains of Drosophila melanogaster, and to
the genomes of two closely related Drosophila species, D.simulans
and D.sechellia. In both cases, we detect the diversity minimum and
discuss its biological implications.