Automated generation of heuristics for biological sequence comparison

Abstract

Background: Exhaustive methods of sequence alignment are accurate but slow, whereas heuristic approaches run quickly, but their complexity makes them more difficult to implement. We introduce bounded sparse dynamic programming (BSDP) to allow rapid approximation to exhaustive alignment. This is used within a framework whereby the alignment algorithms are described in terms of their underlying model, to allow automated development of efficient heuristic implementations which may be applied to a general set of sequence comparison problems.

Results: The speed and accuracy of this approach compares favourably with existing methods. Examples of its use in the context of genome annotation are given.

Conclusions: This system allows rapid implementation of heuristics approximating to many complex alignment models, and has been incorporated into the freely available sequence alignment program, exonerate.

Figure 1

Example of joining two HSPs. A single point on each HSP is chosen to be be included in the alignment. This is the centre of the HSP according to the scores, such that equivalenced bases on either side contribute to half of the HSP score. As shown in this example, if the centre of the HSPs according to their length had been chosen instead, it would not have been possible to join them to form an alignment.

Figure 2

The five types of sub-alignment region around HSPs in which dynamic programming may be applied. The start of an HSP (A), handling small gaps by joining two adjacent ends of HSPs (B), handling large gaps by joining two distant HSPs via a span (C,D) and the end of an HSP (E). Other features, such as splice sites are incorporated into the alignment within the SARs.

Figure 3

A toy example of bounded sparse dynamic programming. In this example the bounds indicate that if the overall alignment threshold is greater than 280, no sub-alignment DP is required. Otherwise, the region between A and B is confirmed first, and the bounds obviate DP between A and C. For clarity, terminal bounds are not included in this example.

Figure 4

Models for alignment of an EST to genomic sequnce. The exhaustive model for aligning ESTs to genome DNA, showing portal states and span states is shown in Figure 4 (a). The portal states are match forward and match reverse, and these share a set of HSPs. The span states are intron forward and intron reverse, and may accommodate large gaps. These portal and span states are represented in the heuristic model shown in Figure 4 (b), with each transition represented by a different derived model, labelled A to E, corresponding to the SAR types show in Figure 2.

Figure 5

Example of generation of a derived model. The original model on the left (for Smith-Waterman-Gotoh) is used to generate the derived model on the right for joining two adjacent HSPs. Extra transitions are allowed from the START state to the INSERT and DELETE states and onto the END state, as the derived model must allow gaps to open directly from the HSPs (in contrast to Smith-Waterman-Gotoh where an alignment cannot start with a gap). Additionally, the original model is local, but in this case the derived model is global, as it must start and end on the HSP.

Figure 6

Example of BSDP during alignment of a protein sequence to genomic DNA. Figure 6 (a) shows 912 candidate SARs positioned on the HSPs. Figure 6 (b) shows the 109 SARs to which DP is applied during BSDP, and Figure 6 (c) shows the 18 SARs which appear in the final alignment.