COSC 844 - Biological Algorithms (Spring 2017)

Georgetown University

Prof. Calvin Newport

Tuesday, 2:00 am to 3:50 pm

Saint Mary's Hall, 3rd Floor Conference Room

Course Overview

Background

Nature includes many distributed systems made up of units that interact using local rules, including, for example, insect swarms, neural networks, developing cells, bird flocks, and even human populations. The collective effect of these simple local actions is often complex global behavior. A major interest in biology is understanding these systems.

A standard approach to advancing this goal is to apply the most common tools from science: differential equations and statistical analysis. For many of the type distributed systems described above, however, these tools seem to fall short. With this in mind, there has been a growing interest in recent years in applying algorithmic methods, primarily innovated in the study of computer science, to better describe and analyze distributed behavior in nature.

This topic has many names, depending on who you ask, including natural algorithms, biological algorithms, and biological distributed algorithms. The core approach of this topic is to attempt to describe the local rules in a natural distributed system as an algorithm, and then study the behavior or fundamental capabilities of the resulting system using existing analytical tools from computer science.

These tools allow us to ask and answer deep questions about these systems that cannot be so easily probed by differential equations, statistical analysis, or numerical simulation; for example, identifying the number of bits of memory needed to break symmetry among cells communicating with chemical signaling (the answer turns out to be the logarithm of the inverse of the error bound), or the computational power of a soup of reacting chemicals (under the right conditions, these soups can compute anything a general purpose computer can compute).

A secondary motivation for studying biological algorithms is that they might generate new ideas and approaches for designing electronic computational systems that feature some of the nice properties observed in nature.

Course Information

This course is a doctoral seminar that will review and discuss the rapidly evolving literature from the study of biological algorithms. Students will come away with a cutting-edge understanding of the main topics, results, and techniques in the field, as well as an understanding of the most promising open problems.

The course is a reading course. We will discuss two or three papers per class meeting. For each paper, we will cover the problems studied and their motivation, as well as the solutions proposed and any results. We will selectively dive into technical details as a group in places where I feel it is tractable and illuminating.

Most of the papers we read will come from the computer science perspective, though we will occasionally read papers from biology, physics, and related fields, where relevant.

Student Responsibilities and Grading

A week before each class meeting, I will email a set of discussion questions for each of the papers to be covered in that meeting. This email will also include guidance on what sections to focus on in the readings and what sections can be skimmed or skipped. Students must email me responses to these questions before the class meeting begins. The goal of these questions is to both ensure you do the reading and to help guide your attention to the areas most fruitful for discussion.

In addition to preparing readings, each student will be assigned one class meeting toward the end of the semester in which to prepare and lead a discussion on a topic of their choosing within biological algorithms. This will be your opportunity to practice surveying this literature and extracting interesting trends and directions on your own.

Grading in a doctoral seminar is pass/fail. To achieve a pass requires three things: (1) good answers to most of the reading response questions; (2) participating in discussion; (3) a respectable effort in organizing your assigned class meeting.

Though there isn't a formal research requirement for this seminar, I encourage interested students to use this seminar to indentify promising research topics to pursue beyond the scope of the course. I am happy to discussion research collaborations. In addition, a fantastic NSF-funded workshop on this topic will be held this summer in Washington D.C. -- presenting a perfect venue to present or discuss early stage results and learn about cutting-edge developments.

Course Schedule

I will post the readings for each class meeting in the schedule below. Notice, I'll be filling in and modifying the details of this schedule on the fly as the semester progresses, so please check often for changes.

As of now, the tentative list of topics I hope to cover with these readings includes:

 


Week 1 (1/17): Solving Distributed Graph Problems on the Fly

A paper published in the journal Science in 2011 claimed that cells in fly embryos might be solving a well-known problem in computer science as part of their development. The paper studied the communication capabilities of these cells and proposed an algorithm that the cells might be executing to solve the problem. A series of follow-up papers within the computer science community grappled with the same model and problem, highlighting tensions between the computer scientist's instinct to identify the best possible solution, and nature's instinct to find something simple that works. We are starting with this topic as it provides a good entry into the general approaches used in the study of biological algorithms, and the tensions they create.

Because this is the first class, I do not expect the students to have completed this reading in advance.


Week 2 (1/24): Synchronization from Oscillators to Algorithms

A famous 1990 paper by Mirolla and Strogatz (cited over 1800 times), appearing in an applied mathematics journal, opens unexpectedly: “Fireflies provide one of the most spectacular examples of synchronization of nature.” The authors wanted to explore how simple local rules could lead to such impressive global displays.

The three papers we’ll read this week follow this thread of investigation, starting with the classical systems biology approach of Mirolla and Strogatz, to a more algorithmic, but still bio-inspired approach applied by a group of Harvard computer scientists, to finally, a purely computer science approach applied a pair of optimization minded MIT-based theoreticians.

These readings provide a good example of the power gained when shifting one’s conception of a natural phenomenon from a system of equations to a distributed system of interacting algorithms. They also, however, provide another example of the tension between a biologist’s interest in understanding nature, and a computer scientist’s interest in identify the optimal solution to a problem for a given set of constraints.

Readings

Reading Instructions

For the Mirollo paper, read through Section 2.2 and understand the results proved. You do not have to understand the techniques. For the Degesys paper, read through Section 3. You can skim the discussions of how the algorithms are applied to wireless networks. Also look at the results proved in Setion 4. You do not need to know the details of how they are proved, but glance at the techniques used. Finally, for the Cornejo paper, read through the algorithm description in Section 4. Also take a look at the algorithms and results proved in the sections that follow. You do not need to look deeply at the proof details.

Reading Questions

  1. Summarize at a high-level the different types of analytical approaches taken in the analysis in each of the three papers (e.g., types of areas of math used).
  2. Cornejo and Kuhn are unhappy with the model used in the Degesys paper (they actually cite another paper that builds on the Degesys paper and uses the same model). Why?
  3. Does the complaint from the above question invalidate the Degesys model from being used to study biological phenonomenon? Why?
  4. Rate these papers in terms of their relevance to understanding biological systems like firefly flashing, and explain your ratings.


Week 3 (1/31): The Computational Power of Simple Signaling Systems

During the first two weeks of this seminar we have studied systems made up of components that communicate with simple signals (e.g., protein expression, beeps and/or flashes). The pair of papers assigned for this week apply techniques from computer science to understand the computational power of these bio-inspired systems.

These papers highlight how concepts of complexity and computability from theoretical computer science can apply to biological systems, and identify interesting trade-offs between properties such as logic complexity, synchrony, and signal diversity in determining the power of a system to solve computational problems.

Readings

Reading Instructions

Pending…

Reading Questions

Pending…