Evolutionary Synthesis and Reverse Engineering of Complex Networks

Analog Genetic Encoding (AGE)

Evolutionary Synthesis and Reverse Engineering of Complex Analog Networks

Claudio Mattiussi, Daniel Marbach, Peter Dürr, Thomas Schaffter, Dario Floreano

The synthesis and reverse engineering of analog networks (see sidebar) are recognized as knowledge-intensive activities, where few systematic techniques exist. Given the importance and pervasiveness of analog networks, there is a founded interest in the development of automatic techniques capable of handling both problems. Evolutionary methods appear as one of the most promising approaches for the fulfillment of this objective.

Analog Genetic Encoding (AGE) is a new way to represent and evolve analog networks. The genetic representation of Analog Genetic Encoding is inspired by the working of biological genetic regulatory networks (GRNs). Like genetic regulatory networks, Analog Genetic Encoding uses an implicit representation of the interaction between the devices that form the network. This results in a genome that is compact and very tolerant of genome reorganizations, thus permitting the application of genetic operators that go beyond the simple operators of mutation and crossover that are typically used in genetic algorithms. In particular, Analog Genetic Encoding permits the application of operators of duplication, deletion, and transpositions of fragments of genome, which are recognized as fundamental for the evolution and complexification of biological organisms. The resulting evolutionary system displays state-of-the-art performance in the evolutionary synthesis and reverse engineering of analog networks.

Animation illustrating key features and applications of AGE
(requires Flash player)

The AGE Genome

The AGE genome is constituted by one or more strings of characters (called chromosomes) from a finite genetic alphabet. The experimenter defines a device set which specifies the kind of devices that can appear in the network. For example, the device set of an evolutionary experiment aimed at the synthesis of an analog electronic circuit could contain a few types of transistors, and the device set of an evolutionary experiment aimed at the synthesis of a neural network could contain a few types of artificial neuron models. The experimenter specifies also the number of terminals of each kind of device. For example, a bipolar transistor has three terminals, a capacitor has two terminals, and an artificial neuron could be specified as having one output terminal and one input terminal. The AGE genome contains one gene for each device that will appear in the network decoded from the genome, as shown in the figure

The basic constituents of the AGE encoding of an analog network

Decoding the AGE Genome

Analog Genetic Encoding specifies the regions of the genome which correspond to the devices and to their terminals and parameters by means of a collection of specific sequences of characters that we call tokens. One specific device token is defined by the experimenter for each element of the device set. The device token signals the start of a fragment of genome that encodes an instance of the corresponding device. The experimenter defines also a terminal token, which delimits the sequences of characters that are associated with the terminals. The interaction between genes is represented in terms of a device interaction map I, which transforms pairs of character sequences associated with two distinct device terminals, into a numeric value that characterizes the link connecting the two terminals. The final result is an analog network decoded from the genome, as shown in the animation

Decoding of an analog network from two AGE chromosomes.

Journal Papers

Marbach, D., Schaffter, T., Mattiussi, C. and Floreano, D. (2009) Generating Realistic In Silico Gene Networks for Performance Assessment of Reverse Engineering Methods. Journal of Computational Biology, 16(2) pp. 229-239. [detailed record] [pdf] [bibtex]
Marbach, D., Mattiussi, C. and Floreano, D. (2009) Replaying the Evolutionary Tape: Biomimetic Reverse Engineering of Gene Networks. Annals of the New York Academy of Sciences, 1158 pp. 234-245. [detailed record] [pdf] [bibtex]
Marbach, D., Mattiussi, C. and Floreano, D. (2009) Combining Multiple Results of a Reverse Engineering Algorithm: Application to the DREAM Five Gene Network Challenge. Annals of the New York Academy of Sciences, 1158 pp. 102-113. [detailed record] [pdf] [bibtex]
Mattiussi, C., Marbach, D., Dürr, P. and Floreano, D. (2008) The Age of Analog Networks. AI Magazine, 29(3) pp. 63--76. [detailed record] [pdf] [bibtex]
Mattiussi, C. and Floreano, D. (2007) Analog Genetic Encoding for the Evolution of Circuits and Networks. IEEE Transactions on Evolutionary Computation, 11(5) pp. 596-607. [detailed record] [pdf] [bibtex]
Mattiussi, C., Waibel, M. and Floreano, D. (2004) Measures of Diversity for Populations and Distances Between Individuals with Highly Reorganizable Genomes. Evolutionary Computation, 12(4) pp. 495-515. [detailed record] [pdf] [bibtex] [demo code]

Conference Papers

Soltoggio, A., Dürr, P., Mattiussi, C. and Floreano, D. (2007) Evolving Neuromodulatory Topologies for Reinforcement Learning-like Problems. Proceedings of the 2007 IEEE Congress on Evolutionary Computation, pp. 2471-2478. [detailed record] [pdf] [bibtex]
Mattiussi, C., Dürr, P. and Floreano, D. (2007) Center of Mass Encoding: A self-adaptive representation with adjustable redundancy for real-valued parameters. Proceedings of the Genetic and Evolutional Computation Conference, GECCO2007, University College, London, pp. 1304-1311. [detailed record] [pdf] [bibtex]
Marbach, D., Mattiussi, C. and Floreano, D. (2007) Bio-mimetic Evolutionary Reverse Engineering of Genetic Regulatory Networks. Proceedings of the 5th European Conference on Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics (EvoBIO 2007), pp. 155-165. [detailed record] [pdf] [bibtex]
Dürr, P., Mattiussi, C. and Floreano, D. (2006) Neuroevolution with Analog Genetic Encoding. Proceedings of the 9th Conference on Parallel Problem Solving from Nature (PPSN iX), 9 pp. 671-680. [detailed record] [pdf] [bibtex]
Mattiussi, C. and Floreano, D. (2004) Evolution of Analog Networks using Local String Alignment on Highly Reorganizable Genomes. NASA/DoD Conference on Evolvable Hardware (EH'2004), pp. 30-37. [detailed record] [pdf] [bibtex]
Mattiussi, C. and Floreano, D. (2004) Connecting Transistors and Proteins. 9th International Conference on Artificial Life (Alife9), pp. 9-14. [detailed record] [pdf] [bibtex]

Patent / Thesis

Mattiussi, C. and Floreano, D. (2007) Method and device for the genetic representation and evolution of networks. Patent # US 2007/0011111 Al. [detailed record] [pdf] [bibtex]
Mattiussi, C. (2005) Evolutionary synthesis of analog networks. Ph.D. Thesis, 2005. [detailed record] [pdf] [bibtex]

	NEWS
	[16 Jun 2009] The LIS releases the gene-network inference challenges of the 4th DREAM conference, to be held in December 2009 at the Broad Institute of MIT and Harvard. [21 Oct 2008] Gene network reverse engineering: about 30 teams participate in the In Silico Challenges provided by the LIS for the 3rd DREAM Conference at MIT. [26 Nov 2007] DREAM2 gene network reverse engineering challenges: the biomimetic approach based on Analog Genetic Encoding (AGE) is best performer in the five-gene network challenge.


	Analog Networks. Many systems of technical and scientific interest can be seen as collections of devices connected by links characterized by a numeric value. We call these systems analog networks. Examples of analog networks are analog electronic circuits – where the devices are the electronic components that are not resistors and the link values correspond to the conductance between the terminals of the devices – artificial neural networks – where the devices are the neurons and the values correspond to the weights associated with the neuron inputs – and genetic regulatory networks (GRNs) – where the devices are the genes and the link values represent the effect of one gene on the activation of another.