Comp 555: BioAlgorithms -- Fall 2013

Problem Set #2

Issued: 9/13/2013      Due: In class 10/8/2013

Answers to Questions 1-4 should to be submitted as hardcopy at classtime on 10/8/2013. Answer to programming question should be emailed to kemal@cs.unc.edu with the subject "COMP 555 PS2"

Question 1. Derive a tight bound for the branch-and-bound strategy for the Median String problem. Hint: Split an l-mer w into two parts, u and v. Use TotalDistance(u, DNA) + TotalDistance(v,DNA) to bound TotalDistance(w,DNA).

Question 2. Design a greedy algorithm for the Multiple Breakpoint Distance problem described below and evaluate its approximation ratio.

Breakpoint Distance problem: given a set of permutations π¹,...,π^k, find an ancestral permutation σ such that sum(br(πⁱ, σ), for i in xrange(1,k)) is minimal, where br(πⁱ, σ) is the number of breakpoints between πⁱ and σ.

In class we defined the number of breakpoints in a permutations as the number of non-adjacent consecutive numbers. This notion can be generalized to define breakpoints between two permutations, br(π¹, π²) as follows: for each number x₁, x₂, x₃, ... x_n in π¹ substitute i for x_i. Similarly, for each number y₁, y₂, y₃, ... y_n in π² substitute i for y_k where y_k = x_i, and count the number of breakpoints in π². In other words, impose the ordering of π¹ on π² and count the number of breakpoints in π².

For example:

π¹ = [0,1,4,3,2,5,6,7]

π² = [0,1,2,3,4,6,5,7]

Imposing π¹'s order on π²gives:

π^2' = [0,1,4,3,2,6,5,7]   (4 -> 2, 2 -> 4)

this gives 3 breakpoints [0,1|4,3,2|6,5|7].

Question 3. Two players play the following game with two “chromosomes” of length n and m nucleotides. At every turn a player can destroy one of the chromosomes and break another one into two nonempty parts. For example, the first player can destroy a chromosome of length n and break another chromosome into two chromosomes of length m/3 and m-m/3. The player left with two single-nucleotide chromosomes loses. Who will win? Describe the winning strategy for each n and m.

Question 4. Consider the sequences v = TACGGGTAT and w = GGACGTACG. Assume that the match premium is +1 and that the mismatch and indel penalties are −1.

• Fill out the dynamic programming table for a global alignment between v and w. Draw arrows in the cells to store the backtrack information. What is the score ofthe optimal global alignment and what alignment does this score correspond to?
• Fill out the dynamic programming table for a local alignment between v and w. Draw arrows in the cells to store the backtrack information. What is the score ofthe optimal local alignment in this case and what alignment achieves this score?

Question 5. Let s(v,w) be the length of a longest common subsequence of the strings v and w and d(v,w) be the edit distance between v and w under the assumption that insertions and deletions are the only allowed operations. Prove that d(v,w) = n+m−2s(v,w), where n is the length of v and m is the length of w.

Programming Problem. Modify BreakpointReversalSort.py as follows:

The given version of the code outputs only one of many possible solutions. The way to generate multiple solutions should be that if at any stage of the program there is more than one reversal that removes two breakpoints, the progam should accept all such reversals and output all solutions. Turn in your code and listing for following inputs:

0,1,2,10,9,3,4,7,6,5,8,11
0,9,2,1,6,8,7,5,3,4,10,11