bt4001_2026T2_Q2_NA.pdf
Algorithmic Thinking in Bioinformatics · Quiz 2 · May 2026
← Course papers · Start practice / exam
Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.
Question 2 MCQ · 2.0 marks
An additive distance matrix [[IMAGE:f9c1103f46ae0fc2_2_2]] , defined for [[IMAGE:f9c1103f46ae0fc2_2_3]] species, requires [[IMAGE:f9c1103f46ae0fc2_2_4]] space when stored as a full
distance matrix. We apply the additive phylogeny algorithm on [[IMAGE:f9c1103f46ae0fc2_2_5]] to construct a simple
phylogenetic tree [[IMAGE:f9c1103f46ae0fc2_2_6]] with [[IMAGE:f9c1103f46ae0fc2_2_7]] leaves and at most [[IMAGE:f9c1103f46ae0fc2_2_8]] branching points (internal nodes), and store
it to a file. Assume that every value stored in both the files including the names of the leaves are
integers, and requires same amount of storage space. Answer the given subquestions with
respect to the same.
What is the asymptotic space complexity required to store the **topology** of the phylogenetic tree?
[[IMAGE:f9c1103f46ae0fc2_2_9]]
[[IMAGE:f9c1103f46ae0fc2_2_10]]
[[IMAGE:f9c1103f46ae0fc2_2_11]]
[[IMAGE:f9c1103f46ae0fc2_2_12]]
A published solution is not available for this question yet.
Question 3 MCQ · 2.0 marks
An additive distance matrix [[IMAGE:f9c1103f46ae0fc2_2_2]] , defined for [[IMAGE:f9c1103f46ae0fc2_2_3]] species, requires [[IMAGE:f9c1103f46ae0fc2_2_4]] space when stored as a full
distance matrix. We apply the additive phylogeny algorithm on [[IMAGE:f9c1103f46ae0fc2_2_5]] to construct a simple
phylogenetic tree [[IMAGE:f9c1103f46ae0fc2_2_6]] with [[IMAGE:f9c1103f46ae0fc2_2_7]] leaves and at most [[IMAGE:f9c1103f46ae0fc2_2_8]] branching points (internal nodes), and store
it to a file. Assume that every value stored in both the files including the names of the leaves are
integers, and requires same amount of storage space. Answer the given subquestions with
respect to the same.
What is the asymptotic space complexity required to store the **branch lengths** of the phylogenetic
tree?
[[IMAGE:f9c1103f46ae0fc2_3_13]]
[[IMAGE:f9c1103f46ae0fc2_3_14]]
[[IMAGE:f9c1103f46ae0fc2_3_15]]
[[IMAGE:f9c1103f46ae0fc2_3_16]]
A published solution is not available for this question yet.
Question 4 MCQ · 1.0 marks
An additive distance matrix [[IMAGE:f9c1103f46ae0fc2_2_2]] , defined for [[IMAGE:f9c1103f46ae0fc2_2_3]] species, requires [[IMAGE:f9c1103f46ae0fc2_2_4]] space when stored as a full
distance matrix. We apply the additive phylogeny algorithm on [[IMAGE:f9c1103f46ae0fc2_2_5]] to construct a simple
phylogenetic tree [[IMAGE:f9c1103f46ae0fc2_2_6]] with [[IMAGE:f9c1103f46ae0fc2_2_7]] leaves and at most [[IMAGE:f9c1103f46ae0fc2_2_8]] branching points (internal nodes), and store
it to a file. Assume that every value stored in both the files including the names of the leaves are
integers, and requires same amount of storage space. Answer the given subquestions with
respect to the same.
What is the asymptotic time complexity required to retrieve the distance between two leaves [[IMAGE:f9c1103f46ae0fc2_3_17]] and
[[IMAGE:f9c1103f46ae0fc2_3_18]] using [[IMAGE:f9c1103f46ae0fc2_3_19]] ?
[[IMAGE:f9c1103f46ae0fc2_3_20]]
[[IMAGE:f9c1103f46ae0fc2_3_21]]
[[IMAGE:f9c1103f46ae0fc2_3_22]]
[[IMAGE:f9c1103f46ae0fc2_3_23]]
A published solution is not available for this question yet.
Question 5 MCQ · 4.0 marks
An additive distance matrix [[IMAGE:f9c1103f46ae0fc2_2_2]] , defined for [[IMAGE:f9c1103f46ae0fc2_2_3]] species, requires [[IMAGE:f9c1103f46ae0fc2_2_4]] space when stored as a full
distance matrix. We apply the additive phylogeny algorithm on [[IMAGE:f9c1103f46ae0fc2_2_5]] to construct a simple
phylogenetic tree [[IMAGE:f9c1103f46ae0fc2_2_6]] with [[IMAGE:f9c1103f46ae0fc2_2_7]] leaves and at most [[IMAGE:f9c1103f46ae0fc2_2_8]] branching points (internal nodes), and store
it to a file. Assume that every value stored in both the files including the names of the leaves are
integers, and requires same amount of storage space. Answer the given subquestions with
respect to the same.
Suppose the distance matrix [[IMAGE:f9c1103f46ae0fc2_3_24]] is not available, and only the files containing information on the
phylogenetic tree are accessible. Then, what is the asymptotic time complexity required to retrieve
the distance between two leaves [[IMAGE:f9c1103f46ae0fc2_4_25]] and [[IMAGE:f9c1103f46ae0fc2_4_26]] ?
[[IMAGE:f9c1103f46ae0fc2_4_27]]
[[IMAGE:f9c1103f46ae0fc2_4_28]]
[[IMAGE:f9c1103f46ae0fc2_4_29]]
[[IMAGE:f9c1103f46ae0fc2_4_30]]
A published solution is not available for this question yet.
Question 6 MCQ · 2.0 marks
Consider the profile matrix given below. [[IMAGE:f9c1103f46ae0fc2_4_31]]
[[IMAGE:f9c1103f46ae0fc2_4_32]]
This profile matrix was computed from a set of five motifs as shown below. Three nucleotides in
the motif set are missing. Use the given profile matrix above to infer the missing nucleotides and
answer the given subquestions with respect to the same.
[[IMAGE:f9c1103f46ae0fc2_4_33]]
What is the nucleotide at position (i) in the given set of motifs?
A
C
G
T
A published solution is not available for this question yet.
Question 7 MCQ · 3.0 marks
Consider the profile matrix given below. [[IMAGE:f9c1103f46ae0fc2_4_31]]
[[IMAGE:f9c1103f46ae0fc2_4_32]]
This profile matrix was computed from a set of five motifs as shown below. Three nucleotides in
the motif set are missing. Use the given profile matrix above to infer the missing nucleotides and
answer the given subquestions with respect to the same.
[[IMAGE:f9c1103f46ae0fc2_4_33]]
Determine the nucleotide/s at positions (ii) and (iii).
A
C
G
T
A published solution is not available for this question yet.
Question 8 NAT · 3.0 marks
Consider the following distance matrix [[IMAGE:f9c1103f46ae0fc2_5_34]] .
[[IMAGE:f9c1103f46ae0fc2_5_35]]
Answer the given subquestions with respect to the same.
Calculate [[IMAGE:f9c1103f46ae0fc2_5_36]] ?
A published solution is not available for this question yet.
Question 9 MSQ · 2.0 marks
Consider the following distance matrix [[IMAGE:f9c1103f46ae0fc2_5_34]] .
[[IMAGE:f9c1103f46ae0fc2_5_35]]
Answer the given subquestions with respect to the same.
Suppose the UPGMA algorithm is applied to this distance matrix. Which of the following pair(s) of
leaves can be merged first?
[[IMAGE:f9c1103f46ae0fc2_6_37]]
[[IMAGE:f9c1103f46ae0fc2_6_38]]
[[IMAGE:f9c1103f46ae0fc2_6_39]]
[[IMAGE:f9c1103f46ae0fc2_6_40]]
A published solution is not available for this question yet.
Question 10 MCQ · 3.0 marks
Consider the following procedure for assigning strings to nodes of a suffix tree [[IMAGE:f9c1103f46ae0fc2_6_41]]
constructed from the string [[IMAGE:f9c1103f46ae0fc2_6_42]] . Here, [[IMAGE:f9c1103f46ae0fc2_6_43]] and [[IMAGE:f9c1103f46ae0fc2_6_44]] represent the set of nodes and edges of [[IMAGE:f9c1103f46ae0fc2_6_45]]
respectively. Which of the following correctly describes the string assigned to a leaf [[IMAGE:f9c1103f46ae0fc2_6_46]] of the suffix
tree?
[[IMAGE:f9c1103f46ae0fc2_6_47]]
A prefix of [[IMAGE:f9c1103f46ae0fc2_6_48]] .
A suffix of [[IMAGE:f9c1103f46ae0fc2_6_49]] .
Any random substring of [[IMAGE:f9c1103f46ae0fc2_7_50]] .
Any random subsequence of [[IMAGE:f9c1103f46ae0fc2_7_51]] .
Cannot be determined from the information provided
A published solution is not available for this question yet.
Question 11 MCQ · 3.0 marks
The waiting time [[IMAGE:f9c1103f46ae0fc2_7_52]] (in arbitrary units) between successive transcription-initiation events at a
promoter is modelled by the density
[[IMAGE:f9c1103f46ae0fc2_7_53]]
Find the maximum likelihood estimate of the parameter [[IMAGE:f9c1103f46ae0fc2_7_54]] for a sample of unit size [[IMAGE:f9c1103f46ae0fc2_7_55]] , with [[IMAGE:f9c1103f46ae0fc2_7_56]]
being the observed sample value.
[[IMAGE:f9c1103f46ae0fc2_7_57]]
[[IMAGE:f9c1103f46ae0fc2_7_58]]
[[IMAGE:f9c1103f46ae0fc2_7_59]]
[[IMAGE:f9c1103f46ae0fc2_7_60]]
A published solution is not available for this question yet.
Question 12 MCQ · 3.0 marks
A researcher clusters tumour samples using vanilla soft [[IMAGE:f9c1103f46ae0fc2_7_61]] -means and steadily increases the
stiffness parameter [[IMAGE:f9c1103f46ae0fc2_7_62]] towards very large values. Which statement best describes the behaviour of
the algorithm, and what does the corresponding GMM assumption imply?
Every sample tends to receive responsibility [[IMAGE:f9c1103f46ae0fc2_7_63]] for all clusters; this
corresponds to [[IMAGE:f9c1103f46ae0fc2_7_64]] .
Assignments become winner-takes-all, recovering hard
[[IMAGE:f9c1103f46ae0fc2_8_65]] -means; since [[IMAGE:f9c1103f46ae0fc2_8_66]] , this corresponds to [[IMAGE:f9c1103f46ae0fc2_8_67]] .
Assignments become winner-takes-all, recovering hard [[IMAGE:f9c1103f46ae0fc2_8_68]] -means; since
[[IMAGE:f9c1103f46ae0fc2_8_69]] , this corresponds to [[IMAGE:f9c1103f46ae0fc2_8_70]] .
The mixing proportions [[IMAGE:f9c1103f46ae0fc2_8_71]] become unequal, allowing clusters of different
sizes.
A published solution is not available for this question yet.
Question 13 NAT · 2.0 marks
You are asked to construct the suffix array of an alien DNA sequence of length [[IMAGE:f9c1103f46ae0fc2_8_72]] , where the
sequence includes the symbol [[IMAGE:f9c1103f46ae0fc2_8_73]] . If the alien DNA is composed of [[IMAGE:f9c1103f46ae0fc2_8_74]] different types of nucleotides,
then what is the number of entries in the suffix array?
A published solution is not available for this question yet.
Question 14 MCQ · 3.0 marks
You join a job that involves working on sample reads for disease [[IMAGE:f9c1103f46ae0fc2_8_75]] . The figure given below
represents the suffix trie of the reference human genome (for a healthy person).
[[IMAGE:f9c1103f46ae0fc2_9_76]]
Answer the given subquestions with respect to the same.
Determine which among the following is the reference DNA sequence?
TTGTCCCCCGGGT$
TTGTCAACTGGGT$
ATGTCAACCGGGT$
ATGTCAACCGGGG$
TTTGCAACCGGGT$
A published solution is not available for this question yet.
Question 15 MSQ · 4.0 marks
You join a job that involves working on sample reads for disease [[IMAGE:f9c1103f46ae0fc2_8_75]] . The figure given below
represents the suffix trie of the reference human genome (for a healthy person).
[[IMAGE:f9c1103f46ae0fc2_9_76]]
Answer the given subquestions with respect to the same.
In this simplified model, assume a person [[IMAGE:f9c1103f46ae0fc2_10_77]] does not have the disease [[IMAGE:f9c1103f46ae0fc2_10_78]] (i.e., [[IMAGE:f9c1103f46ae0fc2_10_79]] is healthy) if the
sample read collected (from [[IMAGE:f9c1103f46ae0fc2_10_80]] ) does not have any mutation. The options given below are the
reads collected from different individuals. Determine which among these individuals is/are
healthy?
TTAC
GTCA
ATGT
GGCC
A published solution is not available for this question yet.
Question 16 MCQ · 4.0 marks
Given the profile matrix of a set of motifs, find the profile-most probable [[IMAGE:f9c1103f46ae0fc2_10_81]] -mer in the sequence
ATGTGCA.
[[IMAGE:f9c1103f46ae0fc2_10_82]]
ATGT
TGTG
GTGC
TGCA
A published solution is not available for this question yet.
Question 17 MCQ · 4.0 marks
A set of gene expression profiles is clustered into two co-expression modules using soft [[IMAGE:f9c1103f46ae0fc2_11_83]] -means.
For a particular gene, the distance of its expression vector from the two module centroids is
[[IMAGE:f9c1103f46ae0fc2_11_84]] and [[IMAGE:f9c1103f46ae0fc2_11_85]] , respectively. Using the soft [[IMAGE:f9c1103f46ae0fc2_11_86]] -means formula with stiffness [[IMAGE:f9c1103f46ae0fc2_11_87]] ,
compute the probabilities that this gene belongs to each module. The probability formula is:
[[IMAGE:f9c1103f46ae0fc2_11_88]]
What are the probabilities [[IMAGE:f9c1103f46ae0fc2_11_89]] and [[IMAGE:f9c1103f46ae0fc2_11_90]] ?
[[IMAGE:f9c1103f46ae0fc2_11_91]] , [[IMAGE:f9c1103f46ae0fc2_11_92]]
[[IMAGE:f9c1103f46ae0fc2_11_93]] , [[IMAGE:f9c1103f46ae0fc2_11_94]]
[[IMAGE:f9c1103f46ae0fc2_11_95]] , [[IMAGE:f9c1103f46ae0fc2_11_96]]
[[IMAGE:f9c1103f46ae0fc2_11_97]] , [[IMAGE:f9c1103f46ae0fc2_11_98]]
A published solution is not available for this question yet.
Question 18 MCQ · 5.0 marks
The GC-content distribution of a bacterial metagenome is modelled as a two-component Gaussian
Mixture Model, where each component corresponds to a distinct taxonomic bin:
• Component 1: Mean [[IMAGE:f9c1103f46ae0fc2_11_99]] , Variance [[IMAGE:f9c1103f46ae0fc2_11_100]] , Weight [[IMAGE:f9c1103f46ae0fc2_11_101]]
• Component 2: Mean [[IMAGE:f9c1103f46ae0fc2_11_102]] , Variance [[IMAGE:f9c1103f46ae0fc2_11_103]] , Weight [[IMAGE:f9c1103f46ae0fc2_11_104]]
Given a contig with normalized GC score [[IMAGE:f9c1103f46ae0fc2_11_105]] , calculate the responsibilities (posterior
probabilities) for each component. Hint:
[[IMAGE:f9c1103f46ae0fc2_11_106]]
[[IMAGE:f9c1103f46ae0fc2_12_107]] , [[IMAGE:f9c1103f46ae0fc2_12_108]]
[[IMAGE:f9c1103f46ae0fc2_12_109]] , [[IMAGE:f9c1103f46ae0fc2_12_110]]
[[IMAGE:f9c1103f46ae0fc2_12_111]] , [[IMAGE:f9c1103f46ae0fc2_12_112]]
[[IMAGE:f9c1103f46ae0fc2_12_113]] , [[IMAGE:f9c1103f46ae0fc2_12_114]]
A published solution is not available for this question yet.