Algorithmic Thinking in Bioinformatics Quiz 1: 13 July 2025 (May 2025 term)

Assume we are using a logistic regression model to estimate the probability of a protein pair $(u, v)$ to truly interact based on two features $X_{uv}^1$ and $X_{uv}^2$. Let $\beta_0$ be the intercept and $\beta_1$ and $\beta_2$ be the weights of the features $X_{uv}^1$ and $X_{uv}^2$ respectively. In the trained model, $\hat{\beta}_1 = 1.1$ and $\hat{\beta}_2 = 0.4$. For a protein pair with $X_{uv}^1 = 0.6$ and $X_{uv}^2 = 3$, this trained model predicted the probability of interaction to be 0.7427. What will this model predict for the probability of interaction of another protein pair with $X_{uv}^1 = 1$ and $X_{uv}^2 = -1$?

You are given a multiset of k-mers A based on a sequencing experiment and you want to reconstruct a genome sequence S whose k-mer composition is consistent with A. Let Go and Gd respectively denote the overlap and de Bruijn graph constructed using A. Which of the following statements is/are true?

You fly to an alien world and are surprised to find life that follows the same central dogma principle. The difference is that the alien life has 5 different nucleotides. Answer the given subquestions with respect to the same.

Suppose a gene g (of length k) does not have any exons. How many different types of protein can be produced from g?

You fly to an alien world and are surprised to find life that follows the same central dogma principle. The difference is that the alien life has 5 different nucleotides. Answer the given subquestions with respect to the same.

Suppose this alien life has 600 distinct amino acids that make up protein sequences. What is your best guess on the length of each codon in this alien species?

You fly to an alien world and are surprised to find life that follows the same central dogma principle. The difference is that the alien life has 5 different nucleotides. Answer the given subquestions with respect to the same.

Suppose this planet cannot block out harmful radiation from space, making this alien life prone to acquiring a very high number of DNA mutations. Then, what is your best guess for the minimum length of each codon?

Consider the following k-mers found from the genome sequence of some organism.
ATG,CAT, TAG,GAT,TTA,AAT, ATA, AGA, ATC, TGC,GCA
Answer the given subquestions with respect to the corresponding overlap graph.

How many nodes are there in the graph?

Consider the following k-mers found from the genome sequence of some organism.
ATG,CAT, TAG,GAT,TTA,AAT, ATA, AGA, ATC, TGC,GCA
Answer the given subquestions with respect to the corresponding overlap graph.

How many edges are there in the graph?

Consider the alignment graph based DP table below to find the best global alignment between two strings (represented along the rows and the columns). The DP table has (n + 1) x (m + 1) entries i.e., DP [0, 0] to DP [n,m], where n is length of first string and m is length of second string. DP [i, j] is the score of best global alignment between the length-i prefix of the first string and length-j prefix of the second string.
Fill the DP table given below and answer the given subquestions accordingly. Scoring is done as follows:

• For each match between two symbols: +1 point
• For each mismatch between two symbols: 0 point
• For each removal of symbol from any one sequence: 0 point

How many entries in the grid consists of the number 2?

Consider the alignment graph based DP table below to find the best global alignment between two strings (represented along the rows and the columns). The DP table has (n + 1) x (m + 1) entries i.e., DP [0, 0] to DP [n,m], where n is length of first string and m is length of second string. DP [i, j] is the score of best global alignment between the length-i prefix of the first string and length-j prefix of the second string.
Fill the DP table given below and answer the given subquestions accordingly. Scoring is done as follows:

• For each match between two symbols: +1 point
• For each mismatch between two symbols: 0 point
• For each removal of symbol from any one sequence: 0 point

In the global alignment, what happens to the last character of the first string? Assume the first string (top string in the alignment) is along the rows i.e., GACAT.

Given below in Figure 2 is the BLOSUM50 scoring matrix for amino acids. Use the same as the scoring matrix and answer the given subquestions.

Figure 2: BLOSUM50 scoring matrix for amino acids

Global alignment among which of the following pairs of the peptides results in the maximum alignment score? Here Xⁿ represents the string with the amino acid X repeated n times.

Given below in Figure 2 is the BLOSUM50 scoring matrix for amino acids. Use the same as the scoring matrix and answer the given subquestions.

Figure 2: BLOSUM50 scoring matrix for amino acids

The peptide STW is aligned with the peptide generated from the RNA string
AGUAUGCCUCAAACUUGG. If gap opening penalty is -20 and gap extension penalty is -2, then use the genetic code given below in Figure 3 to compute the optimal global alignment score between the peptides.

Given below in Figure 2 is the BLOSUM50 scoring matrix for amino acids. Use the same as the scoring matrix and answer the given subquestions.

Figure 2: BLOSUM50 scoring matrix for amino acids

Calculate the local alignment score between the same two peptides as in the previous question.