BACKGROUND
accurate estimation of the evolutionary distance between two sequences is fundamental and critical to phylogenetic analysis aiming to reconstruct the correct evolutionary history and estimate the time of divergence between species.
one popular approach to evolutionary distance estimation relies on sequence alignment.
typically, the pipeline for alignment-based phylogenetic inference generally works by three steps.
firstly, we perform all-to-all pairwise sequence alignment to gain a pairwise distance matrix for the input sequences.
the evolutionary distance between two sequences in the matrix is typically inferred from an optimal alignment, e.g.
equal to one minus percent identity in the optimal alignment.
secondly, we construct a guide tree from the pairwise distance matrix and then conduct progressive alignment of multiple sequences following the order determined by the guide tree.
finally, we infer a phylogenetic tree from the resulting multiple alignments using a tree inference program which can be distance-, parsimony-, bayesian, or likelihood-based.
nevertheless, it needs to be stressed that we could also choose to construct a phylogenetic tree directly from the pairwise distance matrix computed in the first step, using some distance-based tree construction algorithm such as unweighted pair group method with arithmetic mean   <cit>  or neighbor-joining   <cit> .
although they may have high accuracy, alignment-based approaches involve high computational cost, thus resulting in slow speed.
this is because pairwise alignment using dynamic programming has a quadratic complexity with respect to sequence length.
this is even more challenging when constructing the phylogenetic tree for a large number of sequences, especially long sequences .
in this case, some research efforts have been devoted to accelerating the tree construction using high performance computing architectures .
in addition to acceleration, as an alternative to alignment-based approaches, alignment-free approaches emerge and become popular, mainly owing to their speed superiority.
for instance, given a collection of d sequences of average length n, the time complexity for pairwise distance matrix computation can be as high as o when using pairwise alignment.
in contrast, by using alignment-free exact k-mer  counting, the whole computation can be done in o time, significantly reducing the run-time by a factor of n. moreover, alignment-free approaches are capable of overcoming some difficulties, which challenge alignment-based approaches, such as genetic recombination and shuffling during the evolution process.
a variety of alignment-free approaches have been proposed, most of which are based on the concept of sequence seeding that extracts fixed- or variable- length substrings from a given sequence.
based on fixed-length seeding, there are two kinds of alignment-free approaches: exact k-mer counting  <cit>  and spaced k-mer counting  <cit> .
for the exact k-mer counting approach, it builds a k-mer frequency  vector for each sequence and computes the pairwise distance using some distance measure based on the frequency vectors.
example distance measures include euclidean distance  <cit> , kullback-lebler divergence  <cit>  and the one proposed by edgar  <cit> .
the edgar’s distance measure models the similarity between two sequences as the fraction of exact k-mers shared by them, and then computes the pairwise distance by subtracting the similarity value from one.
this distance measure has been shown to be highly related to genetic distance and has been used in other applications like metagenomic sequence classification  <cit> .
for the spaced k-mer counting approach, it allows character mismatches between k-mers at some predefined positions and usually employs multiple pattern templates in order to improve accuracy.
based on variable-length seeding, there are three kinds of approaches: the average common substring  method  <cit> , the k-mismatch acs  method  <cit>  and the mutation distances   <cit> .
the distance based on these methods can be computed using suffix trees/arrays.
given two sequences, the acs method first calculates the length of the longest substring that starts at each position i in one sequence and matches some substring of the other sequence.
subsequently, it averages and normalizes all of the lengths computed to represent the similarity of the two sequences.
finally, the resulting similarity value is used to compute the pairwise distance.
the time complexity of the acs method is directly proportional to the sum of lengths of the two sequences.
in contrast, the k-acs method computes the pairwise distance by finding substring pairs with upto k mismatches, given two sequences.
specifically, instead of determining the longest common substrings, the k-acs method aims to find the longest substring starting at each position in one sequence and matching some substring in the other sequence with upto k mismatches.
the mutation distances is closely related to acs, where the difference is only in the conversion from the similarity value to a pairwise distance.
unlike the acs method, the solutions to the k-acs method involves high computational cost.
for example, an algorithm given by leimeister and morgenstern  <cit>  takes o time in the worst case, which is certainty not a suitable replacement of alignment based methods.
however, they proposed a faster algorithm, namely kmacs, that computes an approximation to k-acs based distance.
another algorithm by apostolico et al.
runs in o time  <cit> .
this raises an open question, whether the exact k-acs based distance can be computed in strictly sub-quadratic time.
initial attempts were focused on the special case of k= <dig>  <cit> .
later, aluru et al.
<cit>  positively answered this question by presenting an algorithm with a worst case run time of o for any constant k. the algorithm is much more complicated than the original acs method and even the k-acs approximation by  <cit> .
moreover the practical variant of this algorithm can get quite slow for even moderately large values of k due to its exponential dependency on k  <cit> .
however, this algorithm has its merit as the first sub-quadratic time algorithm for exact k-acs computation for any positive integer k. a recently proposed algorithm by pizzi is based on filtering approaches  <cit> .
in summary, on one hand, we have a fast approximation algorithm  <cit>  and on the other hand, we have an exact  algorithm  <cit> , that might work well for small values of k in practice.
inspired by both algorithms, we introduce a new greedy heuristic for alignment-free distance estimation, named alfred-g. the heuristic is implemented in c++ and has been incorporated into our open-source alfred software package .
we use x and y to denote the two sequences to be compared.
the length of sequence x is denoted by |x|, its ith character by x, and the substring that starts at position i and ends at position j by x. for brevity, we use x
i to denote the suffix of x starting at i. the total length of x and y is denoted by n. a key data structure in our algorithm is the generalized suffix tree .
the gst of x and y is a compact trie of all suffixes of x and y. it consists of n leaves and at most n− <dig> internal nodes.
corresponding to each leaf, there is a unique suffix of x or y. the edges are labeled with a sequence of characters.
the string-depth of a node u is the length of the string obtained by concatenating the edge labels on the path from the root of gst to u. the space and the construction time of gst are o  <cit> .
for any  pair, |lcp|, the length of the longest common prefix of x
i and y
j is same as the string-depth of the lowest common ancestor node of the leaves corresponding to x
i and y
j. using gst, we can compute it in constant time.
also, we can compute |lcp
k|, the length of the longest common prefix of x
i and y
j with first k mismatches ignored, in o time as follows.
let z=|lcp|, then for any k≥ <dig>
<dig> lcpkxi,yj=z+1+lcpk−1xi+z+ <dig> yj+z+ <dig>
problem definition
the k-mismatch average common substring of x w.r.t.
y, denoted by acs
k is defined as the average of the length of the prefix of a suffix of x, that appears as a substring of y within hamming distance k. specifically, let λ
k= maxj|lcp
k|, then
<dig> acsk=1|x|∑i=1|x|λk
the distance dist
k, based on acs
k is given below  <cit> .
<dig> distk=12log|y|acsk+log|x|acsk−log|x||x|+log|y||y|
methods
approximating acsk
it is observed that acs
k can be easily computed in o time via |x|×|y| number of |lcp
k| queries, which is clearly not affordable.
the first attempt to circumvent this issue was made by leimeister and morgenstern  <cit> , who presented a heuristic method, named kmacs, that quickly computes an approximation to acs
k. the key idea is to replace λ
k with λ
k′ in the equation for acs
k, where α
i=a
r
g maxj|lcp| and λk′=|lcpk|.
using gst, we can compute α
i for all values of i in o time.
therefore, λ
k′ for all values of i and the corresponding distance can be easily obtained in o time.
note that the ratio of λ
k to λ
k′ can be as high as Θ. nonetheless, it has been shown that for most practical cases, the average of the latter can serve as a good approximation to the average of the former.
our approach
the idea is to follow a simple adaptation of aluru et al.’s exact algorithm  <cit>  for 1-mismatch case and then use the heuristic approach by leimeister and morgenstern  <cit>  to extend the result to k-mismatch.
specifically, our approximation to acs
k is obtained by replacing λ
k in the equation for acs
k by λ
k″, where β
i=a
r
g maxj|lcp
1| and λk″=|lcpk|.
to compute β
i for i= <dig> ,…,|x|, we first construct gst and an array a. then for each internal node u in gst, process the set s of suffixes corresponding to the leaves in the subtree of u. let h be the string-depth of u. then  is the first position, in which the prefixes of two suffixes in s can differ.
we sort all suffixes in s by treating the th character all suffixes to be identical, or equivalently first  characters to be the same.
to do so, we follow the steps below:
map each xi∈s to a pair , where key is the lexicographic rank of the suffix x
i+h+ <dig> among all suffixes of x and y. in other words, key is the lexicographic rank of the suffix obtained by deleting the first  characters of x
i. using gst, we can compute key in constant time.
likewise, map each yj∈s to a pair , where key is the lexicographic rank of y
j+h+ <dig> among all suffixes of x and y.
sort all pairs in the ascending order of key.
for each pair , find the closest pairs, say  and , towards the left and right side  that are created from a suffix of y, and update a←a
r
g maxj∈{a,b,a}|lcp
1|.
after processing all internal nodes as described above, compute the following and report it as our approximation to acs
k
1|x|∑i=1|x|λk′′=1|x|∑i=1|x|lcpkxi,yβi
it can be easily verified that a will be correctly updated to β
i while processing the lowest common ancestor node of the leaves corresponding to x
i and yβi.
the overall run time is nk+∑u|s|log|s|=o, where h is the height of gst and its expected value is o  <cit> .
implementation
alfred-g is implemented in c++ and is incorporated in our open-source alfred software package .
this algorithm takes a collection of sequences as input and computes an approximation to acs
k for all pairs of sequences.
for this, we have used the open-source libdivsufsort library  <cit>  to construct the suffix array  and have used the implementations in the sdsl library  <cit>  to build the corresponding lcp table  and the range minimum query  table .
.
the sdsl library has support for using bit compression techniques to reduce the size of the tables and arrays in exchange for slower query time.
however, we don’t compress these data structures, and instead we have used 32-bit integers for indices as well as prefix lengths.
RESULTS
benchmark datasets
we have assessed the performance of alfred-g for the reconstruction of phylogenetic trees by using three sequence datasets, which contain prokaryotic dna sequences, eukaryotic dna sequences, and protein sequences, respectively.
the prokaryotic sequence dataset consists of  <dig> primate mitochondrial genomes, which was previously studied by  <cit>  in order to assess the performance of alignment-free approaches for phylogenetic tree reconstruction.
in the study, a reference tree was constructed based on a multiple alignment of the sequences.
the eukaryotic sequence dataset is constructed by newton et al.
<cit>  from  <dig> roseobacter genomes, by extracting  <dig> universal single-copy genes for the  <dig> genomes with each gene being completely sequenced in all genomes and having no ambiguous start/stop sites.
the  <dig> genes for each genome are, subsequently, concatenated and aligned with clustalw in geneious  <dig>   using escherichia coli k <dig> substrain mg <dig> as the outgroup.
the multiple sequence alignment file is available at http://alurulab.cc.gatech.edu/phylo, from which the raw sequences corresponding to the  <dig> roseobacter genomes are extracted and then used in our study.
in our study, we have used the phylogenetic tree presented in newton et al.
<cit>  as the reference tree.
the protein sequence dataset is taken from balibase   <cit> , which is popular benchmark dataset for multiple sequence alignment.
we have used  <dig> sets of protein sequences in balibase, and constructed the reference trees from the corresponding reference alignments using the proml program available in phylip  <cit> , which implements the maxmimum likelihood method.
for each of the parameter selected for our experiments, we report the average rf-distance of the  <dig> trees constructed from this set.
phylogenetic tree construction and comparison
given a set of d sequences, we first compute the distance between any sequence pair and then construct a pairwise distance matrix of size d×d.
subsequently, the neighbor-joining  algorithm  <cit>  is applied on the pairwise distance matrix to reconstruct the phylogenetic tree, where the neighbor program in phylip is used.
finally, the topology of the tree is compared with the reference tree using the robinson-foulds  distance metric, where the treedist program in phylip is used to compute the rf distance between two trees.
note that the lower the rf distance is, the better the tree topology matches.
in particular, if the rf distance equals zero, it means exact topology match between the two trees.
all experiments are preformed in an apple macbook pro  running mac os  <dig> .
<dig> .
the machine features a  <dig>  ghz dual-core intel core i7-3667u processor with 4mb l <dig> cache and 8gb ram.
performance comparison
as our method is closely related to kmacs, we compared the performance of alfred-g with kmacs in terms of speed and accuracy  for different values of k, ranging from  <dig> to  <dig>  note that for k= <dig>  both kmacs and alfred-g are the same as the acs method.
fig.
<dig> rf distance and run-time plots for the prokaryotic dataset
fig.
<dig> tree generated by alfred-g for the prokaryotic dataset with k=4
fig.
<dig> rf distance and run-time plots for the eukaryotic dataset
fig.
<dig> reference tree and the tree generated by alfred-g for the eukaryotic dataset with k= <dig>
fig.
<dig> rf distance and run-time plots for the balibase protein dataset
in the earlier work by leimeister and morgenstern  <cit> , it has been show that kmacs and spaced-seed  <cit>  are superior to other alignment-free methods, when applied to the aforementioned three datasets.
our experiments show that alfred-g is comparable and often more accurate than kmacs, albeit involving higher computational cost.
it needs to be mentioned that the comparison with spaced-seed is not as straightforward as with kmacs, because spaced-seed has different input parameters and requires tedious pattern templates tuning.
nevertheless, we have carefully evaluated spaced-seed based on the suggestions from  <cit> .
our evaluation shows that spaced-seed is able to recover the entire reference tree  for the prokaryotic dataset, in just  <dig> seconds.
however, for the rest, the performance of spaced-seed is roughly comparable to both ours and kmacs.
CONCLUSIONS
in this paper, we have introduced a greedy alignment-free approach to estimating the evolutionary distance between two sequences.
the core of the heuristic is to identify a 1-mismatch longest substring in sequence y that appears as a prefix of any given suffix in sequence x, and vice versa.
this heuristic has been further applied to reconstruct the phylogenetic tree, given a collection of sequences that are believed to be close enough and have some evolutionary relationship between them.
the performance of our heuristic has been evaluated using three real datasets: one prokaryotic dataset, one eukaryotic dataset and one protein dataset, in terms of tree-topology rf score and speed.
our experimental results show that our heuristic can exactly reconstruct the same phylogenetic tree topology with the reference tree for the prokaryotic dataset, whereas kmacs cannot.
on the remaining two datasets, our heuristic also demonstrates comparable or even better performance than kmacs.
as for speed, our heuristic is slightly slower than kmacs.
although our heuristic has been shown effective for phylogenetic inference, there are still some limitations that could be improved in the future.
firstly, our heuristic assumes an evolution model having only mismatches, not involving insertions or deletions, for simplicity.
this model may not exactly fit the real evolutionary process given a collection of sequences.
nevertheless, our performance evaluation has shown that even though there are some insertions or deletions between sequences , their evolutionary distances can still be estimated with reasonable accuracy using our heuristic.
however, it should be noted that the existence of insertions or deletions may cause our heuristic to underestimate the similarity values, i.e.
acs
k, between sequences, thus overestimating their distances, i.e.
dist
k.
secondly, our heuristic assumes that the homologous regions between two sequences are on the same strand.
actually, this is not always the case.
given a homologous region, the substring in sequence x may have an opposite strand to the corresponding homology in sequence y. in this case, directly applying our heuristic to such sequences may overestimate the distance, since these homologies with opposite strands are not counted in the computation of similarity values.
in some sense, we would expect that the estimation accuracy of alignment-free approaches could be further improved by incorporating support for strand differences in homologies.
thirdly, our heuristic has only used eq.
to estimate the distance from the similarity values computed from eq.
.
actually, we usually need to tune distance equations for different similarity computation approaches and even for similarity values in different ranges.
for example, edgar  <cit>  used percent identity d  between two sequences as a similarity measure, but proposed to use two different distance computations depending on the value of d. in this case, edgar computed the distance as − ln if d> <dig> , and retrieved the distance value from a pre-computed lookup table, otherwise.
hence, it may be beneficial to design some new distance computation equations that better match our approach.
finally, considering the generality and fast speed of our heuristic, we would expect that related research in bioinformatics and computational biology could benefit from our algorithm.
from fifth ieee international conference on computational advances in bio and medical sciences miami, fl, usa.15- <dig> october 2015

 accurate estimation of the evolutionary distance between two sequences is fundamental and critical to phylogenetic analysis aiming to reconstruct the correct evolutionary history and estimate the time of divergence between species. one popular approach to evolutionary distance estimation relies on sequence alignment. typically, the pipeline for alignment-based phylogenetic inference generally works by three steps. firstly, we perform all-to-all pairwise sequence alignment to gain a pairwise distance matrix for the input sequences. the evolutionary distance between two sequences in the matrix is typically inferred from an optimal alignment, e.g. equal to one minus percent identity in the optimal alignment. secondly, we construct a guide tree from the pairwise distance matrix and then conduct progressive alignment of multiple sequences following the order determined by the guide tree. finally, we infer a phylogenetic tree from the resulting multiple alignments using a tree inference program which can be distance-, parsimony-, bayesian, or likelihood-based. nevertheless, it needs to be stressed that we could also choose to construct a phylogenetic tree directly from the pairwise distance matrix computed in the first step, using some distance-based tree construction algorithm such as unweighted pair group method with arithmetic mean or neighbor-joining. although they may have high accuracy, alignment-based approaches involve high computational cost, thus resulting in slow speed. this is because pairwise alignment using dynamic programming has a quadratic complexity with respect to sequence length. this is even more challenging when constructing the phylogenetic tree for a large number of sequences, especially long sequences. in this case, some research efforts have been devoted to accelerating the tree construction using high performance computing architectures. in addition to acceleration, as an alternative to alignment-based approaches, alignment-free approaches emerge and become popular, mainly owing to their speed superiority. for instance, given a collection of d sequences of average length n, the time complexity for pairwise distance matrix computation can be as high as o when using pairwise alignment. in contrast, by using alignment-free exact k-mer counting, the whole computation can be done in o time, significantly reducing the run-time by a factor of n. moreover, alignment-free approaches are capable of overcoming some difficulties, which challenge alignment-based approaches, such as genetic recombination and shuffling during the evolution process. a variety of alignment-free approaches have been proposed, most of which are based on the concept of sequence seeding that extracts fixed- or variable- length substrings from a given sequence. based on fixed-length seeding, there are two kinds of alignment-free approaches: exact k-mer counting and spaced k-mer counting. for the exact k-mer counting approach, it builds a k-mer frequency vector for each sequence and computes the pairwise distance using some distance measure based on the frequency vectors. example distance measures include euclidean distance, kullback-lebler divergence and the one proposed by edgar. the edgar’s distance measure models the similarity between two sequences as the fraction of exact k-mers shared by them, and then computes the pairwise distance by subtracting the similarity value from one. this distance measure has been shown to be highly related to genetic distance and has been used in other applications like metagenomic sequence classification. for the spaced k-mer counting approach, it allows character mismatches between k-mers at some predefined positions and usually employs multiple pattern templates in order to improve accuracy. based on variable-length seeding, there are three kinds of approaches: the average common substring method, the k-mismatch acs method and the mutation distances. the distance based on these methods can be computed using suffix trees/arrays. given two sequences, the acs method first calculates the length of the longest substring that starts at each position i in one sequence and matches some substring of the other sequence. subsequently, it averages and normalizes all of the lengths computed to represent the similarity of the two sequences. finally, the resulting similarity value is used to compute the pairwise distance. the time complexity of the acs method is directly proportional to the sum of lengths of the two sequences. in contrast, the k-acs method computes the pairwise distance by finding substring pairs with upto k mismatches, given two sequences. specifically, instead of determining the longest common substrings, the k-acs method aims to find the longest substring starting at each position in one sequence and matching some substring in the other sequence with upto k mismatches. the mutation distances is closely related to acs, where the difference is only in the conversion from the similarity value to a pairwise distance. unlike the acs method, the solutions to the k-acs method involves high computational cost. for example, an algorithm given by leimeister and morgenstern takes o time in the worst case, which is certainty not a suitable replacement of alignment based methods. however, they proposed a faster algorithm, namely kmacs, that computes an approximation to k-acs based distance. another algorithm by apostolico et al. runs in o time. this raises an open question, whether the exact k-acs based distance can be computed in strictly sub-quadratic time. initial attempts were focused on the special case of k=. later, aluru et al. positively answered this question by presenting an algorithm with a worst case run time of o for any constant k. the algorithm is much more complicated than the original acs method and even the k-acs approximation by. moreover the practical variant of this algorithm can get quite slow for even moderately large values of k due to its exponential dependency on k. however, this algorithm has its merit as the first sub-quadratic time algorithm for exact k-acs computation for any positive integer k. a recently proposed algorithm by pizzi is based on filtering approaches. in summary, on one hand, we have a fast approximation algorithm and on the other hand, we have an exact algorithm, that might work well for small values of k in practice. inspired by both algorithms, we introduce a new greedy heuristic for alignment-free distance estimation, named alfred-g. the heuristic is implemented in c++ and has been incorporated into our open-source alfred software package. we use x and y to denote the two sequences to be compared. the length of sequence x is denoted by |x|, its ith character by x, and the substring that starts at position i and ends at position j by x. for brevity, we use x i to denote the suffix of x starting at i. the total length of x and y is denoted by n. a key data structure in our algorithm is the generalized suffix tree. the gst of x and y is a compact trie of all suffixes of x and y. it consists of n leaves and at most n− internal nodes. corresponding to each leaf, there is a unique suffix of x or y. the edges are labeled with a sequence of characters. the string-depth of a node u is the length of the string obtained by concatenating the edge labels on the path from the root of gst to u. the space and the construction time of gst are o. for any pair, |lcp|, the length of the longest common prefix of x i and y j is same as the string-depth of the lowest common ancestor node of the leaves corresponding to x i and y j. using gst, we can compute it in constant time. also, we can compute |lcp k|, the length of the longest common prefix of x i and y j with first k mismatches ignored, in o time as follows. let z=|lcp|, then for any k≥ lcpkxi,yj=z+1+lcpk−1xi+z+ yj+z+ problem definition the k-mismatch average common substring of x w.r.t. y, denoted by acs k is defined as the average of the length of the prefix of a suffix of x, that appears as a substring of y within hamming distance k. specifically, let λ k= maxj|lcp k|, then acsk=1|x|∑i=1|x|λk the distance dist k, based on acs k is given below. distk=12log|y|acsk+log|x|acsk−log|x||x|+log|y||y| methods approximating acsk it is observed that acs k can be easily computed in o time via |x|×|y| number of |lcp k| queries, which is clearly not affordable. the first attempt to circumvent this issue was made by leimeister and morgenstern, who presented a heuristic method, named kmacs, that quickly computes an approximation to acs k. the key idea is to replace λ k with λ k′ in the equation for acs k, where α i=a r g maxj|lcp| and λk′=|lcpk|. using gst, we can compute α i for all values of i in o time. therefore, λ k′ for all values of i and the corresponding distance can be easily obtained in o time. note that the ratio of λ k to λ k′ can be as high as Θ. nonetheless, it has been shown that for most practical cases, the average of the latter can serve as a good approximation to the average of the former. our approach the idea is to follow a simple adaptation of aluru et al.’s exact algorithm for 1-mismatch case and then use the heuristic approach by leimeister and morgenstern to extend the result to k-mismatch. specifically, our approximation to acs k is obtained by replacing λ k in the equation for acs k by λ k″, where β i=a r g maxj|lcp 1| and λk″=|lcpk|. to compute β i for i=,…,|x|, we first construct gst and an array a. then for each internal node u in gst, process the set s of suffixes corresponding to the leaves in the subtree of u. let h be the string-depth of u. then is the first position, in which the prefixes of two suffixes in s can differ. we sort all suffixes in s by treating the th character all suffixes to be identical, or equivalently first characters to be the same. to do so, we follow the steps below: map each xi∈s to a pair, where key is the lexicographic rank of the suffix x i+h+ among all suffixes of x and y. in other words, key is the lexicographic rank of the suffix obtained by deleting the first characters of x i. using gst, we can compute key in constant time. likewise, map each yj∈s to a pair, where key is the lexicographic rank of y j+h+ among all suffixes of x and y. sort all pairs in the ascending order of key. for each pair, find the closest pairs, say and, towards the left and right side that are created from a suffix of y, and update a←a r g maxj∈{a,b,a}|lcp 1|. after processing all internal nodes as described above, compute the following and report it as our approximation to acs k 1|x|∑i=1|x|λk′′=1|x|∑i=1|x|lcpkxi,yβi it can be easily verified that a will be correctly updated to β i while processing the lowest common ancestor node of the leaves corresponding to x i and yβi. the overall run time is nk+∑u|s|log|s|=o, where h is the height of gst and its expected value is o. implementation alfred-g is implemented in c++ and is incorporated in our open-source alfred software package. this algorithm takes a collection of sequences as input and computes an approximation to acs k for all pairs of sequences. for this, we have used the open-source libdivsufsort library to construct the suffix array and have used the implementations in the sdsl library to build the corresponding lcp table and the range minimum query table.. the sdsl library has support for using bit compression techniques to reduce the size of the tables and arrays in exchange for slower query time. however, we don’t compress these data structures, and instead we have used 32-bit integers for indices as well as prefix lengths.  benchmark datasets we have assessed the performance of alfred-g for the reconstruction of phylogenetic trees by using three sequence datasets, which contain prokaryotic dna sequences, eukaryotic dna sequences, and protein sequences, respectively. the prokaryotic sequence dataset consists of primate mitochondrial genomes, which was previously studied by in order to assess the performance of alignment-free approaches for phylogenetic tree reconstruction. in the study, a reference tree was constructed based on a multiple alignment of the sequences. the eukaryotic sequence dataset is constructed by newton et al. from roseobacter genomes, by extracting universal single-copy genes for the genomes with each gene being completely sequenced in all genomes and having no ambiguous start/stop sites. the genes for each genome are, subsequently, concatenated and aligned with clustalw in geneious using escherichia coli k substrain mg as the outgroup. the multiple sequence alignment file is available at http://alurulab.cc.gatech.edu/phylo, from which the raw sequences corresponding to the roseobacter genomes are extracted and then used in our study. in our study, we have used the phylogenetic tree presented in newton et al. as the reference tree. the protein sequence dataset is taken from balibase, which is popular benchmark dataset for multiple sequence alignment. we have used sets of protein sequences in balibase, and constructed the reference trees from the corresponding reference alignments using the proml program available in phylip, which implements the maxmimum likelihood method. for each of the parameter selected for our experiments, we report the average rf-distance of the trees constructed from this set. phylogenetic tree construction and comparison given a set of d sequences, we first compute the distance between any sequence pair and then construct a pairwise distance matrix of size d×d. subsequently, the neighbor-joining algorithm is applied on the pairwise distance matrix to reconstruct the phylogenetic tree, where the neighbor program in phylip is used. finally, the topology of the tree is compared with the reference tree using the robinson-foulds distance metric, where the treedist program in phylip is used to compute the rf distance between two trees. note that the lower the rf distance is, the better the tree topology matches. in particular, if the rf distance equals zero, it means exact topology match between the two trees. all experiments are preformed in an apple macbook pro running mac os.. the machine features a ghz dual-core intel core i7-3667u processor with 4mb l cache and 8gb ram. performance comparison as our method is closely related to kmacs, we compared the performance of alfred-g with kmacs in terms of speed and accuracy for different values of k, ranging from to note that for k= both kmacs and alfred-g are the same as the acs method. fig. rf distance and run-time plots for the prokaryotic dataset fig. tree generated by alfred-g for the prokaryotic dataset with k=4 fig. rf distance and run-time plots for the eukaryotic dataset fig. reference tree and the tree generated by alfred-g for the eukaryotic dataset with k= fig. rf distance and run-time plots for the balibase protein dataset in the earlier work by leimeister and morgenstern, it has been show that kmacs and spaced-seed are superior to other alignment-free methods, when applied to the aforementioned three datasets. our experiments show that alfred-g is comparable and often more accurate than kmacs, albeit involving higher computational cost. it needs to be mentioned that the comparison with spaced-seed is not as straightforward as with kmacs, because spaced-seed has different input parameters and requires tedious pattern templates tuning. nevertheless, we have carefully evaluated spaced-seed based on the suggestions from. our evaluation shows that spaced-seed is able to recover the entire reference tree for the prokaryotic dataset, in just seconds. however, for the rest, the performance of spaced-seed is roughly comparable to both ours and kmacs.  in this paper, we have introduced a greedy alignment-free approach to estimating the evolutionary distance between two sequences. the core of the heuristic is to identify a 1-mismatch longest substring in sequence y that appears as a prefix of any given suffix in sequence x, and vice versa. this heuristic has been further applied to reconstruct the phylogenetic tree, given a collection of sequences that are believed to be close enough and have some evolutionary relationship between them. the performance of our heuristic has been evaluated using three real datasets: one prokaryotic dataset, one eukaryotic dataset and one protein dataset, in terms of tree-topology rf score and speed. our experimental results show that our heuristic can exactly reconstruct the same phylogenetic tree topology with the reference tree for the prokaryotic dataset, whereas kmacs cannot. on the remaining two datasets, our heuristic also demonstrates comparable or even better performance than kmacs. as for speed, our heuristic is slightly slower than kmacs. although our heuristic has been shown effective for phylogenetic inference, there are still some limitations that could be improved in the future. firstly, our heuristic assumes an evolution model having only mismatches, not involving insertions or deletions, for simplicity. this model may not exactly fit the real evolutionary process given a collection of sequences. nevertheless, our performance evaluation has shown that even though there are some insertions or deletions between sequences, their evolutionary distances can still be estimated with reasonable accuracy using our heuristic. however, it should be noted that the existence of insertions or deletions may cause our heuristic to underestimate the similarity values, i.e. acs k, between sequences, thus overestimating their distances, i.e. dist k. secondly, our heuristic assumes that the homologous regions between two sequences are on the same strand. actually, this is not always the case. given a homologous region, the substring in sequence x may have an opposite strand to the corresponding homology in sequence y. in this case, directly applying our heuristic to such sequences may overestimate the distance, since these homologies with opposite strands are not counted in the computation of similarity values. in some sense, we would expect that the estimation accuracy of alignment-free approaches could be further improved by incorporating support for strand differences in homologies. thirdly, our heuristic has only used eq. to estimate the distance from the similarity values computed from eq.. actually, we usually need to tune distance equations for different similarity computation approaches and even for similarity values in different ranges. for example, edgar used percent identity d between two sequences as a similarity measure, but proposed to use two different distance computations depending on the value of d. in this case, edgar computed the distance as − ln if d>, and retrieved the distance value from a pre-computed lookup table, otherwise. hence, it may be beneficial to design some new distance computation equations that better match our approach. finally, considering the generality and fast speed of our heuristic, we would expect that related research in bioinformatics and computational biology could benefit from our algorithm. from fifth ieee international conference on computational advances in bio and medical sciences miami, fl, usa.15- october 2015 
we present alfred-g, a greedy alignment-free distance estimator for phylogenetic tree reconstruction based on the concept of the generalized acs approach. performance evaluation using real sequence datasets shows that our heuristic is able to reconstruct comparable, or even more accurate, phylogenetic tree topologies than the kmacs heuristic algorithm at highly competitive speed. this algorithm is implemented in c++ and has been incorporated into our open-source alfred software package. 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. 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. alignment-free methodssequence comparisonphylogeny reconstructionfifth ieee international conference on computational advances in bio and medical sciences miami, fl, usa 15- october issue-copyright-statement© the author 2017
 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 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.  we present alfred-g, a greedy alignment-free distance estimator for phylogenetic tree reconstruction based on the concept of the generalized acs approach. in this algorithm, we have investigated a new heuristic to efficiently compute the lengths of common strings with mismatches allowed, and have further applied this heuristic to phylogeny reconstruction. performance evaluation using real sequence datasets shows that our heuristic is able to reconstruct comparable, or even more accurate, phylogenetic tree topologies than the kmacs heuristic algorithm at highly competitive speed.  alfred-g is an alignment-free heuristic for evolutionary distance estimation between two biological sequences. this algorithm is implemented in c++ and has been incorporated into our open-source alfred software package. keywords alignment-free methodssequence comparisonphylogeny reconstructionfifth ieee international conference on computational advances in bio and medical sciences miami, fl, usa 15- october issue-copyright-statement© the author 2017 