Sign In

Communications of the ACM

Research highlights

Technical Perspective: Where Biology Meets Computing

View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook

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 continuous-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 biomolecules, 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-concentration 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 exemplifed 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 social-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, stochasticities, 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.

Back to Top


Bud Mishra ( 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.

Back to Top



©2009 ACM  0001-0782/09/0300  $5.00

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.


No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account
Article Contents:
  • Article
  • Author
  • Footnotes
  • ACM Resources