Cells Take On Traveling Salesman Problem - Science News: 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.