Searching the World’s DNA Data

A single biological sample can produce millions of fragments of genetic information. Multiply that output by years of experiments involving humans, animals, plants, viruses and environmental samples, and researchers face a problem that is as computational as it is biological: How do they find the DNA sequence they need?

University of Maryland computer science Ph.D. student Ryan Synk is studying whether machine learning can make that search faster and more reliable.

Advised by Professor of Computer Science Ramani Duraiswami, Synk is developing LOCALE, a system designed to search the National Institutes of Health’s Sequence Read Archive, or SRA. The federal repository contains raw sequencing data submitted by researchers from around the world, making it a resource for studying organisms, diseases and genetic variation.

Its size and structure, however, also make it difficult to navigate.

“The very thing that makes it really useful to researchers is also the thing that makes it hard to analyze well,” Synk said. “It’s just really big.”

Math Meets Computing

Synk, who earned an undergraduate degree in mathematics and computer science from UMD in 2020, did not initially plan to pursue computer science research. He began as a mathematics major and added computer science after taking courses required by the math program.

“I found it to be a fun way of applying this mathematical thinking that I had to real problems,” Synk said.

His interest in machine learning was influenced in part by AlphaGo, the artificial intelligence system that defeated a professional Go player. As Synk took more computer science courses, he found that he preferred building programs to being tested on computer science concepts.

“I really hated taking CS exams, but I really loved doing CS projects,” Synk said. “I found myself constantly wanting to work on coding stuff.”

A numerical analysis course helped connect his interests in mathematics, science and programming. The class examined how scientific questions, including climate simulations, can be translated into algorithms that computers can run and evaluate.

Synk later worked with UMD Professor of Computer Science Tom Goldstein through the Research Experience for Undergraduates program (REU) and completed an internship at Lawrence Berkeley National Laboratory. Those experiences introduced him to scientific computing, large computing clusters and academic research.

Searching Raw Sequences

Synk’s doctoral research now combines machine learning and scientific computing. LOCALE grew out of his work on vector search, a method that represents information as lists of numbers called vectors. This enables computers to identify similar items by the similarity of their vectors.

Searching the SRA differs from searching a traditional DNA reference database. Sequencing machines typically break DNA into many short fragments called reads. Researchers receive those pieces rather than one complete, neatly ordered genome.

“It’s all there in this more raw, unprocessed state, and that’s what makes it hard to work with,” Synk said.

BLAST, a widely used biological search tool, works well when comparing sequences against assembled reference genomes. It is less suited to searching large collections of unassembled reads at the scale of the SRA.

Other search systems divide sequences into smaller sections, known as k-mers, and count how many sections overlap. That approach can operate at a larger scale, but a small mutation or sequencing error may change several sections and cause otherwise similar sequences to appear unrelated.

LOCALE uses machine learning to identify similarities despite those changes. The system is designed to retrieve relevant records even when fragments contain errors introduced by sequencing equipment or natural biological variation.

“These sequencing machines aren’t perfect,” Synk said. “If you want to search over stuff that’s been sequenced, you want to be robust to the noise introduced by a sequencer.”

Scaling DNA Search

A more flexible search system could help biologists examine how frequently a viral sequence appears in collected samples, compare genetic information across populations or study environmental samples containing DNA from multiple organisms.

Synk said the central goal is to give researchers a practical way to locate relevant information within a repository that continues to expand.

“If you were able to relatively quickly do these kinds of searches, it would benefit biologists,” Synk said. “They could understand the prevalence of a potentially cancer-causing or viral gene in a population.”

The system has not yet been applied to the entire archive. Synk said the next stage will focus on reducing its computational demands and testing it across a larger share of the SRA.

“We haven’t solved it yet,” he said. “But the next step is scaling up our work and determining how it can make these large collections of sequencing data more useful to biologists.”

—Story by Samuel Malede Zewdu, CS Communications