CS 581: Algorithmic Genomic Biology
Homework policy:
Homework problems
from the textbook are based on homework problems at the end of
each chapter.
Homework must be submitted via MOODLE and are
due by 1 PM on the due date.
Most homework up to April 4 can be submitted up to
48 hours late for reduced credit; note that
some homeworks (and all due after April 4)
must be submitted on time for any credit.
Homework assignments
 January 21.
If you did not take CS 374, do problems
1, 14, 15, 20, 21, 29, 32, and 36 from Appendix B.
If you did not take CS 361 or STAT 361, do
problem 42 from Appendix B and problem 1 from
Math 361 sample final exam (PDF).
 January 24.
HW problems from Chapter 1: do any three of
1, 5, 10, 11, 13.
Also solve homework problem 15 from Chapter 5.

January 31:
HW problems from Chapter 8: 812
 February 8:
HW problems from Chapter 8: 13, 17, 18
 February 15:
HW problems from Chapter 9: 13, 10
 February 22:
Problem 11 from Chapter 9.
Provide a discussion of each of the presentations
you heard at the CSL conference.
 March 1:
Read, compare, and critique two or more papers about
either
multiple sequence alignment methods
or tree estimation methods. All papers
must be from the last 5 years.
(Write this as though it was
going to be published in a journal;
thus, introduction, full bibliography,
and show care about the writing.)
Submit this in PDF format.
 March 6: submit two questions for each paper that
will be presented on March 7 (late submissions not allowed).
 March 8:
HW problems from Chapter 9: One of problems 13 or 15.
Also submit two questions for each paper that will be presented
on March 9 (late submissions not allowed).
 March 13: submit two questions for each paper
that will be presented on March 14 (late submissions not allowed).
 March 15:
HW problems from Chapter 10: Do two of problems 13.
Also submit two questions for each paper
that will be presented on March 16 (late submissions not allowed).
 March 22: SPRING BREAK (no homework)
 March 29:
Submit up to three revised homework problems for regrading.
 April 5:
Homework problem 42 from Appendix B.
 April 12:

HW 14:
Read, compare, and critique two or more papers about
any topic we've studied in this semester.
All papers
must be from the last 5 years.
(Write this as though it was
going to be published in a journal;
thus, introduction, full bibliography,
and show care about the writing.)
Submit this in PDF format on Moodle.

Extra credit.
Consider the following model of site evolution.
You have a rooted binary model tree T and substitution
probability p(e) on each edge e that must be
greater than zero and less than 1.
The state at the root is the number of leaves in the tree T.
If the site
changes on edge e, the new state is the number of leaves below
e.
For this model answer the following questions:
 Which parameters of the model are identifiable?
(In other words, is the unrooted tree topology identifiable?
What about the location of the root? What about the
substitution probabilities?)
 If you constrain the model so that
the substitution probabilities on different edges are different,
which parameters of the model are identifiable?
 For those parameters that are identifiable,
describe a polynomial time algorithm to estimate
the parameters and prove that it is consistent.
 April 14. Submit proposal for final project.
 April 19:
HW problems from chapter 11: do three of
2, 6, 7, 10
 April 26: No homework. Submit draft of final project for comments.
 May 3: No homework. Final project due.