Name: [SOLVED] Cspb 3104 assignment 9
Brand: Assignment Chef
SKU: 45446
Price: 25 USD
Availability: InStock
Rating: 5 (1 reviews)

5/5 - (1 vote)

5/5 – (1 vote)

Question 1: Most Likely Mutation Tree

This question is inspired by this research article: Spada et al. J Clin Microbiol. 2004 Sep; 42(9): 4230–4236. and this episode of the erstwhile popular TV show Numb3rs https://www.hulu.com/watch/315041 (need a hulu subscription).

Viruses have RNA which mutate rapidly. Let us assume that the RNA of a viral species can be written as an $l$ letter string made up of A, C, T and G. While replicating, a virus can mutate through random changes in $k$ out of these $l$ positions with probability proportional to $2^{- k^{2}}$ .

We collect viral samples starting from a single individual and after sequencing, we observe $n$ mutants $A_{1}, \dots, A_{n}$ , but we do not know which individual mutated to another nor what the order of these mutations were. We wish to reconstruct the mutation tree that connects $A_{i}$ to $A_{j}$ if $A_{i}$ mutated into $A_{j}$ or vice-versa.

Assume that $l$ is large enough that the same RNA sequence cannot be obtained through two different sequences of mutations.

You are given a weighted undirected graph $G$ whose vertices are the RNA sequences $A_{1}, \dots, A_{n}$ and there is an edge between any two nodes $(A_{i}, A_{j})$ with weight $2^{- d (i, j)^{2}}$ , where $d (i, j)$ is the the number of differences between $A_{i}$ and $A_{j}$ .

A spanning tree $T$ of $G$ then represents a possible history of mutations, the likelihood of which is given by the product of the edge weights of $T$ .

Show how to compute the most likely spanning tree $T$ in this graph.

Answer 1 (Expected Length: 6 lines)

your answer here

Question 2 (A): Distance Between Clusters

Let $G$ be a weighted undirected graph with vertices $V$ and edges $E$ .

Assume that all edge weights are unique and let $T$ be a MST for this graph.

Let us partition the vertices into two clusters $V_{1}$ and $V_{2}$ . If an edge $e : (u, v)$ satisfies $u \in V_{1}$ and $v \in V_{2}$ , we will call it partition crossing.

We define the distance between these clusters as the minimum weight among all partition crossing edges of the graph.

Show that the minimum weight partition crossing edge must belong to the MST $T$ .

Hint: Attempt a proof by contradiction.

Answer 2(A) ( Expected Length: 6 lines)

your answer here

Question 2 (B) : Distance Between Point Clusters

Let $Q : {(x_{1}, y_{1}), \dots, (x_{n}, y_{n})}$ be the coordinates of $n$ points on a plane. Given a partition of $Q$ into two clusters $Q_{1}$ and $Q_{2}$ , the distance between these clusters is defined as the smallest among the pairwise distances taking one point in $Q_{1}$ and one in $Q_{2}$ :

d (Q 1, Q 2) = min (x i, y i) \in Q 1, (x j, y j) \in Q 2 (y j - y i) 2 + (x j - x i) 2 -----------------\sqrt .

Given such a partition of $Q$ , write an efficient algorithm to calculate the distance between them. In particular, we would like you to use the idea from 2(A) for this task. Also, what is the complexity of your method?

Answer 2 (B) (Expected Length: 8 lines)

your answer here

Question 2(C): Finding maximally separated clusters

Now you are given $Q$ as above ( $n$ points scattered in the plane), but without a partition. Use the idea from 2(B) to partition the set $Q$ into maximally separated clusters $Q_{1}$ and $Q_{2}$ . Ie, find $Q_{1}$ and $Q_{2}$ such that $d (Q_{1}, Q_{2})$ is maximized.

Answer 2(C) (Expected Size: 4 lines)

your answer here

Question 3: Circular dependencies

Jane Programmer (of the dreaded dynamic programming assignment) has been reviewing her school’s course catalog. Classes in her department are organized into 8 divisions — PBNJ-1000 through PBNJ-8999, with each division more difficult than the last. But Jane has noticed some issues — some upper division classes have lower division prerequisites, but the opposite is true as well. In fact, her current course, PBNJ-3104, requires PBNJ-2400 and PBNJ-2400 requires PBNJ-1300, but PBNJ-1300 requires PBNJ-3104!

She wants to report these circular dependencies to the dean of the department by finding two classes which depend on each other and have the largest difference in class number. In the example above, PBNJ-3104 and PBNJ-1300 depend on each other and have a difference of 3104 – 1300 = 1804.

Given a list of classes and their prerequisites, describe an algorithm that will help Jane find the pair of classes with maximum difference between their class numbers.

What is the running time of your algorithm in terms of number of classes and prereqs?

HINT: Your algorithm should involve the strongly connected components of a graph.

Whatsapp Us

[SOLVED] Cspb 3104 assignment 9

Question 1: Most Likely Mutation Tree

Answer 1 (Expected Length: 6 lines)

Question 2 (A): Distance Between Clusters

Answer 2(A) ( Expected Length: 6 lines)

Question 2 (B) : Distance Between Point Clusters

Answer 2 (B) (Expected Length: 8 lines)

Question 2(C): Finding maximally separated clusters

Answer 2(C) (Expected Size: 4 lines)

Question 3: Circular dependencies

Answer 3 (Expected Length: 5 lines)

Testing your solutions — Do not edit code beyond this point

Reviews

Whatsapp Us

[SOLVED] Cspb 3104 assignment 9

Question 1: Most Likely Mutation Tree

Answer 1 (Expected Length: 6 lines)

Question 2 (A): Distance Between Clusters

Answer 2(A) ( Expected Length: 6 lines)

Question 2 (B) : Distance Between Point Clusters

Answer 2 (B) (Expected Length: 8 lines)

Question 2(C): Finding maximally separated clusters

Answer 2(C) (Expected Size: 4 lines)

Question 3: Circular dependencies

Answer 3 (Expected Length: 5 lines)

Testing your solutions — Do not edit code beyond this point

Reviews

Related products

[SOLVED] Assignment 2 – Implementing fscanf

[SOLVED] Library search system

[SOLVED] MongoDB CRUD Faculty

[SOLVED] COP3530 P0 100/100

[SOLVED] P4 Minesweeper Game using SFML/C++ ( Dec/2022 )

[SOLVED] Info 4604/5604 assignment #1: perceptron #1 1 (version 1.0)