Algorithmic Thinking in Bioinformatics End Term: 13 April 2025 (January 2025 term)

Your lab has bought a new mass spectrometer and you are asked to test the accuracy of the same. You use the machine to generate the spectrum for the peptide $\mathit{Peptide} = \mathit{WIL}$. The spectrum generated is given below:

0 113 186 226 299 299 412 415

Use Figure 1 given below to calculate the percentage of error of the machine.

Figure 1: Masses of different amino acids

(Error is calculated by dividing the total number of missing and false masses, by the length of the theoretical spectrum.)

Round up the answer to 2 decimal places.

An evil warlord wants to mutate a human chromosome into the DNA sequence of a dangerous virus and implant it in cyborgs to create his robotic army. The synteny blocks of the two species are given below:

$\begin{aligned} \mathit{Human\ DNA} &: -5 -1 -2 -4 +3 \\ \mathit{Virus} &: -5 +4 +1 -2 -3 \end{aligned}$

The most sophisticated machines available require 1 hour to apply a single 2-break operation. Use breakpoint graphs to determine the minimum number of hours needed by the evil warlord to complete the transformation.

In a soft K-means clustering process, a dataset is clustered into two groups. A data point has distances $d_1 = 3$ and $d_2 = 6$ from the two cluster centroids. Using the soft K-means formula with $\beta = 1$, compute the probabilities of the data point belonging to each cluster.

After assigning probabilities, update the centroid $\mu_1$ given that the current centroid is $\mu_1 = 4$ and this data point's value is $x = 5$. Assume no other points are assigned to cluster 1. Use the centroid update formula:

$\mu_k^{\text{new}} = \frac{\sum_i P(C_k \mid x_i) x_i}{\sum_i P(C_k \mid x_i)}$

where $P(C_k \mid x)$ is computed using the softmax-like probability formula:

$P(C_k \mid x) = \frac{e^{-\beta d_k}}{\sum_{j=1}^{K} e^{-\beta d_j}}$

Recall the color coding algorithm to compute a $k$-length path (connecting the regulators and receptors) with maximum weight. We had the following optimal substructure:

$W[v, X] = \max_{u \mid c(u) \in X \setminus \{c(v)\}} W[u, X \setminus \{c(v)\}] + w(u, v), \qquad 1 < |X| \le k$

Consider a set of proteins $T = \{T_1, \ldots, T_m\}$. You are asked to compute the path with maximum weight such that there are at least $x$ and at most $y$ proteins from $T$. To accommodate the same the DP matrix is modified as follows:

Instead of a 2-D matrix, we use a 3-D DP matrix $W$ such that $W[v, X, p]$ stores the maximum weight of a path of length $|X|$ ending at $v$ containing a vertex of each color in $X$ and exactly $p$ proteins from $T$. Which among the following is the correct optimal substructure for the algorithm?

The number of occurrences of the four nucleotides in the genome sequence of some virus is given in Table 1. The suffix array of the genome sequence

Table 1: Frequency of the Nucleotides

is: $[10, 3, 4, 9, 8, 6, 1, 2, 7, 5, 0]$. Assume $ is present at the end of the original genome sequence for all computations. Which of the following represents the correct genome sequence?

Recall that in order to construct an overlap graph, we need to determine which k-mers are overlapping. But if the k-mers are error-prone, then it would be difficult to determine the same. An overlap alignment is used in such scenarios.

Overlap alignment of sequence $v = v_1 \ldots v_n$ to sequence $w = w_1 \ldots w_m$ is a type of sequence alignment that maximizes the global alignment score between a suffix of $v$ and a prefix of $w$.

Recall that the two sequences $v$ and $w$ are of lengths $n$ and $m$ respectively. Consider the alignment graph for the global alignment problem ($v$ is along the rows and $w$ is along the columns). What zero-weight extra edge/s (free taxi rides) should be added to the same so as to compute the overlap alignment between the two sequences?

The overlap graph of some linear (i.e., non-circular) genome Dna has 138 nodes. Answer the given subquestions about the de Bruijn graph constructed on the same set of k-mers. Remember that Dna can be reconstructed by using both the graphs when answering these questions.

What is the number of edges in the de Bruijn graph? Enter the value as a single integer.

The overlap graph of some linear (i.e., non-circular) genome Dna has 138 nodes. Answer the given subquestions about the de Bruijn graph constructed on the same set of k-mers. Remember that Dna can be reconstructed by using both the graphs when answering these questions.

What is the maximum number of nodes possible in the de Bruijn graph? Enter the value as a single integer.

Answer the given subquestions.

What is the Burrows Wheeler Transform of the string ‘AACAAG$’?

Answer the given subquestions.

Is the transformed string more compressible using run-length encoding than the original string ?

Scientists of an alien world have used the UPGMA algorithm to construct the following Ultrametric tree (Figure 2) on six different species. The green nodes in the tree represent current-day species, while the red nodes represent their extinct ancestors. The numbers next to the red nodes represent the age of the node in million years.

Based on the above data, answer the given subquestions.

During the construction of the phylogeny using the UPGMA algorithm, what was the average distance between the species represented by the nodes “N4” and “E”? Enter the value as a single integer.

Scientists of an alien world have used the UPGMA algorithm to construct the following Ultrametric tree (Figure 2) on six different species. The green nodes in the tree represent current-day species, while the red nodes represent their extinct ancestors. The numbers next to the red nodes represent the age of the node in million years.

Based on the above data, answer the given subquestions.

How many million years ago did the species marked at the “N1” node diverge to form the descendants? Enter the value as a single integer.

Based on the above data, answer the given subquestions.

Calculate the entropy for the fifth column? Round up the answer to 3 decimal places.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

The pooling layer in the DeepBIND model reduces the dimensionality of its input.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

How many 6-mers in the sequence GCTAGTCCATTGGA have a nonzero probability of binding to the TF according to the PWM in the given table? Enter the answer as an integer.

Based on the above data, answer the given subquestions.

Which of the following substrings is least likely to be bound by the TF? Enter the answer as an integer.