Cargando…
kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison
Motivation: Alignment-based methods for sequence analysis have various limitations if large datasets are to be analysed. Therefore, alignment-free approaches have become popular in recent years. One of the best known alignment-free methods is the average common substring approach that defines a dist...
Autores principales: | , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Oxford University Press
2014
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4080746/ https://www.ncbi.nlm.nih.gov/pubmed/24828656 http://dx.doi.org/10.1093/bioinformatics/btu331 |
_version_ | 1782324032157253632 |
---|---|
author | Leimeister, Chris-Andre Morgenstern, Burkhard |
author_facet | Leimeister, Chris-Andre Morgenstern, Burkhard |
author_sort | Leimeister, Chris-Andre |
collection | PubMed |
description | Motivation: Alignment-based methods for sequence analysis have various limitations if large datasets are to be analysed. Therefore, alignment-free approaches have become popular in recent years. One of the best known alignment-free methods is the average common substring approach that defines a distance measure on sequences based on the average length of longest common words between them. Herein, we generalize this approach by considering longest common substrings with k mismatches. We present a greedy heuristic to approximate the length of such k-mismatch substrings, and we describe kmacs, an efficient implementation of this idea based on generalized enhanced suffix arrays. Results: To evaluate the performance of our approach, we applied it to phylogeny reconstruction using a large number of DNA and protein sequence sets. In most cases, phylogenetic trees calculated with kmacs were more accurate than trees produced with established alignment-free methods that are based on exact word matches. Especially on protein sequences, our method seems to be superior. On simulated protein families, kmacs even outperformed a classical approach to phylogeny reconstruction using multiple alignment and maximum likelihood. Availability and implementation: kmacs is implemented in C++, and the source code is freely available at http://kmacs.gobics.de/ Contact: chris.leimeister@stud.uni-goettingen.de Supplementary information: Supplementary data are available at Bioinformatics online. |
format | Online Article Text |
id | pubmed-4080746 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2014 |
publisher | Oxford University Press |
record_format | MEDLINE/PubMed |
spelling | pubmed-40807462014-07-03 kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison Leimeister, Chris-Andre Morgenstern, Burkhard Bioinformatics Original Papers Motivation: Alignment-based methods for sequence analysis have various limitations if large datasets are to be analysed. Therefore, alignment-free approaches have become popular in recent years. One of the best known alignment-free methods is the average common substring approach that defines a distance measure on sequences based on the average length of longest common words between them. Herein, we generalize this approach by considering longest common substrings with k mismatches. We present a greedy heuristic to approximate the length of such k-mismatch substrings, and we describe kmacs, an efficient implementation of this idea based on generalized enhanced suffix arrays. Results: To evaluate the performance of our approach, we applied it to phylogeny reconstruction using a large number of DNA and protein sequence sets. In most cases, phylogenetic trees calculated with kmacs were more accurate than trees produced with established alignment-free methods that are based on exact word matches. Especially on protein sequences, our method seems to be superior. On simulated protein families, kmacs even outperformed a classical approach to phylogeny reconstruction using multiple alignment and maximum likelihood. Availability and implementation: kmacs is implemented in C++, and the source code is freely available at http://kmacs.gobics.de/ Contact: chris.leimeister@stud.uni-goettingen.de Supplementary information: Supplementary data are available at Bioinformatics online. Oxford University Press 2014-07-15 2014-05-13 /pmc/articles/PMC4080746/ /pubmed/24828656 http://dx.doi.org/10.1093/bioinformatics/btu331 Text en © The Author 2014. Published by Oxford University Press. All rights reserved. http://creativecommons.org/licenses/by/3.0/ This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/3.0/), which permits unrestricted reuse, distribution, and reproduction in any medium, provided the original work is properly cited. |
spellingShingle | Original Papers Leimeister, Chris-Andre Morgenstern, Burkhard kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison |
title | kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison |
title_full | kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison |
title_fullStr | kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison |
title_full_unstemmed | kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison |
title_short | kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison |
title_sort | kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison |
topic | Original Papers |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4080746/ https://www.ncbi.nlm.nih.gov/pubmed/24828656 http://dx.doi.org/10.1093/bioinformatics/btu331 |
work_keys_str_mv | AT leimeisterchrisandre kmacsthekmismatchaveragecommonsubstringapproachtoalignmentfreesequencecomparison AT morgensternburkhard kmacsthekmismatchaveragecommonsubstringapproachtoalignmentfreesequencecomparison |