Algorithms in Nature
Computer science and biology have shared a long history together. For many years, computer scientists have designed algorithms to process and analyze biological data (e.g. microarrays), and likewise, biologists have discovered several operating principles that have inspired new optimization methods (e.g. neural networks). Recently, these two directions have been converging based on the view that biological processes are inherently algorithms
that nature has designed to solve computational problems.
This website documents new studies that have taken a joint computational-biological approach to study the algorithmic properties of biological processes across all levels of life (molecular, cellular, and organism).
Please contact us
to have your paper added to this list.
Reviews and Perspectives
Distributed information processing in biological and computational systems.
S. Navlakha and Z. Bar-Joseph. Communications of the ACM, 2015.
The ecology of collective behavior.
D. Gordon. PLoS Computational Biology 2014.
Design principles of regulatory networks: searching for the molecular algorithms of the cell.
W.A. Lim et al. Cell 2013.
Theoretical distributed computing meets biology: a review.
O. Feinerman and A. Korman. Proc. Intl. Conf. on Distributed Computing and Internet Technologies, LNCS 7753, 1-18, 2013.
Biology as reactivity.
J. Fisher, D. Harel, T.A. Henzinger. Communications of the ACM, 54(10):72-82, 2011.
Algorithms in nature: the convergence of systems biology and computational thinking.
S. Navlakha and Z. Bar-Joseph. Nature-EMBO Molecular Systems Biology, 7:546, 2011.
Algorithmic systems biology.
C. Priami. Communications of the ACM, 52:80-88, 2009.
Executable cell biology.
J. Fisher and T.A. Henzinger. Nature Biotechnology, 25(11):1239-1249, 2007.
J. Wing. Communications of the ACM, 49:33-35, 2006.
Design patterns from biology for distributed computing.
Babaoglu et al. ACM Trans. Auton. Adapt. Syst., 1:1, 26-66, 2006.
Protein molecules as computational elements in living cells.
D. Bray. Nature, 1995.
Network Design and Analysis
Decreasing-rate pruning optimizes the construction of efficient and robust distributed networks.
Navlakha et al. PLoS Comput. Biol., 2015.
[CS+Bio: Experimentally tested how rates of synapse pruning affect network topology, and used these insights to propose novel network design algorithms based on hyperconnection followed by aggressive pruning.]
How the rate of developmental synapse pruning affects network topology.
Topological properties of robust biological and computational networks.
Navlakha et al. J. R. Soc. Interface, 2014.
[CS+Bio: Developed new insight on how biological networks accomodate failures and noise and used these ideas to design robust communicaton networks.]
Adjusting network topology in yeast based on expected environmental noise.
Robustness and compensation of information transmission of signaling pathways.
Uda et al. Science, 341(6145) 558-561, 2013.
[CS+Bio: Develop an information-theoretic model of robustness and compensation of information transmission in signaling pathways at the cell population level.]
Information transmission of signaling pathways.
Energetic costs of cellular computation.
Mehta and Schwab. PNAS, 109(44), 17978-17982, 2012.
[CS+Bio: Analytically model the energetic costs cells require to compute and learn about their environments and how this restricts their behavior (e.g. sporulation).]
A cellular network for the computation of an external ligand concentration.
The regulation of ant colony foraging activity without spatial information.
Prabhakar et al. PLoS Comp. Biol., 8(8) e100267009, 2012.
[CS+Bio: Discovered the 'Anternet': connections between how ants determine the number of foragers to send out of the nest and the transmission control protocol used on the Internet.]
Poisson distribution of intervals between the arrival of successive returning foragers at the nest.
Physarum polycephalum percolation as a paradigm for topological phase transitions in transportation networks.
A. Fessel et al. Phys. Rev. Lett., 109:078193, 2012.
[CS+Bio: Studied the percolation transition of growing slime mold networks and proposed a link between vascular network growth and cancer treatment.]
Formation of an extended tubular network by fusion and growth of microplasmodia.
Evolution of a modular software network.
M. Fortuna et al. Proc. Natl. Acad. Sci. USA, 108:19985-9, 2011.
[CS+Bio: Studied the evolutionary principles of module-dependency graph of the Linux operating system and proposed analogies with time-varying ecological networks of interacting species.]
Evolution of the modular structure of the network of dependencies between packages of the Linux operating system.
Information transduction capacity of noisy biochemical signaling networks.
R. Cheong et al. Science, 334:354-358, 2011.
[CS+Bio: Developed a information-theoretic framework to predict the amount of information transduced by molecular and cellular networks in the presence of noise.]
Information-theoretic analysis of cell signaling fidelity.
Rules for biologically inspired adaptive network design.
A. Tero et al. Science, 327:439-442, 2010.
Biological solutions to transport network design.
Bebber et al. Proc. R. Soc. B, 274, 2307-2315, 2007.
Physarum can compute shortest paths.
Bonifaci et al. SODA 2012.
[CS+Bio: Developed a new distributed network design algorithm based on foraging strategies of the slime mold P. polycephalum.]
Slime-mold-inspired network design.
Comparing genomes to computer operating systems in terms of the topology and evolution of their regulatory control networks.
K-K. Yan et al. Proc. Natl. Acad. Sci. USA, 107:9186-91, 2010.
Universal distribution of component frequencies in biological and technological systems.
T. Pang and S. Maslov. Proc. Natl. Acad. Sci. USA, 2013.
[CS+Bio: Compared and contrasted the organizational and evolutionary principles of the Linux call graph with regulatory networks with respect to robustness and cost effectiveness.]
The structure of the E. coli regulatory network and the Linux call graph.
Efficient physical embedding of topologically complex information processing networks in brains and computer circuits.
Bassett et al. PLoS Comp. Biol., 2010.
[CS+Bio: Proposed new similarities between the modular structure of computer circuits (VLSI design) and brain circuits based on the Rentian scaling and information.]
Schematic for computing the Rentian exponent of a network.
Defining network topologies that can achieve biochemical adaptation.
Ma et al. Cell, 2009.
[CS+Bio: Discovering core topologies to perform adaptation in biochemical networks, and their potential role in engineering networks.]
A bio-inspired distributed clustering algorithm for wireless sensor networks.
C. Charalambous and S. Cui. Proc. of the Intl. Conf. on Wireless Internet, 6:1-6:8, 2008.
A biologically-inspired clustering algorithm dependent on spatial data in sensor networks.
Wokoma et al. Proc. of the IEEE European Workshop on Wireless Sensor Networks, 386-390, 2005.
[CS: Developed a distributed clustering algorithm inspired by lateral induction during intercell signaling (i.e. Notch and Delta activity) and quorum-sensing bacteria.]
Backup in gene regulatory networks explains differences between binding and knockout results.
Gitter et al. Molecular Systems Biology, 5:276, 2009.
Role of duplicate genes in genetic robustness against null mutations.
Gu et al. Nature, 421: 63–66, 2003.
[Bio: Discovered how duplicate genes (paralogs) functionally compensate for mutations or knock-outs; implications for fault tolerant network design.]
Compensation of a TF by a paralog (backup).
Intracellular signaling as a parallel distributed process.
D. Bray. J. Theor. Biol., 1990.
Programmable chemical controllers made from DNA.
Y-J Chen et al. Nature Nanotechnology, 2013.
[CS+Bio: Solving distributed consensus using DNA networks.]
An empirical model of crown shyness for lodgepole pinein British Columbia.
J. Goudie et al. Forest Ecology and Management, 2009.
Greedy scheduling of cellular self-replication leads to optimal doubling times with a log-Frechet distribution.
R. Pugatch. PNAS, 2015.
Designing collective behavior in a termite-inspired robot construction team.
Werfel et al. Science, 343 (6172), 754-758, 2014.
[CS: Present a multi-agent construction system inspired by mound-building termites to automatically generate low-level rules that guarantee construction of a user defined structure.]
Natural and artificial collective construction.
Space partitioning without territoriality in gannets.
E. D. Wakefield et al. Science, 341:6141 68-70, 2013.
[CS+Bio: Describe a competition-based model for how a segregated map of feeding locations for different colonies emerges without territoriality.]
Gannet colony foraging ranges.
Slime mold uses an externalized spatial "memory" to navigate in complex environments.
Reid et al. PNAS, 109(43), 17490-17494, 2012.
[CS+Bio: Describe a distributed model for how the brainless slime mold uses spatial memory during food search.]
Testing the slime mold's navigational ability using the U-shaped trap problem.
Cell-cycle regulation of NOTCH signaling during C. elegans vulval development.
S. Nusser-Stein, A. Beyer, I. Rimann, M. Adamczyk, N. Piterman, A. Hajnal, J. Fisher. Nature-EMBO Molecular Systems Biology, 8:618, 2012.
[CS+Bio: Describe how bounded synchrony models of synchronization can be achieved through cell-cycle control of signal transduction; a possible global principle used during the development of multicellular organisms.]
A model for bounded asynchrony during VPC differentiation.
The cell cycle switch computes approximate majority.
L. Cardelli and A. Csikasz-Nagy. Nature Sci. Reports, 2:656, 2012.
[CS+Bio: Showed how the cell cycle implements the approximate majority algorithm when deciding when to switch from inactive to active states of mitosis.]
Switch kinetics in the absence of external control.
Collaborative search on the plane without communication.
O. Feinerman et al. Proc. of the ACM Symp. on Principles of Distributed Computing, 77-86, 2012.
Memory lower bounds for randomized collaborative search and implications for biology.
O. Feinerman and Korman. Proc. of the Intl. Symp. on Distributed Computing, 2012.
[CS: Introduced new distributed computing tools for the generalized cow-path search problem based on ant foraging behavior.]
Illustration of two agents performing phase i of the distributed search algorithm.
A biological solution to a fundamental distributed computing problem.
Y. Afek et al. Science, 331:183-185, 2011.
[CS+Bio: Developed a novel solution to the maximal independent set problem based on cell fate determination processes in the fly brain.]
A probabilistic algorithm to elect leaders in a graph.
Fast and accurate decisions through collective vigilance in fish shoals.
Ward et al. Proc. Natl. Acad. Sci. USA, 108:2312-2315, 2011.
Predatory Fish Select for Coordinated Collective Motion in Virtual Prey.
Ioannou et al. Science, 337(6099), 1212-1215, 2012.
[Bio: Showed how speed and accuracy of decision-making increases with group size in fish shoals; implications for distributed consensus protocols.]
Collective vigilance in fish shoals.
Scalable network synchronization with pulse-coupled oscillators.
R. Pagliari and A. Scaglione. IEEE Transactions on Mobile Computing, 10:392-405, 2011.
Firefly-inspired heartbeat synchronization in overlay networks.
Babaoglu et al. Proc. of the Intl. IEEE Conf. on Self-Adaptive and Self-Organizing Systems, 77-86, 2007.
Firefly-inspired sensor network synchronicity with realistic radio effects.
Werner-Allen et al. Proc. of the Intl. ACM Conf. on Embedded Networked Sensor Systems, 142-153, 2005.
A scalable synchronization protocol for large scale sensor networks and its applications.
Y-W. Hong and A. Scaglione. IEEE J. Selected Areas Communication, 23:1085-1099, 2005.
Decentralized synchronization protocols with nearest neighbor communication.
D. Lucarelli and I-J. Wang. Proc. of the Intl. ACM Conf. on Embedded Networked Sensor Systems, 62-68, 2004.
Self-stabilizing pulse synchronization inspired by biological pacemaker networks.
A. Daliot et al. Proc. of the Intl. Conf. on Self-Stabilizing Systems, 32-48, 2003.
Brief announcement: linear time byzantine self-stabilizing clock synchronization.
A. Daliot et al. Proc. of the ACM Symp. on Principles of Distributed Computing, 379-379, 2004.
[CS: Synchronization protocols inspired by the study of coupled oscillators.]
The generalized input-output synchronization problem.
On optimal decision-making in brains and social insect colonies. J.A. Marshall et al. Journal of the Royal Society Interface, 6:1065-1075, 2009.
[Bio: Showed how honeybees optimally balance between accuracy and speed when choosing amongst new candidate homes.]
Evidence for complex, collective dynamics and emergent, distributed computation in plants.
D. Peak et al. Proc. Natl. Acad. Sci. USA, 101:918-922, 2004.
[CS+Bio: Mapped the problem of adjusting stomata opening times to a distributed consensus computation based on cellular automata.]
Leaf surface showing a field of stomata (brightness = closed).
A universal strategy for visually guided landing.
Baird et al. PNAS, 2013.
[CS+Bio: Proposed a new visually-guided landing strategy used by bees that removes some common assumptions used within current engineering approaches. The simple bee-inspired strategy may be applicable to future flying robots.]
Convergent acoustic field of view in echolocating bats.
L. Jakobsen, J.M. Ratcliffe, A. Surlykke. Nature, 2012.
[CS+Bio: Explore the relationship between bat size and echolocation call frequency; suggest that echolocation is a dynamic system that allows different species, regardless of their body size, to converge on optimal fields of view in response to habitat and task.]
Sonar beam width decreases as emitter (bat) size increases relative to wavelength.
The hippomcapus as a stable memory allocator for cortex.
L. Valiant. Neural Comput., 2012.
Stereopsis and 3D surface perception by spiking neurons in laminar cortical circuits.
Y. Cao and S. Grossberg. Neural Networks, 2011.
[CS+Bio: Developed a hierarchical cortical model of stereopsis and 3D surface perception based on response properties of the visual cortex.]
A model circuit diagram of 3D visual processing.
Short-term memory in neuronal networks through dynamical compressed sensing.
S. Ganguli and H. Sompolinsky. NIPS, 2010.
One rule to grow them all: a general theory of neuronal branching and its practical application.
Cuntz et al. PLoS Computational Biology, 6(8):e1000877, 2010.
[CS: Proposed new algorithms for constructing distributed minimum spanning trees based on rules of neuronal branching.]
Generating neuronal branching structures using optimized graphs.
Optimal localization by pointing off axis.
Yovel et al. Science, 327:701-704, 2010.
[CS+Bio: Discovered an optimal object tracking strategy based on studying echolocation in Egyptian fruit bats.]
Tracking strategy used by the bat compared to typical guidance systems.
A neuromorphic approach to computer vision.
T. Serre and T. Poggio. Communications of the ACM, 53:54-61, 2010.
A quantitative theory of immediate visual recognition.
T. Serre et al. Progress in Brain Research, 165:33-56, 2007.
Hierarchical models of object recognition in cortex.
M. Riesenhuber and T. Poggio. Nature Neuroscience, 2:1019-1025, 1999.
[CS+Bio: Proposed new hierarchical models for object recognition based on neuron activation patterns in the inferotemporal cortex in the macaque brain.]
Hierarchical feed-forward models of the visual cortex with varying levels of discrimination.
Reducing the dimensionality of data with neural networks.
G.E. Hinton and R. R. Salakhutdinov. Science, 2006.
A pomegranate-inspired nanoscale design for large-volume-change lithium battery anodes.
Liu et al. Nature Nanotechnology, 2014.
[Bio+CS: Proposed a new hierarchical structured silicon anode design based on clustering patterns of seeds in pomegranates.]
Pomegranate-inspired clustering design.
Radar tracking and motion-sensitive cameras on flowers reveal the development of pollinator multi-destination routes over large spatial scales.
Lihoreau et al. PLoS Biology, 10(9):e1001392, 2012.
[Bio+CS: Proposed a new model for learning short traveling salesman routes by tracking bumblebee foraging routes.]
Aerial view of the experimental field on which the bumblebees foraged.
Evolutionary trade-offs, Pareto optimality, and the geometry of phenotype space.
Shoval et al. Science, 336(6085), 1157-1160, 2012.
Evolutionary tradeoffs between economy and effectiveness in biological homeostasis systems.
Szekely et al. PLoS Computational Biology, 9(8):e1003163, 2013.
[Bio+CS: Describe how Pareto-optimality can be used to better understand the range of phenotypes found in nature.]
The Pareto front (best trade-offs) after eliminating dominated phenotypes.
A slime mold solver for linear programming problems.
Johannson and Zou. Proc. of the 8th Computability in Europe (CIE) Conf., 344-354, 2012.
[CS: Showed how to encode general linear programming (LP) problems as instances of the distributed growth dynamics of slime mold; prove that the model converges to the optimal solutions of the LP.]
Thermodynamics of prediction.
Still et al. Phys. Rev. Lett., 109, 120604, 2012.
[CS: Described a mathematical connection between the effective use of information and efficient thermodynamic operation for a environment-interacting system; applicable to a wide range of dynamical systems.]
Evidence of non-random mutation rates suggests an evolutionary risk management strategy.
Martincorena et al. Nature, 2012.
[CS+Bio: Proposed an evolutionary risk-management strategy model to preferentially select which genes to protect against mutation at a cost of reduced protection of other genes.]
Synonymous diversity along the E. coli genome is heterogeneous.
Rumor has it...: Relay communication of stress cues in plants.
Falik et al. PLoS One, 6, 11:e23625, 2012.
[Bio: Discovered that plants can transmit distress signals to each other through their roots; discuss possible adaptive communication mechanisms modeling this process.]
The adjustment of stomatal width by neighboring plants following stress inducement.
Heliostat field optimization: A new computationally efficient model and biomimetic layout.
Noone et al. Solar Energy, 7:792-803, 2012.
[CS+Bio: Proposed a compact and energy-efficient algorithm to layout solar power mirrors (heliostats) inspired by the arrangement of florets in a sunflower.]
Individual heliostat efficiency as a function of position including shading and blocking.
Fish schooling as a basis for vertical-axis wind turbine farm design.
Whittlesey et al. Bioinspiration and Biomimetics, 5:035005, 2010.
[Bio+CS: Proposed a new design model for placing turbines in wind power farms based on how schools of fish minimize drag.]
Infotaxis as a strategy for searching without gradients.
Vergassolia et al. Nature, 2007.
Saket Navlakha and Ziv Bar-Joseph, 2012-2015.