General Information
| Description | The k -mismatch average common substring approach to alignment-free sequence comparison |
| Homepage | http://kmacs.gobics.de/ |
Publications
kmacs: the k -mismatch average common substring approach to alignment-free sequence comparison
Motivation:
Alignment-based methods for sequence analysis have various limitations if large datasets are to be analysed. Therefore, alignment-free approaches have become popular in recent years. One of the best known alignment-free methods is the average common substring approach that defines a distance measure on sequences based on the average length of longest common words between them. Herein, we generalize this approach by considering longest common substrings with k mismatches. We present a greedy heuristic to approximate the length of such k -mismatch substrings, and we describe kmacs , an efficient implementation of this idea based on generalized enhanced suffix arrays.
Results:
To evaluate the performance of our approach, we applied it to phylogeny reconstruction using a large number of DNA and protein sequence sets. In most cases, phylogenetic trees calculated with kmacs were more accurate than trees produced with established alignment-free methods that are based on exact word matches. Especially on protein sequences, our method seems to be superior. On simulated protein families, kmacs even outperformed a classical approach to phylogeny reconstruction using multiple alignment and maximum likelihood.
Availability and implementation:
kmacs is implemented in C++, and the source code is freely available at http://kmacs.gobics.de/
Contact:
chris.leimeister@stud.uni-goettingen.de
Supplementary information:
Supplementary data are available at Bioinformatics online.
Related Tools
SBARS
Published February 2014
Fast creation of dotplots for DNA sequences on different scales using GA-,GC-content
slaMEM
Published December 2013
Efficient retrieval of maximal exact matches using a sampled LCP array
AlignBucket
Published July 2015
A tool to speed up ‘all-against-all’ protein sequence alignments optimizing length constraints
DLTree
Published March 2017
Efficient and accurate phylogeny reconstruction using the dynamical language method
FAIR Evaluation
Sorry, you must be signed in to evaluate this object.
