Kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison.

ABSTRACT:

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

SUBMITTER: Leimeister CA 

PROVIDER: S-EPMC4080746 | biostudies-literature | 2014 Jul

REPOSITORIES: biostudies-literature