title: andi: fast and accurate estimation of evolutionary distances between closely related genomes.
abstract: BACKGROUND
  A standard approach to classifying sets of genomes is to calculate their pairwise distances. This is difficult for large samples. We have therefore developed an algorithm for rapidly computing the evolutionary distances between closely related genomes.
  
  
  RESULTS
  Our distance measure is based on ungapped local alignments that we anchor through pairs of maximal unique matches of a minimum length. These exact matches can be looked up efficiently using enhanced suffix arrays and our implementation requires approximately only 1 s and 45 MB RAM/Mbase analysed. The pairing of matches distinguishes non-homologous from homologous regions leading to accurate distance estimation. We show this by analysing simulated data and genome samples ranging from 29 Escherichia coli/Shigella genomes to 3085 genomes of Streptococcus pneumoniae.
  
  
  METHODS
  We have implemented the computation of anchor distances in the multithreaded UNIX command-line program andi for ANchor DIstances. C sources and documentation are posted at http://github.com/evolbioinf/andi/
  
  
  BACKGROUND
  haubold@evolbio.mpg.de
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Department of Evolutionary Genetics, Max-Planck-Institute for Evolutionary Biology, 24306 Plön, Germany, Institue for Neuro- and Bioinformatics, Lübeck University, 23562 Lübeck, Germany and Mathematical Stochastics, Mathematical Institute, Freiburg University, Germany.
authors.forename: Bernhard
authors.initials: B
authors.lastname: Haubold
authors.affiliation: Department of Evolutionary Genetics, Max-Planck-Institute for Evolutionary Biology, 24306 Plön, Germany, Institue for Neuro- and Bioinformatics, Lübeck University, 23562 Lübeck, Germany and Mathematical Stochastics, Mathematical Institute, Freiburg University, Germany Department of Evolutionary Genetics, Max-Planck-Institute for Evolutionary Biology, 24306 Plön, Germany, Institue for Neuro- and Bioinformatics, Lübeck University, 23562 Lübeck, Germany and Mathematical Stochastics, Mathematical Institute, Freiburg University, Germany.
authors.forename: Fabian
authors.initials: F
authors.lastname: Klötzl
authors.affiliation: Department of Evolutionary Genetics, Max-Planck-Institute for Evolutionary Biology, 24306 Plön, Germany, Institue for Neuro- and Bioinformatics, Lübeck University, 23562 Lübeck, Germany and Mathematical Stochastics, Mathematical Institute, Freiburg University, Germany.
authors.forename: Peter
authors.initials: P
authors.lastname: Pfaffelhuber
mesh_terms: D000465:Algorithms; D000818:Animals; D005075:Biological Evolution; D030541:Databases, Genetic; D016678:Genome; D023281:Genomics / Q000379:methods*; D006801:Humans; D010802:Phylogeny; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software