The Average Common Substring (ACS) is a popular alignment-free distance measure for phylogeny reconstruction. The ACS can be computed in O(n) space and time, where n=x+y is the input size. The compressed string matching is the study of string matching problems with the following twist: the input data is in a compressed format and the underling task must be performed with little or no decompression. In this paper, we revisit the ACS problem under this paradigm where the input sequences are given in their run-length encoded format. We present an algorithm to compute ACS(X,Y) in O(Nlog N) time using O(N) space, where N is the total length of sequences after run-length encoding.
@cite_14: 
@cite_4: 
@cite_10: 
@cite_9: 
@cite_1: 
@cite_17: Alignment free sequence comparison methods are attracting persistent interest, driven by data-intensive applications in genome-wide molecular taxonomy and phylogentic reconstruction. Among the methods based on substring composition, the Average Common Substring ( ( ACS )) measure proposed by (RECOMB 2005) admits a straightforward linear time sequence comparison algorithm, while yielding impressive results in multiple applications. An important direction of research is to extend the approach to permit a bounded edit hamming distance between substrings, so as to reflect more accurately the evolutionary process. To date, however, algorithms designed to incorporate (k 1 ) mismatches have (O(kn^2) ) worst-case complexity, worse than the (O(n^2) ) alignment algorithms they are meant to replace. On the other hand, accounting for mismatches does show to lead to much improved classification, while heuristics can improve practical performance. In this paper, we close the gap by presenting the first provably efficient algorithm for the (k ) -mismatch average common string ( ( ACS _k )) problem that takes (O(n) ) space and (O(n ^ k+1 n) ) time in the worst case for any constant (k ). Our method extends the generalized suffix tree model to incorporate a carefully selected bounded set of perturbed suffixes, and can be applicable to other complex approximate sequence matching problems.
@cite_3: Abstract Alignment-free approaches are gaining persistent interest in many sequence analysis applications such as phylogenetic inference and metagenomic classification clustering, especially for large-scale sequence datasets. Besides the widely used k-mer methods, the average common substring (ACS) approach has emerged to be one of the well-known alignment-free approaches. Two recent works further generalize this ACS approach by allowing a bounded number k of mismatches in the common substrings, relying on approximation (linear time) and exact computation, respectively. Albeit having a good worst-case time complexity aastex amsbsy amsfonts amssymb bm mathrsfs pifont stmaryrd textcomp portland, xspace amsmath, amsxtra empty 10 9 7 6 @math log ^ ...
@cite_6: Background Alignment-free sequence comparison approaches have been garnering increasing interest in various data- and compute-intensive applications such as phylogenetic inference for large-scale sequences. While k-mer based methods are predominantly used in real applications, the average common substring (ACS) approach is emerging as one of the prominent alignment-free approaches. This ACS approach has been further generalized by some recent work, either greedily or exactly, by allowing a bounded number of mismatches in the common substrings.
@cite_0: 
@cite_2: Up to now, various approaches for phylogenetic analysis have been developed. Almost all of them put stress on analyzing nucleic acid sequences or protein primary sequences. In this paper, we propose a new sequence distance for efficient reconstruction of phylogenetic trees based on the distribution of length about common subsequences between two sequences. We describe some applications of this method, which not only show the validity of the method, but also suggest a number of novel phylogenetic insights.
@cite_16: 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.
@cite_13: Measures of sequence similarity and distance based more or less explicitly on subword composition are attracting an increasing interest driven by intensive applications such as massive document classification and genome-wide molecular taxonomy. A uniform character of such measures is in some underlying notion of relative compressibility, whereby two similar sequences are expected to share a larger number of common substrings than two distant ones. This paper reviews some of the approaches to sequence comparison based on subword composition and suggests that their common denominator may ultimately reside in special classes of subwords, the nature of which resonates in interesting ways with the structure of popular subword trees and graphs.
@cite_12: We describe a novel method for efficient reconstruction of phylogenetic trees, based on sequences of whole genomes or proteomes. The core of our method is a new measure of pairwise distances between sequences, whose lengths may greatly vary. This measure is based on information theoretic tools (Kullback-Leibler relative entropy). We present an algorithm for efficiently computing these distances. The algorithm uses suffix arrays to compute the distance of two l long sequences in O(l) time. It is fast enough to enable the construction of the phylogenomic tree for hundreds of species, and the phylogenomic forest for almost two thousand viruses. An initial analysis of the results exhibits a remarkable agreement with “acceptable phylogenetic truth”. To assess our approach, it was implemented together with a number of alternative approaches, including two that were previously published in the literature. Comparing their outcome to ours, using a “traditional” tree and a standard tree comparison method, our algorithm improved upon the “competition” by a substantial margin.
@cite_11: A growing number of measures of sequence similarity are being based on some underlying notion of relative compressibility. Within this paradigm, similar sequences are expected to share a large number of common substrings, or subsequences, or more complex patterns or motifs, and so on. In this paper, measures of sequence similarity are introduced and studied in which patterns in a pair are considered similar if they coincide up to a preset number of mismatches, that is, within a bounded Hamming distance. It is shown here that for some such measures bounds are achievable that are slightly better than O ( n 2 ) . Preliminary experiments demonstrate the potential applicability to phylogeny and classification of these similarity measures.
The Average Common Substring (ACS), proposed by Burstein @cite_12 , is a simple alignment-free sequence comparison method. This measure and its various extensions @cite_17 @cite_11 @cite_16 @cite_9 @cite_2 @cite_3 @cite_6 have proven to be useful in multiple applications @cite_13 @cite_0 @cite_1 @cite_4 @cite_14 @cite_10 . Formally, ACS of a sequence @math w.r.t. another sequence @math , denoted by @math , is @math The @math of two input sequences is the length of their longest common prefix. The (symmetric) distance based on ACS is @cite_12 : @math