Fill the given blanks to complete the Neighbor-Joining algorithm. NEIGHBORJOINING(D, n) if n = 2 T ← the tree consisting of a single edge of length D_{1,2} return T D ← the neighbor-joining matrix constructed from the distance matrix D find elements i and j such that D_{i,j} is a minimum non-diagonal element of D Δ ← (TOTALDISTANCE_D(i) − TOTALDISTANCE_D(j)) / (n − 2) limbLength_i ← [ I ] limbLength_j ← [ II ] add a new row/column m to D so that D_{k,m} = D_{m,k} = 1/2 (D_{k,i} + D_{k,j} − D_{i,j}) for any k remove rows i and j from D remove columns i and j from D T ← NEIGHBORJOINING(D, n − 1) add two new limbs (connecting node m with leaves i and j) to the tree T assign length limbLength_i to LIMB(i) assign length limbLength_j to LIMB(j) return T

(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

Figure from the original question paper

(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

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

(D) Option figure from the original question paper

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 | 4 | 1 | | B | | 0 | 4 | 2 | 3 | | C | | | 0 | 4 | 1 | | 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.

(A) Option figure from the original question paper

(C) Option figure from the original question paper

(D) Option figure from the original question paper

(B) Option figure from the original question paper

(E) Option figure from the original question paper

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 constructed the following phylogeny using the “Additive Phylogeny” algorithm. The algorithm chose the leaf A in the first iteration, the leaf B in the second iteration, and the leaf C in the third iteration. Figure from the original question paper Which among the following is/are correct about the weights of the edges in the phylogeny?

(D) Weight of the edge between H and F is 2

(E) Weight of the edge between H and G is 1

(A) Weight of the edge between H and F is 1

(B) Weight of the edge between H and G is 2

(C) Weight of the edge between A and H is 1

May 2024 term · Algorithmic Thinking in Bioinformatics · BSBT4001

Algorithmic Thinking in Bioinformatics Quiz 2: 4 August 2024 (May 2024 term)

The IIT Madras BS Algorithmic Thinking in Bioinformatics (Algorithmic Thinking in Bioinformatics) Quiz 2 paper sat on 4 Aug 2024, in the May 2024 term: 15 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: 15
Marks: 50
Duration: 120 min
MCQ: 7
MSQ: 4
Numerical: 4

Take as mock test Practise with answers

Updated 25 Sept 2026

Official paper: IIT M DEGREE AN EXAM QDB2 4 Aug 2024 · No negative marking.

Question 1

+3 marksOne correct option

Fill the given blanks to complete the Neighbor-Joining algorithm.

text

1NEIGHBORJOINING(D, n)
2  if n = 2
3    T ← the tree consisting of a single edge of length D_{1,2}
4    return T
5  D* ← the neighbor-joining matrix constructed from the distance matrix D
6  find elements i and j such that D*_{i,j} is a minimum non-diagonal element of D*
7  Δ ← (TOTALDISTANCE_D(i) − TOTALDISTANCE_D(j)) / (n − 2)
8  limbLength_i ← [    I    ]
9  limbLength_j ← [    II    ]
10  add a new row/column m to D so that D_{k,m} = D_{m,k} = 1/2 (D_{k,i} + D_{k,j} − D_{i,j})
11    for any k
12  remove rows i and j from D
13  remove columns i and j from D
14  T ← NEIGHBORJOINING(D, n − 1)
15  add two new limbs (connecting node m with leaves i and j) to the tree T
16  assign length limbLength_i to LIMB(i)
17  assign length limbLength_j to LIMB(j)
18  return T

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

+3 marksOne correct option

Show answer

Correct answer

Question 3 on its own page

Question 4

+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	4	1
B		0	4	2	3
C			0	4	1
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.

Select all that apply.

Show answer

Correct answers

Question 4 on its own page

Question 5

+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: 1

Question 5 on its own page

Question 6

+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 have constructed the following phylogeny using the “Additive Phylogeny” algorithm. The algorithm chose the leaf A in the first iteration, the leaf B in the second iteration, and the leaf C in the third iteration.

Which among the following is/are correct about the weights of the edges in the phylogeny?

Select all that apply.

A
Weight of the edge between H and F is 1
B
Weight of the edge between H and G is 2
C
Weight of the edge between A and H is 1
D
Weight of the edge between H and F is 2
E
Weight of the edge between H and G is 1

Show answer

Correct answers

D
Weight of the edge between H and F is 2
E
Weight of the edge between H and G is 1

Question 6 on its own page

Question 7

+3 marksNumerical answer

You are asked to construct the suffix tree of an alien DNA sequence. If the alien DNA is composed of 6 different types of nucleotides, then what is the maximum number of children a node can have in the tree? Assume the symbol $ is appended at the end of the sequence.

Show answer

Correct answer: 7

Question 7 on its own page

Question 8

+3 marksNumerical answer

If a genome sequence Text of length 100 takes 400 Bytes of memory space, then how many Bytes of memory space is required to store the Burrows-Wheeler transform of Text?
Enter the value as a single integer.

Show answer

Correct answer: 400

Question 8 on its own page

Question 9

+4 marksOne or more correct options

You join a job that involves working on sample reads for disease X. The figure given below represents the suffix trie of the reference human genome (for a healthy person).

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 trie to identify which among these individuals is/are healthy?

Select all that apply.

A
CCGGG
B
CCGGT
C
CTAAC
D
TCAAC
E
ATCCG

Show answer

Correct answers

A
CCGGG
D
TCAAC

Question 9 on its own page

Question 10

+3 marksOne correct option

You join a job that involves working on sample reads for disease X. The figure given below represents the suffix trie of the reference human genome (for a healthy person).

Based on the above data, answer the given subquestions.

Use the suffix trie given to determine, which among the following is the reference human genome for a healthy person?

A
TTGTCCCCCGGGT$
B
TTGTCAACTGGGT$
C
ATGTCAACCGGGT$
D
ATGTCAACCGGGG$
E
TTTGCAACCGGGT$

Show answer

Correct answer

C
ATGTCAACCGGGT$

Question 10 on its own page

Question 11

+3 marksNumerical answer

Based on the above data, answer the given subquestions.

Show answer

Correct answer: 16

Question 11 on its own page

Question 12

+3 marksOne correct option

Based on the above data, answer the given subquestions.

Find the consensus of the motifs?

A
CAGAAT
B
CGGAAT
C
TAGAGG
D
GAGAAT
E
GGGACT

Show answer

Correct answer

E
GGGACT

Question 12 on its own page

Question 13

+4 marksOne correct option

Based on the above data, answer the given subquestions.

Use the profile matrix to determine which of the following k-mers have the highest probability?

A
ACAGGA
B
GAGACT
C
AGGACT
D
ACGGAA
E
GGGAAA

Show answer

Correct answer

B
GAGACT

Question 13 on its own page

Question 14

+4 marksOne correct option

Consider the following hard K-means clustering problem with five points: A (1, 2), B (2, 3), C (6, 7), D (8, 8), and E (7, 6). Consider the number of clusters to be K = 2 and the initial centroids to be C1 = (0, 0) and C2 = (7, 7). After how many iterations will the algorithm terminate and what will be the final centroids?

A
2, (1.5, 2.5), (7, 7)
B
3, (1.5, 2.5), (7, 7)
C
2, (1.5, 2.5), (7.5, 7)
D
3, (2, 3), (7, 7)

Show answer

Correct answer

A
2, (1.5, 2.5), (7, 7)

Question 14 on its own page

Question 15

+3 marksOne or more correct options

Which of the following is/are True?

Select all that apply.

A
K-means algorithm requires the initial centroids to be chosen randomly.
B
K-means algorithm may not find the globally optimal solution.
C
The complexity of the K-means algorithm is polynomial with respect to the number of data points and clusters.
D
K-means algorithm can be used for clustering data points in higher- dimensional spaces.

Show answer

Correct answers

A
K-means algorithm requires the initial centroids to be chosen randomly.
C
The complexity of the K-means algorithm is polynomial with respect to the number of data points and clusters.
D
K-means algorithm can be used for clustering data points in higher- dimensional spaces.

Question 15 on its own page