Algorithmic Thinking in Bioinformatics · Quiz 2 · Jan 2026

Which of the following statements is false about UPGMA?

For some string

we have

. Which of the following represents the original string

?

In a gene expression analysis study, we are clustering cells based on their expression levels of two genes using **(vanilla) soft K-means clustering**. The stiffness parameter is

. In the first iteration, suppose the cluster centroids represent two **cell types** with mean gene expression profiles:

Now consider a new cell

, where the coordinates represent its expression levels of the two genes. Which of the following options correctly represents the responsibilities (soft cluster memberships) of cell

belonging to cell types

and

?

Consider the following hard K-means clustering problem with five points:

,

,

,

, and

. The number of clusters is

, and the initial centroids are

and

. After how many iterations will the algorithm terminate, and what will be the final centroids?

What is the number of nodes in the **suffix trie** constructed on the genome:

. Assume the branch on the single-letter suffix

is not represented in this trie. Enter your answer as a single integer.

Consider a clustering setup with

clusters. One cluster center has already been fixed at

. We now wish to select the second cluster center from the remaining points

. In order to encourage diversity between clusters, points that are farther from the existing center are given higher preference. Specifically, each point is assigned a selection probability proportional to the square of its distance from the nearest existing center (similar to a soft assignment where distant points receive higher weight). The Euclidean distances of the remaining points from

are:

What is the probability of selecting

as the second cluster center under this distance-based soft selection scheme? Round your answer to two decimal digits.

The number of elements in the Burrows-Wheeler matrix is

. What is the length of the original genome sequence (including the

symbol)? Enter the value as a single integer.

What is the minimum possible length of the run-length encoding of a genome sequence of length

. (Hint: Beware that the length of a run-length encoding of a string should include the characters in the encoded string, as well as their counts.) Enter the value as a single integer.

You enter an alien world as a renowned computational biologist and discover five different species. The distance matrix among these species is provided below.

Now, to construct the phylogeny on these species, you apply the Neighbor-Joining algorithm and generate the following

matrix.

Answer the given sub-questions based on the same.

________________________. Enter the value as a single integer.

You enter an alien world as a renowned computational biologist and discover five different species. The distance matrix among these species is provided below.

Now, to construct the phylogeny on these species, you apply the Neighbor-Joining algorithm and generate the following

matrix.

Answer the given sub-questions based on the same.

_____________________. Enter the value as a single integer.

You enter an alien world as a renowned computational biologist and discover five different species. The distance matrix among these species is provided below.

Now, to construct the phylogeny on these species, you apply the Neighbor-Joining algorithm and generate the following

matrix.

Answer the given sub-questions based on the same.

______________________. Enter the value as a single integer.

You enter an alien world as a renowned computational biologist and discover five different species. The distance matrix among these species is provided below.

Now, to construct the phylogeny on these species, you apply the Neighbor-Joining algorithm and generate the following

matrix.

Answer the given sub-questions based on the same.

Which of the following species forms a cherry in the resulting phylogeny?

Given below is the profile matrix for a set of

motifs

.

.

Answer the given sub-questions with respect to the same.

Find the consensus of the motifs?

Given below is the profile matrix for a set of

motifs

.

.

Answer the given sub-questions with respect to the same.

Use the profile matrix to determine which of the following

-mers have the highest probability?

Given below is the profile matrix for a set of

motifs

.

.

Answer the given sub-questions with respect to the same.

Calculate the entropy of the first column. Round up the answer to

decimal places.