Fast and accurate phylogeny reconstruction using filtered spaced-word matches
Open Access
- 4 January 2017
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 33 (7) , 971-979
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/ Supplementary data are available at Bioinformatics online.Keywords
Funding Information
- International Max Planck Research School Molecular Biology, Göttingen.
This publication has 58 references indexed in Scilit:
- MetaCluster 5.0: a two-round binning approach for metagenomic data for low-abundance species in a noisy sampleBioinformatics, 2012
- Separating Significant Matches from Spurious Matches in DNA SequencesJournal of Computational Biology, 2011
- ALF—A Simulation Framework for Genome EvolutionMolecular Biology and Evolution, 2011
- A robust and accurate binning algorithm for metagenomic sequences with arbitrary species abundance ratioBioinformatics, 2011
- A Novel Abundance-Based Algorithm for Binning Metagenomic Sequences Using l -tuplesJournal of Computational Biology, 2011
- Alignment-Free Sequence Comparison (II): Theoretical Power of Comparison StatisticsJournal of Computational Biology, 2010
- Alignment-Free Sequence Comparison (I): Statistics and PowerJournal of Computational Biology, 2009
- Alignment-free genome comparison with feature frequency profiles (FFP) and optimal resolutionsProceedings of the National Academy of Sciences, 2009
- SOAP: short oligonucleotide alignment programBioinformatics, 2008
- The Average Common Substring Approach to Phylogenomic ReconstructionJournal of Computational Biology, 2006