2026-08-10T22:21:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4233 2024-03-06T10:29:22Z ddc:004 open_access

Alignment-free sequence comparison with spaced k-mers Boden, Marcus Schöneich, Martin Horwege, Sebastian Lindner, Sebastian Leimeister, Chris Morgenstern, Burkhard Alignment-free sequence comparison phylogeny reconstruction 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marcus Boden and Martin Schöneich and Sebastian Horwege and Sebastian Lindner and Chris Leimeister and Burkhard Morgenstern 2013 Is Part Of OASIcs, Volume 34, German Conference on Bioinformatics 2013 InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.GCB.2013.24 urn:nbn:de:0030-drops-42334 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.GCB.2013.24 eng https://creativecommons.org/licenses/by/3.0/legalcode