Searching genomic data faster with new algorithm

July 10, 2012 by Larry Hardesty in Biology / Biotechnology


Since 2002, the rate at which genomes can be sequenced has been doubling every four months or so, whereas doubles only every 18 months. Without the advent of new , biologists' ability to generate will soon outstrip their ability to do anything useful with it.

In the latest issue of , MIT and Harvard University researchers describe a new algorithm that drastically reduces the time it takes to find a particular in a database of genomes. Moreover, the more genomes it's searching, the greater the speedup it affords, so its advantages will only compound as more data is generated.

In some sense, this is a algorithm — like the one that allows computer users to compress data files into smaller zip files. "You have all this data, and clearly, if you want to store it, what people would naturally do is compress it," says Bonnie Berger, a professor of applied math and computer science at MIT and senior author on the paper. "The problem is that eventually you have to look at it, so you have to decompress it to look at it. But our insight is that if you compress the data in the right way, then you can do your analysis directly on the compressed data. And that increases the speed while maintaining the accuracy of the analyses."

Exploiting redundancy

The researchers' compression scheme exploits the fact that evolution is stingy with good designs. There's a great deal of overlap in the genomes of closely related species, and some overlap even in the genomes of distantly related species: That's why experiments performed on yeast cells can tell us something about human drug reactions.


"If I want to run a computation on my genome, it takes a certain amount of time," Baym explains. "If I then want to run the same computation on your , the fact that we're so similar means that I've already done most of the work."



The new algorithm would be useful in any application where the central question is, as Baym puts it: "I have a sequence; what is it similar to?" Identifying microbes is one example. The new algorithm could help clinicians determine causes of infections, or it could help biologists characterize "microbiomes," collections of microbes found in animal tissue or particular microenvironments; variations in the human microbiome have been implicated in a range of medical conditions. It could be used to characterize the microbes in particularly fertile or infertile soil, and it could even be used in forensics, to determine the geographical origins of physical evidence by its microbial signatures.

Berger's group is currently working to extend the technique to information on proteins and RNA sequences, where it could pay even bigger dividends. Now that the has been mapped, the major questions in biology are what genes are active when, and how the proteins they code for interact. Searches of large databases of biological information are crucial to answering both questions.

Provided by Massachusetts Institute of Technology

"Searching genomic data faster with new algorithm" July 10, 2012 http://phys.org/news/2012-07-genomic-faster-algorithm.html