Skip to main content
Premium Trial:

Request an Annual Quote

Algorithm Whiz Kid Boosts Sequence Searches


Sometimes a fresh perspective on an old problem can yield new solutions. Department of Energy graduate fellow Ben Campbell Smith from Harvard University recently demonstrated this concept during a summer stint at the Biological Data Management and Technology Center at the Lawrence Berkeley National Laboratory.

Upon arriving at his assigned lab, Smith was tasked with solving a bottleneck problem that prohibits the center’s researchers from updating their Integrated Microbial Genomes system. The IMG system combines microbial data from the Joint Genome Institute, the University of California, San Francisco, and LBNL’s Life Sciences and Physical Biosciences divisions in order to facilitate comparative analyses. Whenever a microbe’s genome is sequenced, the data is sent to a supercomputer at the Pacific Northwest National Laboratory in Washington, which uses Blast to conduct all-by-all searches for matches among the roughly 3.2 million microbial sequences already in the database. The challenge is in formatting those results so that specific comparisons between two genomes can be located quickly and easily by researchers.

Before Smith’s arrival, the center utilized an algorithm written with Python that read the output line-by-line and then wrote the results to separate files based on the two taxons. But with datasets usually comprising 20 billion lines, the algorithm would often take 30 days to complete the task. With Smith’s new algorithm, these same jobs now take about 12 hours to complete.

Smith says that the algorithm he devised, which he wrote using the C++ programming language, is based on run-of-the-mill computer science solutions. “A lot of the basic components, like using binary search trees and stuff like that, are very well established computer science techniques, but to be honest, I knew nothing about this kind of bioinformatics work,” says Smith. “So I came there and they said here’s the project, and basically I thought, this sounds like a lot of other sorting kind of stuff people do, and this is how they normally do it.”

While Smith says he enjoyed his foray into bioinformatics code tweaking, his heart belongs to high-energy particle physics. His PhD work focuses on searching for the Higgs boson particle, a yet-to-be identified particle that, if discovered, may help solidify our current understanding of electrons and quarks, Smith says. But he is still involved with the LBNL project and aims to ensure that the new algorithm will work seamlessly.

One of the kinks has to do with memory limitations on the current system, but he is determined to make it work without the need for new hardware. “Right now, I’m finishing it up, but one of the problems is that the trees no longer fit in the RAM of the computers they have,” he says. “But I think it’s one of those things where we could be more clever and get it to work with existing computers.”

The Scan

CDC Calls Delta "Variant of Concern"

CNN reports the US Centers for Disease Control and Prevention now considers the Delta variant of SARS-CoV-2 to be a "variant of concern."

From FDA to Venture Capital

Former FDA Commissioner Stephen Hahn is taking a position at a venture capital firm, leading some ethicists to raise eyebrows, according to the Washington Post.

Consent Questions

Nature News writes that there are questions whether informed consent was obtained for some submissions to a database of Y-chromosome profiles.

Cell Studies on Multimodal Single-Cell Analysis, Coronaviruses in Bats, Urban Microbiomes

In Cell this week: approach to analyze multimodal single-cell genomic data, analysis of bat coronaviruses, and more.