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 ( mishra@nyu.edu) 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.