# 辅导COMPSCI 720、辅导Java，c++程序

- 首页 >> Database 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)

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)