Doi: 10.1145/1467247.1467270

technical Perspective
Where Biology
meets computing
by bud Mishra

alan tURinG DieD

in 1954 in his laboratory after eating a cyanide-laced apple. Though Turing’s mother believed her son’s death to be a result of the kind of accidents that befalls absent-minded mathematicians engaged in laboratory experiments, it is generally assumed to be a suicide.

During his last years, Turing had become an experimentalist, interested in bio-chemical systems. He had proposed a reaction-diffusion model in his 1952 paper entitled “The Chemical Basis of Morphogenesis,” putting forth his hypothesis of biological pattern formation. Turing’s models describe how the concentration of certain substances (called morphogens) distributed in space change under two con-tinuous-time processes: local chemical reactions, in which the substances are converted into each other, and diffusion, which causes the substances to spread out in space. The solutions to Turing’s Reaction-Diffusion equation display diverse patterns such as traveling waves, spirals, spots, stripes and dissipative solitons. Turing’s models focused on only continuously varying concentrations of morphogens: he famously wrote, “since the role of genes is presumably catalytic, …they may be eliminated from the discussion.”

However, genes turned out to be far more important in biological pattern formation. Triggered by a small group of transcriptional activators (proteins and microRNAs), the genes turn themselves on and off in a complex but tightly programmed choreography and control the concentration and spatial distribution of many biomol-ecules, including the transcriptional activators. Thus, pattern formation in biology is better understood by hybrid automata, in which the genes form complex discrete modes with their own program for state-transitions, while exhibiting continuous dynamics as the system dwells in various modes.

Another interesting characteristics of pattern formation is captured nicely in Wolpert’s French-Flag (or PI, Positional Information) Model, where the discrete levels of morphogen-concen-tration gradients, varying complexly over space and time, determine the fates of the biological cells in the local neighborhoods. This model is highly robust, scale-invariant, and asynchronous; they exhibit temporal structures in which order of the events are far more important than their exact timing. Thus, while the genotype/syntax of these systems are easily described by hybrid automata, their phenotype/ semantics can be ideally described by temporal logics.

As luck would have it, a growing community of computer scientists has been thinking about problems like these for last few decades and developing many powerful model-checking tools to debug complex asynchronous systems. Many of these researchers have now turned to systems biology, as exemplified by the paper here by Grosu et al.

The authors describe a biological model of interacting heart cells and studies how they form complex electrical patterns, using model-checking and machine-learning tools for specification, learning, and detection of emergent behavior/patterns in networks of hybrid automata. These tools shed important light on the process of atrial fibrillation (Afib), an abnormal rhythm originating in the upper chambers of the heart and afflicting millions, with incidences increasing with age. The cardiac tissue is a spatial network of myocytes (muscle fiber cells) that must contract in a coordinated fashion in order to pump blood effectively. Coordination is ensured through a reaction-diffusion system (RDS): the pace-making myocytes generate an electric stimulus that diffuses to the neighboring myocytes; these react in an all-or-nothing fashion, which

reinforces the stimulus and ensures its further propagation without damping. Reaction is governed by specific molecules (ion channels) in the myocyte membrane. The authors introduce many innovations to attack this problem algorithmically, namely, they replace the standard Luo-Rudi model of nonlinear partial differential equations by a network of hybrid automata and analyze them through efficient mode-abstractions and superposition; they develop a new modal logic, based on spatial-superposition, for specifying emergent behavior; they devise an ingenious method for learning the formulae of this logic from the spatial patterns; and finally, apply bounded model checking to detect the onset of one such biomedically important emergent patterns, that is, spiral waves.

The authors lead one to believe that the future of computer science very likely lies not just in devising powerful tools to catalyze large-scale experiments or to warehouse massive amount of experimental data to be searched and mined, but also as an interpreter and re-describer of complex phenomena. In this role, using tools described here, computer scientists can revolutionize the way we attempt to understand a large tangle of interconnected neurons, a large so-cial-network of presumably altruistic individuals, a crowd responding to a catastrophe, a global financial market interacting through complex trades, an interconnected power-grid, and so on. We could try to understand their topology, structural evolution, spatial patterning, self-organization, stochas-ticities, causal links, and emergent behaviors. We could look for design principles in these complex systems, some of which are thought (by some) to have been crafted by an intelligent designer, who appears to have cavalierly released these systems without proper documentation.

 

Bud Mishra ( [e-mail]) is a professor of computer science, mathematics, and cell biology at new york university’s courant institute and school of medicine. he is also a visiting scholar at the cold spring harbor laboratory and a fellow of both acm and ieee.