Logged in as: guest Log in | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Home | Research | Courses | Publications | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Comp 590-087/790-087: BioAlgorithms -- Fall 2011
Homework Information: Some of the problems are probably too long to attempt the night before the due date, so plan accordingly. No late homework will accepted. However, your lowest homework will be dropped. Feel free to work with others, but the work you hand in should be your own.
Doublet starred (**) parts of questions are optional and worth up to 10% extra credit. Question 1. Clustering
Question 2. Tree construction
A. How many canonical single-character Small Parsimony Problems are there for the following tree? (Hint: Consider that each problem falls into one of 4 classes. It has either 4, 3, 2, or 1 distinct leaf labels. Notice that the order of labels in the 1st and 2nd positions does not matter. Likewise, for the 3rd and 4th positions. Also swapping the 1st and 2nd labels with the 3rd and 4th does not change the problem) B. Give an example of each canonical Small Parsimony Problem from part A, and find its solution. C. A parisimony score of at least n-1 is required to generate n distinct leafs. How many of the canonical Small Parsimony Problems for this tree have higher parsimony scores?
Question 3. Hidden Markov Models Assume that a genome is composed of two types of segments, normal sequence and CG islands with the following base compostions and mean segment sizes:
|