White Blood Cells Solve Traveling-Salesman Problem

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 — successfully find a target, with only limited information and even more limited 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 Centre for Advanced Studies of Blanes.

While some of the best mathematical minds have been tackling the traveling-salesman problem for decades and some have found efficient solutions, 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 fancy algorithms and serious computing power are usually needed when the number of targets reaches mere double digits.

The new research, to appear in an upcoming Physical Review E, shows that when there aren’t a lot of targets, cells do a pretty good job of finding the shortest possible route that hits all the targets. These cells “search” by tuning into local concentrations of chemical signals and following the signals to the nearest target. Repeating that process 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. “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.”

Using the follow-your-nose-strategy, a process of moving in response to chemical gradients known as chemotaxis, an immune cell seeking five different targets will find a perfect traveling salesman route, show computer simulations by Reynolds, a scientist at the Biotechnology and Biological Sciences Research Council’s Rothamsted Research institute, in Harpenden, England. With 10 targets, the cells were still pretty efficient: on average, their routes were only 12 percent longer than the shortest possible path. These routes were comparable to the solutions calculated by a computer algorithm.

Currently, when there are many target cities, the best way to tackle the traveling-salesman problem is a tool called linear programming, says William Cook, an expert in computational mathematics at Georgia Tech in Atlanta.

This method finds a lower bound — a distance 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 exponentially, and scientist still don’t have one clean algorithm that can crunch the numbers, no matter how many cities, and find the shortest route.

In fact, researchers don’t even know if such a solution is out there. (The Clay Mathematics Institute in Cambridge, Massachusetts, offers $1,000,000 to anyone who can come up with this solution or prove that it does not exist.)

Tackling the traveling salesman problem with chemotaxis is a nice example of when the suboptimal is optimal, says Bartumeus. Of course, with all the information, time and resources in the world, thorough, systematic searches are ideal. But such situations rarely exist and perfect can’t be the enemy of good. Increasingly, there are examples of organisms using suboptimal strategies, such as chemotaxis or asearch pattern known as a Lévy walk (SN: 6/15/10, p. 15), or a combination of both strategies, which work best for the nonideal situations in which they exist.

By applying similar simple strategies, scientists are coming up with efficient ways to find all kinds of things, Bartumeus notes, like the source of a swirling plume of chemicals in a river, or even a child who has gone missing in a neighborhood of tangled, narrow streets.

Image: A white blood cell under scanning electron microscope. Photo: wellcome images/Flickr

source: http://www.wired.com/wiredscience/2011/04/cells-math-problem/