Print This Post Print This Post 1,183 views
Jan 12

Voyage of the DNA Treader.

Uncategorized Comments Off on Voyage of the DNA Treader.

Reported in PhysOrg, December 30, 2010

Richard Feynman was right: there is plenty of room at the bottom, and the beeping, lumbering trashcans of 1950s science fiction are gradually giving way to micro-droids the size of a speck of dust . . . or even a molecule.

But this new breed of invisibly tiny robots raises a new question: how can even rudimentary intelligence be squeezed into something whose largest moving part consists of a handful of atoms? One solution, says Caltech graduate student in computation and Nadine Dabby, is to build the smarts into the environment instead.

At January’s TEDxCaltech conference, Dabby will present a one-molecule robot capable of following a trail of chemical breadcrumbs. A paper she co-authored in Nature last May describes a “molecular spider” that can be coaxed to “walk” down a predetermined path.

The “legs” of the spider are made of short segments of DNA, as are the “substrate molecules” making up the path, each of which is anchored at one end like a blade of grass. Leg and substrate can bind together temporarily, but this process leaves the substrate slightly less “sticky” than it previously was, and the next leg that contacts it will not be held so long. That subtle difference in stickiness is what produces the robot’s walking behavior. With no sense of direction, plan, or purpose, its legs continually flutter around randomly, like those of the proverbial drunkard in probability studies. But because they are held less firmly by substrate that has previously been visited, the overall motion tends to proceed in the forward direction.

The breadcrumb pathway is laid out on the surface of a self-assembling biomolecule, generated by a process called “DNA origami.” Developed at Caltech in Erik Winfree’s lab by then-postdoc Paul W. K. Rothemund (now a senior research associate), this technique weaves a single into a space-filling rectangle. Long parallel stretches alternating with sharp U-turns create a pattern reminiscent of the back-and-forth track of a farmer plowing a field.

To cement the woven DNA in place, several much shorter DNA snippets are added; these “staple strands” bind at specific positions along the woven molecule’s length, clamping adjacent runs together like Zip-ties around a power cord. And those staple strands have a second function: they act as anchors for the substrate molecules that define the path. The rough 16 x 12 grid into which they fall isn’t dense enough to create very elaborate labyrinths, but it did allow the researchers to set up a few straightaways, some bends, and a sharp turn or two.

Technically, the spider has not eight legs but four, and it only walks on three of those. The fourth is used to bind the molecule to its start position, until a chemical signal from the researchers breaks the bond and sends the robot on its way. (Picture a three-legged iguana tethered to a post; the leash snaps, and the creature stumbles off on its rubbery legs.)

And what does a nano-bot in action look like? Using fluorescent markers and atomic-force microscopy, the team successfully produced a short and rather grainy “movie” of a spider actually making its sticky-footed way up the garden path.

With a pace measured in nanometers per minute, the tiny tripper isn’t likely to break any land speed records. Nevertheless, Dabby muses, given a few enhancements to its ability to interpret and alter its molecular environment, the robot could function as a biological computer, executing arbitrarily complex algorithms.

That first small step down a tiny trail of DNA just might represent one giant leap for bot-kind.

Print This Post Print This Post 1,825 views
Jan 12

Million-dollar mathematics problem.

Uncategorized Comments Off on Million-dollar mathematics problem.

Reported by NewScientist, 27 December 2010 in 2011 preview.

A draft solution to the so-called “P versus NP” problem generated excitement in 2010 – will 2011 bring a correct proof?

Vinay Deolalikar made waves in August when his draft solution to a mathematical problem that haunts computer science hit the internet.

It’s known as “P versus NP”, and a correct solution is worth $1 million. Sadly for Deolalikar, of Hewlett-Packard Labs in Palo Alto, California, his work didn’t check out. But the flurry of online activity surrounding the paper demonstrated a new way of doing mathematics – via blogs and wikis – and generated fresh excitement around the problem.

Formulated in 1971, P versus NP deals with the relationship between two classes of problems that are encountered by computers. P problems are relatively easy for computers to solve. But it can take an impracticably long time to solve NP problems, such as finding the shortest route between several cities – though it is easy to show whether a possible solution is correct.

If P = NP, computers may eventually be able to solve a host of complex problems, from protein folding to factorising very large numbers. The ability to solve the latter would spell trouble for algorithms that we rely on for internet security. Most people assume the opposite is true, that P ≠ NP; had Deolalikar’s paper been correct, it would have proved this.

The Clay Mathematics Institute in Cambridge, Massachusetts, has promised $1 million to the first person who can prove it one way or the other. To find out how likely this is to happen in 2011, see “Prediction: Its time has not come”.

Prediction: Its time has not come

Unlike many problems in science, highly theoretical enigmas like P versus NP are rarely solved piecemeal. Instead, they tend to remain unsolved for years and then, apparently out of nowhere, a proof that works pops up.

Predicting these breakthroughs might seem impossible, but we devised a way to estimate the likelihood of P versus NP being solved next year. We compared its “age”, or the time since the problem was formulated, to other long-standing mathematical problems.

First we compared P versus NP with 18 mathematical problems, from Fermat’s last theorem to the Poincaré conjecture, that were not solved until more than a decade after their “births” (see graph). This made arriving at a solution to P versus NP in 2011, when it will turn a sprightly 40, look premature: just 22 per cent of these other problems were solved before they turned 40. By the same logic, in 2024, we should be on the lookout for a solution to P versus NP. That’s when it turns 53, the age by which 50 per cent of the problems we examined were solved.

Here’s hoping that solving P versus NP turns out to be faster than proving the Honeycomb conjecture, which states that if you need to divide a surface into tiled shapes of equal size, a hexagon is the shape that requires the smallest length of dividing lines. Proving that took more than 1500 years.

We also compared P versus NP to 26 other problems that still haven’t been solved. In 2011, it will be younger than 81 per cent of those. Samuel Arbesman and Rachel Courtland

Read more: “In with the New Scientist: Our predictions for 2011”

preload preload preload