Sudoku, folding proteins and coherent diffraction

pnas_elser_cover.jpg…all of these problems have a lot in common – they involve exhaustive search with a huge number of parameters, accompanied by a similarly large number of constraints, or rules.

The picture on the left is from the cover illustration to PNAS issue back in January of this year, accompanied by the paper by Elser et al., “Searching with iterated maps” PNAS 104, 418 (2007).

One of the key applications is in coherent x-ray imaging – coherent diffraction patterns are fourier transforms of real-space density of an object, but due to phase problem (loss of phases during the measurements of x-ray intensities) one can’t simply perform inverse fourier transform to get back to real-space image. But oversampling – measuring intensities at at least twice the spatial frequency of the object – can solve the phase problem by bringing the number of equations equal to the number of unknown variables again. One can solve for phases by considering restraints, or rules, imposed by such experiments – for example, intensities are known (while phases are not), real space densities are real positive numbers, typically contained within a finite volume (support). There may be more elaborate restraints.

By using an approach based on differential map algorithm one can alternate performing simple projections in real and reciprocal space, using the restraints mentioned above, alternated with Fourier transforms to go from real space to reciprocal space and back.

This approach can be applied to other problems – from finding the local minimum in energy landscape for protein folding, packing and tiling probelms to finding a unique solution for sudoku problems, jumble and other puzzles.

For more info see this wikipedia page or slides of talk by Veit Elser from his Cornell webpage.

This entry was posted in coherent, xray and tagged , , , , . Bookmark the permalink.

One Response to Sudoku, folding proteins and coherent diffraction

  1. Pingback: Cancer Becomes Clearer With Lensless X-Ray Camera | Cancer Research Journal

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s