Dr. Dobb's Journal, January 2006
"I'm a biologist," she said. "I used to study genes, but now I study genomes, proteomes, interactomes, basically anything omic; that is, anything having to do with entire species. It's a perspective that might hurt many delicate human egos.
"For example, we have roughly the same number of genes as mice and most are very similar in form and function. We think of ourselves as a higher form of life, but the genome itself doesn't bear that out. The difference must be in the interactions, the networks of binding and repulsion that give rise to the unique capabilities of each species.
"Lately, I've been trying to figure out why protein interaction networks have the topologies they do. You see, most proteins have very few connections and very few have many connections. We call those the hubs. This gives rise to "scale-free" networks reminiscent of Mandelbrot's fractals or, in fact, the Internet.
"One theory is that scale-free networks have better failure properties. The thinking goes like this: Because mutations strike randomly at the genome, most mutations will wound proteins that interact with very few other proteins, thus are presumably less important. Fatal mutations of hub proteins can occur, too, but they are rare because hubs are rare.
"I'm here to ask your help to determine how many interaction links are needed to achieve high fault tolerance while ensuring that no unwounded protein is more than two interaction links away from another one."
Liane had slipped in shortly after Professor Dopsis arrived and had followed the discussion closely.
"Professor, could we try a little warm up?" she asked. "If there were just four protein nodes, then a simple square of interactions in Figure 1 would achieve this goal. Removing any node allows any remaining pair of nodes to communicate over at most two links."
"Well done," Dopsis replied. "Here's a second warm up. Can you achieve this distance two condition for six nodes even if one node is wounded (call that the "wounded distance two condition"), using 10 links or fewer assuming no node can have more than three interaction links?"
Liane came up with a nine-link solution to this warm up; see Figure 2.
"You're good," Dopsis said with her playful smile. "Here are more questions for you:
Ecco and Liane solved these problems that same morning. Professor Dopsis, in the meantime, told me of her work in the Amazon and how much she loved adventure. After hearing the answers, she left.
"She might come back," Ecco said. "The network problems here fit a general formulation that she will eventually face: Can you find the minimum number of links necessary for N nodes, maximum distance D between any pair of unwounded nodes, maximum degree (number of interactions per node) K, and up to X wounded nodes?"
Ecco made no attempt to solve the problem. Would you like to give it a try?
Further reading for the inspirations of this puzzle include "Regulation of Metabolic Networks: Understanding Metabolic Complexity in the Systems Biology Era," by Lee Sweetlove and Alisdair Fernie (New Phytologist 2005, 168: 9-24) and "Evolutionary Capacitance as a General Feature of Complex Gene Networks," by Aviv Bergman and Mark Siegal (Nature, July 31, 424(6948):549-52).
DDJ