“You can do pretty well by following your nose.” —ANDY REYNOLDS
Cells can chart
efficient course
from A to Z
By Rachel Ehrenberg
Forget GPS. With no fancy maps or
even brains, immune system cells can
solve a simple version of the traveling
salesman problem, a computational
conundrum that has vexed mathematicians for decades.
The new research, which simulates
how a type of white blood cell seeks and
destroys infectious particles, shows
how living things — be they cells, sharks
or bees — find a target with only limited
information and cognitive skills.
“Some search strategies are perhaps
not the best, but they make the whole
exploration of a space very efficient,”
says theoretical ecologist Frederic
Bartumeus of the Spanish Council
for Scientific Research’s Center for
Advanced Studies in the city of Blanes.
The best mathematical minds have
been tackling the traveling salesman
problem for decades, and they have
found some efficient solutions. But no
one has figured out how to completely
solve the puzzle: For a given number of
cities, a traveling salesman must plan a
route that visits each city once, covering
the minimum possible overall distance.
A pencil and paper and brute force can
find the shortest route when there aren’t
a lot of target cities. But elaborate algorithms and serious computing power
are usually needed when the number of
targets reaches double digits.
The new research, to appear in
Physical Review E, shows that when there
aren’t a lot of targets, cells do a decent
job of finding the shortest possible route.
These cells “search” by tuning in to local
concentrations of chemical signals and
salesman problem, a computational
This map comes close to charting the shortest route connecting
71,009 Chinese cities. New studies
show that even cells can find nearly
optimal paths using simple rules.
then following the most intense signal to
a target. Repeating that process, known
as chemotaxis, allows immune cells to
find and demolish numerous invaders.
“You can do pretty well by following
your nose,” says mathematical biologist
Andy Reynolds, who did the new work
at the Biotechnology and Biological
Sciences Research Council’s Rotham-
sted Research institute in Harpenden,
England. “There’s no need to know
where all of the other sites are or to have
the means to figure out which one is the
nearest one.”
Computer simulations by Reynolds
show that using the follow-your-nose
strategy, an immune cell seeking five dif-
ferent targets will find a perfect traveling
salesman route. With 10 targets, the cells
were still pretty efficient: On average,
their routes were only 12 percent longer
than the shortest path. These routes were
comparable to the solutions calculated by
a simple computer algorithm.
When there are many target cit-
ies, the best approach to the traveling
salesman problem is a tool called linear
programming, says William Cook, an
expert in computational mathematics at
Georgia Tech. This method finds a lower
bound — a distance that the minimum
route can’t be shorter than — which can
then guide the search for a short route.
Routes that have 1,000 cities or fewer
can be easily solved with this method.
But when you add cities to your route,
the number of calculations required to
find the shortest path increases expo-
nentially. Scientists still don’t have
one clean algorithm that can crunch
the numbers, no matter how many cit-
ies, and find the shortest route. In fact,
researchers don’t even know if such a
solution is possible. (The Clay Math-
ematics Institute in Cambridge, Mass.,
offers $1 million to anyone who can solve
this kind of math problem or prove that
a solution does not exist.)
