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}}$