TY - JOUR

T1 - Communication and complexity in a GRN-based multicellular system for graph colouring

AU - Buck, Moritz

AU - Nehaniv, C.L.

N1 - Original article can be found at http://www.sciencedirect.com Copyright Elsevier [Full text of this article is not available in the UHRA]

PY - 2008

Y1 - 2008

N2 - Artificial Genetic Regulatory Networks (GRNs) are interesting control models through their simplicity and versatility. They can be easily implemented, evolved and modified, and their similarity to their biological counterparts makes them interesting for simulations of life-like systems as well. These aspects suggest they may be perfect control systems for distributed computing in diverse situations, but to be usable for such applications the computational power and evolvability of GRNs need to be studied. In this research we propose a simple distributed system implementing GRNs to solve the well known NP-complete graph colouring problem. Every node (cell) of the graph to be coloured is controlled by an instance of the same GRN. All the cells communicate directly with their immediate neighbours in the graph so as to set up a good colouring. The quality of this colouring directs the evolution of the GRNs using a genetic algorithm. We then observe the quality of the colouring for two different graphs according to different communication protocols and the number of different proteins in the cell (a measure for the possible complexity of a GRN). Those two points, being the main scalability issues that any computational paradigm raises, will then be discussed.

AB - Artificial Genetic Regulatory Networks (GRNs) are interesting control models through their simplicity and versatility. They can be easily implemented, evolved and modified, and their similarity to their biological counterparts makes them interesting for simulations of life-like systems as well. These aspects suggest they may be perfect control systems for distributed computing in diverse situations, but to be usable for such applications the computational power and evolvability of GRNs need to be studied. In this research we propose a simple distributed system implementing GRNs to solve the well known NP-complete graph colouring problem. Every node (cell) of the graph to be coloured is controlled by an instance of the same GRN. All the cells communicate directly with their immediate neighbours in the graph so as to set up a good colouring. The quality of this colouring directs the evolution of the GRNs using a genetic algorithm. We then observe the quality of the colouring for two different graphs according to different communication protocols and the number of different proteins in the cell (a measure for the possible complexity of a GRN). Those two points, being the main scalability issues that any computational paradigm raises, will then be discussed.

KW - Genetic Regulatory Networks (GRNs)

KW - Artificial life

KW - Graph colouring problem

KW - Distributed computing

KW - Multicellularity

U2 - 10.1016/j.biosystems.2008.06.002

DO - 10.1016/j.biosystems.2008.06.002

M3 - Article

SN - 0303-2647

VL - 94

SP - 28

EP - 33

JO - Biosystems

JF - Biosystems

IS - 1-2

ER -