Figure from the original question paper

(B) Option figure from the original question paper

(A) Option figure from the original question paper

(C) Option figure from the original question paper

(D) Option figure from the original question paper

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

You enter an alien world as a renowned computational biologist. The table below is presented to you as part of a preliminary study done by a group of scientists to study the local fauna around the base camp. They have analyzed the DNA and figured out that there are only two bases “+” and “0”. The table below represents the DNA sequence in 6 positions for the different species found. The DNA sequence (“+” and “0”) | species | 1 | 2 | 3 | 4 | 5 | 6 | |---|---|---|---|---|---|---| | A | 0 | + | + | 0 | 0 | + | | B | + | 0 | 0 | 0 | 0 | + | | C | 0 | + | + | 0 | + | + | | D | 0 | 0 | 0 | 0 | 0 | 0 | | E | 0 | + | + | 0 | + | + | Based on the above data, answer the given subquestions. The scientists have tried to construct the distance matrix as follows: | | A | B | C | D | E | |---|---|---|---|---|---| | A | 0 | 3 | 1 | 3 | 1 | | B | | 0 | 3 | 2 | 4 | | C | | | 0 | 3 | 0 | | D | | | | 0 | 4 | | E | | | | | 0 | Your task is to verify if the distance matrix is correct, and if there are wrong values in the matrix, then substitute with the correct values. Which among the following represent the corrections you have to make? Here d[x, y] represents the Hamming distance between the x and y species. Choose all the options that apply.

(B) Option figure from the original question paper

(D) Option figure from the original question paper

(A) Option figure from the original question paper

(C) Option figure from the original question paper

(E) Option figure from the original question paper

January 2025 term · Algorithmic Thinking in Bioinformatics · BSBT4001

Algorithmic Thinking in Bioinformatics Quiz 2: 16 March 2025 (January 2025 term)

The IIT Madras BS Algorithmic Thinking in Bioinformatics (Algorithmic Thinking in Bioinformatics) Quiz 2 paper sat on 16 Mar 2025, in the January 2025 term: 17 questions for 50 marks in 120 minutes. Every question is below with its answer. Take it as a timed mock test to be marked, or read it through first.

Questions: 17
Marks: 50
Duration: 120 min
MCQ: 8
Numerical: 5
MSQ: 4

Take as mock test Practise with answers

Updated 25 Sept 2026

Official paper: IIT M DEGREE AN EXAM QDB2 16 Mar 2025 · No negative marking.

Question 1

+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. Which of the following options correctly represents the updated mean $\mu_2$ ?

$x_i$	$r_{i,2}$
3	0.1
7	0.7
10	0.6
5	0.4
8	0.8

Show answer

Correct answer

Question 1 on its own page

Question 2

+3 marksOne correct option

Show answer

Correct answer

Question 2 on its own page

Question 3

+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

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 3 on its own pageAlso asked in Quiz 2 3 Aug 2025

Question 4

+2 marksNumerical answer

The number of leaves in the suffix tree (including the $ symbol) of a genome sequence is 15 and the number of elements in the Burrows-Wheeler matrix is 225. What is the length of the original genome sequence (including the $ symbol)?
Enter the value as a single integer.

Show answer

Correct answer: 15

Question 4 on its own page

Question 5

+2 marksNumerical answer

What is the maximum possible length of the run-length encoding of a genome sequence of length 50. (Hint: Beware that the length of a run-length encoding of a string should include both the counts and the characters in the encoded string.)

Show answer

Correct answer: 100

Question 5 on its own page

Question 6

+2 marksOne or more correct options

Recall that if the distance matrix is additive, then there is a unique simple tree that fits this matrix. Suppose you are given an additive distance matrix D and you construct two phylogenies from D. The first phylogeny T1 is constructed using the Additive Phylogeny algorithm, while the second phylogeny T2 is constructed using the Neighbor Joining algorithm. Choose all the statements which are correct about the two trees.

Select all that apply.

A
T1 and T2 have the same leaves.
B
T1 and T2 have the same cherries.
C
T1 and T2 are identical

Show answer

Correct answers

A
T1 and T2 have the same leaves.
B
T1 and T2 have the same cherries.
C
T1 and T2 are identical

Question 6 on its own page

Question 7

+4 marksOne or more correct options

You enter an alien world as a renowned computational biologist. The table below is presented to you as part of a preliminary study done by a group of scientists to study the local fauna around the base camp. They have analyzed the DNA and figured out that there are only two bases “+” and “0”. The table below represents the DNA sequence in 6 positions for the different species found.

The DNA sequence (“+” and “0”)

species	1	2	3	5	6
A	0	+	+	0	+
B	+	0	0	0	+
C	0	+	+	+	+
D	0	0	0	0	0
E	0	+	+	+	+

Based on the above data, answer the given subquestions.

The scientists have tried to construct the distance matrix as follows:

	A	B	C	D	E
A	0	3	1	3	1
B		0	3	2	4
C			0	3	0
D				0	4
E					0

Your task is to verify if the distance matrix is correct, and if there are wrong values in the matrix, then substitute with the correct values. Which among the following represent the corrections you have to make? Here $d[x, y]$ represents the Hamming distance between the $x$ and $y$ species. Choose all the options that apply.

Select all that apply.

Show answer

Correct answers

Question 7 on its own page

Question 8

+3 marksNumerical answer

The DNA sequence (“+” and “0”)

species	1	2	3	5	6
A	0	+	+	0	+
B	+	0	0	0	+
C	0	+	+	+	+
D	0	0	0	0	0
E	0	+	+	+	+

Based on the above data, answer the given subquestions.

Show answer

Correct answer: 0

Question 8 on its own page

Question 9

+4 marksOne or more correct options

The DNA sequence (“+” and “0”)

species	1	2	3	5	6
A	0	+	+	0	+
B	+	0	0	0	+
C	0	+	+	+	+
D	0	0	0	0	0
E	0	+	+	+	+

Based on the above data, answer the given subquestions.

The scientists applied the Neighbor-Joining algorithm to construct the phylogeny and have tried to construct the following $D^\star$ matrix. Choose the option/s that correctly fills the entries in the matrix?

	A	B	C	D	E
A	0	-12	-14	?	?
B		0	-10	?	-14
C			0	-10	-18
D				0	?
E					0

Select all that apply.

Show answer

Correct answers

Question 9 on its own page

Question 10

+3 marksOne correct option

Based on the above data, answer the given subquestions.

What is the probability of observing data point 7 according to this model?

Show answer

Correct answer

Question 10 on its own page

Question 11

+3 marksNumerical answer

Based on the above data, answer the given subquestions.

Given that data point 7 is observed, what is the probability that the observation is from component A?
Round your answer to 3 decimal digits.

Show answer

Correct answer: 0.4475 (accepted within ±0.0025)

Question 11 on its own page

Question 12

+3 marksOne or more correct options

Based on the above data, answer the given subquestions.

We say a person S does not have the disease X (i.e., S is healthy) if the sample read collected (from S) does not have any mutation. The options given below are the reads collected from different individuals. Match the reads with the suffix tree to identify which among these individuals suffer from the disease? Choose all the options that apply.

Select all that apply.

A
TCAAC
B
ATGCC
C
AGCCG
D
ACGGT
E
CCGGG

Show answer

Correct answers

B
ATGCC
C
AGCCG
D
ACGGT

Question 12 on its own page

Question 13

+3 marksOne correct option

Based on the above data, answer the given subquestions.

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

A
[13, 5, 6, 0, 4, 7, 8, 9, 10, 11, 2, 12, 3, 1]
B
[13, 12, 3, 1, 2, 11, 10, 9, 8, 7, 4, 6, 5, 0]
C
[0, 5, 6, 4, 7, 8, 9, 10, 11, 2, 1, 3, 12, 13]
D
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]

Show answer

Correct answer

A
[13, 5, 6, 0, 4, 7, 8, 9, 10, 11, 2, 12, 3, 1]

Question 13 on its own page

Question 14

+3 marksOne correct option

Based on the above data, answer the given subquestions.

You are trying to read the entire genome sequence of a new individual. But due to a technical problem, the machine could read the first 7 nucleotides only. Later you learn that the individual is not affected by the disease X. Which of the following reads is the string that the machine could not read?

A
CCGGG$
B
TCAAC$
C
AGCCG$
D
ATGCC$
E
CGGGT$

Show answer

Correct answer

E
CGGGT$

Question 14 on its own page

Question 15

+3 marksOne correct option

Based on the above data, answer the given subquestions.

Show answer

Correct answer

Question 15 on its own page

Question 16

+2 marksOne correct option

Based on the above data, answer the given subquestions.

Which of the following is the consensus of the motifs?

A
CTCTCA
B
TTTAAT
C
GGGACT
D
CCCTGA

Show answer

Correct answer

D
CCCTGA

Question 16 on its own page

Question 17

+3 marksNumerical answer

Based on the above data, answer the given subquestions.

Show answer

Correct answer: 16

Question 17 on its own page