A bioinformatics research team at the University of Maryland has turned to technology originally developed for the gaming community to help analyze vast amounts of short-read data from next-generation sequencing instruments.
UMD’s Michael Schatz and colleagues have exploited an emerging trend in the IT community in which developers are harnessing 3D graphics hardware called graphics processing units to accelerate a range of applications.
The approach, called GPGPU, or general-purpose GPU, already has a few life science computing converts, but Schatz and the UMD team believe that next-generation sequencing could be the killer app that convinces the broader bioinformatics community to adopt GPU-based computing.
“As sequencing technology is getting very cheap with the new methods, we were concerned that the computing resources required to process the data wouldn’t be getting cheaper,” UMD’s Cole Trapnell told BioInform. “You may be generating all this sequence, but you might need a supercomputer to deal with it, so we liked the idea that graphics cards offered a researcher without a $100,000 IT budget the ability to process the data that he’s generating with his new Solexa machine, or whatever.”
In a paper published earlier this month in BMC Bioinformatics
, Schatz, Trapnell, and colleagues discuss a version of the MUMmer sequence-alignment program that they developed to run on a graphics card from nVidia.
The authors report that the program, called MUMmerGPU, got faster as the reads got shorter. For a query length of around 800 base pairs, MUMmerGPU was twice as fast as the CPU version. For a query length of 25 base pairs, however, the improvement was more than 10-fold.
While the order-of-magnitude acceleration was only seen for very short queries, “these read characteristics are beginning to dominate the marketplace for genome sequencing,” the authors note in the paper. “For example Solexa/Illumina sequencing machines create on the order of 20 million 50 bp reads in a single run. … Thus our application should perform extremely well on workloads commonly found in the near future.”
MUMmerGPU, which is available for download here, is well-suited for aligning many reads to a reference genome, which would have great utility for genotyping, for example. Schatz told BioInform that the team next plans to apply the approach to de novo assembly of short-read data.
“De novo assembly is the big target. That’s what’s on everybody’s minds,” he said. “You’re talking about millions and millions and millions of reads being produced by centers that don’t have supercomputers, so GPUs seem like an ideal fit for that.”
The first step in that task will be to develop a GPU-enabled method for computing overlaps between short reads, “which is a big component but not an assembler in itself,” Schatz said. “I think that’s one of the first things on our to-do list.”
‘An Unusual Choice’
Trapnell said that MUMmerGPU was an “unusual choice in terms of an application to use GPGPU computing for” because it’s very memory-intensive. GPU hardware has been optimized for visualizing 3D models and other graphics tasks, which means that it’s more suitable for scientific computing problems that rely on numeric computation.
Indeed, several bioinformatics projects that have turned to GPGPU computing have been in the area of protein-folding, which is more numerically intensive than alignment algorithms. Last year, Stanford University’s [email protected]
project released a version its software that runs on graphics processing units from ATI Technologies, while Sony developed a [email protected]
client for the PlayStation 3, which runs on the Cell processor, a GPU/CPU hybrid [BioInform 10-06-06
“We took a very cheap piece of hardware and it’s just 10 times faster. I think that’s a fantastic result.”
However, others in the bioinformatics community have coaxed significant improvements in speed from the Smith-Waterman alignment algorithm using GPUs. In 2005, researchers at Lawrence Livermore National Laboratory implemented Smith-Waterman on an nVidia GeForce 6800 graphics card and saw a six-fold speedup over the algorithm on a 2.0 GHz AMD Opteron [BioInform 12-05-05
More recently, Weiguo Liu and colleagues from Singapore’s Nanyang Technological University reported a 16-fold speedup in a GPU-enabled version of Smith-Waterman.
According to Schatz, some problems are “a natural fit” for GPGPU computing, “especially protein folding [or] applications where there is a lot of geometry or a lot of physics.” Other bioinformatics applications like Smith-Waterman and MUMmer, on the other hand, “take a little bit of creativity to kind of twist the problem around so that it’s formulated in the right way.”
Schatz said that Liu’s team “had to play some tricks so that they were filling out the alignment matrix kind of in a clever way so that they could do it in parallel.” However, he added, “once this technology gets more commonplace I think more tricks will come about where there will be avenues to apply GPU technology.”
Schatz and his team had some help from nVidia’s Compute Unified Device Architecture, or CUDA, a new programming toolkit that simplifies the process of porting existing algorithms to graphics hardware.
“nVidia’s working really hard to make writing GPGPU programs no more difficult than writing a normal, conventional C program,” Trapnell said. “I was impressed at how easy they made it to get MUMmer working correctly, for example.”
That’s not to say that the implementation was seamless. “We were able to get MUMmerGPU working correctly very quickly, but it took us a much longer portion of time to get it working fast,” Trapnell said, noting that because the hardware and CUDA programming tools are still relatively new, “they’re just not there yet in terms of being able to give you a good idea about how your code is going to run on the machine.”
Nevertheless, Schatz and Trapnell said they were pleased with the results of the project. “We took a very cheap piece of hardware and it’s just 10 times faster. I think that’s a fantastic result,” Schatz said.
Schatz acknowledged that while it might take “a little bit of work” for some users to get the graphics driver, the CUDA driver, and other necessary components in place, once those systems are set up, “you could run it just as easily as you could run the CPU version of MUMmer.”
Schatz sees a real opportunity for the methodology within a year or so when high-end GPUs will be available on most PCs. “You’re going to buy your machine from Dell or whoever and it’s going to have this GPU card in there that supports this architecture, and then our software will just run right out of the box with nothing extra to do,” he said.