Algorithmic Thinking in Bioinformatics · End Term · May 2026 · AN

Consider the following graphical representation of a circular genome (also known as a "**genome** **graph**") and answer the given subquestions with respect to the same.

Which of the following circular genomes correspond to this genome graph?

Consider the following graphical representation of a circular genome (also known as a "**genome** **graph**") and answer the given subquestions with respect to the same.

Suppose this genome graph was constructed using the genome:

A reversal operation was performed on this genome, resulting in the genome graph shown below. Compare the original and resulting genome graphs and determine which collection of synteny blocks was reversed?

Given below is the spectral convolution for a theoretical spectrum of a cyclic peptide, and answer the given subquestions.

What is the number of amino acids in the peptide? Assume every amino acid in the peptide is unique. Enter your answer as a single integer.

Given below is the spectral convolution for a theoretical spectrum of a cyclic peptide, and answer the given subquestions.

Use the integer masses of different amino acids from the figure given below to determine which of the following might be the corresponding peptide.

There is a collection of

strings

, each of length

. Aurora chooses a

-mer randomly from each string and constructs the set of

motifs

. Following this, she performs the first iteration of the Randomized Motif Search algorithm and the first iteration of the Gibbs Sampling algorithm using

. The first columns of the profile matrices constructed during the first iteration of both algorithms are given below:

Identify each of these first columns belong to which algorithm.

Given below is an excerpt of the DP table constructed for global alignment of the strings TCGGAG and CGCGG. Note that the DP table stores both the alignment score and the back pointer at every cell. Which of the following correctly represents the contents of the shaded cell?

In a bioinformatics study, four tissue samples are profiled based on the expression levels (in arbitrary normalized units) of two marker genes, Gene X and Gene Y. The samples are:

where each coordinate represents (Gene X expression, Gene Y expression). Researchers want to cluster these samples into

groups using hard K-means clustering, in order to distinguish a "low-expression" phenotype from a "high-expression" phenotype. The initial centroids are taken as

and

. Distance metric: use the **Euclidean distance**

both for assigning samples to centroids and for any comparison of distances. Each centroid is recomputed as the arithmetic mean (coordinate-wise) of the samples currently assigned to it. Counting convention: one **iteration** consists of a full pass in which (i) every sample is assigned to its nearest centroid and (ii) the centroids are recomputed from those assignments. The algorithm terminates at the end of the first iteration in which the assignments are unchanged from the previous one; **include this final checking iteration in the count.** After how many iterations will the algorithm terminate, and what will be the final centroids?

Which of the strings has ``N$OTUONMNO'' as its Burrows-Wheeler transform?

The additive phylogeny algorithm is applied to a distance matrix

with

species including

, and

, and the phylogeny

is constructed. The total length of the path between

and

in

is

, and the total length of the path between

and

in

is

. What is the maximum possible value of

? Enter your answer as a single integer.

Construct the de Bruijn graph on the

-mer composition of GTCAACGTCG and calculate the number of nodes

and the number of edges

in the same.

In a bioinformatics study, the time

(in hours) taken for a bacterial cell to complete DNA replication is modeled as a random sample

from a distribution with density:

Here

represents the rate parameter governing the efficiency of the replication machinery. Find the maximum likelihood estimator (MLE) of

based on the observed replication times.

You are studying the signaling 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 to get activated and translocated to the nucleus, wherein the TF protein regulates a target gene." Based on the above data, answer the given subquestions.

Suppose the negative logarithm of the probability of transmission from receptor protein to a kinase protein is

, between any two kinase proteins is

and from kinase protein to a transcription factor is

, and from a transcription factor to a gene is

. What is the negative logarithm of the probability that the gene will receive the information? Enter your answer correct to two decimal points.

You are studying the signaling 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 to get activated and translocated to the nucleus, wherein the TF protein regulates a target gene." Based on the above data, answer the given subquestions.

Suppose you randomly color the signaling pathway using

colors. What is the probability that this pathway is a colorful pathway?

Which of the following statements about the EM algorithm are **TRUE**

A genomics lab has two DNA sequencing machines, each with a different base-calling accuracy. For each sequencing run, one machine is randomly selected and used to sequence a 5-base read from a sample; each base is recorded as either **C** (correctly matches the reference genome) or **E** (erroneous base call, mismatches the reference). Consider the table below, which contains sample data from six sequencing runs, and answer the given subquestions with respect to the same.

Here

and

denote the base-calling accuracy (probability of a correct call) of Machine 1 and Machine 2, respectively. What are the Maximum Likelihood Estimates (MLEs) for

and

based on the given data?

A genomics lab has two DNA sequencing machines, each with a different base-calling accuracy. For each sequencing run, one machine is randomly selected and used to sequence a 5-base read from a sample; each base is recorded as either **C** (correctly matches the reference genome) or **E** (erroneous base call, mismatches the reference). Consider the table below, which contains sample data from six sequencing runs, and answer the given subquestions with respect to the same.

For this part, restrict attention to the **first three runs only** (runs 1, 2 and 3), and assume that the machine identity

is **hidden**; the lab only has the raw base-call outcomes

, not which machine produced them. The two machines have unknown accuracies

and

. For each run, a machine is chosen at random with equal probability (

) and used to sequence 5 bases. Suppose the initial parameter guesses are:

Perform one iteration of the EM algorithm: **E-step**: Compute the posterior probabilities (responsibilities)

for each run

. **M-step**: Use these posterior weights to update

Use the updated parameters

and determine the posterior probability that **run 2** (

) was generated by Machine 1:

Round your answer correct to two decimal points.