Fast algorithms for computing sequence distances by exhaustive substring composition

Abstract

The increasing throughput of sequencing raises growing needs for methods of sequence analysis and comparison on a genomic scale, notably, in connection with phylogenetic tree reconstruction. Such needs are hardly fulfilled by the more traditional measures of sequence similarity and distance, like string edit and gene rearrangement, due to a mixture of epistemological and computational problems. Alternative measures, based on the subword composition of sequences, have emerged in recent years and proved to be both fast and effective in a variety of tested cases. The common denominator of such measures is an underlying information theoretic notion of relative compressibility. Their viability depends critically on computational cost. The present paper describes as a paradigm the extension and efficient implementation of one of the methods in this class. The method is based on the comparison of the frequencies of all subwords in the two input sequences, where frequencies are suitably adjusted to take into account the statistical background.

Figure 1

Phylogenetic trees derived for small samples under various compositional distances.

Figure 2

Phylogenetic trees derived for small samples under various compositional distances. With a sample of "closer" species, some differences appear in the tree already for small values of k (top row): all fixed k-mers with k = 5, same as for k = 6 or 7 (left); maximal k-mers up to a maximum K = 5 (center); and all k-mers up to a maximum K = 5, same as for k = 6 or 7 (right). This is repeated with K = 15 in the second row, with K = 45 in the third row except for the middle entry set at K = 6 and K = 7, respectively, since trees then stabilize for higher K.