Algorithmic Thinking in Bioinformatics Quiz 1 PYQ Jan 2025: 23 Feb 2025

Question 1

+3 marksOne correct option

Given below is the algorithm to print the longest common subsequence between the $i$ -prefix of $v$ and the $j$ -prefix of $w$ . The matrix $\mathit{Backtrack}$ stores the directions along which the algorithm should perform the backtracking operation in the form of arrows. Fill the given blanks to complete the algorithm.

text

1OUTPUTLCS(Backtrack, v, i, j)
2  if i = 0 or j = 0
3    return
4  if Backtrack_{i,j} = ↓
5    OUTPUTLCS([    I    ])
6  else if Backtrack_{i,j} = →
7    OUTPUTLCS([    II    ])
8  else
9    OUTPUTLCS([    III    ])
10    output v_i

A
B
C
D

Show answer

Correct answer

B

Question 1 on its own page

Question 2

+3 marksNumerical answer

Calculate the optimal global alignment score for the DNA sequences GAATTC and GATTA. Scoring is done as follows:
• For every match: +2 points
• For every mismatch: -1 points
• For every insertion or deletion: -2 points

Show answer

Correct answer: 5

Question 2 on its own page

Question 3

+3 marksNumerical answer

Show answer

Correct answer: 5

Question 3 on its own page

Question 4

+4 marksNumerical answer

Show answer

Correct answer: 50

Question 4 on its own page

Question 5

+5 marksNumerical answer

You are analyzing a dataset of $N = 100$ protein-protein interaction (PPI) samples. Each interaction is represented by 3 numerical features: $X = [X^{(1)}, X^{(2)}, X^{(3)}]$ , where $X^{(1)}, X^{(2)}, X^{(3)} \in \mathbb{R}$ . The binary target variable $y$ represents whether an interaction occurs ( $y = 1$ ) or not ( $y = 0$ ).

You aim to train a logistic regression model with L2 regularization (ridge regression) to predict interactions based on these features. The regularized cost function, $J(\theta)$ , is defined as:

$J(\theta) = J'(\theta) + \lambda \sum_{i=1}^{3} \theta_i^2$

where, $J'(\theta)$ is the cross entropy loss as seen in lecture videos.

$J(\theta)$ penalizes large weights to avoid overfitting using the following settings:

Regularization strength $\lambda = 0.1$
Initial parameters: $\theta_0 = 0.5,\ \theta_1 = -0.5,\ \theta_2 = 0.3,\ \theta_3 = -0.2$
Learning rate: $\alpha = 0.01$

Compute the regularized cost function $J(\theta)$ , for a single protein interaction sample $x_{uv} = [2, 3, 1]$ with target $y_{uv} = 1$ .

Note: Use $\lambda/2m$ as the constant in regularization term of the cost function, where $m$ is the batch size.

Show answer

Correct answer: 0.6325 (accepted within ±0.0075)

Question 5 on its own page

Question 6

+3 marksOne or more correct options

The figure below shows the genetic code describing the translation of an RNA codon into one of the twenty different amino acids. Use the figure below to answer the given subquestions.

A protein “X” has only three amino acids – “Serine”, “Leucine” and “Valine” in the same order. Which of the following RNA strings translate into the protein “X”?

Select all that apply.

A
CUC AGUGU A
B
CUUUUGAGCGUUGUU
C
AGUCUCGU A
D
UC AUU AGUG
E
UCGUUGGUU

Show answer

Correct answers

C
AGUCUCGU A
D
UC AUU AGUG
E
UCGUUGGUU

Question 6 on its own page

Question 7

+3 marksNumerical answer

The figure below shows the genetic code describing the translation of an RNA codon into one of the twenty different amino acids. Use the figure below to answer the given subquestions.

What is the probability that a random RNA sequence of length 3 encodes for the “Arginine” amino acid? Assume that the different positions of the 3-mer RNA sequence are set to a nucleotide independently and uniformly at random.

Show answer

Correct answer: 0.09495 (accepted within ±0.00495)

Question 7 on its own page

Question 8

+3 marksNumerical answer

The figure below shows the genetic code describing the translation of an RNA codon into one of the twenty different amino acids. Use the figure below to answer the given subquestions.

Suppose protein X consists of 3 amino acids. What is the maximum number of possible mRNA sequences that can generate the protein X?

Show answer

Correct answer: 216

Question 8 on its own page

Question 9

+3 marksNumerical answer

Consider the following cell signaling network and answer the given subquestions with respect to the same. Please note that the weight we written next to each edge e is the probability of (information flow through) this edge, and that the probability (or score) of a path is calculated under the assumption that the information flow through different edges are independent of each other.

Show answer

Correct answer: 180

Question 9 on its own page

Question 10

+3 marksOne correct option

Consider the following cell signaling network and answer the given subquestions with respect to the same. Please note that the weight we written next to each edge e is the probability of (information flow through) this edge, and that the probability (or score) of a path is calculated under the assumption that the information flow through different edges are independent of each other.

A
YES
B
NO

Show answer

Correct answer

A
YES

Question 10 on its own page

Question 11

+3 marksNumerical answer

Consider the following cell signaling network and answer the given subquestions with respect to the same. Please note that the weight we written next to each edge e is the probability of (information flow through) this edge, and that the probability (or score) of a path is calculated under the assumption that the information flow through different edges are independent of each other.

In a random coloring of the path Ra, X1, Y1, Z1, G1 using 6 colors, what is the probability that this path is colorful? (Random coloring refers to coloring each node in the graph with one of the 6 colors uniformly and independently at random.)

Show answer

Correct answer: 0.09495 (accepted within ±0.00495)

Question 11 on its own page

Question 12

+3 marksOne or more correct options

Answer the given subquestions about the graphs given below regarding overlap and de Bruijn graphs. Recall that the Hamiltonian path approach is used in an overlap graph and the Eulerian path approach is used in the de Bruijn graph for the genome assembly problem.
(Hint: Be careful with the direction of the arrows.)

Which of the given graphs can be the overlap graph representing all k-mers of a string representing some linear (non-circular) genome?

Select all that apply.

A
Graph 1
B
Graph 2
C
Graph 3

Show answer

Correct answers

A
Graph 1
B
Graph 2

Question 12 on its own page

Question 13

+3 marksOne correct option

Answer the given subquestions about the graphs given below regarding overlap and de Bruijn graphs. Recall that the Hamiltonian path approach is used in an overlap graph and the Eulerian path approach is used in the de Bruijn graph for the genome assembly problem.
(Hint: Be careful with the direction of the arrows.)

Which of the given graphs can be the de Bruijn graph representing all k-mers of a string representing some linear (non-circular) genome?

A
Graph 1
B
Graph 2
C
Graph 3

Show answer

Correct answer

C
Graph 3

Question 13 on its own page

Question 14

+2 marksNumerical answer

Consider the following two global alignments for the two input DNA sequences: $v = GTTACTAG$ and $w = GGACTTACG$ and answer the given subquestions with respect to the same.

-	G	-	-	T	T	A	C	T	A	G
G	G	A	C	T	T	A	C	-	-	G

(a) Alignment 1

G	-	-	-	T	T	A	C	T	A	G
G	G	A	C	T	T	A	C	-	-	G

(b) Alignment 2

Also consider the following score matrix (S).

1st String \ 2nd String	A	C	G	T	-
A	1	-3	-5	-1	-3
C	-4	1	-3	-2	-3
G	-9	-7	1	-1	-3
T	-3	-5	-8	1	-4
-	-4	-2	-2	-1

Table 2: Score Matrix S

Show answer

Correct answer: 0

Question 14 on its own page

Question 15

+2 marksNumerical answer

Consider the following two global alignments for the two input DNA sequences: $v = GTTACTAG$ and $w = GGACTTACG$ and answer the given subquestions with respect to the same.

-	G	-	-	T	T	A	C	T	A	G
G	G	A	C	T	T	A	C	-	-	G

(a) Alignment 1

G	-	-	-	T	T	A	C	T	A	G
G	G	A	C	T	T	A	C	-	-	G

(b) Alignment 2

Also consider the following score matrix (S).

1st String \ 2nd String	A	C	G	T	-
A	1	-3	-5	-1	-3
C	-4	1	-3	-2	-3
G	-9	-7	1	-1	-3
T	-3	-5	-8	1	-4
-	-4	-2	-2	-1

Table 2: Score Matrix S

Suppose we compute the score using the score matrix (S). What is the difference in the alignment score for the two global alignments? Enter the value as a single integer.

Show answer

Correct answer: 0

Question 15 on its own page

Question 16

+4 marksWritten answer

Consider the following two global alignments for the two input DNA sequences: $v = GTTACTAG$ and $w = GGACTTACG$ and answer the given subquestions with respect to the same.

-	G	-	-	T	T	A	C	T	A	G
G	G	A	C	T	T	A	C	-	-	G

(a) Alignment 1

G	-	-	-	T	T	A	C	T	A	G
G	G	A	C	T	T	A	C	-	-	G

(b) Alignment 2

Also consider the following score matrix (S).

1st String \ 2nd String	A	C	G	T	-
A	1	-3	-5	-1	-3
C	-4	1	-3	-2	-3
G	-9	-7	1	-1	-3
T	-3	-5	-8	1	-4
-	-4	-2	-2	-1

Table 2: Score Matrix S

Suppose the score is calculated as follows:

$\mathit{score} = \#\mathit{matches} - 2 \times \#\mathit{mismatches} + \mathit{total\ gap\ penalty}$

For every gap of length $k$ , the gap penalty is calculated as $\sigma - (k-1)$ , where the gap opening penalty $\sigma$ is computed from the score matrix $S$ given in Table 2. The total gap penalty is the sum of the gap penalties for every gap.

What is the difference in the alignment score?

Enter the value as a single integer.

Show answer

Correct answer: 3 or -3

Question 16 on its own page