CMSC 858M: Computational Evolutionary Dynamics

About this course

The organizing question of this course is: how can we model how systems are evolving over time, and how can we use those models to computationally predict future behavior and to "predict" unobserved past behavior. Our main focus will be on applications to biological systems including viruses, other genomes, and --- most prominently --- the evolution of biological networks. We will also consider applications in non-biological areas.

Instructor: Carl Kingsford; carlk AT cs.umd.edu; Office hours: by appointment in CBCB 3113.

Meeting Time: Fridays, 9:00-11:30.

Prerequisites: No previous biological knowledge is assumed. A certain amount of mathematical maturity is required (that any CS Ph.D. student will likely have), but the class will generally be self-contained.

Grading: There will be several homework sets, one or two in-class presentations per person, a take-home final, and a class project.

Textbook: We will cover several chapters in the textbook Evolutionary Dynamics by Martin Nowak. Much additional material will come from recent papers.

Credit: This course is not a core Ph.D. or M.S. course, and it does not count towards MS Comps. This is a lecture / seminar course about recent research in the field.

Tentative syllabus

This syllabus may change as the course itself evolves.

1. Week 1: What is evolution? Replication, Mutation, Selection. How can we model it computationally? Chapter 1 of Evolutionary Dynamics.
• Syllabus
• Lecture Notes
• Reading: Nowak, ch. 1 and ch. 2
• Homework: choose 5 papers from the list below you would like to present.
2. Week 2: Models for the evolution of changing networks. How can the evolution of biological (and social) networks be simulated? How do different evolutionary models lead to qualitatively different networks?
• Presentation instructions
• Lecture Notes
• Lecture Slides
• Homework 1
• Enthought Python Distribution. Python also avilable on glue.umd.edu; any Mac; and is installable on Windows.

3. Week 3: Network Archeology: How can past configurations of a network be computationally inferred?
• Lecture Notes
• Sample Python code for disease simulation
• The NetworkX Python library
• Presentation:
  1. Geet's slides for Bornholdt and Sneppen (2000). Robustness as an evolutionary principle. Proc R Soc Lond B Biol Sci 267: 2281-2286.
4. Week 4: Evolution of modularity in biological networks. What processes lead to the emergence of "modules" or reusable components in evolving systems? How does modularity emerge without design?
• Lecture Notes
• Simple implementation of (nearly) Kashtan & Alon
• Presentations:
  1. Chris' slides for Leskovec, Backstrom, Kumar, and Tomkins (2008). Microscopic evolution of social networks. In: Proc. 14th Intl. Conf. on Knowledge Discovery and Data mining. pp. 462-470.
  2. Vikas' slides for Przulj, Kuchaiev, Stevanovic, and Hayes (2010). Geometric evolutionary dynamics of protein interaction networks. Pac. Symp. Biocomput., 15:178-189.
5. Week 5: BattleGraph! And introduction to evolutionary game theory.
   • Lecture Notes
   • Homework 2: BattleGraph
   • The BattleGraph simulator and sample players
   • Presentations:
     1. Patrick's slides for Boyd and Richerson (2009). Culture and the evolution of human cooperation. Phil. T Royal Soc. Lond. B 364(1533):3281-8.
     2. Hao's slides for Palla, Barabasi, and Vicsek (2007). Quantifying social group evolution. Nature 446: 664-667.
6. Week 6: Evolution of evolvability (and battlegraph results)
• Lecture Notes
• BattleGraph Results
• BattleGraph Players
• Presentations:
  1. Ben's slides for Raman and Wagner (2010). The evolvability of programmable hardware. J. R. Soc. Interface 8:269-281.
  2. Seth's slides for Kashtan, Noor, and Alon (2007). Varying environments can speed up evolution. PNAS, 104:13711-13716.
7. Week 7: Turmites and spatial games (parts of Chapter 9 in Evolutionary Dynamics.
• Lecture Notes
• Implementation of Turmites (Requires matplotlib and numpy libraries)
• Presentations:
  1. Ted: Parter, Kashtan and Alon (2008). Facilitated Variation: How evolution learns from past environments to generalize to new environments. PLoS Comput Biol 4(11): e1000206.
  2. Emre's sldies for Ciliberti, Martin, Wagner (2007). Robustness can evolve gradually in complex regulatory gene networks with varying topology. PLoS Comput Biol, 3(2):e15.
8. Week 8: Idealized models of evolving systems: flocks, swarms. When does coordination emerge?
• Lecture Notes
• Presentation:
  1. Hsueh-Chien's slides for Shinar, Dekel, Tlusty and Alon (2006). Rules for biological regulation based on error minimization. PNAS 103(11), 3999-4004.
  2. Amanda's slides for Palla, Lovasz, and Vicsek (2010). Multifractal network generator. PNAS 107:7640-645.
9. Week 9: Simplified model of evolution: context-free grammars for strings, graphs, and images.
   • Lecture Notes
   • Context Free Art software
   • Presentation:
     1. Jim's slides for Yan, Fang, Bhardwaj, Alexander, and Gerstein (2010). Comparing genomes to computer operating systems in terms of the topology and evolution of their regulatory control networks. PNAS 107:9186-9191.
10. Week 10: Genetic mixing: horizontal gene transfer, recombination, reassortment, and transposons.
11. Week 11: Open or catch up day (topic to be decided later)
12. Week 12: Open or catch up day (topic to be decided later).
13. Week 13: Project Presentations.

Related Reading

Initially Created Oct 29, 2010. Images taken from Navlakha & Kingsford.