Bacteria Turns Problem Solver

The E. coli bacteria doesn’t get a great press. Even though it’s often harmless, and can even be beneficial to its host, all you ever hear about it is when it causes food poisoning. That’s so unfair: what about its Sudoku skills?

That may seem like the strangest introduction you’ll ever read, but it’s true: a team at the University of Tokyo has proven that E. coli bacteria can be used to communicate information, solve problems and complete a Sudoku puzzle.

For those not in the know, Sudoku involves a 9 x 9 grid (in the standard form of the game) in which some of the squares already contain numbers. The player then has to use logic and deduction to fill in the other squares so that each horizontal line, each vertical line, and each of nine 3×3 grids contain the digits one through nine, each appearing once.

(Despite what those who dislike the game often claim, it has nothing to do with mathematics. It’s a logic puzzle that merely uses digits as they are easier to keep track of. One spoof comic in the UK even produced a working SuDocWho with the faces of William Hartnell through Christopher Ecclestone.)

The Tokyo team kept its experiment simple by working on a 4 x 4 grid, but says there’s no theoretical reason it wouldn’t work in the full-blown version of the game. The key to the “solution” of the puzzle was in two aspects of E. coli: recombinases, the enzymes used in genetic recombination such as when a damaged cell repairs DNA molecules; and antisense RNA.

With apologies to biologists for a gross oversimplification, RNA is the counterpart of DNA and includes a molecule type known as messenger RNA, which encodes the blueprint for creating proteins. Antisense RNA’s role is to, where necessary, block this blueprint from being passed on. (More info on DNA and RNA in Jimmy Roger’s article: Science Is Sexy: DNA You Say?)

The system the researchers built involved each bacteria having one of four recombinases, corresponding to the digit (1 through 4) that the particular bacteria represented. Bacteria can “broadcast” their recombinases, so the other bacteria were set up so that as soon as they received three different digits from such broadcasts, they recognized that logically they must represent the remaining digit, and in turn began broadcasting that information themselves.

However, that process only discovers the digit and not the position. To get round this, the researchers assigned antisense RNA corresponding to the lines and mini-grids. The antisense RNA blocked each bacteria from receiving digit information from bacteria that didn’t belong in its vertical line, horizontal line or mini-grid.

To run the simulation, the bacteria that represented digits already filled in at the start of the puzzle were set to broadcast their digit straight away. That kicked off a chain reaction (if physicists will forgive my hijacking that phrase) and hey presto: the puzzle was soon resolved!