CS294-56

Computational Aspects of Evolution

Evolution is one of the greatest problems in science, and a flourishing research endeavor.  Over the past century, sophisticated mathematical tools and mathematical insights have been used in the pursuit of better understanding of the theory; in almost all cases they were of the sort usually employed in physics.  Computational techniques and ideas have also been gloriously applied, albeit mostly for processing as in genomics and phylogeny. 

The premise of this course is that computational/algorithmic thinking, and the kind of mathematics that underlies it, can be productively applied to some of the most important problems in Evolution.  Corollary, it is important for computational/algorithmic thinkers to understand Evolution.  Hence this reading course.

Meeting:  Fridays 1-3 in Soda 320.  Make-up time for travel etc. Tuesday 5-7, Soda 320.

2 units.

Course Requirements:  Each week, read the assigned readings, post a paragraph about what you read, attend the meeting, and participate in the (live and on-line) discussions.  Possibly lead one of the discussions.

This is a reading course, organized in three parts:

Part I:  Foundations of the theory:  Darwin, Weismann, and material on the "modern synthesis" of darwinism with mendelism.  We'll read selections from "The Origin" and other material.

Part II:  Fundamentals of Molecular Evolution, by Graur and Li.  This book we will read essentially cover-to-cover.  (If you plan to take this class, you will need to get this book now, as well as the Origin of Species.  I'll provide the rest.)   Also, some material on Development and Evolution.

Part III:  Computational theories of evolution.  For example:  Valiant's theory of evolvability, Evolutionary algorithms, Livnat[1]'s theory of mixability, Evolutionary game theory, Biological networks, Artificial Life, Origins of Life, etc.

Readings, in rough order of our reading:

o Charles Darwin “The Origin of Species” 1859.  (Make sure your copy has the 1959 foreword by Huxley.) I’ll assign parts, but everybody should find the time to read it all, it’s worth it.  The graphic novel is no substitute…  Also, the Wallace-Darwin paper(s) , 1858.

o Weismann  “On Heredity”, Chapter 2 (II) here , 1889.

o Graur and Li “Fundamentals of Molecular Evolution” second edition. We’ll read this whole book, beginning concurrently with the above.  This book (which I have been reading over the break) was an eye-opener for me, re: how much Biology I was missing that is obviously crucial to begin to understand Evolution.  (Hint: A, C, G, and T are not symbols, each has a distinct personality, aspirations, and quirks.)

o Much more, to come…

Wanna smile? Evolutionists gather around wall stain

in the image of Charles Darwin (from The Onion)

Calendar/Announcements

Friday January 22:  First meeting, administrivia and introduction. 

Reading assigned for next week: 

1. The Wallace-Darwin paper(s)

2. Huxley’s introduction to the Origin

3. The Origin of Species:  The summaries of Chapters IV, V, VII, IX, XIV, and chapter XV (recapitulation and conclusion)

4. Graur-Li introduction (pages 1-4)

 Write me if you have trouble finding Huxley’s introduction.

(Note: That the film Creation about Darwin’s life opens in the Bay Area the same day as this course is sheer coincidence…)

Friday January 29:  Second meeting, very lively discussion of the readings – I almost learned more from

the discussion than from the readings.  Thanks everybody!

Here is the evolution of “The Origin” (thanks, Nick!)

it takes a few minutes unless you click the "Fast" button.

Please send me your essays.  Don’t pay attention to Telebears, everybody will be admitted to the class.

Readings assigned for next week: Weismann  “On Heredity”, Chapter 2 (II) here , 1889 together with Haig’s

“Weismann rules! OK? Epigenetics and the Lamarckian temptation.”

Chapter 1 of Graur-Li. (To the non-biologists:  note that I found this a challenging read, but very

illuminating.)

Join the class’s Google group!

Friday February 5:  Another great discussion!  Many thanks to all for your comments, questions, answers,

interest, postings in the discussion group, and essays.  Speaking of your essays, thanks for making them so

insightful and inspiring.  Feel free to post them on the discussion group, and feel free not to, and just send them

to me. 

Readings assigned for next week:  Chapter 2 of Graur-Li.  This is a summary of the standard quantitative accounts

of Evolution.  It should be much smoother reading.  To see a more rigorous development, but also an account

of the “synthesis” browse the first chapter of S. Rice’s excellent book, plus these other two introductions.

You may want to skim chapter 1 again, I found it great reading the second and third time.

Friday February 12:  Fourth meeting.  I will be out of town, class will meet the usual time. 

Now that I’m back:  From all available evidence, I get the impression that this was a discussion

I should be sad to have missed.  There is some high quality (and intensity) discussion in the

discussion group, make sure you follow it. 

Readings assigned for next week:  Chapter 3 of Graur-Li.  This should be a very easy chapter, it’s

about probabilistic models of point mutations, and alignment algorithms; you may want to review Chapter 2 and discuss the two together.

Also, to further fuel the argument in the discussion group, here are three chapters 1, 2, 3 – and discussions! – from the “Mathematical Challenges” book which Nick quoted in the group. 

Friday February 19:  Another lively and informative discussion, thanks everybody. 

Readings:  Chapter 4 or Graur-Li.  Also, in order to help the class appreciate the beauty and diversity of life, our subject, several chapters of standard textbooks .

Friday February 26:  A great discussion! We talked about the neutral theory, positive selection, directed mutations, on whether the molecular clock is broke, and sketched an experiment that can elucidate the true nature of mutations. (To the folks at Tahoe: I hope the skiing was as good :b)

Next we’ll read about phylogeny (Chapter 5 of Graur-Li). Also, these pages on the connection between evolution and development (a.k.a. evo-devo). Plus this interesting paper about the evolution of evolvability and the role of modularity in it (you may want to skip the parts about computation)

Friday March 5: Another very interesting and lively discussion (on phylogenetic reconstruction methods and their uses, the most eye-opening connection between evolution and development, and the evolution of modularity).

For next time we are reading Chapter 6 of Graur-Li. Also, given our goal to explore “computational approaches to evolution,” I thought we should familiarize ourselves with one recent work in exactly this direction by Les Valiant. And here are the two papers on sex, mixability, and modularity from our group that I mentioned. Probably we’ll read them at some later time.

Friday March 12: For me, this was the most interesting chapter to-date. We had a very interesting discussion, but were left with the feeling that we have not exhausted the topics. Vitaly and I talked about Valiant’s paper. Readings for next week: Chapter 6 (reprise) and Chapter 7.

Friday March 19: I don’t know what happened in class (somebody please post in the group), but assuming you had a productive discussion of the Chapters 6 and 7, I propose we next look at the last chapter, Chapter 8, on Genome Evolution. After that, we’ll have a series of other readings: on evolutionary game theory, mixability, etc.

Friday April 2: Very inspiring discussion of whole genome evolution, with only 15 mins of digression to the use of evolution as a (often careless) metaphor for cultural change.

For next time: Each one of us will review the whole book and come up with 2-3 points that seem most remarkable and/or open-ended. Also, we’ll read and discuss the two papers on sex, mixability, and modularity we have mentioned often. Please don’t be polite because I’m a co-author here, let’s uphold the critical tradition of this class!

Friday April 9: A very interesting review of several points from the whole book, mostly from the last three chapters, e.g., transposable elements and the moleculars of the immune system. One question I brought up, and might be checkable: Could be that the CG-rich actinobacteria (p. 432) have had fewer mutations/million years than the CG-poor mollicutes, e.g.? Also, an explanation, discussion and reserved criticism of the two mixability papers.

Next time we’ll discuss evolutionary game theory. Here is a high-level exposition, contemplation, and lots of references, and here is a rather low-level exposition. And see the discussion group for scanned chapters from a very nice book (thanks Nick!).

Friday April 23: Discussion of the rest of Nowak’s book (graphs, space, cancer, HIV, virulence and language (!)), plus the burning meta-subject of how can one do transformative mathematical/CS work on Evolution: which subareas, which style, which math techniques, which approach, which decade, etc.).

There will be no class Friday April 30, but for the capstone class meeting on May 7 we’ll read a pot pourri of papers on aspects that we had promised ourselves to cover but haven’t yet: (1) two papers on speciation (a book chapter plus the latest from the species problem debate); (2) a paper by Nowak on the origins of life (there will be more posted later on this); (3) a paper on the evolution of eusociality; and (4) two papers on biological networks.

[1] Adi Livnat, a post doc here at Berkeley, you will meet.  He got me into the subject (I am a co-author in the paper that I call “Livnat’s theory of mixability”), and is my advisor for this class.