Scientists harness logic of 'Sudoku' math puzzle to vastly enhance genome-sequencing capability

Jun 24, 2009

A math-based game that has taken the world by storm with its ability to delight and puzzle may now be poised to revolutionize the fast-changing world of genome sequencing and the field of medical genetics, suggests a new report by a team of scientists at Cold Spring Harbor Laboratory (CSHL). The report will be published as the cover story in the July 1st issue of the journal Genome Research.

Combining a 2,000-year-old Chinese math theorem with concepts from cryptology, the CSHL scientists have devised " Sudoku." The strategy allows tens of thousands of DNA samples to be combined, and their - the order in which the letters of the DNA alphabet (A, T, G, and C) line up in the genome - to be determined all at once.

This achievement is in stark contrast to past approaches that allowed only a single DNA sample to be sequenced at a time. It also significantly improves upon current approaches that, at best, can combine hundreds of samples for sequencing.

"In theory, it is possible to use the Sudoku method to sequence more than a hundred thousand DNA samples," says CSHL Professor Gregory Hannon, Ph.D., a genomics expert and leader of the team that invented the "Sudoku" approach. At that level of efficiency, it promises to reduce costs dramatically. A sequencing project that costs upwards of $10 million using conventional methods may be accomplished for $50,000 to $80,000 using DNA Sudoku, he estimates.

Originally devised to overcome a sequencing limitation that dogged one of the Hannon lab's research projects, the new method has tremendous potential for clinical applications. It can be used, says Hannon, to analyze specific regions of the genomes of a large population and identify individuals who carry mutations that cause - a process known as genotyping.

The CSHL team has already begun to explore this possibility via a collaboration with Dor Yeshorim, a New York-based organization that has collected DNA from thousands of members of orthodox Jewish communities. The organization's aim is to prevent genetic diseases such as Tay-Sachs or cystic fibrosis that occur frequently within specific ethnic populations. The team's new method will now allow the many thousands of DNA samples gathered by Dor Yeshorim to be processed and sequenced in a single time-saving and cost-effective experiment, which should identify individuals who carry disease-causing mutations.

The advantages of DNA Sudoku

The mixing together and simultaneous sequencing of a massive number of DNA samples is known as multiplexing. In previous multiplexing approaches, scientists first tagged each sample with a barcode - a short string of DNA letters known as oligonucleotides - before mixing it with other samples that also had unique tags. After the sample mix had been sequenced, scientists could use the barcode tags on the resulting sequences as identification markers and thus tell which sequence belonged to which sample.

"But this approach is very limiting," explains Yaniv Erlich, a graduate student in the Hannon laboratory and first author on the "DNA Sudoku" paper. "It's time-consuming and costly to have to design a unique barcode for each sample prior to sequencing, especially if the number of samples runs in the thousands."

In order to circumvent this limitation, Erlich and others in the Hannon lab came up with the idea of mixing the samples in specific patterns, thereby creating pools of samples. And instead of tagging the individual samples within each pool, the scientists tagged each pool as a whole with one barcode. "Since we know which pool contains which samples, we can link a sequence to an individual sample with high confidence," says Erlich.

The key to the team's innovation is the pooling strategy, which is based on the 2,000-year-old Chinese remainder theorem. "It minimizes the number of pools and the amount of sequencing," says Hannon of their method, which they dubbed "DNA Sudoku" because of its similarity to the logic and combinatorial number-placement rules used in the popular game.

The method, which the CSHL team has patented, is currently best suited for genotype analyses that require only short segments of an individual's genome to be sequenced to find out if the individual is carrying a certain variant of a gene or a rare mutation. But as sequencing technologies improve and researchers gain the ability to generate sequences for longer segments of the genome, Hannon envisions wider clinical applications for their method such as HLA typing, already an important diagnostic tool for autoimmune diseases, cancer, and for predicting the risk of organ transplantation.

More information: "DNA Sudoku—harnessing high-throughput sequencing for multiplexed specimen analysis" appears in the July 1st print issue of Genome Research. The full citation is: Yaniv Erlich, Kenneth Chang, Assaf Gordon, Roy Ronen, Oron Navon, Michelle Rooks, and Gregory J. Hannon. This article is available online at http://.cshlp.org/content/early/2009/05/15/gr.092957.109.full.pdf+html (doi:10.1101/gr.092957.109)

Source: Cold Spring Harbor Laboratory (news : web)

Explore further: Fungus deadly to AIDS patients found to grow on trees

add to favorites email to friend print save as pdf

Related Stories

Human chromosome 3 is sequenced

Apr 27, 2006

The sequencing of human chromosome 3 at Baylor College represents the final stage of a multi-year project to sequence the human genome.

Horse genome sequence draft is issued

Feb 07, 2007

The U.S.-led Horse Genome Sequencing Project has issued its first draft, making it available to biomedical and veterinary scientists around the world.

Recommended for you

Some anti-inflammatory drugs affect more than their targets

18 hours ago

Researchers have discovered that three commonly used nonsteroidal anti-inflammatory drugs, or NSAIDs, alter the activity of enzymes within cell membranes. Their finding suggests that, if taken at higher-than-approved ...

Researchers discover new strategy germs use to invade cells

Aug 20, 2014

The hospital germ Pseudomonas aeruginosa wraps itself into the membrane of human cells: A team led by Dr. Thorsten Eierhoff and Junior Professor Dr. Winfried Römer from the Institute of Biology II, members of the Cluster ...

Progress in the fight against harmful fungi

Aug 20, 2014

A group of researchers at the Max F. Perutz Laboratories has created one of the three world's largest gene libraries for the Candida glabrata yeast, which is harmful to humans. Molecular analysis of the Candida ...

How steroid hormones enable plants to grow

Aug 19, 2014

Plants can adapt extremely quickly to changes in their environment. Hormones, chemical messengers that are activated in direct response to light and temperature stimuli help them achieve this. Plant steroid ...

User comments : 1

Adjust slider to filter visible comments by rank

Display comments: newest first

Birger
not rated yet Jun 25, 2009
One possible application of this might be the sequencing of fossil DNA from extinct species, a subject successfully pursued by the team of Svante Pääbo at the Max Planck Institute. This is notoriously difficult, since the DNA is highly fragmented.
Another question is if this technology can be harnessed to push sequencing costs so low that "personalized medicine" becomes feasible -different people respond differently to specific medicines, and different tumors vary widely in their response to cancer medicines.