Nature Likes a Good Algorithm

A living cell constantly needs to process information. It distinguishes threats from opportunities and determines when to divide versus when to die. According to Luca Cardelli, “cells would not survive without computation.”

This intersection of biology and computer science was the theme of Cardelli’s April 30 talk “The Cell Switch Computes Approximate Majority.” A computer scientist, Cardelli is the assistant director of Microsoft Research and a professor at the University of Oxford. This was the second event in McCormick’s CS+X colloquium series.

A biochemical switch triggers the irreversible transitions between phases of the cell cycle. For example, the switch fires when the cell decides to divide and duplicate. From there, it is committed to progressing to the next stage.

“It’s a universal mechanism,” Cardelli says. “Everything from yeast to us uses this same switch for cell division.

In an effort to “catch nature running an algorithm,” Cardelli aimed to find an algorithm relating to the cell cycle switch. He discovered that the cell cycle emulates the approximate majority algorithm—a well-studied distributed computing algorithm—when deciding to switch states. The approximate majority algorithm folds a minority population into a majority population, so that a single population results.

“The algorithm has ideal properties to settling a population into one of two states,” Cardelli said.

The algorithm switches the majority into a totality, therefore enabling the cell to make an irreversible decision. Cardelli said the algorithm is also fast, reliable, and robust, which are optimal qualities for both nature and a good algorithm. While there are many more details in real biological networks, he said, “nature likes a good algorithm.”