Algorithmic Thinking in Bioinformatics · End Term · May 2025 · FN

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.

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.

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.

Based on the above data, answer the given subquestions.

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

Based on the above data, answer the given subquestions.