Assignment 3
Due: 7:00 PM on Wednesday, Mar 30, 2005
Question #1
Write and document a Java program that computes the generalized
maximum parsimony score of a given rooted binary evolutionary tree
T and a given object-by-character matrix D relative to a
given DNA cost-matrix C, where the leaves
of T are labelled with character-data from D. The
algorithm used to compute the generalized maximum parsimony score will
be that given in Section 4.2 of the Sankoff and Cedergren (1983) class
handout.
The names of the tree and DNA cost-matrix files should be command-line
arguments to your program. Each tree file is formatted as follows:
The first lines contains two positive integers n and m
specifying the number of taxa and the number of characters per taxon,
respectively,
each of the next n lines specifies a leaf in the tree via
that leaf's index, name, and object-by-character matrix data (as
a string of length m over the DNA alphabet), and the final
(n - 1) lines specify the internal nodes of the tree via that
node's index and name, the index and linking-edge length to that
node's first child-node, and the index and linking-branch length
to that node's second child-node. The internal nodes will be listed
in postorder, i.e, each node will be listed after its
children-nodes are listed. Two examples of the tree
given on page 3 of the Felsenstein (1992) class handout encoded in this
format are given
in files etree1.dat,
etree2.dat,
etree3.dat,
etree4.dat, and
etree5.dat. Each cost-matrix file will specify
a 4 x 4 matrix on 4 lines (one per row), where the rows in order
correspond to the symbols, A, G, C, and T. Two sample DNA cost-matrices
are given in files cm1.dat and
cm2.dat. Your program should print out
intermediate values produced during your computation as specified in the
following sample run typescript file.
You may assume that all all given files are formatted correctly..
Hints
Question #2
Given the following trees
and the following object-by-character matrix
| | C1 | C2 | C3 |
| A | A | G | G |
| B | A | C | A |
| C | A | C | C |
| D | T | G | A |
| E | T | G | G |
| F | T | G | G |
do the following:
- compute the scores of both trees relative to this given dataset
under the maximum parsimony criterion using Fitch internal-vertex
character state reconstruction;
- give one of the most-parsimonious internal-vertex state assignments
for each tree; and
- say which tree is preferable under the maximum parsimony criterion.
Perform Fitch internal-vertex character state reconstruction using the
algorithm given in the Swofford et al. (1996) class handout.
Submission
Please hand in printed copies of your Java source code
files for Question #1 along with your answer for Question #2.
You must also submit your Java files electronically using the
submit-assignment command.
Note that each
such file must have the following comment block
at the top, where
the X's are replaced with the appropriate information. For instance,
my code for MPG.java would begin with the
following comment block:
/////////////////////////////////////////////////////////////////
// CS 4762 (Winter 2005), Assignment #3, Question #1 //
// Program File Name: MPG.java //
// Student Name: Todd Wareham //
// Login Name: harold //
// MUN #: 8008765 //
/////////////////////////////////////////////////////////////////
You do not have to develop your code on our CS departmental systems.
However, as your code will be compiled and tested on our CS departmental
systems as part of the assignment marking process,
you should ensure that your code compiles and runs correctly on at
least one of these systems.
- Mar 17, 8:40am
Changed due date of of Assignment #3 to March 30.
- Feb 28, 4:15pm
Changed due date of of Assignment #3 to March 23.
- Feb 8, 9:15am
Assignment #3 posted.
Created: February 8, 2005
Last Modified: March 17, 2005
