There are many parallel requirements of computational and biological systems, suggesting that each can learn from the other. Like virtually all large-scale computing platforms, biological systems are mostly distributed consisting of molecules, cells,ororganisms that interact, coordinate, and reach decisions without central control. However, unlike most computational methods, biological systems rely on very limited communication protocols, do not assume that the identity of the communicating agents is known and only utilize simple computations. This makes biological systems more robust to interference and environmental noise, and allows them to function efficiently in harsh settings, a property that is desirable in computational systems as well. Recent work demonstrated that for certain network based distributed algorithms, our improved ability to study biological processes at the molecular and cellular levels allows us to both improve our understanding of these biological processes as well as suggest novel ways to improve distributed computational algorithms. In this thesis we study distributed computing models for two natural phenomena, i) food search in bacteria swarm, ii) post translational modification in epigenetics. For bacteria, we propose a model based on an extension of the distributed gradient descent (DGD) algorithm. We show that our DGD model accurately predicts the true dynamics of bacterial chemotaxis while raising a number of novel hypotheses, some of which we experimentally validated. We then show that the revised DGD model can be used to improve the performance of robotic swarms and for efficient response during mass evacuations. For epigenetics, we present a distributed shared memory consensus model for explaining post translational histone modifications. To our knowledge this is the first time that a shared memory model (rather than message passing) is used for studying a biological coordination process.

157 pages

Thesis Committee:
Ziv Bar-Joseph (Chair)
Russell Schwartz
Hanna Salman
Saket Navlakha

Robert F. Murphy, Head, Computational Biology Department
Tom M. Mitchell, Interim Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu