Fast alignment-free sequence comparison using spaced-word frequencies.

ABSTRACT:

Motivation

Alignment-free methods for sequence comparison are increasingly used for genome analysis and phylogeny reconstruction; they circumvent various difficulties of traditional alignment-based approaches. In particular, alignment-free methods are much faster than pairwise or multiple alignments. They are, however, less accurate than methods based on sequence alignment. Most alignment-free approaches work by comparing the word composition of sequences. A well-known problem with these methods is that neighbouring word matches are far from independent.

Results

To reduce the statistical dependency between adjacent word matches, we propose to use 'spaced words', defined by patterns of 'match' and 'don't care' positions, for alignment-free sequence comparison. We describe a f

SUBMITTER: Leimeister CA 

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

REPOSITORIES: biostudies-literature