Bioinformatics & Computational Biology

Question 1 (14 marks)

(a) Recurrence (3 marks)

$F(i,j)=\max\begin{cases}F(i-1,j-1)+s(a_i,b_j) & \text{(diagonal / match-mismatch)}\\ F(i-1,j)-2 & \text{(gap in B, vertical)}\\ F(i,j-1)-2 & \text{(gap in A, horizontal)}\end{cases}$

with $s(a_i,b_j)=+1$ if equal, $-1$ if not. (1 mark diagonal, 1 mark gap terms, 1 mark scoring function)

(b) DP matrix (7 marks)

Initialization: $F(0,j)=-2j$, $F(i,0)=-2i$.

Rows = Seq A (GATTACA), Cols = Seq B (GCATGCU).

(Award marks proportionally; full correct = 7, minor arithmetic slips −1 each.)

(c) Score and alignment (4 marks)

Optimal score = $F(7,7) = 0$ (2 marks).

One valid traceback (2 marks):

G C A T G C U -   → actually 8-length classic alignment:
G - A T T A C A
G C A T - G C U

Score check: G/G(+1), −/C(−2), A/A(+1), T/T(+1), T/−(−2), A/G(−1), C/C(+1), A/U(−1) = +1−2+1+1−2−1+1−1 = −2... accept alignments that reconstruct the score 0; the classic NW alignment scoring 0 is:

G-ATTACA
GCA-TGCU

Full credit for any traceback consistent with the filled matrix ending at score 0.

Question 2 (10 marks)

(a) BLAST algorithm (6 marks)

1. Seeding (2): Break query into short words (default 3 aa / 11 nt). Find database positions where a word (or high-scoring neighbor word above threshold T) matches — these are seeds/hits.
2. Extension (2): Extend each seed in both directions, accumulating score, forming High-scoring Segment Pairs (HSPs); stop when score drops by X below the running max. (Gapped BLAST allows gaps.)
3. Evaluation (2): Score HSPs; compute E-value (expected number of hits of that score by chance in a database of that size). Lower E-value = more significant.

• Word size role: smaller word = more sensitive but slower; larger = faster but misses weak matches.

(b) PAM vs BLOSUM (4 marks)

• PAM (1): derived from closely related sequences (accepted point mutations) then extrapolated by matrix multiplication to larger evolutionary distances (PAM250 = distant).
• BLOSUM (1): derived directly from observed substitutions in conserved blocks of aligned proteins; lower number = less similar sequences (BLOSUM45 = distant).
• Distant homologs (2): use PAM250 or BLOSUM45 (low BLOSUM number, high PAM number). Justify: these matrices tolerate more substitutions, so they score divergent alignments favorably.

Question 3 (12 marks)

(a) UPGMA (8 marks)

Smallest distance = A–B = 4. Merge (A,B), node height = 4/2 = 2. (2 marks)

New distances (average):

• (AB)–C = (6+6)/2 = 6
• (AB)–D = (8+8)/2 = 8
• C–D = 8

Matrix now: (AB), C, D. Smallest = (AB)–C = 6. Merge → ((AB)C), height = 6/2 = 3. (2 marks)

New distances:

• ((AB)C)–D = (8+8+8)/3 = 8 (average over all leaves). (2 marks)

Final merge ((AB)C)–D, height = 8/2 = 4. (2 marks)

(b) Tree (2 marks)

        ___________ D    (root height 4)
       |
     __|____ C           (height 3)
    |    |
   _|__  |
  |    | 
  A    B                 (height 2)

Node heights: (A,B)=2, ((AB),C)=3, root=4.

(c) Assumption (2 marks) UPGMA assumes a molecular clock (constant evolutionary rate / ultrametric distances, all leaves equidistant from root). Neighbor-joining relaxes this — allows unequal branch/substitution rates.

Question 4 (12 marks)

(a) Pipeline stages (7 marks) — 1 mark each (up to 7):

1. QC / trimming (FastQC, trim adapters & low-quality bases).
2. Alignment/mapping to reference (BWA/Bowtie) → SAM/BAM.
3. Sort & index BAM.
4. Mark duplicates (remove PCR duplicate bias).
5. Base quality score recalibration (BQSR) (correct systematic quality errors).
6. Variant calling (GATK HaplotypeCaller / FreeBayes) → raw VCF.
7. Variant filtering / annotation (VQSR or hard filters; annotate with VEP/SnpEff).

(b) Allele fraction (3 marks)

• Alt allele fraction = $5/20 = 0.25$ (1 mark).
• Expected het ≈ 0.5, but 0.25 with 5 alt reads is above typical noise (~1–2%) yet below clean 0.5. Given 5 supporting reads it is more consistent with a true heterozygous variant (possibly with allelic bias) than pure sequencing noise, which would give far fewer alt reads. (2 marks for reasoned conclusion — accept "likely het SNP, verify depth/quality").

(c) Formats (2 marks): (i) aligned reads = BAM/SAM (CRAM); (ii) variants = VCF.

Question 5 (12 marks)

(a) RNA-seq workflow (5 marks)

1. QC/trim reads (1).
2. Align to genome/transcriptome (STAR/HISAT) or pseudo-align (Salmon/kallisto) (1).
3. Quantify counts per gene (featureCounts) (1).
4. Normalize — for library size (sequencing depth) and gene length/composition (TPM/CPM, or DESeq2 size factors) because raw counts differ by depth so can't compare across samples (1).
5. Differential expression testing (DESeq2/edgeR) → DEG list with adjusted p-values (1).

(b) log2 fold change (3 marks) $\log_2\!\left(\frac{200}{50}\right)=\log_2(4)=2.$ (2 marks). Interpretation: gene is 4-fold up-regulated (higher expression) in treatment vs control (1 mark).

(c) ML overfitting (4 marks)

• Problem = overfitting (memorizes training data, poor generalization) (2).
• Two remedies (any two, 1 each): regularization (L1/L2, dropout); feature selection / dimensionality reduction; more training data; cross-validation; simpler model; early stopping.

[
  {"claim":"log2(200/50)=2","code":"result = (log(Integer(200)/Integer(50),2) == 2)"},
  {"claim":"Alt allele fraction 5/20 = 0.25","code":"result = (Rational(5,20) == Rational(1,4))"},
  {"claim":"UPGMA (AB)-C averaged distance = 6","code":"result = (Rational(6+6,2) == 6)"},
  {"claim":"UPGMA final ((AB)C)-D averaged over 3 leaves = 8, root height = 4","code":"d=Rational(8+8+8,3); result = (d==8 and Rational(d,2)==4)"},
  {"claim":"NW init F(0,7) = -14 with gap -2","code":"result = (-2*7 == -14)"}
]