Affordable Access

Alignment-free sequence comparison with spaced k-mers

Authors
  • Boden, Marcus
  • Schöneich, Martin
  • Horwege, Sebastian
  • Lindner, Sebastian
  • Leimeister, Chris
  • Morgenstern, Burkhard
Publication Date
Jan 01, 2013
Source
Dagstuhl Research Online Publication Server
Keywords
Language
English
License
Unknown
External links

Abstract

Alignment-free methods are increasingly used for genome analysis and phylogeny reconstruction since they circumvent various difficulties of traditional approaches that rely on multiple sequence alignments. In particular, they are much faster than alignment-based methods. Most alignment-free approaches work by analyzing the k-mer composition of sequences. In this paper, we propose to use 'spaced k-mers', i.e. patterns of deterministic and 'don't care' positions instead of contiguous k-mers. Using simulated and real-world sequence data, we demonstrate that this approach produces better phylogenetic trees than alignment-free methods that rely on contiguous k-mers. In addition, distances calculated with spaced k-mers appear to be statistically more stable than distances based on contiguous k-mers.

Report this publication

Statistics

Seen <100 times