COMPSCI 720, S1, 2022
Assignment 4 Due: 1 June 2022, 4.00 pm NZT
Please submit a single PDF file with your solutions to Canvas. A (scanned) handwritten report is fine as
long as it is neat.
1. Fixed-parameter algorithms in computational biology.
Select a paper that describes a fixed-parameter algorithm for a problem in computational biology,
read the paper, and write a report (maximum 800 words) that clearly describes the topic/problem
of the paper, summarizes the result, and describes the main ideas of the fixed-parameter algorithm.
Use consistent notation throughout. Any terminology not previously covered in class, needs to be
introduced formally as part of your report.
For inspiration on possible papers, see the following recent review: Bulteau and Weller (2019), “Parameterized
algorithms in bioinformatics: an overview” (available on Canvas).
Please do not choose one of the two papers that we have covered in class, and attach a copy of the
paper you have read to your submission.
(5 marks)
2. rSPR distance.
(a) Give two rooted binary phylogenetic X-trees T and T
0
such that drSPR(T , T
0
) = 2.
(1 mark)
(b) What is the rSPR distance between the following two rooted binary phylogenetic trees T and Explain your answer.
(c) Let F be a maximum agreement forest for two rooted binary phylogenetic X-trees T and T
0
such
that |F| = k + 1. Given T , T
0
, and F, there is a polynomial-time algorithm for constructing
a sequence T0, T1, T2, . . . , Tk of rooted binary phylogenetic X-trees such that T0 = T , Tk = T
0
and, for each i ∈ {0, 1, 2, . . . , k − 1}, drSPR(Ti
, Ti+1) = 1. Describe such an algorithm using
pseudocode.
Tip. Have a look at the proof of Theorem 2.1. of the paper Bordewich and Semple (2004) “On
the computational complexity of the rooted subtree prune and regraft distance”.
(2.5 marks)