Featured Research

from universities, journals, and other organizations

Physicist's Algorithm Simplifies Biological Imaging -- And Also Solves Sudoku Puzzles

Date:
March 3, 2006
Source:
Cornell University
Summary:
Cornell physicist Veit Elser has been engrossed recently in resolving a pivotal question in biological imaging. So he hasn't had much time for brainteasers and number games. But in discovering an algorithm critical for X-ray diffraction microscopy, Elser and colleagues solved two problems. First, they gave researchers a new tool for imaging the tiniest and most delicate of biological specimens. And second, they discovered that the same algorithm also solves the internationally popular numbers puzzle Sudoku.

A Sudoku puzzle designed by Elser's difference map algorithm. The challenge is to fill in the missing cells of the table with letters A-Y so that there are no duplicates in any row, column or five-by-five block (outlined in red). The correctness of the solution should be immediately obvious to any Cornellian, as it will spell out the name of one of the university's founders.
Credit: Image courtesy of Veit Elser / Cornell University

Cornell physicist Veit Elser has been engrossed recently in resolving a pivotal question in biological imaging. So he hasn't had much time for brainteasers and number games.

But in discovering an algorithm critical for X-ray diffraction microscopy, Elser and colleagues solved two problems. First, they gave researchers a new tool for imaging the tiniest and most delicate of biological specimens. And second, they discovered that the same algorithm also solves the internationally popular numbers puzzle Sudoku.

Not just one puzzle. All of them.

The Sudoku discovery appeals to Elser's whimsical side. But the algorithm, he notes, has potential for all kinds of other endeavors. "There are a lot of problems that you can represent in terms of this language," he says. "We're providing the technique. Whatever people use it for, it's great for us."

The so-called difference-map algorithm, which Elser says could have applications from productivity optimization to nanofabrication, tackles problems for which the solution must meet two independent constraints. In the case of Sudoku, the constraints are simple: Each of nine numbers, considered alone, appears nine times in the grid so that there is only one per row and column. And all nine numbers appear within each of the nine blocks.

In X-ray diffraction microscopy, the constraints are more complex. But the beauty of the algorithm, as Elser demonstrates, is that complexity doesn't matter. By applying the algorithm to the jumble of raw data from such an experiment, researchers can now reconstruct from it a clear, detailed image.

The result, shown in images published with a recent article in the Proceedings of the National Academy of Sciences (PNAS) with lead author David Shapiro of the State University of New York at Stony Brook and other colleagues, is a richly detailed image of a specimen as small as a single yeast cell -- taken without staining, sectioning or otherwise damaging the specimen.

Unlike optical microscopes, which use a lens to focus light on a target (and are therefore only useful for specimens larger than the wavelength of visible light), imaging methods based on X-rays and electrons take advantage of the finer wavelengths provided by these forms of illumination.

But some of these methods can damage the specimen with harmful radiation, require that a specimen be stained or otherwise altered or lack the penetrating power necessary for three-dimensional reconstructions. X-ray diffraction microscopy, which uses "soft" X-rays and measures the resulting diffraction pattern, is often the method of choice because it gives a detail-rich image and leaves the specimen relatively unscathed.

The tricky part comes in using the diffraction pattern to reconstruct an image of the specimen. Instead of directly measuring the pixel-by-pixel contrast within the specimen, researchers are left with data that represents the object broken down into its constituent waves: a vast number of them, of different frequencies and amplitudes, waiting to be added up in a process called a Fourier synthesis to reconstruct the image.

"But if it were just combining waves with a definite oscillation and adding them up, that would be a piece of cake for a computer to do," says Elser.

The challenge is in the waves' phases, which are critical in reconstructing an image from the diffraction data. Without attention to that piece of the puzzle, the resulting image is reduced to noise.

"People used to say that's an impossible problem," Elser says. "Then people got to thinking about the fact that there are going to be constraints coming from some rather mundane facts -- that in principle will make the problem of deducing the phase like the solution of a solvable puzzle."

The mundane fact, in this case, was a basic premise of the X-ray diffraction experiment: that the object in view have a clearly defined boundary (i.e., that all pixel values outside that boundary be set to zero).

"If I set up waves with known amplitudes and synthesize them, I'll find that for essentially all random combinations of phases, the thing I get is an object not confined," Elser says. "It takes a very clever combination of the phases of all those waves to add up to something in only one region; and cancel out everywhere else."

For the second constraint, the researchers required that the wave amplitudes used in the Fourier synthesis matched those measured by the experiment.

With the two constraints in place, the difference-map algorithm completes the job.



Story Source:

The above story is based on materials provided by Cornell University. Note: Materials may be edited for content and length.


Cite This Page:

Cornell University. "Physicist's Algorithm Simplifies Biological Imaging -- And Also Solves Sudoku Puzzles." ScienceDaily. ScienceDaily, 3 March 2006. <www.sciencedaily.com/releases/2006/03/060303203416.htm>.
Cornell University. (2006, March 3). Physicist's Algorithm Simplifies Biological Imaging -- And Also Solves Sudoku Puzzles. ScienceDaily. Retrieved August 2, 2014 from www.sciencedaily.com/releases/2006/03/060303203416.htm
Cornell University. "Physicist's Algorithm Simplifies Biological Imaging -- And Also Solves Sudoku Puzzles." ScienceDaily. www.sciencedaily.com/releases/2006/03/060303203416.htm (accessed August 2, 2014).

Share This




More Computers & Math News

Saturday, August 2, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Google Mystery Barge Headed For The Scrap Yard

Google Mystery Barge Headed For The Scrap Yard

Newsy (Aug. 1, 2014) We may never know what was going on inside one of Google's mystery barges in Portland, Maine as it's now headed for the scrap yard. Video provided by Newsy
Powered by NewsLook.com
Escaping Email: Inspired Vision or Pipe Dream?

Escaping Email: Inspired Vision or Pipe Dream?

AP (Aug. 1, 2014) Dustin Moskovitz is plotting an escape from email, using his communications expertise in an attempt to change the way people connect at work, where the incessant drumbeat of email has become an excruciating annoyance. (Aug. 1) Video provided by AP
Powered by NewsLook.com
Google (Kind Of) Complies With 'Right To Be Forgotten Law'

Google (Kind Of) Complies With 'Right To Be Forgotten Law'

Newsy (July 31, 2014) Google says it is following Europe's new "Right To Be Forgotten Law," which eliminates user information upon request, but only to a certain degree. Video provided by Newsy
Powered by NewsLook.com
Tesla, Panasonic Ink Deal To Make Huge Battery 'Gigafactory'

Tesla, Panasonic Ink Deal To Make Huge Battery 'Gigafactory'

Newsy (July 31, 2014) The deal will help build a massive battery factory that Tesla says will produce 500,000 lithium batteries by 2020. Video provided by Newsy
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:

Breaking News:
from the past week

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile: iPhone Android Web
Follow: Facebook Twitter Google+
Subscribe: RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins