Homework: Computing Human Evolution

The files for this homework are in hw02.zip. The only file you need to modify is "dna.ml". Once you are finished, be sure to submit your homework.
Frequently Asked Questions

The course staff has documented some of the most frequently asked questions for this assignment from past semesters in an FAQ.

Grading

Background

Biologists use evolutionary trees (Figure A below) to show species evolving from ancestor species. To practice using enumerations and recursion over lists and trees, we will write a program that automatically generates hypothesis trees like the one in Figure A.
Figure A: Evolutionary Tree for Apes
Our program input will be real samples of DNA, the genetic code that describes how to build organisms (Figure B). DNA has two complementary helices, each a sequence of the nucleotides adenine, thymine, guanine, and cytosine. Adenine always appears opposite thymine; same for guanine and cytosine.
Figure B: Modeling the DNA Double Helix
The assignment file "dna.ml" contains the DNA sequences for 8 ape species. This is real data from the Entrez Nucleotide database. You will use this data to
  1. Generate all possible evolutionary trees with the ape DNA at the leaves. Internal nodes in these trees correspond to ancestor species.
  2. Estimate each tree's complexity.
  3. Choose the simplest tree as a candidate.
  4. Compare your candidate with the tree in Figure A.
For example, given the four DNA helices ("GCAT", "TCGT", "TAGA" and "GAGA") one possible evolutionary tree is shown in Figure C below. This constitutes an evolutionary tree for the given helices, since the helices are at the leaves of the tree, while the internal nodes have as labels helices that are in some sense as close as possible to the labels of their children. Specific details on constructing evolutionary trees are provided in the homework file.
Figure C: Completely Labeled Tree with Helices of Length Four

Supplementary Links

Browse these links for more background information:


We derive our images from Wikimedia sources available under Creative Commons licenses.