Affordable Access

Alignment-free sequence comparison with spaced k-mers

Publication Date
Dagstuhl Research Online Publication Server
  • Alignment-Free Sequence Comparison, Phylogeny Reconstruction
  • Data Processing Computer Science
External links


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.

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times