Accelerated large-scale multiple sequence alignment

Abstract

Background: Multiple sequence alignment (MSA) is a fundamental analysis method used in bioinformatics and many comparative genomic applications. Prior MSA acceleration attempts with reconfigurable computing have only addressed the first stage of progressive alignment and consequently exhibit performance limitations according to Amdahl's Law. This work is the first known to accelerate the third stage of progressive alignment on reconfigurable hardware.

Results: We reduce subgroups of aligned sequences into discrete profiles before they are pairwise aligned on the accelerator. Using an FPGA accelerator, an overall speedup of up to 150 has been demonstrated on a large data set when compared to a 2.4 GHz Core2 processor.

Conclusions: Our parallel algorithm and architecture accelerates large-scale MSA with reconfigurable computing and allows researchers to solve the larger problems that confront biologists today. Program source is available from http://dna.cs.byu.edu/msa/.

Figure 1

Example multiple alignment and derived profile. Each position in a profile consists of a vector with character frequencies f_N for the corresponding column in a group of aligned sequences. (a) Multiple alignment of sequences s_i. (b) Profile derived from the alignment.

Figure 2

Profile space. In three dimensions, profile space is a triangle on the plane x + y + z = 1; however, five dimensions are required to represent DNA alignments. Points in profile space are shown with coordinates and an aligned column example (transposed). The corners of profile space represent columns of an alignment that contain all the same character.

Figure 3

Sample point determination. Sample points are determined by projecting lattice points onto the profile plane.

Figure 4

Planes parallel to profile space. Planes parallel to profile space are separated by a distance of $\epsilon =\sqrt{D}∕DL$. For this example, D = 3 and L = 4.

Figure 5

Profile reduction before alignment.

Figure 6

Example profile calculation and reduction for sequences 1 and 2. From the alignment {s₁, s₂}, a continuous profile is derived and then reduced to form the corresponding discrete profile p_1,2. S is a table of sample points.

Figure 7

Example profile calculation and reduction for sequences 3 and 4. From the alignment {s₃, s₄}, a continuous profile is derived and then reduced to form the corresponding discrete profile p_3,4. S is a table of sample points.

Figure 8

Near neighbors in profile space. Given two profile points, nearby sample points and associated symbol codes are shown.

Figure 9

Example profile alignment. A pairwise alignment algorithm treats discrete profiles as sequences. The resulting edit operations E_1,2,3,4 indicate the computed alignment between the discrete profiles p_1,2 and p_3,4, and the corresponding groups of sequences {s₁, s₂} and {s₃, s₄}.

Figure 10

Alignment quality on the BRAliBase data set. MUDISC (the new method) is compared with several alignment programs on a seven (k7) and fifteen (k15) sequence RNA reference set from BRAliBase 2.1. A higher score indicates better quality and is shown in relation to the average pairwise sequence identity (APSI). MUDISC uses discrete profile alignment.

Figure 11

Alignment quality on the MDSA data set. MUDISC (the new method) is compared with several alignment programs on the MDSA data set which contains nucleotide adaptations of the BAliBASE and SMART reference alignments. BAliBASE includes reference sets 1-7. MUDISC uses discrete profile alignment.

Figure 12

Alignment run time comparison with stages. Overall program runtimes are shown on the Influenza and HIV data sets with a breakdown of time spent in each stage.