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

Shown below is the motif detector matrix of a Transition Factor(TF) learnt by DeepBind.

Suppose this motif is scanned by DeepBind along the given sequence CAGTTCTACGCT. What is the dimension of the one hot encoded sequence after padding?

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

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

0 114 126 128 129 137 242 251 266 372 379 380 394 508

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?

Consider a system of 5 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$.

If we need 2 Bytes 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 6, 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 the motif finding problem with an assumption of motif of length 6?

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. What is the minimum number of colors required to determine the most probable pathway?

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 2. 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} &= {+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. 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.

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.

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.