An Alignment-Free Heuristic For Fast Sequence Comparisons With Applications To Phylogeny Reconstruction

Keywords

Alignment-free matching; Approximate sequence matching; Phylogeny reconstruction

Abstract

Alignment-free methods for sequence comparisons have become popular in many bioinformatics applications, specifically in the estimation of sequence similarity measures to construct phylogenetic trees. Recently, the average common substring measure, ACS, and its k-mismatch counterpart, ACS-k, have been shown to produce results as effective as multiple-sequence alignment based methods in phylogeny. In this work, we present a novel linear-time heuristic to approximate ACS-k, which is faster than computing the exact ACS-k while being closer to the exact ACS-k values compared to previously published linear-time greedy heuristics.

Publication Date

8-15-2018

Publication Title

ACM-BCB 2018 - Proceedings of the 2018 ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics

Number of Pages

540-

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1145/3233547.3233648

Socpus ID

85056125237 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85056125237

This document is currently not available here.

Share

COinS