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. 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 ( http://alurulab.cc.gatech.edu/phylo ).

Finding substrings of a text T that match a regular expression p is a fundamental problem. Despite being the subject of extensive research, no solution with a time complexity significantly better than $O\left(\right|T\left|\right|p\left|\right)$ has been found. Backurs and Indyk in FOCS 2016 established conditional lower bounds for the algorithmic problem based on the Strong Exponential Time Hypothesis that helps explain this difficulty. A natural question is whether we can improve the time complexity for matching the regular expression by preprocessing the text T? We show that conditioned on the Online Matrix–Vector Multiplication (OMv) conjecture, even with arbitrary polynomial preprocessing time, a regular expression query on a text cannot be answered in strongly sublinear time, i.e., $O\left(\right|T{|}^{1-\epsilon })$ for any $\epsilon >0$. Furthermore, if we extend the OMv conjecture to a plausible conjecture regarding Boolean matrix multiplication with polynomial preprocessing time, which we call Online Matrix–Matrix Multiplication (OMM), we can strengthen this hardness result to there being no solution with a query time that is $O\left(\right|T{|}^{3/2-\epsilon })$. These results hold for alphabet sizes three or greater. We then provide data structures that answer queries in $O\left(\frac{\left|T\right|\left|p\right|}{\tau }\right)$ time where $\tau \in [1,|T\left|\right]$ is fixed at construction. These include a solution that works for all regular expressions with $Exp\left(\tau ·\left|T\right|\right)$ preprocessing time and space. For patterns containing only ‘concatenation’ and ‘or’ operators (the same type used in the hardness result), we provide (1) a deterministic solution which requires $Exp\left(\tau ·\frac{\left|T\right|}{{log}^2\left|T\right|}\right)$ preprocessing time and space, and (2) when $\left|p\right|\le {\left|T\right|}^z$ for $z=2^{o\left(\sqrt{log\left|T\right|}\right)}$, a randomized solution with amortized query time which answers queries correctly with high probability, requiring $Exp\left(\tau ·\frac{\left|T\right|}{2^{\Omega \sqrt{log\left|T\right|}}}\right)$ preprocessing time and space.