Given below are three algorithms for the motif finding problem. Identify which figure belongs to which algorithm. ████████ randomly select k-mers Motifs = (Motif_1, ..., Motif_t) in each string from Dna BestMotifs ← Motifs for j ← 1 to N i ← RANDOM(t) Profile ← profile matrix formed from all strings in Motifs except for Motif_i Motif_i ← Profile-randomly generated k-mer in the i-th sequence if SCORE(Motifs) < SCORE(BestMotifs) BestMotifs ← Motifs return BestMotifs (a) Figure I ████████ BestMotifs ← motif matrix formed by first k-mers in each string from Dna for each k-mer Motif in the first string from Dna Motif_1 ← Motif for i = 2 to t form Profile from motifs Motif_1, ..., Motif_{i-1} Motif_i ← Profile-most probable k-mer in the i-th string in Dna Motifs ← (Motif_1, ..., Motif_t) if SCORE(Motifs) < SCORE(BestMotifs) BestMotifs ← Motifs return BestMotifs (b) Figure II ████████ randomly select k-mers Motifs = (Motif_1, ..., Motif_t) in each string from Dna BestMotifs ← Motifs while forever Profile ← PROFILE(Motifs) Motifs ← MOTIFS(Profile, Dna) if SCORE(Motifs) < SCORE(BestMotifs) BestMotifs ← Motifs else return BestMotifs (c) Figure III

(B) Figure I: Gibbs Sampling; Figure II: Greedy Motif Search; Figure III: Randomized Motif Search

(A) Figure I: Gibbs Sampling; Figure II: Randomized Motif Search; Figure III: Greedy Motif Search

(C) Figure I: Greedy Motif Search; Figure II: Randomized Motif Search; Figure III: Gibbs Sampling

(D) Figure I: Randomized Motif Search; Figure II: Gibbs Sampling; Figure III: Greedy Motif Search

In a Gaussian Mixture Model (GMM) with two components, the parameters are as follows: - Component 1: Mean (\mu_1) = 2, Variance (\sigma_1^2) = 1, Mixture Proportion (\pi_1) = 0.6 - Component 2: Mean (\mu_2) = 5, Variance (\sigma_2^2) = 2, Mixture Proportion (\pi_2) = 0.4 Given a data point x = 3, calculate the responsibilities (posterior probabilities) for each component. Hint: \mathcal{N}(x \mid \mu, \sigma^2) = \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)

(D) Option figure from the original question paper

(A) Option figure from the original question paper

(B) Option figure from the original question paper

(C) Option figure from the original question paper

Consider a univariate Gaussian Mixture Model (GMM) with 3 components. Suppose for component 2 you are given the following data points and corresponding responsibilities: | x_i | r_{i,2} | |---|---| | 3 | 0.7 | | 2 | 0.5 | | 5 | 0.5 | Compute the updated mean \mu_2 for component 2. Which of the following options correctly represents the updated mean \mu_2?

(A) Option figure from the original question paper

(B) Option figure from the original question paper

(C) Option figure from the original question paper

(D) Option figure from the original question paper

In a soft K-means clustering model, each data point is D-dimensional and there are K clusters. The model learns: - A mean vector of dimension D for each cluster, - A separate variance (scalar) for each dimension in each cluster, - A cluster proportion (prior probability) for each cluster (which must sum to 1). How many independent parameters are there in total?

(C) Option figure from the original question paper

(A) Option figure from the original question paper

(B) Option figure from the original question paper

(D) Option figure from the original question paper

Algorithmic Thinking in Bioinformatics Quiz 2 PYQ May 2025: 3 Aug 2025

Question 1

+5 marksOne correct option

Given below are three algorithms for the motif finding problem. Identify which figure belongs to which algorithm.

text

1████████
2randomly select k-mers Motifs = (Motif_1, ..., Motif_t) in each string from Dna
3BestMotifs ← Motifs
4for j ← 1 to N
5  i ← RANDOM(t)
6  Profile ← profile matrix formed from all strings in Motifs except for Motif_i
7  Motif_i ← Profile-randomly generated k-mer in the i-th sequence
8  if SCORE(Motifs) < SCORE(BestMotifs)
9    BestMotifs ← Motifs
10return BestMotifs

(a) Figure I

text

1████████
2BestMotifs ← motif matrix formed by first k-mers in each string from Dna
3for each k-mer Motif in the first string from Dna
4  Motif_1 ← Motif
5  for i = 2 to t
6    form Profile from motifs Motif_1, ..., Motif_{i-1}
7    Motif_i ← Profile-most probable k-mer in the i-th string in Dna
8  Motifs ← (Motif_1, ..., Motif_t)
9  if SCORE(Motifs) < SCORE(BestMotifs)
10    BestMotifs ← Motifs
11return BestMotifs

(b) Figure II

text

1████████
2randomly select k-mers Motifs = (Motif_1, ..., Motif_t) in each string from Dna
3BestMotifs ← Motifs
4while forever
5  Profile ← PROFILE(Motifs)
6  Motifs ← MOTIFS(Profile, Dna)
7  if SCORE(Motifs) < SCORE(BestMotifs)
8    BestMotifs ← Motifs
9  else
10    return BestMotifs

(c) Figure III

A
Figure I: Gibbs Sampling; Figure II: Randomized Motif Search; Figure III: Greedy Motif Search
B
Figure I: Gibbs Sampling; Figure II: Greedy Motif Search; Figure III: Randomized Motif Search
C
Figure I: Greedy Motif Search; Figure II: Randomized Motif Search; Figure III: Gibbs Sampling
D
Figure I: Randomized Motif Search; Figure II: Gibbs Sampling; Figure III: Greedy Motif Search

Show answer

Correct answer

B
Figure I: Gibbs Sampling; Figure II: Greedy Motif Search; Figure III: Randomized Motif Search

Question 1 on its own pageAlso asked in Quiz 2 16 Mar 2025

Question 2

+3 marksOne correct option

A dataset is clustered into two groups using soft K-means. The distance of a data point from the two cluster centroids is $d_1 = 7.0$ and $d_2 = 2.0$ , respectively. Using the soft K-means formula with $\beta = 0.3$ , compute the probabilities of the data point belonging to each cluster. The probability formula is:

$P(C_k \mid x) = \frac{e^{-\beta d_k}}{\sum_{j=1}^{K} e^{-\beta d_j}}$

What are the probabilities $P(C_1)$ and $P(C_2)$ ?

A
B
C
D

Show answer

Correct answer

C

Question 2 on its own page

Question 3

+3 marksOne correct option

In a Gaussian Mixture Model (GMM) with two components, the parameters are as follows:

Component 1: Mean $(\mu_1) = 2$ , Variance $(\sigma_1^2) = 1$ , Mixture Proportion $(\pi_1) = 0.6$
Component 2: Mean $(\mu_2) = 5$ , Variance $(\sigma_2^2) = 2$ , Mixture Proportion $(\pi_2) = 0.4$

Given a data point $x = 3$ , calculate the responsibilities (posterior probabilities) for each component. Hint:

$\mathcal{N}(x \mid \mu, \sigma^2) = \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)$

A
B
C
D

Show answer

Correct answer

D

Question 3 on its own page

Question 4

+2 marksOne correct option

Consider a univariate Gaussian Mixture Model (GMM) with 3 components. Suppose for component 2 you are given the following data points and corresponding responsibilities:

$x_i$	$r_{i,2}$
3	0.7
2	0.5
5	0.5

Compute the updated mean $\mu_2$ for component 2. Which of the following options correctly represents the updated mean $\mu_2$ ?

A
B
C
D

Show answer

Correct answer

A

Question 4 on its own page

Question 5

+2 marksOne correct option

In a soft K-means clustering model, each data point is $D$ -dimensional and there are $K$ clusters. The model learns:

A mean vector of dimension $D$ for each cluster,
A separate variance (scalar) for each dimension in each cluster,
A cluster proportion (prior probability) for each cluster (which must sum to 1).

How many independent parameters are there in total?

A
B
C
D

Show answer

Correct answer

C

Question 5 on its own page

Question 6

+3 marksOne or more correct options

Which of the following statements about additive distance matrices are true?

Select all that apply.

A
Every 3 x 3 distance matrix is additive.
B
Every 4 x 4 distance matrix is additive.
C
There exists a 3 x 3 distance matrix that is not additive.
D
There exists a 4 x 4 distance matrix that is not additive.
E
For every additive distance matrix, there exists a simple tree fitting the matrix.

Show answer

Correct answers

A
Every 3 x 3 distance matrix is additive.
D
There exists a 4 x 4 distance matrix that is not additive.
E
For every additive distance matrix, there exists a simple tree fitting the matrix.

Question 6 on its own page

Question 7

+3 marksNumerical answer

Show answer

Correct answer: 16

Question 7 on its own page

Question 8

+4 marksNumerical answer

Show answer

Correct answer: 3

Question 8 on its own page

Question 9

+3 marksNumerical answer

What is the number of edges in the corresponding suffix trie? Enter the value as a single integer.

Show answer

Correct answer: 32

Question 9 on its own page

Question 10

+2 marksNumerical answer

What is the length of the reference sequence from which this suffix tree has been constructed? Include $ in the calculation of length. Enter the value as a single integer.

Show answer

Correct answer: 8

Question 10 on its own page

Question 11

+3 marksOne correct option

Use the given suffix tree to determine which of the following is the suffix array for the reference sequence ? Assume $ comes first in the alphabet.

A
[7, 6, 5, 3, 1, 4, 2, 0]
B
[7, 6, 5, 3, 1, 4, 0, 2]
C
[7, 5, 3, 1, 6, 4, 2, 0]
D
[7, 5, 3, 1, 6, 4, 0, 2]
E
None of these

Show answer

Correct answer

C
[7, 5, 3, 1, 6, 4, 2, 0]

Question 11 on its own page

Question 12

+2 marksOne correct option

Given below in Table 2 is the profile matrix derived from a set of 10 motifs $\mathit{Motifs}$ . Answer the given subquestions with respect to the same.

Table 2: Profile Matrix $\mathit{Profile}(\mathit{Motifs}) =$

A:	0.2	0	0	0.5	0.7
C:	0.1	0.6	0	0.2	0.3
G:	0.1	0.4	0	0.3	0
T:	0.6	0	1	0	0

Find the consensus of the motifs?

A
TCATGA
B
AACCGT
C
TCTAAA
D
TCATAA

Show answer

Correct answer

D
TCATAA

Question 12 on its own page

Question 13

+2 marksNumerical answer

Given below in Table 2 is the profile matrix derived from a set of 10 motifs $\mathit{Motifs}$ . Answer the given subquestions with respect to the same.

Table 2: Profile Matrix $\mathit{Profile}(\mathit{Motifs}) =$

A:	0.2	0	0	0.5	0.7
C:	0.1	0.6	0	0.2	0.3
G:	0.1	0.4	0	0.3	0
T:	0.6	0	1	0	0

Show answer

Correct answer: 16

Question 13 on its own page

Question 14

+4 marksNumerical answer

Given below in Table 2 is the profile matrix derived from a set of 10 motifs $\mathit{Motifs}$ . Answer the given subquestions with respect to the same.

Table 2: Profile Matrix $\mathit{Profile}(\mathit{Motifs}) =$

A:	0.2	0	0	0.5	0.7
C:	0.1	0.6	0	0.2	0.3
G:	0.1	0.4	0	0.3	0
T:	0.6	0	1	0	0

Calculate the entropy of the first column. Round up the answer to 3 decimal places.

Show answer

Correct answer: 1.575 (accepted within ±0.005)

Question 14 on its own page

Question 15

+5 marksOne correct option

You are applying the Neighbor-Joining algorithm on some distance matrix. The $D^\star$ matrix obtained during some iteration is given in Table 1. Answer the given subquestions with respect to the same.

Table 1: $D^\star$ matrix

	A	B	C	D	E
A	0	-12	-16	-11	-15
B		0	-10	-20	-12
C			0	-12	-16
D				0	-11
E					0

A
B
C
D

Show answer

Correct answer

C

Question 15 on its own page

Question 16

+4 marksOne correct option

You are applying the Neighbor-Joining algorithm on some distance matrix. The $D^\star$ matrix obtained during some iteration is given in Table 1. Answer the given subquestions with respect to the same.

Table 1: $D^\star$ matrix

	A	B	C	D	E
A	0	-12	-16	-11	-15
B		0	-10	-20	-12
C			0	-12	-16
D				0	-11
E					0

Which of the following represents the distance matrix for the next iteration?

A
B
C
D

Show answer

Correct answer

A

Question 16 on its own page

Question 17

+2 marksOne correct option

You are given the Burrows-Wheeler Transform $\mathit{BWT}$ of a $n$ -length string $\mathit{Text}$ . Assume that the $ symbol is included at the end of $\mathit{Text}$ . Let $\mathit{First}$ represent the string obtained by sorting the characters of $\mathit{BWT}$ . Assume that every occurrence of a repeated character is considered as an unique character (both in $\mathit{BWT}$ and $\mathit{First}$ ) and is sequentially numbered.

Let $\mathit{Text}[i]$ , $\mathit{BWT}[i]$ and $\mathit{First}[i]$ represent the $i^{\text{th}}$ character in $\mathit{Text}$ , $\mathit{BWT}$ and $\mathit{First}$ respectively.

We use these three strings to construct a directed graph $G = (V, E)$ as follows. Every character in $\mathit{Text}$ including the repeated characters forms a node in $G$ , so that there are $n$ nodes in the graph. Hence, for every $1 \le i \le n$ , $\mathit{Text}[i]$ is a node in $G$ .

For example, consider the string $NGNNING\$$. There are 4 occurrences of$ N $, 2 occurrences of$ G $and 1 occurrences of both$ I $and \$ . So, the vertex set $V$ of the graph $G$ is $\{N_1,\ N_2,\ N_3,\ N_4,\ G_1,\ G_2,\ I,\ \$ }$.

Now, we add edges to $G$ as follows: For every location $1 \le i \le n$ , we add a directed edge from $\mathit{First}[i]$ to $\mathit{BWT}[i]$ . Answer the given subquestions with respect to this graph $G$ .

A
B
C
D

Show answer

Correct answer

A

Question 17 on its own page

Question 18

+1 markOne correct option

You are given the Burrows-Wheeler Transform $\mathit{BWT}$ of a $n$ -length string $\mathit{Text}$ . Assume that the $ symbol is included at the end of $\mathit{Text}$ . Let $\mathit{First}$ represent the string obtained by sorting the characters of $\mathit{BWT}$ . Assume that every occurrence of a repeated character is considered as an unique character (both in $\mathit{BWT}$ and $\mathit{First}$ ) and is sequentially numbered.

Let $\mathit{Text}[i]$ , $\mathit{BWT}[i]$ and $\mathit{First}[i]$ represent the $i^{\text{th}}$ character in $\mathit{Text}$ , $\mathit{BWT}$ and $\mathit{First}$ respectively.

We use these three strings to construct a directed graph $G = (V, E)$ as follows. Every character in $\mathit{Text}$ including the repeated characters forms a node in $G$ , so that there are $n$ nodes in the graph. Hence, for every $1 \le i \le n$ , $\mathit{Text}[i]$ is a node in $G$ .

For example, consider the string $NGNNING\$$. There are 4 occurrences of$ N $, 2 occurrences of$ G $and 1 occurrences of both$ I $and \$ . So, the vertex set $V$ of the graph $G$ is $\{N_1,\ N_2,\ N_3,\ N_4,\ G_1,\ G_2,\ I,\ \$ }$.

Now, we add edges to $G$ as follows: For every location $1 \le i \le n$ , we add a directed edge from $\mathit{First}[i]$ to $\mathit{BWT}[i]$ . Answer the given subquestions with respect to this graph $G$ .

A
B
C
D
E

Show answer

Correct answer

C

Question 18 on its own page