As bioinformatics software developers learn to better manipulate powerful desktop processors, the argument that hardware accelerators are the only serious option for speeding up search algorithms is no longer an open-and-shut case. That being said, some algorithms are more in need of a boost than others. Smith-Waterman, used for optimal local sequence alignments, has long been regarded as the precise yet time-consuming and processor-heavy workhorse of database search tools. This lack of speed is perhaps one of the reasons why countless researchers have made the much faster, albeit slightly less accurate, Blast their algorithm of choice. The number of computations Smith-Waterman must run in order to provide such precision is what results in its sluggishness.
Successful attempts to accelerate Smith-Waterman have exploited SIMD (Single Instruction, Multiple Data) processing technology, integrated into most modern processor architecture in order to streamline parallel data processing. SIMD processing technology is what gives the GPUs in gaming consoles like Sony’s PlayStation the computational muscle necessary to produce such advanced renderings. SIMD technology is particularly well suited for parallelizing data of a uniform type that only requires a single operation, such as converting thousands or millions of pixels from one color to another. Whereas a CPU will operate on a single piece of data at a time, a SIMD-enabled processor instead calculates whole rows of data as large units or blocks, thus increasing compute time significantly.
According to Vipin Chaudhary, SIMD expert and associate professor of computer science at the University at Buffalo, Smith-Waterman lends itself well to SIMD acceleration because of its dynamic programming. “With Smith-Waterman, you can take different parts of the sequence and compute them in parallel, so you’re running the same code on different pieces of data,” he says. “In a typical Intel or AMD processor, you’re usually able to get an eight-fold speed up [over a traditional implementation].” Accelerations of Smith-Waterman have conventionally been capped at eight or 10 times because no matter how much you accelerate the algorithm, there is still a small percentage of the code that cannot be altered.
Denmark-based bioinformatics vendor CLC Bio recently released an accelerated, cross-platform-compatible Smith-Waterman solution that touts benchmarks beyond the eight- to 10-fold range in certain scenarios. The tool, the Bioinformatics Cell, is a software solution that includes a speed-injected treatment of Smith-Waterman for use with any desktop or laptop computer running Intel or AMD processors. According to CLC, standard Smith-Waterman searches on an average desktop that usually take 12 hours are reduced to roughly seven minutes with this SIMD-enabled version.
In tests running a Dell desktop with a 2.17 GHz Intel Core 2 Duo processor and 2 GB of RAM using only one of the cores, the Cell reportedly performed 45 to 48 times faster than a traditional software implementation of Smith-Waterman when running queries on a database containing more than 50,000 nucleotides. Though NCBI Blastp is still much faster, returning results in 53.9 seconds, CLC’s Smith-Waterman completed the same search in five minutes — but with roughly 14 percent more hits than Blastp.
Making the SIMD Switch
Some users are saying the switch to SIMD-powered Smith-Waterman is a worthwhile interruption. “There’s no question that you get a really significant speed-up [with the Cell], and frankly, I never even did much with Smith-Waterman before this implementation,” says Ronald Worthington, assistant professor of pharmaceutical sciences at Southern Illinois University. Worthington currently has a grant from the National Science Foundation to identify different bacterial genomes relating to industrial fermentation processes. He uses whole-genome shotgun data to identify transfer messenger RNA genes that are not annotated in the newer genome sequences. Prior to using the Cell tool, Worthington preferred WU-Blast over NCBI’s Blast because the former provided more reasonable alignments using the same parameters. But no version of Blast is comparable to the accuracy of the alignments provided by Smith-Waterman, he says. “For me, [the Cell] is really nice because it gives me this confidence that if there’s a match coming out of this whole-genome data, which is noisy because there’s sequencing errors in there, I’m going to find it.”
Diehard Blast users also might find CLC’s Smith-Waterman appealing because the graphical user interface is exactly the same as NCBI Blast. In essence, CLC’s developers have swapped out the NCBI Blast search engine so that all of the database search parts of the code have been replaced with the Smith-Waterman algorithm. The result is a search tool with the same familiar look but that, unlike Blast, ensures optimal local alignments between sequences.
However, the idea that a fast Smith-Waterman could replace Blast for many researchers misses the point, says Chris Mueller, a computer science graduate student at the University of Indiana currently working on a version of Blastp for the Cell BE processor. Mueller thinks that Blast’s lack of sensitivity is a red herring when it comes to bench users who essentially see Blast as good enough. “The main workflow for biologists with Blast is to look for sequences similar to the one they just sequenced,” he says. “For most, this is a one shot deal once every few months, so performance doesn’t really matter.”
CLC CEO Thomas Knudsen agrees that Blast has many benefits, but he contends that it’s time for a Smith-Waterman transplant. “Blast is a very thought-through algorithm and has worked well for the last 20 years and developed into something pretty useful — except that it doesn’t identify all the hits,” Knudsen says. “We thought it would be nice for people if they could remain working in the same environment with the same algorithm, but just make it more sensitive than Blast.”
Regardless of which side of the Blast vs. accelerated Smith-Waterman fence you sit on, many experts feel that CLC will really strike gold if it can produce an SIMD-accelerated version of HMMER, a dynamic search algorithm more widely used than Smith-Waterman. “One of the big things that genomics companies [do] is constantly screen the new data that’s coming online to look for targets of interest using the HMMER software with the Pfam database, but it’s really, really slow,” says Worthington at Southern Illinois. He says that some Pfam searches he ran went on for weeks, even with dual-processor computers. “If CLC can produce [an SIMD-enabled HMMER], it will be huge for the genomics industry and academics.”