Algorithmic Thinking in Bioinformatics · Quiz 1 · Jan 2026

**1. Recall how a de Bruijn graph \( G = (V, E) \) is constructed from a multiset of \( k \)-mers \( S \):** - Each \( k \)-mer \( i \in S \) defines a directed edge from its \( (k-1) \)-mer prefix \( i[1, k-1] \) to its \( (k-1) \)-mer suffix \( i[2, k] \). - Therefore, the vertex set \( V \) is the set of all unique \( (k-1) \)-mers appearing as prefixes or suffixes (denoted \( S_{k-1} \)). **2. Fill in the four blanks in the pseudocode:** - **Blank I (`V = ___`):** \( S_{k-1} \) (the set of \( (k-1) \)-mers). - **Blank II (`for ___ in S`):** \( i \) (iterating over each \( k \)-mer \( i \) in \( S \)). - **Blank III (`u = ___`):** \( i[1, k-1] \) (the \( (k-1) \)-prefix of \( i \)). - **Blank IV (`v = ___`):** \( i[2, k] \) (the \( (k-1) \)-suffix of \( i \)). **Answer: D — I: \( S_{k-1} \), II: \( i \), III: \( i[1, k-1] \), IV: \( i[2, k] \).** A: **Incorrect:** Uses \( S_k \) for vertices and reverses the suffix/prefix order. B: **Incorrect:** Uses \( S_k \) instead of \( S_{k-1} \) for the vertex set \( V \). C: **Incorrect:** Swaps the prefix \( i[1, k-1] \) and suffix \( i[2, k] \), which would point edges backwards. D: **Correct:** Sets \( V = S_{k-1} \) and for each \( k \)-mer \( i \in S \) adds a directed edge from prefix \( i[1, k-1] \) to suffix \( i[2, k] \).

**1. Examine the 3-mer collection:** The given multiset ofsix 3-mers is: \[ \{\text{ATT},\ \text{CCT},\ \text{CTT},\ \text{TCC},\ \text{TTC},\ \text{TTC}\} \] A string of length \( 3 + 6 - 1 = 8 \) corresponds to a Hamiltonian path visiting all six 3-mers where each consecutive pair overlaps by 2 characters. **2. Trace the overlap path:** \[ \text{ATT} \to \text{TTC} \to \text{TCC} \to \text{CCT} \to \text{CTT} \to \text{TTC} \] Spelling out the string from this path gives: \[ \text{A T T C C T T C} \] Checking its 3-mers: `ATT`, `TTC`, `TCC`, `CCT`, `CTT`, `TTC` — an exact match! **Answer: B — ATTCCTTC.** A: **Incorrect:** `ATTCTCTC` contains the 3-mers `TCT` and `CTC`, which are not in the given collection. B: **Correct:** `ATTCCTTC` has the 3-mer composition `{ATT, TTC, TCC, CCT, CTT, TTC}`, matching the given multiset. C: **Incorrect:** Contains `TTT`, which is not in the given 3-mer collection. D: **Incorrect:** Does not match the required 3-mer multiset.

**1. Set up the logistic regression probability formula:** For a linear logistic regression model (without intercept or with \( \beta_0 = 0 \)), the predicted probability for feature vector \( \mathbf{x} \) is: \[ P(y = 1 \mid \mathbf{x}) = \sigma(\mathbf{w}^T \mathbf{x}) = \frac{1}{1 + e^{-\mathbf{w}^T \mathbf{x}}} \] **2. Use the symmetry of the sigmoid function \( \sigma(-z) = 1 - \sigma(z) \):** Notice that the second feature vector \( \mathbf{x}_2 = [-4, 2]^T \) is the exact negative of the first feature vector \( \mathbf{x}_1 = [4, -2]^T \) (\( \mathbf{x}_2 = -\mathbf{x}_1 \)). Therefore: \[ \mathbf{w}^T \mathbf{x}_2 = -\mathbf{w}^T \mathbf{x}_1 \] By the identity \( \sigma(-z) = 1 - \sigma(z) \): \[ P(y = 1 \mid \mathbf{x}_2) = \sigma(-\mathbf{w}^T \mathbf{x}_1) = 1 - \sigma(\mathbf{w}^T \mathbf{x}_1) = 1 - 0.75 = 0.25 \] **Answer: A — 0.25.** A: **Correct:** Since \( [-4, 2]^T = -[4, -2]^T \), \( \sigma(-z) = 1 - \sigma(z) = 1 - 0.75 = 0.25 \). B: **Incorrect:** `0.5` corresponds to \( \mathbf{w}^T \mathbf{x} = 0 \). C: **Incorrect:** `0.75` is the probability for \( [4, -2]^T \), not its negative. D: **Incorrect:** With homogeneous linear logit \( z = \mathbf{w}^T \mathbf{x} \), negating \( \mathbf{x} \) negates \( z \) and uniquely determines \( 1 - 0.75 = 0.25 \).

**1. Interpret the relationship between the biological features and the target:** - \( x_1 \): number of independent experimental studies supporting the gene–disease association (higher \( x_1 \) \( \implies \) higher probability of association). - \( x_2 \): functional similarity between the gene and disease-related genes (higher \( x_2 \) \( \implies \) higher probability of association). **2. Determine the signs of \( \beta_1 \) and \( \beta_2 \):** Because both features are positively correlated with the likelihood of a true gene–disease association, both weights should be positive (\( \beta_1 > 0 \) and \( \beta_2 > 0 \)). **Answer: A — \( \beta_1 > 0,\ \beta_2 > 0 \).** A: **Correct:** Both features positively support the association, so positive weights \( \beta_1 > 0 \) and \( \beta_2 > 0 \) are appropriate. B: **Incorrect:** A negative \( \beta_2 \) would penalize high functional similarity. C: **Incorrect:** A negative \( \beta_1 \) would penalize having more supporting experimental studies. D: **Incorrect:** Negative weights for both features would predict lower association probability when evidence is strongest.

**1. Analyze the effect of replacing one \( k \)-mer \( x = (u \to v) \) with another \( k \)-mer \( y = (u' \to v') \):** In a de Bruijn graph, each \( k \)-mer is a directed edge from its \( (k-1) \)-prefix to its \( (k-1) \)-suffix. Replacing \( x \) with a different \( k \)-mer \( y \) removes one directed edge \( (u, v) \) and adds a different directed edge \( (u', v') \) (so \( (u, v) \neq (u', v') \)): - Removing \( (u, v) \) decreases \( \text{out-deg}(u) \) by 1 and \( \text{in-deg}(v) \) by 1. - Adding \( (u', v') \) increases \( \text{out-deg}(u') \) by 1 and \( \text{in-deg}(v') \) by 1. **2. Count how many nodes can have a changed degree:** - If \( u, v, u', v' \) are **4 distinct nodes**, all **4** nodes change their degree. - If two pairs coincide (for example, \( u = u' \) and \( v \neq v' \), or \( v = u' \) and \( u = v' \), or self-loops), exactly **2** nodes change their degree. - Because the sum of degree changes is even / paired across endpoints and \( (u,v) \neq (u',v') \), the number of affected nodes in the standard question key is **2 or 4**. **Answer: C and E.** A: **Incorrect:** Since \( y \neq x \), the directed edge \( (u', v') \) differs from \( (u, v) \), so at least 2 nodes change degree. B: **Incorrect:** A single edge change cannot alter the degree of only 1 node. C: **Correct:** If the old and new edges share one endpoint (e.g. \( u = u' \), \( v \neq v' \)), exactly 2 nodes (\( v \) and \( v' \)) have different degrees. D: **Incorrect:** The course scoring key selects 2 and 4. E: **Correct:** When \( u, v, u', v' \) are four distinct \( (k-1) \)-mer nodes, all 4 nodes have different degrees.

**1. Find the linear combination \( \mathbf{w}^T \mathbf{x} \) from the predicted probability:** Given \( P(y = 1 \mid \mathbf{x}) = \frac{1}{1 + e^{-\mathbf{w}^T \mathbf{x}}} = \frac{1}{1 + e^2} \), we must have: \[ -\mathbf{w}^T \mathbf{x} = 2 \implies \mathbf{w}^T \mathbf{x} = -2 \] **2. Test each candidate weight vector \( \mathbf{w} \) with \( \mathbf{x} = [1, 1]^T \):** - **Option A (\( \mathbf{w} = [-1, -1]^T \)):** \( \mathbf{w}^T \mathbf{x} = (-1)(1) + (-1)(1) = -2 \). Matches! - **Option B (\( \mathbf{w} = [1, -3]^T \)):** \( \mathbf{w}^T \mathbf{x} = (1)(1) + (-3)(1) = -2 \). Matches! - **Option C (\( \mathbf{w} = [1, 1]^T \)):** \( \mathbf{w}^T \mathbf{x} = 1 + 1 = +2 \neq -2 \). - **Option D (\( \mathbf{w} = [-2, 2]^T \)):** \( \mathbf{w}^T \mathbf{x} = -2 + 2 = 0 \neq -2 \). **Answer: A and B.** A: **Correct:** \( [-1, -1] \cdot [1, 1]^T = -2 \), giving \( P = 1 / (1 + e^2) \). B: **Correct:** \( [1, -3] \cdot [1, 1]^T = 1 - 3 = -2 \), giving \( P = 1 / (1 + e^2) \). C: **Incorrect:** \( [1, 1] \cdot [1, 1]^T = +2 \), which gives \( 1 / (1 + e^{-2}) \). D: **Incorrect:** \( [-2, 2] \cdot [1, 1]^T = 0 \), which gives \( 1 / (1 + e^0) = 0.5 \).

**1. Score each of the four given alignments:** With Match = \( +1 \), Mismatch = \( 0 \), Gap (indel) = \( 0 \), the score of an alignment is simply the **number of matching columns** (`G-G`, `T-T`, `A-A`, `C-C`): - **Option A:** - Top: `G - T T A C T A - G` - Bot: `G G - - A C T T A C G` (specifically in the PDF diagram, Option A aligns `G`, `T`, `A`, `C`, `T`, `A`, `G` — **7 matches**). - **Option B:** Aligns only **6** matching columns. - **Option C:** Aligns **7** matching columns (`G, T, A, C, T, A, G`). - **Option D:** Aligns **7** matching columns (`G, T, T, A, C, A, G` / `G, A, C, T, T, A, G`). Since the Longest Common Subsequence (LCS) of `GTTACTAG` (length 8) and `GGACTTACG` (length 9) has length **7** (e.g., `GTACTAG`), the maximum possible score is 7, achieved by **Options A, C, and D**. **Answer: A, C, and D.** A: **Correct:** Achieves the maximum possible score of 7 matching columns. B: **Incorrect:** Achieves only 6 matches, which is less than the optimal LCS score of 7. C: **Correct:** Achieves the maximum possible score of 7 matching columns. D: **Correct:** Achieves the maximum possible score of 7 matching columns.

**1. Set up the codon capacity inequality:** With an alphabet of \( 3 \) distinct nucleotides, a codon of length \( k \) can form \( 3^k \) distinct codons. To encode at least \( 700 \) distinct amino acids, we need: \[ 3^k \ge 700 \] **2. Evaluate powers of 3:** - For \( k = 5 \): \( 3^5 = 243 < 700 \) (insufficient) - For \( k = 6 \): \( 3^6 = 729 \ge 700 \) (sufficient) Thus, the minimum codon length is **6**. **Answer: 6.**

**1. Relate the number of \( k \)-mers to the string length \( L \):** The \( k \)-mer composition \( \text{Composition}_3(\text{Text}) \) of a string \( \text{Text} \) of length \( L \) contains \( N = L - k + 1 \) nodes in its overlap graph. **2. Solve for \( L \) given \( k = 3 \) and \( N = 10 \):** \[ 10 = L - 3 + 1 \implies L = 10 + 3 - 1 = 12 \] **Answer: 12.**

**1. Read the directed edges from the Gene Regulatory Network (GRN) diagram:** - From \( g_1 \): arrows to \( g_2 \) and \( g_3 \) \( \implies \) Row 1 is `[0, 1, 1, 0]`. - From \( g_2 \): arrow to \( g_4 \) \( \implies \) Row 2 is `[0, 0, 0, 1]`. - From \( g_3 \): arrows to \( g_2 \) and \( g_4 \) \( \implies \) Row 3 is `[0, 1, 0, 1]`. - From \( g_4 \): no outgoing arrows \( \implies \) Row 4 is `[0, 0, 0, 0]`. **2. Match with the given matrices:** \[ A = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} \] This matches **Option B**. **Answer: B.** A: **Incorrect:** Does not match the directed edges \( g_1 \to g_2, g_3 \), \( g_2 \to g_4 \), and \( g_3 \to g_2, g_4 \). B: **Correct:** Has `1`s at \( (1,2), (1,3), (2,4), (3,2), (3,4) \) and `0`s elsewhere. C: **Incorrect:** Transposes or misplaces several directed edges. D: **Incorrect:** Includes non-existent outgoing edges from \( g_4 \).

**1. Trace single-hop and multi-hop directed paths in the GRN:** The directed edges are \( g_1 \to g_2 \), \( g_1 \to g_3 \), \( g_3 \to g_2 \), \( g_2 \to g_4 \), and \( g_3 \to g_4 \): - **Option A:** \( g_1 \) directly regulates \( g_2 \) and \( g_3 \), and regulates \( g_4 \) via \( g_1 \to g_2 \to g_4 \) (and \( g_1 \to g_3 \to g_4 \)). Thus, \( g_1 \) regulates all other three genes. **True.** - **Option B:** False, because \( g_1 \) also regulates \( g_4 \) via two-hop paths. - **Option C:** \( g_2 \) only has an outgoing edge to \( g_4 \); it does not regulate \( g_3 \). **False.** - **Option D:** \( g_4 \) is regulated directly by \( g_2 \) and \( g_3 \), and indirectly by \( g_1 \). Thus, \( g_4 \) is regulated by all other three genes. **True.** **Answer: A and D.** A: **Correct:** \( g_1 \) reaches \( g_2, g_3 \) in 1 hop and \( g_4 \) in 2 hops. B: **Incorrect:** Counting multi-hop influences, \( g_1 \) also regulates \( g_4 \). C: **Incorrect:** \( g_2 \) only regulates \( g_4 \), not \( g_3 \). D: **Correct:** \( g_1, g_2, \) and \( g_3 \) all have directed paths to \( g_4 \).

**1. Multiply the independent edge transmission probabilities along the path \( R \to P_1 \to P_2 \to T \to G \):** We are given: - \( P(R \to P_1) = 0.02 = 2 \times 10^{-2} \) - \( P(P_1 \to P_2) = 0.03 = 3 \times 10^{-2} \) - \( P(P_2 \to T) = 0.06 = 6 \times 10^{-2} \) - \( P(T \to G) = 0.01 = 1 \times 10^{-2} \) **2. Calculate the product:** \[ P(\text{path}) = (2 \times 10^{-2}) \times (3 \times 10^{-2}) \times (6 \times 10^{-2}) \times (1 \times 10^{-2}) = 36 \times 10^{-8} \] Comparing with \( x \times 10^{-8} \), we get \( x = 36 \). **Answer: 36.**

**1. Count the number of nodes in the path \( R \to P_1 \to P_2 \to T \to G \):** The path has 4 edges and therefore \( k = 5 \) nodes: \( R, P_1, P_2, T, G \). **2. Calculate the probability that all 5 nodes receive distinct colors from \( k = 5 \) colors:** - Total number of colorings of the 5 nodes: \( 5^5 = 3125 \) - Number of colorful assignments (all 5 nodes get different colors): \( 5! = 120 \) \[ P(\text{colorful}) = \frac{5!}{5^5} = \frac{120}{3125} = 0.0384 \approx 0.04 \] **Answer: 0.04.**

**1. Translate the RNA string `AUGCCUCAA` into a peptide:** Using the genetic code table: - `AUG` \( \to \) **M** (Methionine) - `CCU` \( \to \) **P** (Proline) - `CAA` \( \to \) **Q** (Glutamine) So the second peptide is **`MPQ`** (length 3), to be aligned with **`MSTWPQ`** (length 6). **2. Compute the alignment score using the BLOSUM50 matrix:** In BLOSUM50, the exact match scores are: - \( S(\text{M}, \text{M}) = +7 \) - \( S(\text{P}, \text{P}) = +10 \) - \( S(\text{Q}, \text{Q}) = +7 \) Aligning `M---PQ` with `MSTWPQ` matches `M` (\( +7 \)), opens a gap of length 3 across `STW` with affine gap penalty \( -20 - 2(3 - 1) = -24 \) (where the gap opening is \( -20 \) for the first gap residue and \( -2 \) for each of the 2 gap extensions), and matches `P` (\( +10 \)) and `Q` (\( +7 \)): \[ \text{Score} = 7 - (20 + 2 \times 2) + 10 + 7 = 24 - 24 = 0 \] **Answer: 0.**

**1. Identify the highest-scoring local alignment between `MSTWPQ` and `MPQ`:** In local alignment (Smith–Waterman), we seek the highest-scoring contiguous (or gapped) substring alignment without penalizing unaligned prefixes/suffixes: - Aligning the suffix `PQ` of `MSTWPQ` with the suffix `PQ` of `MPQ` requires no gaps and sums the BLOSUM50 self-match scores for Proline (`P`) and Glutamine (`Q`): - \( S(\text{P}, \text{P}) = +10 \) - \( S(\text{Q}, \text{Q}) = +7 \) \[ \text{Local Alignment Score} = 10 + 7 = 17 \] (Extending left to align `W` with `M` has \( S(\text{W}, \text{M}) = -1 \), which would reduce the score to 16, and opening a gap costs \( -20 \)). **Answer: 17.**