Question 1

1████████
2randomly select k-mers Motifs = (Motif_1, ..., Motif_t) in each string from Dna
3BestMotifs ← Motifs
4for j ← 1 to N
5  i ← RANDOM(t)
6  Profile ← profile matrix formed from all strings in Motifs except for Motif_i
7  Motif_i ← Profile-randomly generated k-mer in the i-th sequence
8  if SCORE(Motifs) < SCORE(BestMotifs)
9    BestMotifs ← Motifs
10return BestMotifs

1████████
2BestMotifs ← motif matrix formed by first k-mers in each string from Dna
3for each k-mer Motif in the first string from Dna
4  Motif_1 ← Motif
5  for i = 2 to t
6    form Profile from motifs Motif_1, ..., Motif_{i-1}
7    Motif_i ← Profile-most probable k-mer in the i-th string in Dna
8  Motifs ← (Motif_1, ..., Motif_t)
9  if SCORE(Motifs) < SCORE(BestMotifs)
10    BestMotifs ← Motifs
11return BestMotifs

1████████
2randomly select k-mers Motifs = (Motif_1, ..., Motif_t) in each string from Dna
3BestMotifs ← Motifs
4while forever
5  Profile ← PROFILE(Motifs)
6  Motifs ← MOTIFS(Profile, Dna)
7  if SCORE(Motifs) < SCORE(BestMotifs)
8    BestMotifs ← Motifs
9  else
10    return BestMotifs

Given below are three algorithms for the motif finding problem. Identify which figure belongs to which algorithm. ████████ randomly select k-mers Motifs = (Motif_1, ..., Motif_t) in each string from Dna BestMotifs ← Motifs for j ← 1 to N i ← RANDOM(t) Profile ← profile matrix formed from all strings in Motifs except for Motif_i Motif_i ← Profile-randomly generated k-mer in the i-th sequence if SCORE(Motifs) < SCORE(BestMotifs) BestMotifs ← Motifs return BestMotifs (a) Figure I ████████ BestMotifs ← motif matrix formed by first k-mers in each string from Dna for each k-mer Motif in the first string from Dna Motif_1 ← Motif for i = 2 to t form Profile from motifs Motif_1, ..., Motif_{i-1} Motif_i ← Profile-most probable k-mer in the i-th string in Dna Motifs ← (Motif_1, ..., Motif_t) if SCORE(Motifs) < SCORE(BestMotifs) BestMotifs ← Motifs return BestMotifs (b) Figure II ████████ randomly select k-mers Motifs = (Motif_1, ..., Motif_t) in each string from Dna BestMotifs ← Motifs while forever Profile ← PROFILE(Motifs) Motifs ← MOTIFS(Profile, Dna) if SCORE(Motifs) < SCORE(BestMotifs) BestMotifs ← Motifs else return BestMotifs (c) Figure III A dataset is clustered into two groups using soft K-means. The distance of a data point from the two cluster centroids is $d_1 = 7.0$ and $d_2 = 2.0$, respectively. Using the soft K-means formula with $\beta = 0.3$, compute the probabilities of the data point belonging to each cluster. The probability formula is: $$P(C_k \mid x) = \frac{e^{-\beta d_k}}{\sum_{j=1}^{K} e^{-\beta d_j}}$$ What are the probabilities $P(C_1)$ and $P(C_2)$? In a Gaussian Mixture Model (GMM) with two components, the parameters are as follows: - Component 1: Mean $(\mu_1) = 2$, Variance $(\sigma_1^2) = 1$, Mixture Proportion $(\pi_1) = 0.6$ - Component 2: Mean $(\mu_2) = 5$, Variance $(\sigma_2^2) = 2$, Mixture Proportion $(\pi_2) = 0.4$ Given a data point $x = 3$, calculate the responsibilities (posterior probabilities) for each component. Hint: $$\mathcal{N}(x \mid \mu, \sigma^2) = \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)$$