updated October 28, 2007
(completed text for scale-free networks)
Topologies for Artificial Gene Networks
One of the objectives of this research is to study the importance of network topologies in the behavior of gene networks. Additionally it is also important to know how several reverse engineering methods behave against diverse topologies.
Our artificial gene networks follow several topologies:
- Erdös-Renyi-like random networks
- Regular lattices
- Watts-Strogatz (small-world) networks
- Albert-Barabási (scale-free) networks
Starting with the work of Erdös and Renyi. Such networks have the characteristic that, on average, each gene is much like any other gene. The Kauffman networks (also known as nk systems) contain n genes that each have the same number k of inputs from other genes. Our random networks have a fixed number of inputs and each gene has equal probability of affecting each other gene.
Regular lattices are the opposite to random networks. Here each gene receives inputs from a small number of nearest neighbors. One dimensional lattices are rings, two dimensional ones are square grids. In regular lattice networks there is a well marked notion of neighborhood for each gene. Note that genes on the opposite sides of the lattice are very distant from each other (i.e. perturbations on one will take a long time to propagate to the other).
Watts and Strogatz studied small-world networks and showed that these are intermediate between regular lattices and random networks. Small world networks reproduce the famous "6 degrees of separation" effect, where each node in the network can be reached from another through a small number of connections. The algorithm of Watts and Strogatz first starts by constructing a 1D regular lattice, where each gene is connected to k nearest neighbors; then it proceeds to rewire each connection randomly with a certain probability. Our software uses the Watts-Strogatz algorithm to generate small-world gene networks.
Scale free networks
Albert and Barabási made popular the concept that many networks have the property that the majority of their nodes have a small number of connections while a small number of nodes have a very large number of connections. The distribution of numbers of connections (degree distribution) is a power law, usually with a low exponent. Several researchers have shown evidence that real gene networks are scale free, though others disagree. Albert and Barabási argue that such networks are natural if they form in a historical way, with new nodes being linked to the network such that the probability to link to an existing node is proportional to the number of nodes that one is already linked to. Our software uses the Albert-Barabási algorithm to generate scale-free gene networks.