An alignment-free test for recombination

Motivation: Why recombination? is one of the central questions in
biology. This has led to a host of methods for quantifying recombination
from sequence data. These methods are usually based on
aligned DNA sequences. Here, we propose an efficient alignmentfree
alternative.
Results: Our method is based on the distribution of match lengths,
which we look up using enhanced suffix arrays. By eliminating the
alignment step, the test becomes fast enough for application to
whole bacterial genomes. Using simulations we show that our test
has similar power as established tests when applied to long pairs of
sequences. When applied to 58 genomes of Escherichia coli, we pick
up the strongest recombination signal from a 125 kb horizontal gene
transfer engineered 20 years ago.
Availability and implementation: We have implemented our method
in the command-line program rush. Its C sources and documentation
are available under the GNU General Public License from http://guan
ine.evolbio.mpg.de/rush/.
Contact: haubold@evolbio.mpg.de
Supplementary information: Supplementary data are available at
Bioinformatics online.