Assignment

Due: 2023-11-30

To submit the assignment, upload a .pdf-, .doc-, .docx-, .txt-, or .jpg-file with your solutions to PandA before the deadline. Scanned, handwritten solutions are OK as long as they are easily readable. All answers must be written in English.

1.

Consider the following graph orientation problem.

As an example, let the input be the undirected graph in figure (a) below. Both of the directed graphs in (b) and (c) satisfy condition (1), but only (c) satisfies condition (2). Hence, the orienta- tion in (c) is a valid output, but the one in (b) is not.

(a) (b) (c)

Describe a polynomial-time algorithm that solves the problem. You may specify your algorithm in pseudocode or in plain English. For full marks, also demonstrate how your algorithm works on a small example (either use the graph given in (a) above or create an example by yourself), prove the algorithm’s correctness, and explain why the algorithm runs in polynomial time.

Hint: Use a greedy approach. (30 marks)

(a) Let T1, T2, and T3 be phylogenetic trees and TM the majority rule consensus tree of {T1, T2, T3}. The trees T1, T2, and TM are as specified below. Suppose we have been told that T3 is a binary phylogenetic tree, i.e., every internal node has exactly two children. Draw T3. (20 marks)

T: T : T: T : 123M

e?e =⇒

cd

   Input: A connected, undirected graph G.

Output: An orientation Λ of G such that: (1) the resulting directed graph Λ(G) has no cycles; and (2) the maximum number of outgoing edges from any vertex in Λ(G) (taken over all vertices) is as small as possible.

          2.

 cdebcd abaab

1

(b) For every positive integer n with n ≥ 3, define Ln as the set {l1,l2,...,ln} and define Tn as the following set of n rooted triplets on Ln:

Tn = ?l1l2 |l3, l2l3 |l4, ..., ln−2ln−1 |ln, ln−1ln |l1, lnl1 |l2

Prove for every positive integer n with n ≥ 3 that Tn is not consistent with any phylogenetic tree even if one rooted triplet is removed from the set. You are allowed to use the lemma from slide 45 of Lecture 5 as a fact (i.e., you don’t need to prove that lemma here). (20 marks)

3. Show that the Robinson-Foulds distance sometimes fails to distinguish between phylogenetic net- works that have different branching structures. To do so, give an example of two rooted phyloge- neticnetworksN1 andN2 suchthatN1 ̸=N2 anddRF(N1,N2)=0.

To simplify the marking process, please list all the elements in the cluster collections of N1 and N2. (30 marks)

2