Introduction

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/.

Publications

  1. Kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison.
    Cite this
    Leimeister CA, Morgenstern B, 2014-07-01 - Bioinformatics (Oxford, England)

Credits

  1. Chris-André Leimeister
    Developer

    Department of Bioinformatics, Institute of Microbiology and Genetics, Germany

  2. Burkhard Morgenstern
    Investigator

    Department of Bioinformatics, Institute of Microbiology and Genetics, Germany

Community Ratings

UsabilityEfficiencyReliabilityRated By
0 user
Sign in to rate
Summary
AccessionBT003709
Tool TypeApplication
Category
PlatformsLinux/Unix
TechnologiesC++
User InterfaceTerminal Command Line
Download Count0
Country/RegionFrance
Submitted ByBurkhard Morgenstern