Algorithmic Thinking in Bioinformatics · Quiz 2 · Jan 2023

You enter an alien world as a renowned computational biologist. The below table is presented to you as a part of a preliminary study done by a group of scientists to study the local fauna around the base camp. They analyze the DNA and figure out that there are only two bases “+” and “0”. The below table represents the DNA sequence in 6 positions for the different species found. You build a phylogenetic tree that best represents the evolutionary relationship among the species, using the Neighbor-Joining algorithm (on the Hamming distance matrix).

Based on the above data, answer the given subquestions

The length or weight of the internal edge (i.e., non-limb edge) in the inferred phylogenetic tree is____________ . Fill in the blank.

You enter an alien world as a renowned computational biologist. The below table is presented to you as a part of a preliminary study done by a group of scientists to study the local fauna around the base camp. They analyze the DNA and figure out that there are only two bases “+” and “0”. The below table represents the DNA sequence in 6 positions for the different species found. You build a phylogenetic tree that best represents the evolutionary relationship among the species, using the Neighbor-Joining algorithm (on the Hamming distance matrix).

Based on the above data, answer the given subquestions

Consider the two distance matrices DM1 and DM2 shown below. Which of the following statement(s) is/are true?

Which of the following is/are false about UPGMA?

Given below are a set of genetic sequences and the position (sites) of their nucleotides.

Based on the above data, answer the given subquestions.

You are asked to construct a rooted binary phylogenetic tree from the given data. You identify 3 tree configurations that are possible - Tree A, Tree B, and Tree C (see the figure below) based on the information. Identify the most parsimonious tree. (**HINT:** Which columns can you ignore?)

Given below are a set of genetic sequences and the position (sites) of their nucleotides.

Based on the above data, answer the given subquestions.

You add 4 more sequences to this tree. How many internal nodes and branches will the modified tree have?

Answer the given subquestions.

Answer the given subquestions.

Find the number of edges in the **suffix tree** constructed from the **suffix trie** obtained in the previous question.

Select the correct sequence of steps in the context of the K-means clustering algorithm: I. Measurement of distances of each point to centroids. II. Initialization of cluster centroids. III. Updation of cluster centroids, and repeat. IV. Assignment of data points to respective clusters.

The K-means clustering method is prone to give erroneous results in which of the following cases? Note that the color here represents the ground-truth clusters.

Answer the given subquestions.

Consider the following **hard** K-means clustering problem with four points: P (1, 1), Q (2, 1), R (4, 3), and S (5, 4). Consider the number of clusters to be k = 2 and the initial centroids to be C1 = (0, 0) and C2 = (4, 4). After how many iterations will the algorithm terminate and what will be the final centroids?

Answer the given subquestions.

Given the data points in the previous question, let’s say we want to cluster them via (vanilla) soft k- means instead of the hard k-means algorithm. Let the stiffness parameter β be 1. Then, in the first iteration where the centroids are C1=(0,0) and C2=(4,4), what is C1’s and C2’s respective responsibility for the data point P=(1,1)?