Sequence embedding for fast construction of guide trees for multiple sequence alignment

Abstract

Background: The most widely used multiple sequence alignment methods require sequences to be clustered as an initial step. Most sequence clustering methods require a full distance matrix to be computed between all pairs of sequences. This requires memory and time proportional to N2 for N sequences. When N grows larger than 10,000 or so, this becomes increasingly prohibitive and can form a significant barrier to carrying out very large multiple alignments.

Results: In this paper, we have tested variations on a class of embedding methods that have been designed for clustering large numbers of complex objects where the individual distance calculations are expensive. These methods involve embedding the sequences in a space where the similarities within a set of sequences can be closely approximated without having to compute all pair-wise distances.

Conclusions: We show how this approach greatly reduces computation time and memory requirements for clustering large numbers of sequences and demonstrate the quality of the clusterings by benchmarking them as guide trees for multiple alignment. Source code is available for download from http://www.clustal.org/mbed.tgz.

Figure 1

Tree Distances. Tree distances of SparseMap and mBed guide trees from full matrix guide trees for the BAliBase benchmark set (386 families), using the Robinson-Foulds metric. Data points above the bisectrix (red) indicate instances where the SparseMap tree is inferior to the mBed tree, and vice versa. Multiple data points may lie on top of each other.

Figure 2

Complexity of Embedding. Total time required to compute a full pair-wise distance matrix (red) is plotted against time taken to embed sequences (blue) for each entry in the HOMSTRAD/Pfam dataset (containing up to 10,000 sequences per entry).

Figure 3

Times for embedding up to 300,000 tRNA sequences. Number of calls to the d(x, y) distance function made during computation of a full pair-wise distance matrix (red), plotted against number of sequences for random subsets of Rfam entry RF00005 which contains 381,602 tRNA sequences. We only show the number of calls up to 40,000 sequences. In blue we show the times for embedding subsets up to 300,000 sequences in size. The full data set takes 40 minutes to embed.

Figure 4

Variation in alignment score induced by choice of guide tree. Alignment quality scores for a collection of five test cases (a-e) taken from the HOMSTRAD/Pfam dataset, and aligned with ClustalW using guide trees generated from a variety of sources. Quality scores using guide trees from ClustalW -quicktree and from mBed are shown as arrows. Scores from 1000 randomised guide trees are shown in dark blue. Scores from 1000 SparseMap guide trees are shown in light blue.

Figure 5

PCA visualisation of embedded H3 Influenza virus sequences. An embedding of 3994 GenBank haemaglutinin sequences from H3N2 influenza viruses, generated using mBed, and visualised using the first three axes of a PCA of the embedded vectors. Each sequence has been coloured by year of isolation to show the progression of sequence change between the years 1967 (blue) and 2008 (red).