The threshold q-gram distance: a simple, efficient, and effective distance measure for genomic sequence comparison

The q–gram distance between two strings s, s′, introduced by Ukkonen in 1992, is an alignment-free string similarity measure which can be computed in linear time, as opposed to the quadratic time necessary for alignment/edit distance. It is based on the L1-distance, or Manhattan-distance, between the multiplicity vectors of fixed-length substrings (so- called q-grams or k-mers), and has been successfully applied in diverse bioinformatics settings. In this paper, we introduce the threshold q-gram distance (TqD), a new distance measure which is similar to the q-gram distance but uses reduced information on the multiplicities of the q-grams. The new measure retains the linear time computation of the q-gram dis- tance but requires significantly less space. Storage space and accuracy of the measure can be controlled via a user-defined threshold t, which sets a limit on the maximum value of the integers in the multiplicity vectors. In particular, for t = 1, the comparison is made only on the basis of the sets of uniquely occurring q-grams on the one hand, and of repeated q-grams, on the other. We tested the new distance measure, using the benchmarking tool AFproject of Zielezinski et al. [Genome Biology, 2019], on several real-life data sets for phylogenetic reconstruction and compared the results with those of other k-mer based distance measures. Our experiments show that the new measure TqD compares well to other non-alignment based measures regarding accuracy, while requiring substantially less memory than the classic q-gram distance.