Local homology recognition and distance measures in linear time using compressed amino acid alphabets

Abstract

Methods for discovery of local similarities and estimation of evolutionary distance by identifying k-mers (contiguous subsequences of length k) common to two sequences are described. Given unaligned sequences of length L, these methods have O(L) time complexity. The ability of compressed amino acid alphabets to extend these techniques to distantly related proteins was investigated. The performance of these algorithms was evaluated for different alphabets and choices of k using a test set of 1848 pairs of structurally alignable sequences selected from the FSSP database. Distance measures derived from k-mer counting were found to correlate well with percentage identity derived from sequence alignments. Compressed alphabets were seen to improve performance in local similarity discovery, but no evidence was found of improvements when applied to distance estimates. The performance of our local similarity discovery method was compared with the fast Fourier transform (FFT) used in MAFFT, which has O(L log L) time complexity. The method for achieving comparable coverage to FFT is revealed here, and is more than an order of magnitude faster. We suggest using k-mer distance for fast, approximate phylogenetic tree construction, and show that a speed improvement of more than three orders of magnitude can be achieved relative to standard distance methods, which require alignments.

Figure 1

Here we show a core block from the CLUSTAL_W alignment of selected sequences containing SH2 domains. The upper alignment uses A, the standard amino acid alphabet. The lower version is the same alignment presented in the SE-V(10) alphabet (Table 1) in which members of a class are represented by its first letter in alphabetical order (e.g. I, L, M and V are shown as I). Columns that are perfectly conserved in the given alphabet are indicated with upper case letters and an asterisk (*) below. The number of conserved columns increases from 17 in A to 25 in SE-V(10). The number of fully conserved k-mers increases from 6 to 13 for k = 3 and from 4 to 9 for k = 4.

Figure 2

Scatterplots show the correlation between D, the fractional identity in the full alphabet computed from CLUSTAL_W alignments, and the fractional common k-mer count (F, equation 3) or the k-mer distance (Y, equation 4). We show three selected cases: the full alphabet A, k = 3 [the parameters used in (16)]; Dayhoff(6), k = 6 (used by MAFFT); and an intermediate case, SE-B(10), k = 4. Note that the relationship between D and Y is approximately linear.

Figure 3

The geometry of a diagonal (bold line) in a dynamic programming matrix. The length of the diagonal is λ, the margin is µ. If the diagonal can be identified in a pre-processing step such as k-mer extension or FFT, then the shaded region can be excluded, reducing the time needed to compute a global alignment by dynamic programming.