Algorithmic Thinking in Bioinformatics End Term: 31 August 2025 (May 2025 term)

We run the RANDOMIZEDMOTIFSEARCH algorithm on the following set of DNA strings with $k = 4$.

$\mathit{Dna} = \begin{matrix} \text{TACCT} \\ \text{ATGTC} \\ \text{CGGCG} \\ \text{ACTAA} \end{matrix}$

During some iteration of the algorithm, the profile matrix on the chosen 4-mers are given below.

$\text{PROFILE}(\mathit{Motifs}) = \begin{matrix} \text{A:} & 0.4 & 0.2 & 0.2 & 0.2 \\ \text{C:} & 0.2 & 0.4 & 0.2 & 0.2 \\ \text{G:} & 0.2 & 0.2 & 0.4 & 0.2 \\ \text{T:} & 0.2 & 0.2 & 0.2 & 0.4 \end{matrix}$

Which of the following can be the set of motifs that are chosen for the next iteration?

The theoretical spectrum of the peptide "GAS" is

0 57 71 87 128 144 158 215

Given below in Figure 1 is the partially filled table to compute the spectral convolution. Complete the table and determine which among the following masses have the minimum multiplicity.

Figure 1: Partially filled Spectral Convolution Table

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 shown below has $n \times m$ 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 following questions 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 3? Enter the answer as a single integer.

Imagine an episode of Tom and Jerry, where Jerry uses the cat ('Butch') and the dog ('Spike') and switches their personalities in the lab. Tom was shocked and could not believe that Butch is behaving like a dog. Imagine you are a friend of Tom, and you have to explain him that it is possible to switch personalities by mutating their genes. You find the synteny blocks in the chromosomes of Butch, Tom and Spike as given below.

\begin{aligned} \mathit{Butch} &= {+5}\ {+3}\ {-1}\ {+4}\ {+2} \\ \mathit{Tom} &= {-3}\ {-2}\ {-1}\ {+5}\ {+4} \\ \mathit{Spike} &= {+1}\ {+2}\ {+3}\ {+4}\ {+5} \end{aligned} \tag{1}

Suppose Jerry's machine first runs an algorithm to determine the breakpoint graph and the sequence of transformations and then applies it on the species. Assume the algorithm only uses the minimum number of transformations needed to convert a species into another. Use the breakpoint graph to determine the total number of transformations Jerry needs to mutate Butch into Spike. Enter the answer as a single integer.

The de Bruijn graph of some linear (i.e., non-circular) genome Dna comprises of 2 nodes (N1 and N2) and 3 edges – two of these edges are directed from N1 to N2 and the remaining edge is directed from N2 to N1. To reconstruct Dna, you are allowed to start only from the node N1. Answer the given subquestions with respect to the same.

If the k-mers represented by both N1 and N2 are fixed, then how many unique genome sequences can be constructed from this de Bruijn graph? Enter the answer as a single integer.

The de Bruijn graph of some linear (i.e., non-circular) genome Dna comprises of 2 nodes (N1 and N2) and 3 edges – two of these edges are directed from N1 to N2 and the remaining edge is directed from N2 to N1. To reconstruct Dna, you are allowed to start only from the node N1. Answer the given subquestions with respect to the same.

Suppose you don’t know the 2-mers representing N1 and N2. Then which of the following is/are possible choices for Dna?

Based on the above data, answer the given subquestions.

What is the value of the probability density function at x = 45 under this model? Round the answer to three decimal digits.

Based on the above data, answer the given subquestions.

What is the probability that this data point was generated by the first cluster? Round the answer to three decimal digits.

You are asked to construct a phylogeny on the distance matrix D using the Additive Phylogeny algorithm. At the end of the 5^(th) iteration, you notice the D^(bald) matrix consumes 81 units of memory space. Assume every entry in a matrix requires 1 unit of space. Also assume the count of the iterations starts from 1. Answer the given subquestions with respect to the same.

How many units of space is required to the corresponding D^(trimmed) matrix? Enter the answer as a single integer.

You are asked to construct a phylogeny on the distance matrix D using the Additive Phylogeny algorithm. At the end of the 5^(th) iteration, you notice the D^(bald) matrix consumes 81 units of memory space. Assume every entry in a matrix requires 1 unit of space. Also assume the count of the iterations starts from 1. Answer the given subquestions with respect to the same.

How many leaves will be there in the final phylogeny constructed at the end of the algorithm? Enter the answer as a single integer.

You are asked to construct a phylogeny on the distance matrix D using the Additive Phylogeny algorithm. At the end of the 5^(th) iteration, you notice the D^(bald) matrix consumes 81 units of memory space. Assume every entry in a matrix requires 1 unit of space. Also assume the count of the iterations starts from 1. Answer the given subquestions with respect to the same.

Given below in Figure 2 is the pseudocode for the UPGMA algorithm.

Figure 2: UPGMA Algorithm

Read the pseudocode carefully and calculate the number of iterations required by the UPGMA algorithm to construct the Ultrametric tree on D? Enter the answer as a single integer.

Consider the PWM of a transcription factor (TF) as given in the below table.

Table 1: PWM of a transcription factor (TF)

Based on the above data, answer the given subquestions.

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

Consider the PWM of a transcription factor (TF) as given in the below table.

Table 1: PWM of a transcription factor (TF)

Based on the above data, answer the given subquestions.

Which of the following substrings is most likely to be bound by the TF?

There are two coins from which one is randomly chosen and tossed 5 times, and the sequence of heads or tails is recorded. Consider the table below, which contains sample data from the experiment described above.

Based on the above data, answer the given subquestions.

There are two coins from which one is randomly chosen and tossed 5 times, and the sequence of heads or tails is recorded. Consider the table below, which contains sample data from the experiment described above.

Based on the above data, answer the given subquestions.

(BONUS QUESTION)

Now assume that the coin identity $Z$ is hidden from the given table, but the outcomes $X$ are observed. Two coins have unknown head probabilities $\theta_1$ and $\theta_2$. One of the coins is chosen at random with equal probability ($P(Z = 1) = P(Z = 2) = 0.5$), and then tossed 5 times.

Suppose the initial parameter guesses are:

$\theta_1^{(0)} = 0.4, \quad \theta_2^{(0)} = 0.8.$

Perform one iteration of the EM algorithm:

E-step: Compute the posterior probabilities

$r_{i1} = P(Z_i = 1 \mid X_i, \theta^{(0)}), \quad r_{i2} = 1 - r_{i1}$

for each trial $i = 1, \ldots, 6$.

M-step: Use these posterior weights to update

$\theta_1^{(1)} = \frac{\sum_{i=1}^{6} r_{i1} \cdot (\text{heads in trial } i)}{\sum_{i=1}^{6} r_{i1} \cdot 5},$

$\theta_2^{(1)} = \frac{\sum_{i=1}^{6} r_{i2} \cdot (\text{heads in trial } i)}{\sum_{i=1}^{6} r_{i2} \cdot 5}.$

Using the updated parameters $\theta_1^{(1)}, \theta_2^{(1)}$, compute the posterior probability that trial 5 ($HTHHH$) was generated by coin 1:

$P(Z_5 = 1 \mid X_5, \theta_1^{(1)}, \theta_2^{(1)}).$