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.