A self-described bioinformatics hobbyist has tinkered with an implementation of the Smith-Waterman algorithm for single-instruction multiple-data (SIMD) processors and made it eight times faster than previous SIMD implementations.
The Smith-Waterman algorithm is widely acknowledged as the best local alignment algorithm in bioinformatics, but its dynamic programming approach is notoriously slow.
As a result, countless lines of code have been written over the past several decades in an effort to develop a faster implementation of the sequence-alignment workhorse.
That trend has recently extended beyond the bioinformatics community, and the algorithm has become something of a grand challenge for developers experimenting with hardware-based accelerated systems like field-programmable gate arrays and graphics processing units.
In the latest example, Michael Farrar, a programmer at a telecommunications IT firm who described bioinformatics as a “hobby,” recently published a paper in Bioinformatics describing how he used Smith-Waterman for single-instruction multiple-data (SIMD) processors that offers up to an eight-fold speedup over previous SIMD implementations, which were themselves around six times faster than the unmodified version of the algorithm.
A version of the approach is currently available through the FASTA server at the University of Virginia, in an updated version of William Pearson’s SSEARCH implementation (source code for the programs is available here).
“The vectorized Smith-Waterman is faster than FASTA for average sized protein sequences,” Pearson told BioInform via e-mail.
Farrar, who has a day job at IT services firm Enea and credits an article in an in-flight magazine for alerting him to the computational challenges of genomics, said that he decided to tackle the Smith-Waterman challenge largely because several people told him it couldn’t be done.
Farrar said that his method improves upon previous SIMD implementations, such as Andrzej Wozniak’s, published in 1997, and Torbjørn Rognes and Erling Seeberg’s, published in 2000, in the way it formats the data for efficient querying.
“The reason it’s hard to vectorize the Smith-Waterman algorithm is when you’re computing one value, it requires the value above it, the value to the left of the above [value], and the value to the left. Vector operations are really good in the horizontal or the vertical, but not both, so then you have tradeoffs on how you want to do it,” he said.
“It’s not a heuristic approach in any way. It still produces the exact same results as Smith-Waterman.”
Both the Wozniak and Rognes implementations accessed the data in ways that accelerated the querying process, but Farrar noted that both methods still retained data dependencies between values that hampered their speed.
Farrar’s method accesses the data in a “striped” manner that enables it to avoid those data dependencies, he said. The approach moves all the conditional calculations out of the “inner loop” of the code, leaving only the essential dynamic programming calculations, which has “a significant effect on execution time,” according to the Bioinformatics paper.
Farrar noted that the implementation, which he calls striped Smith-Waterman, is “not a heuristic approach in any way. It still produces the exact same results as Smith-Waterman.”
Its performance, however, is comparable to heuristic approaches. In a comparison of SSEARCH against both methods in the Bioinformatics paper, the striped Smith-Waterman approach was only 30 percent slower than Blast and up to four times faster than FASTA.
According to the paper, other bioinformatics dynamic programming algorithms could benefit from the same sort of striped SIMD implementation, including global alignment algorithms, hidden Markov model approaches, sequence assembly algorithms, and intron/exon structure prediction algorithms.
Farrar said that he’s currently applying the approach to some of these other areas, but noted that he’s still doing bioinformatics on his own time, “so don’t expect another paper any time soon.”