License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.GCB.2013.24
URN: urn:nbn:de:0030-drops-42334
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4233/
Go to the corresponding OASIcs Volume Portal

Boden, Marcus ; Schöneich, Martin ; Horwege, Sebastian ; Lindner, Sebastian ; Leimeister, Chris ; Morgenstern, Burkhard

Alignment-free sequence comparison with spaced k-mers

pdf-format:
p024-boden.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{boden_et_al:OASIcs:2013:4233,
  author =	{Marcus Boden and Martin Sch{\"o}neich and Sebastian Horwege and Sebastian Lindner and Chris Leimeister and Burkhard Morgenstern},
  title =	{{Alignment-free sequence comparison with spaced k-mers}},
  booktitle =	{German Conference on Bioinformatics 2013},
  pages =	{24--34},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-59-0},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{34},
  editor =	{Tim Bei{\ss}barth and Martin Kollmar and Andreas Leha and Burkhard Morgenstern and Anne-Kathrin Schultz and Stephan Waack and Edgar Wingender},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4233},
  URN =		{urn:nbn:de:0030-drops-42334},
  doi =		{10.4230/OASIcs.GCB.2013.24},
  annote =	{Keywords: Alignment-free sequence comparison, phylogeny reconstruction}
}

Keywords: Alignment-free sequence comparison, phylogeny reconstruction
Collection: German Conference on Bioinformatics 2013
Issue Date: 2013
Date of publication: 09.09.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI