English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Spaced words and kmacs: Fast alignment-free sequence comparison based on inexact word matches.

MPS-Authors
/persons/resource/persons37779

Hatje,  K.
Research Group of Systems Biology of Motor Proteins, MPI for biophysical chemistry, Max Planck Society;

/persons/resource/persons15357

Kollmar,  M.
Research Group of Systems Biology of Motor Proteins, MPI for biophysical chemistry, Max Planck Society;

External Resource
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

2053244.pdf
(Publisher version), 576KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Horwege, S., Lindner, S., Boden, M., Hatje, K., Kollmar, M., Leimeister, C. A., et al. (2014). Spaced words and kmacs: Fast alignment-free sequence comparison based on inexact word matches. Nucleic Acids Research, 42(W1), W7-W11. doi:10.1093/nar/gku398.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0023-C6E4-C
Abstract
In this article, we present a user-friendly web interface for two alignment-free sequence-comparison methods that we recently developed. Most alignment-free methods rely on exact word matches to estimate pairwise similarities or distances between the input sequences. By contrast, our new algorithms are based on inexact word matches. The first of these approaches uses the relative frequencies of so-called spaced words in the input sequences, i.e. words containing 'don't care' or 'wildcard' symbols at certain pre-defined positions. Various distance measures can then be defined on sequences based on their different spaced-word composition. Our second approach defines the distance between two sequences by estimating for each position in the first sequence the length of the longest substring at this position that also occurs in the second sequence with up to k mismatches. Both approaches take a set of deoxyribonucleic acid (DNA) or protein sequences as input and return a matrix of pairwise distance values that can be used as a starting point for clustering algorithms or distance-based phylogeny reconstruction.