Fractal Biology


Fractal Biology image from book

Biologists study not only genes, but also 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.

A puzzle that obsesses biologists is 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 members of the latter groups the hubs. This gives rise to what are sometimes called scale-free networks reminiscent of Mandelbrot’s fractals or in fact the Web. You can build a scale-free network as follows: Make 70 percent of all nodes have one edge and the remaining 30 percent have two or more. Of the 30 percent, 70 percent have two edges exactly and 30 percent have three edges or more. Of these 30 percent, 70 percent have three edges exactly and 30 percent have four edges or more, and so on.

One theory is that scale-free networks have good 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.

A typical problem is 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.

If there were just four protein nodes, then a simple square of interactions would achieve this goal (see Figure 1-6). Removing any node allows any remaining pair of nodes to communicate over at most two links.

image from book
Figure 1-6: A four-node network in which there is a one- or two-link path from any node to any other even if a node is deleted.

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 ten links or fewer and assuming no node can have more than three interaction links?

Solution to Warm-up

Figure 1-7 shows a nine-link solution.

image from book
Figure 1-7: A six-node network in which there is a one- or two-link path from any node to any other even if a node is deleted.

  1. Can you achieve the wounded distance two condition for eight nodes using 16 links, assuming no node can have more than four interaction links?

  2. What is the fewest number of links needed to achieve the wounded distance two condition for twelve nodes and at most five interaction links for any node?

  3. What is the fewest number of links needed for 12 nodes, but without any limit on the number of interaction links any particular node can have?

  4. We have a particular network having 108 proteins. We don’t yet know all the interactions. What is the fewest number of links needed to achieve the wounded distance two condition for any pair among these 108 nodes if there is a limit of 60 interactions that any single node can have? Try for a solution that uses fewer than 600 links.




Puzzles for Programmers and Pros
Puzzles for Programmers and Pros
ISBN: 0470121688
EAN: 2147483647
Year: 2007
Pages: 81
Authors: Dennis Shasha

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net