Algorithmic Thinking in Bioinformatics End Term: 1 September 2024, Set QDB3 (May 2024 term)

Consider a system of 6 genes that regulate each other as follows:

• $G_1$ regulates $G_2$, $G_3$ and $G_4$.
• $G_5$ is regulated by $G_3$ and $G_2$.
• $G_2$ regulates $G_3$.
• $G_3$ regulates $G_4$.
• $G_6$ is regulated by $G_4$.

If we need 1 Byte to store a boolean value (i.e., 0 or 1), then how many Bytes are required to store the adjacency matrix of the underlying gene regulatory network?

In an alien world, mutations occur in every 10 million years only. A ultrametric tree is constructed on some of these alien species. If the height of the tree (defined as the maximum number of edges from the root to a leaf node in the tree) is 5, then calculate the age of the root node (in million years) of this ultrametric tree. (Hint: The distance between two nodes in consecutive levels is given in the question.)

What is the number of free parameters that are learned in the EM setup of motif finding problem with an assumption of motif of length 5?

A mass spectrometer generates the following $\mathit{Spectrum}$ for the peptide "$\mathit{Peptide} =$ CILA".

0 71 103 112 113 174 184 216 226 287 287 297 330 400

The figure given below depicts the mass of all amino acids.

The criteria to trim peptides in the leaderboard based cyclopeptide sequencing algorithm is modified as follows:

"Suppose the algorithm is considering the peptide $P$. Let the number of elements in the theoretical spectrum of $P$ be $n$. If $\text{SCORE}(P, \mathit{Spectrum}) < 0.75 * n$, then the peptide is trimmed".

Which of the following peptides will be trimmed?

Which of the following statements about the EM algorithm is/are FALSE?

You are studying the signalling pathway system of an alien world. Existing literature shows that information in the alien world is transmitted in the following procedure.
“A receptor protein in the cell membrane transmits information to a series of three kinase proteins that are sequentially activated inside the cell. The final activated kinase causes a transcription factor (TF) to get activated and translocated to the nucleus, wherein the TF protein regulates a target gene.” As part of your research, you construct the underlying signalling network, and want to find the most probable pathway along which a specific gene g will receive the information from a receptor on the cell membrane. Will it suffice to use 10 colors to determine the most probable pathway?

Consider the below matrix that represents a one-hot encoded representation of an input sequence used by DeepBind. Decode the sequence and find the length of the motif detector $k$.

$\begin{bmatrix} 0.25 & 0.25 & 0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 & 0.25 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0.25 & 0.25 & 0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 & 0.25 \end{bmatrix}$

Consider dynamic programming to do a manual alignment of the following sequences: AGTGT and TATGT. Fill up the score matrix (or grid) below, and calculate the number of entries in the matrix/grid with the value 3. The $(i, j)^{\text{th}}$ entry in the grid corresponds to the score of the best-scoring alignment between the $i$-length prefix of first string and $j$-length prefix of second string. 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

Remember the episode of Tom and Jerry, where Jerry picks an orange cat and a dog ('Spike') and switches their personalities in the lab. Tom was shocked and could not believe that the orange cat was actually 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 the orange cat (henceforth denoted by $\mathit{Cat}$), Tom and Spike as given below.

\begin{aligned} \mathit{Cat} &= {+4}\ {+5}\ {-1}\ {-3}\ {-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. Transforming a genome into another using $n$ operations (2-break operations: reversal, translocation, fusion or fission) takes $n$ minutes, as each 2-break operation takes 1 minute to apply. 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 minutes Jerry needed to mutate "Cat" into Spike.

The de Bruijn graph of some linear (i.e., non-circular) genome Dna comprises of 2 nodes (N1 and N2) and 6 edges – three of these edges are directed from N1 to N2 and the remaining three edges are 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?

The de Bruijn graph of some linear (i.e., non-circular) genome Dna comprises of 2 nodes (N1 and N2) and 6 edges – three of these edges are directed from N1 to N2 and the remaining three edges are 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.

Which of the following statements is/are correct?
I. If we are allowed to start from N1 node only and the k-mers represented by both N1 and N2 are fixed, then there is exactly one genome sequence that can be reconstructed from this de Bruijn graph.
II. If we are allowed to start from either node and the k-mers represented by both N1 and N2 are fixed, then there are exactly two genome sequences that can be reconstructed from this de Bruijn graph.

Based on the above data, answer the given subquestions.

Which of the following options is the original message?

Based on the above data, answer the given subquestions.

Choose the option representing the original suffix array of the message.