# DNA Sudoku

Researchers get help from a venerable number theory and a popular puzzle game to solve genetic medical mysteries

FILLING IN THE BLANKS: Could pinpointing genetic mutations be as easy as 1-2-3, er, A-C-G-T? Image: FLICKER/EDUARDO MUESES

• ### The Best Science Writing Online 2012

Showcasing more than fifty of the most provocative, original, and significant online essays from 2011, The Best Science Writing Online 2012 will change the way...

A 2,000-year-old math theorem, along with Sudoku, may soon help researchers untangle DNA at blazing speeds.

Hunting for a particular genetic mutation in hundreds of thousands of specimens can be an expensive and time-consuming process. In the past several years, faster multiplex DNA sequencing machines have sped up the acquisition of data, but researchers have still been hobbled by having to label each sample with a unique molecular identifier (or bar code) for analysis.

Scientists at Cold Spring Harbor Laboratory (CSHL) in Long Island, N.Y., are proposing a new take on a very old idea to tackle large data sets simultaneously. The team is applying the Chinese remainder theorem to pinpoint single samples in larger pools, which are arranged in rows and columns.

Invented about 2,000 years ago, the theorem is a method for mapping information using prime and co-prime numbers. In the case of DNA sequencing and Sudoku, the theorem is used to organize data points with coordinates in a box, but it can also be used to figure out all sorts of missing information in other domains, such as distant points sensed with high-speed radar, pieces of code, and who that attractive person was that you saw at three out of seven parties on a cruise ship.

By using the idea, researchers can deal with whole libraries of genetic information instead of looking at just "one genetic sequence at a time," says Yaniv Erlich, the lead author of the paper, published as the cover story of this month's Genome Research.

In Sudoku players must fill every row and column each with all nine numerals, but in applying this to so many genetic samples to search, the researchers call on state-of-the-art robots, machines and programs to do the specimen placing and searching for them. "Every cell in a Sudoku [puzzle] is like a specimen, and every digit is like a genotype," says Erlich, a doctoral student who had used the Chinese remainder theorem in previous work with radar. He brought the idea to the attention of his CSHL professor Greg Hannon.

Rights & Permissions

View
1. 1. PaoloMagrassi 12:36 PM 7/2/09

Chinese Remainder Theorem [Britannica]: ancient theorem that gives the conditions necessary for multiple equations to have a simultaneous integer solution. [...] It addresses the following type of problem. One is asked to find a number that leaves a remainder of 0 when divided by 5, remainder 6 when divided by 7, and remainder 10 when divided by 12. The simplest solution is 370. Note that this solution is not unique, since any multiple of 5 ෠౲ (= 420) can be added to it and the result will still solve the problem.

2. 2. riverboots 05:11 PM 7/2/09

Does the Chinese Remainder Theorem become case-sensitive in neurological conformity?

3. 3. emueses 10:46 AM 7/6/09

Interesting article. BTW, thanks for using my picture.

4. 4. jwr257 12:50 PM 7/12/09

Here is an easier solution..use the idle time on your computer (Windows, Mac, or Linux) to cure diseases, study global warming, discover pulsars, and do many other types of scientific research. It's safe, secure, and easy by using BOINC at http://boinc.berkeley.edu/. BOINC ( The Berkeley Open Infrastructure for Network Computing) is a non-commercial middleware system for volunteer and grid computing.

5. 5. Benedict9 in reply to riverboots 12:56 AM 7/13/09

Why naturally!

6. 6. ervedge 12:59 AM 7/30/09

The reference/url for "the paper" by Erlich should be:
http://genome.cshlp.org/content/19/7/1243
http://hannonlab.cshl.edu/dna_sudoku/main.html

7. 7. bertwindon 02:35 PM 4/3/10

Baloni

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Click one of the buttons below to register using an existing Social Account.

## More from Scientific American

• News | 6 hours ago | 2

### Hopes Dashed for HIV Cure with Bone Marrow Transplant

• Reuters | 9 hours ago | 1

### Winter Storm Pushes Up U.S. East Coast after Deep-Freeze in the South

• Reuters | 11 hours ago | 2

### As Keystone Ruling Nears, Canada Short on Time for Climate Plan

• Reuters | 12 hours ago | 9

### Arctic Thaw Tied to European, U.S. Heatwaves and Downpours

• Reuters | 13 hours ago

More »

## Latest from SA Blog Network

• ### Gag Me With a Spoon: "Val-Speak" Takes Over SoCal

Cocktail Party Physics | 5 hours ago
• ### Nerds and Words: Week 49

Overthinking It | 12 hours ago
• ### Photoblogging: Muppet or Flamingo?

MIND
The Thoughtful Animal | 14 hours ago
• ### Sunday Species Snapshot: Fijian Monkey-Faced Bat

Extinction Countdown | 16 hours ago
• ### Right now, there's a giant blue chicken in Trafalgar Square

Tetrapod Zoology | 16 hours ago

## Science Jobs of the Week

DNA Sudoku

X

Give a 1 year subscription as low as \$14.99

X

X

###### Welcome, . Do you have an existing ScientificAmerican.com account?

No, I would like to create a new account with my profile information.

X

Are you sure?

X

X

X