title: Fast and accurate phylogeny reconstruction using filtered spaced-word matches.
abstract: Word-based or 'alignment-free' algorithms are increasingly used for phylogeny reconstruction and genome comparison, since they are much faster than traditional approaches that are based on full sequence alignments. Existing alignment-free programs, however, are less accurate than alignment-based methods.
  
  
  
  We propose Filtered Spaced Word Matches (FSWM) , a fast alignment-free approach to estimate phylogenetic distances between large genomic sequences. For a pre-defined binary pattern of match and don't-care positions, FSWM rapidly identifies spaced word-matches between input sequences, i.e. gap-free local alignments with matching nucleotides at the match positions and with mismatches allowed at the don't-care positions. We then estimate the number of nucleotide substitutions per site by considering the nucleotides aligned at the don't-care positions of the identified spaced-word matches. To reduce the noise from spurious random matches, we use a filtering procedure where we discard all spaced-word matches for which the overall similarity between the aligned segments is below a threshold. We show that our approach can accurately estimate substitution frequencies even for distantly related sequences that cannot be analyzed with existing alignment-free methods; phylogenetic trees constructed with FSWM distances are of high quality. A program run on a pair of eukaryotic genomes of a few hundred Mb each takes a few minutes.
  
  
  
  The program source code for FSWM including a documentation, as well as the software that we used to generate artificial genome sequences are freely available at http://fswm.gobics.de/.
  
  
  
  chris.leimeister@stud.uni-goettingen.de.
  
  
  
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Department of Bioinformatics, University of Göttingen, Institute of Microbiology and Genetics, Goldschmidtstr. 1, 37077?Göttingen, Germany.
authors.forename: Chris-André
authors.initials: CA
authors.lastname: Leimeister
authors.affiliation: Department of Bioinformatics, University of Göttingen, Institute of Microbiology and Genetics, Goldschmidtstr. 1, 37077?Göttingen, Germany.
authors.forename: Salma
authors.initials: S
authors.lastname: Sohrabi-Jahromi
authors.affiliation: Department of Bioinformatics, University of Göttingen, Institute of Microbiology and Genetics, Goldschmidtstr. 1, 37077 Göttingen, Germany.|University of Göttingen, Center for Computational Sciences, Goldschmidtstr. 1, 37077 Göttingen, Germany.
authors.forename: Burkhard
authors.initials: B
authors.lastname: Morgenstern
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D003198:Computer Simulation; D016680:Genome, Bacterial; D018745:Genome, Plant; D023281:Genomics / Q000379:methods; D010802:Phylogeny; D016415:Sequence Alignment; D017422:Sequence Analysis, DNA; D012689:Sequence Homology, Nucleic Acid; D012984:Software; D013997:Time Factors