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

Abstract The q –gram distance between two strings $$s,s^\prime$$ , 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 $$L_1$$ -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 (T q D), 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 distance 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 T q D compares well to other non-alignment based measures regarding accuracy, while requiring substantially less memory than the classic q -gram distance.