首页 >
> 详细

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)

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-21:00
- 微信：codinghelp

- Fit5217辅导、Python程序语言辅导 2022-05-31
- 辅导ecs 170 Introduction To Artificial... 2022-05-31
- 辅导ecs 170 Homework Assignment 5 2022-05-31
- Fit 5003 Software Security辅导 2022-05-30
- 辅导cse 101 Data Structures And Algori... 2022-05-30
- 辅导econ7150、辅导java，Python编程 2022-05-30
- Econ7150编程辅导 讲解 S1 2022 2022-05-29
- 讲解cse 101 程序 辅导 Data Structures 2022-05-29
- 辅导fit 5003 Software Security 2022-05-29
- Stat7055 Introductory Statistics For B... 2022-05-28
- Assignment 3 Description: Computer Sy... 2022-05-28
- 辅导laboratory 程序、辅导program编程 2022-05-28
- 讲解eece 1080C Programming For Ece 2022-05-28
- Comp10002 Foundations Of Algorithms辅导... 2022-05-28
- 辅导 Swen30006、辅导java/C++编程 2022-05-28
- Comp326讲解导、辅导python，Java程序 2022-05-28
- 辅导 Dungeon Crawler C++ - Assignment ... 2022-05-27
- 辅导mast30025 Linear Statistical Model... 2022-05-27
- Prog2002辅导、辅导sql语言编程 2022-05-26
- 辅导 Info411/911 Data Mining Knowledge... 2022-05-26