|
January 2006 Dr. Ecco's Omniheurist Corner.
January 01, 2006
URL:http://www.drdobbs.com/parallel/fractal-biology/184406402
Dennis, a professor of computer science at New York University, is the author of four puzzle books: The Puzzling Adventures of Dr. Ecco (Dover, 1998); Codes, Puzzles, and Conspiracy (Freeman 1992, reprinted by Dover in 2004 as Dr. Ecco: Mathematical Detective); and recently Dr. Ecco's Cyberpuzzles (W.W. Norton, 2002); and Puzzling Adventures (W.W. Norton, 2005). With Philippe Bonnet, he has written Database Tuning: Principles, Experiments, and Troubleshooting Techniques (2002, Morgan Kaufmann). With Cathy Lazere, he wrote Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (1995, Copernicus/Springer). He can be contacted at [email protected].
Our visitor that Saturday morning, an attractive woman with dark hair and a mischievous gleam in her eyes, introduced herself as Gloria Dopsis.
"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
White guess: 1, 2
Red guess: 3, 4
Green guess: 3, 4
You win 4 times out of the 24 possible permutations. That's 1/6 of the time. I think that's the best one can do. See if you can do better.
Black -- 1
White -- 2
Red -- 3
Green -- 4
Here are the programs. The boxes are numbered 1, 2, 3, and 4 in left-to-right order.
Black: 1; Black -> win, White -> 2, Red -> 3, Green -> 4
White: 2; White -> win, Black -> 1, Red -> 3, Green -> 4
Red: 3; Red -> win, Black -> 1, White -> 2, Green -> 4
Green: 4; Green -> win, Black -> 1, White -> 2, Red -> 3
The notation means the following:
Black starts at box 1; if box 1 has a black chip, then Black wins;
if box 1 has a white chip, then Black next opens box 2;
if box 1 has a red chip, then Black next opens box 3;
and so on.
This strategy wins 10 times out of 24 permutations. To see this, consider any ordering of the colors in boxes.
1 2 3 4 win/lose
Black White Red Green win
Black White Green Red win
Black Red White Green win
Black Red Green White lose
Black Green White Red lose
Black Green Red White win
White Black Red Green win
White Black Green Red win
White Red Black Green lose
White Red Green Black lose
White Green Black Red lose
White Green Red Black lose
Red Black White Green lose
Red Black Green White lose
Red White Black Green win
Red White Green Black lose
Red Green Black White win
Red Green White Black lose
Green Black White Red lose
Green Black Red White lose
Green White Black Red lose
Green White Red Black win
Green Red Black White lose
Green Red White Black win
Black —> box 1
White —> box 2
Red —> box 3
Green —> box 4
Blue —> box 5
Orange —> box 6
Here is the program for the agent for color X. Start at the box corresponding to color X in the arbitrary association. If you find X, then you've won, so you can stop. Otherwise, look up the color you find, say Y, in the arbitrary association and look at that box. If you find X, then you've won, so you can stop. Otherwise, look up the color you find, say Z, in the arbitrary association and look at that box. If you find X, then you've won. Otherwise, you lose.
For example, White does the following:
White: 2;The idea for this problem comes from Peter Winkler and the solution approach for the procedural agent scenario comes from Michael Rabin. The idea is to use the color-number association (which is completely arbitrary) in a consistent manner to direct each color to the next bucket. For the algebraists: You win whenever the longest cycle in the permutation is of length n/2 or less.
Black->1, White->win, Red->3, Green->4, Blue->5, Orange->6;
Black->1, White->win, Red->3, Green->4, Blue->5, Orange->6;
DDJ
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.