A greedy alignment-free distance estimator for phylogenetic inference (extended abstract)

Accurate estimation of 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. Conventionally, sequence alignment is usually used for this purpose due to its high accuracy. However, alignment-based approaches involve high computational cost. Therefore, as an alternative, alignment-free approaches emerge and become popular, mainly owing to their speed superiority. The average common substring (ACS) method [1] is one of the popular alignment-free sequence comparison method. The k-mismatch average common substring (k-ACS) [2] method extends ACS by allowing a bounded number of mismatches.