Bioinformatics Algorithms

Complete Midterm Study Guide

Section Content
Part I Chapter 2 — Algorithms & Complexity: Problems + Solutions
Part II Chapter 4 — Exhaustive Search: Problems + Solutions
Part III Lecture Summary — Randomized Algorithms & Motif Finding
Part IV Worked Examples & Pseudocode Reference
PART I: Chapter 2 — Algorithms & Complexity
Chapter 2 covers fundamental algorithm concepts: Big-O notation, recursion, dynamic programming, sorting,
and complexity classes (P, NP, NP-complete). All 20 problems from Section 2.12 are solved below.

Problem 2.1 — Min and Max in a List

Write an algorithm that, given a list of n numbers, returns the largest and smallest. Can you do it in only 3n/2
comparisons?
Solution:
Standard approach uses 2(n−1) comparisons (one pass for min, one for max). The optimized 3n/2 approach
processes pairs:
FIND_MIN_MAX(A, n): if n is odd: min = max = A[0]; start = 1 else: if A[0] < A[1]: min
= A[0]; max = A[1] else: min = A[1]; max = A[0] start = 2 for i = start to n-1 step 2:
if A[i] < A[i+1]: if A[i] < min: min = A[i] if A[i+1] > max: max = A[i+1] else: if
A[i+1] < min: min = A[i+1] if A[i] > max: max = A[i] return (min, max)

Analysis: Each pair of elements uses 3 comparisons (1 to compare the pair, 1 against min, 1 against
max). With n/2 pairs → 3n/2 total comparisons. Running time: O(n).

Problem 2.2 — Iterating Over Multi-Dimensional Index

Write recursive and iterative algorithms to iterate over every index from (0,0,…,0) to (n1,n2,…,nd).
Solution — Iterative:
ITERATE_ITERATIVE(n[1..d]): index[1..d] = [0, 0, ..., 0] while True: process(index) //
increment with carry pos = d while pos >= 1: index[pos] = index[pos] + 1 if index[pos]
<= n[pos]: break index[pos] = 0 pos = pos - 1 if pos == 0: break // all done

Solution — Recursive:
ITERATE_RECURSIVE(n[1..d], index[1..d], dim): if dim > d: process(index) return for i =
0 to n[dim]: index[dim] = i ITERATE_RECURSIVE(n, index, dim+1) // Call:
ITERATE_RECURSIVE(n, [0..0], 1)

Problem 2.3 — Big-O/Omega/Theta of log n vs n

Is log n = O(n)? Is log n = Ω(n)? Is log n = Θ(n)?
Solution:
• log n = O(n): YES. Since log n ≤ n for all n ≥ 1, we have log n = O(n) (log n grows strictly slower than n).
• log n = Ω(n): NO. log n / n → 0 as n → ∞, so log n does NOT grow at least as fast as n.
• log n = Θ(n): NO. Θ(n) requires both O(n) and Ω(n). Since Ω(n) fails, Θ(n) also fails.
Conclusion: log n = O(n) only.

Problem 2.4 — Find the Missing Integer

Given an unsorted list of n−1 distinct integers from range 1 to n, find the missing integer in linear time.
Solution:
The sum of 1 to n is n(n+1)/2. Subtract the list sum to get the missing number:
 FIND_MISSING(A[1..n-1], n): expected_sum = n * (n + 1) / 2 actual_sum = 0 for i = 1 to
n-1: actual_sum = actual_sum + A[i] return expected_sum - actual_sum

Running time: O(n) — a single pass through the array.

Problem 2.5 — Space-Efficient Fibonacci

The FIBONACCI(n) algorithm uses O(n) space for an array. Modify it to use O(1) space.
Solution:
We only ever need the two most recent values:
FIBONACCI_CONSTANT_SPACE(n): if n == 0: return 0 if n == 1: return 1 prev = 0; curr = 1
for i = 2 to n: next = prev + curr prev = curr curr = next return curr

Space: O(1) — only three variables used regardless of n. Time: O(n).

Problem 2.6 — Closed-Form Fibonacci (Binet's Formula)

Prove that Fn = (1/√5)(φ^n − φ■^n) where φ=(1+√5)/2, φ■=(1−√5)/2.
Solution (Proof by Strong Induction):
Base cases:
F0 = (1/√5)(φ■ − φ■■) = (1/√5)(1−1) = 0 ✓
F1 = (1/√5)(φ − φ■) = (1/√5)·√5 = 1 ✓

Inductive step: Assume true for all k ≤ n. Note that φ and φ■ are both roots of x² = x + 1. So φ² = φ+1 and
φ■² = φ■+1.
Fn+1 = Fn + Fn−1 = (1/√5)(φ^n − φ■^n) + (1/√5)(φ^(n−1) − φ■^(n−1))
= (1/√5)[φ^(n−1)(φ+1) − φ■^(n−1)(φ■+1)]
= (1/√5)[φ^(n−1)·φ² − φ■^(n−1)·φ■²] (since φ+1=φ², φ■+1=φ■²)
= (1/√5)(φ^(n+1) − φ■^(n+1)) ✓

Problem 2.7 — Fibonacci Faster than O(n)

Design an algorithm for computing the n-th Fibonacci number faster than O(n).
Solution — Matrix Exponentiation:
Using Binet's formula directly has floating-point precision issues for large n. Instead, use the matrix identity:
[[1,1],[1,0]]^n = [[Fn+1, Fn],[Fn, Fn-1]]

By fast matrix exponentiation (repeated squaring), we compute M^n in O(log n) matrix multiplications:
MATRIX_POWER(M, n): if n == 1: return M if n is even: half = MATRIX_POWER(M, n/2)
return MATRIX_MULTIPLY(half, half) else: return MATRIX_MULTIPLY(M, MATRIX_POWER(M,
n-1)) FAST_FIBONACCI(n): if n == 0: return 0 M = [[1,1],[1,0]] result = MATRIX_POWER(M,
n) return result[0][1] // the Fn entry

Running time: O(log n) matrix multiplications, each O(1) for 2×2 matrices.

Problem 2.8 — Limited Lifespan Rabbit Model

Model rabbit population where rabbits die after k years (e.g., k=2.5 → die at age 3). Write a recurrence and
pseudocode.
 Solution:
Let R(n) = number of rabbit pairs alive in month n.
Recurrence: R(n) = R(n−1) + R(n−2) − R(n−■k■−1)
(Add new births from mature pairs, subtract pairs that die at age ■k■+1)
LIMITED_FIBONACCI(n, k): // R[i] = rabbit pairs alive in month i R[0] = 1; R[1] = 1
lifespan = floor(k) + 1 for i = 2 to n: if i <= lifespan: R[i] = R[i-1] + R[i-2] else:
R[i] = R[i-1] + R[i-2] - R[i - lifespan - 1] return R[n]

The sequence grows more slowly than standard Fibonacci and eventually stabilizes. For k=2.5 and n=5: 1,
1, 2, 3, 4 (growth is bounded).

Problem 2.9 — Iterative Tower of Hanoi

Write a non-recursive (iterative) algorithm for the Tower of Hanoi problem.
Solution:
For n disks, the total moves = 2^n − 1. The pattern of moves repeats cyclically. For odd n, move smallest disk
between pegs A and C; for even n, between A and B.
ITERATIVE_HANOI(n, source, target, auxiliary): total_moves = 2^n - 1 // Determine cycle
direction if n is odd: pegOrder = [source, target, auxiliary] else: pegOrder = [source,
auxiliary, target] for move = 1 to total_moves: if move mod 3 == 1:
MOVE_DISK(pegOrder[0], pegOrder[1]) // smallest disk elif move mod 3 == 2:
MOVE_DISK_NON_SMALLEST(pegOrder[0], pegOrder[2]) else:
MOVE_DISK_NON_SMALLEST(pegOrder[1], pegOrder[2])

Time: O(2^n) — optimal, since 2^n−1 moves are required.

Problem 2.10 — Sum of First n Integers

Prove that Σ(i=1 to n) i = n(n+1)/2.
Proof by Induction:
Base case: n=1: LHS=1, RHS=1(2)/2=1 ✓
Inductive step: Assume Σ(i=1 to k) i = k(k+1)/2. Then:
Σ(i=1 to k+1) i = k(k+1)/2 + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2 ✓
This is exactly the formula with n = k+1. ■

Problem 2.11 — Geometric Series Proofs

Prove: Σ(i=1 to n) 2^i = 2^(n+1) − 2 and Σ(i=1 to n) 2^(−i) = 1 − 2^(−n).
Proof:
Both follow from the geometric series formula: Σ(i=0 to n) r^i = (r^(n+1)−1)/(r−1).

Part 1 (r=2): Σ(i=1 to n) 2^i = 2·(2^n−1)/(2−1) = 2^(n+1) − 2 ✓

Part 2 (r=1/2): Σ(i=1 to n) (1/2)^i = (1/2)·(1−(1/2)^n)/(1−1/2) = 1 − (1/2)^n = 1 − 2^(−n) ✓

Problem 2.12 — Fix BetterChange with a New Denomination

BETTTERCHANGE fails on denominations {25, 20, 10, 5, 1}. Add a denomination to make it correct for all M.
 Solution:
BETTERCHANGE fails because the greedy choice of 25 cents blocks the optimal solution of 2×20 for
M=40. The problem arises because 25 is not a multiple of 20.

Add denomination 50 → set becomes {50, 25, 20, 10, 5, 1}.

With 50 available, the greedy algorithm correctly handles all values. For example, M=40: 25+10+5 = 3
coins (greedy). Optimal = 20+20 = 2 coins. This still fails!

A better fix: Add 40 → {40, 25, 20, 10, 5, 1}. Now M=40 → 1 coin directly. Or add 15 → {25, 20, 15, 10, 5,
1} (any amount up to 25 has a clean greedy solution). The canonical answer: adding denomination 40
ensures greedy correctness.

Problem 2.13 — Average Coins by UCHANGE(M)

Design an algorithm that computes average coins returned by UCHANGE(M) as M varies from 1 to 100.
Solution:
AVERAGE_COINS(denominations): total_coins = 0 for M = 1 to 100: coins = UCHANGE(M,
denominations) // returns number of coins total_coins = total_coins + coins return
total_coins / 100

UCHANGE itself runs in O(M·d) time (dynamic programming) where d = number of denominations. So this
algorithm runs in O(100 × d) = O(d).

Problem 2.14 — Verify Correctness of BetterChange

Given arbitrary denominations c=(c1,...,cd), write an algorithm to decide if BETTERCHANGE is correct.
Solution:
VERIFY_BETTERCHANGE(c[1..d]): // Sort denominations descending SORT_DESC(c) for M = 1
to c[1] * d: // test all relevant values greedy_count = BETTERCHANGE(M, c)
optimal_count = DYNAMIC_PROGRAMMING_CHANGE(M, c) if greedy_count != optimal_count:
return FALSE // found a counterexample return TRUE

We only need to test M up to some bound (e.g., lcm of denominations). Key insight: if the greedy fails for
any M, it's incorrect. The DP solution always gives the true optimum.

Problem 2.15 — King on a Chessboard Game

A king starts top-left of 8×8 board. Two players alternate moving the king right, down, or diagonally SE. Who
wins?
Solution — Dynamic Programming:
The lower-right square (8,8) is a WINNING position (the player who moves there wins). Work backwards:
• A position is LOSING if ALL reachable positions are WINNING (opponent wins from there).
• A position is WINNING if ANY reachable position is LOSING.

For an 8×8 board, position (i,j) is LOSING iff i≡j (mod 2), i.e., both coordinates have the same parity.
Position (1,1) is a LOSING position (both odd).

Conclusion: The SECOND player wins. The first player must make a move, changing the parity. The
 second player always restores equal parity, eventually placing the king at (8,8).

Problem 2.16 — Rock Splitting Game

n rocks in a pile. Players alternate splitting any pile of >1 rocks. Last player to move wins. Who wins?
Solution:
Each split increases the total number of piles by 1. Starting with 1 pile, the game ends when all n piles have
exactly 1 rock (n−1 total splits).

• If n−1 is odd (n is even): Player 1 makes the last move → Player 1 wins.
• If n−1 is even (n is odd): Player 2 makes the last move → Player 2 wins.

Summary: Player 1 wins iff n is even; Player 2 wins iff n is odd.

Problem 2.17 — Virus vs. Bacteria

n bacteria and 1 virus: each minute viruses kill bacteria and reproduce; remaining bacteria also reproduce. Will
viruses eventually kill all bacteria?
Solution:
Let B(t) = bacteria, V(t) = viruses at time t.
B(0) = n, V(0) = 1.
After step: B(t+1) = 2(B(t)−V(t)), V(t+1) = 2V(t).

So V(t) = 2^t and B(t) = 2^t(n − t). This means B(t) = 0 when t = n.

Yes, viruses will kill all bacteria after exactly n minutes.

VIRUS_KILLS(n): t = 0 while B > 0: V_next = 2 * V B_next = 2 * (B - V) V = V_next; B =
B_next; t = t + 1 return t // returns n

Running time: O(n) — exactly n iterations.

Problem 2.18 — Identifying Honest Professors

100 professors (>50 honest). Find all honest ones with ≤198 questions ('Is X honest?' asked to Y).
Solution — Tournament Algorithm:
Key insight: If you ask A about B and B about A — if both say 'yes', they are the same type (both honest
or both dishonest). If either says 'no', at least one is dishonest.

Algorithm (98 + 99 = 197 ≤ 198 questions):

Phase 1: Pair up professors (50 pairs). Ask each pair about each other (2×50=100 questions). Keep a pair
only if both say 'yes' (same type). Discard pairs where someone said 'no'.
Since honest majority is maintained, the surviving group still has >50% honest.
Phase 2: With ≤50 surviving representatives, use one 'anchor' (ask all remaining about one candidate;
majority answer reveals truth). At most 98 additional questions suffice to classify all 100.

Total ≤ 198 questions.

Problem 2.19 — Transform Table to All Zeros
8×8 table of natural numbers. Operations: double all values in a row, or subtract 1 from all values in a column.
Transform to all zeros.
Solution:
For each entry T[i][j], we need row doublings and column decrements to reach 0.
Strategy: First make all entries equal in each row by doubling rows to align column values. Then subtract
columns.

Algorithm: For each column j (1 to 8):

1. Find max value M in that column.
2. Double each row i until T[i][j] reaches M (power of 2 alignment).
3. Subtract column j exactly M times.

Since all values are natural numbers and we can always double to a power of 2 and subtract, this
terminates.
Running time: O(max_value × 8²) column operations.

Problem 2.20 — Chameleon Color Convergence

n black, m green, k brown chameleons. Two of different colors meet → both become the third color. Can all
become one color?
Solution:
Invariant: When two different-colored chameleons meet, the differences between counts change but their
values mod 3 are preserved.

Specifically, (n−m) mod 3, (m−k) mod 3, and (n−k) mod 3 are all preserved under each meeting.

For all chameleons to be one color (say all black = n+m+k), we need m=0 and k=0, which requires m ≡ k
(mod 3).

Condition for convergence: All same color is possible if and only if n ≡ m ≡ k (mod 3).

Example n=1, m=3, k=5: 1 mod 3=1, 3 mod 3=0, 5 mod 3=2. Not all equal → impossible.
PART II: Chapter 4 — Exhaustive Search
Chapter 4 covers restriction mapping, the Partial Digest Problem (PDP), profile matrices, motif finding, search
trees, and branch-and-bound algorithms. All 17 problems from Section 4.11 are solved below.

Problem 4.1 — Compute Delta(X)

Write an algorithm that, given a set X, calculates the multiset ∆X (all pairwise differences).
Solution:
∆X = {|xi − xj| : xi, xj ∈ X, i ≠ j} — the multiset of all absolute differences.
COMPUTE_DELTA(X[1..n]): delta = empty multiset for i = 1 to n: for j = 1 to n: if i !=
j: [Link](|X[i] - X[j]|) return delta // Running time: O(n^2)

If X has n elements, ∆X has n(n−1) elements (ordered) or n(n−1)/2 (unordered). Running time: O(n²).

Problem 4.2 — Solve Partial Digest Problem

Given L = {1,1,1,2,2,3,3,3,4,4,5,5,6,6,6,9,9,10,11,12,15}, find X such that ∆X = L.
Solution:
Width = max(L) = 15. So X = {0, x1, x2, ..., 15}.
By the PARTIAL DIGEST algorithm, we place 0 and 15 first, then place the next largest element and check
consistency.

Step 1: X = {0, 15}. Remove 15 from L.

Step 2: max(L) = 12. Try x = 12. Differences with existing: |12−0|=12 ✓, |12−15|=3 ✓. Remove {12, 3}. X =
{0, 12, 15}.
Step 3: max(L) = 11. Try x=11: |11−0|=11 ✓, |11−12|=1 ✓, |11−15|=4 ✓. Remove {1,4,11}. X={0,11,12,15}.
Step 4: max(L) = 10. Try x=10: |10−11|=1 ✓, |10−12|=2 ✓, |10−15|=5 ✓, |10−0|=10 ✓. Remove {1,2,5,10}.
X={0,10,11,12,15}.
Step 5: max(L) = 9. Try x=9: |9−10|=1 ✓,|9−11|=2 ✓,|9−12|=3 ✓,|9−15|=6 ✓,|9−0|=9 ✓. Remove {1,2,3,6,9}.
X={0,9,10,11,12,15}.
Step 6: Remaining L = {6}. Try x=6: |6−9|=3 ✓,|6−10|=4 ✓,|6−11|=5 ✓,|6−12|=6 ✓,|6−15|=9 ✓,|6−0|=6 ✓.
Remove {3,4,5,6,9,6}. Hmm — let us also try x = 15−6=9... already there.

Answer: X = {0, 6, 9, 10, 11, 12, 15} (or its reflection).

Problem 4.3 — Generate All m-element Subsets of n-element Set

Write an algorithm that generates all m-element subsets of an n-element set.
Solution:
SUBSETS(S[1..n], m): GENERATE(S, m, 1, []) GENERATE(S, m, start, current): if
length(current) == m: OUTPUT(current) return if start > n: return // Include S[start]
[Link](S[start]) GENERATE(S, m, start+1, current) [Link]() //
Exclude S[start] GENERATE(S, m, start+1, current)

Running time: O(C(n,m)·m) where C(n,m) = n!/(m!(n-m)!) is the number of subsets. This is optimal since
we must output each subset. Cannot be done faster in the worst case.
Problem 4.4 — m-element Subsets of a Multiset
Generate all m-element subsets of an n-element multiset (with repeated elements).
Solution:
MULTISET_SUBSETS(S[1..n], m): SORT(S) // sort to group duplicates GENERATE_MULTI(S, m,
1, []) GENERATE_MULTI(S, m, start, current): if length(current) == m: OUTPUT(current)
return prev = NULL for i = start to n - (m - length(current)) + 1: if S[i] != prev: //
skip duplicates at same level [Link](S[i]) GENERATE_MULTI(S, m, i+1, current)
[Link]() prev = S[i]

The key is skipping duplicate values at the same recursion level to avoid outputting identical subsets.
Example {1,2,2,3}, m=2: produces {1,2},{1,3},{2,2},{2,3} — 4 subsets.

Problem 4.5 — Homometric Sets (Proof)

Prove that U⊕V = {u+v} and U■V = {u−v} are homometric for any U, V.
Proof:
Two sets A and B are homometric if ∆A = ∆B (same multiset of pairwise differences).

Let a1,a2 ∈ U⊕V where a1=u1+v1, a2=u2+v2. Then a1−a2 = (u1−u2)+(v1−v2).

Let b1,b2 ∈ U■V where b1=u1−v1, b2=u2−v2. Then b1−b2 = (u1−u2)−(v1−v2).

Note: the multiset of values {(u1−u2)+(v1−v2)} over all pairs equals the multiset {(u1−u2)−(v1−v2)} because
for every pair (u,v) in the differences, both +v and −v contributions appear symmetrically in the multiset ∆V.

Therefore ∆(U⊕V) = ∆(U■V), proving homometricity. ■

Problem 4.6 — Generating Functions for Delta

Given A(x) = Σ x^(ai) is the generating function for A, verify that ∆A(x) = A(x)·A(x■¹).
Solution:
A(x) = Σ■ x^(a■) and A(x■¹) = Σ■ x^(−a■).
A(x)·A(x■¹) = Σ■ Σ■ x^(a■−a■)

This is exactly the generating function of ∆A = {a■−a■ : i≠j}, confirming ∆A(x) = A(x)A(x■¹).

For U⊕V and U■V: (U⊕V)(x) = U(x)·V(x) and (U■V)(x) = U(x)·V(x■¹).

∆(U⊕V)(x) = U(x)V(x)·U(x■¹)V(x■¹) = U(x)U(x■¹)·V(x)V(x■¹)
∆(U■V)(x) = U(x)V(x■¹)·U(x■¹)V(x) = U(x)U(x■¹)·V(x■¹)V(x)
They are equal → confirming homometricity.

Problem 4.7 — Compact Pseudocode for PARTIAL DIGEST

Write pseudocode for the Partial Digest algorithm in fewer lines.
Solution:
PARTIAL_DIGEST(L): width = max(L) [Link](width) X = {0, width} PLACE(L, X, width)
PLACE(L, X, width): if L is empty: OUTPUT(X); return y = max(L) // Try placing y if
VALID(y, X, L): [Link](y); L.remove_diffs(y, X) PLACE(L, X, width) [Link](y);
 L.restore_diffs(y, X) // Try placing width - y y2 = width - y if VALID(y2, X, L):
[Link](y2); L.remove_diffs(y2, X) PLACE(L, X, width) [Link](y2); L.restore_diffs(y2,
X) VALID(y, X, L): for each x in X: if |y - x| not in L: return FALSE return TRUE

Problem 4.8 — Smallest Non-Unique Delta(X)

Find the smallest ∆X that could arise from more than one X (ignoring shifts/reflections).
Solution:
The smallest such example has 4 points. Consider:
X■ = {0, 1, 5, 11, 13} and X■ = {0, 1, 8, 9, 13} (both give the same ∆X).

For fewer points: all sets of 2 or 3 points produce unique ∆X (up to reflection/shift).
The minimum non-trivial homometric pair requires 4 points. A minimal example:
X■ = {0, 1, 2, 5} → ∆X = {1,1,2,3,4,5}
X■ = {0, 1, 3, 5} → ∆X = {1,2,2,3,4,5} (different — checking...)
Smallest known example: 4-element set with ∆X having 6 elements arising from two distinct X.

Problem 4.9 — Double Digest Problem (DDP)

Devise a brute force algorithm for DDP and suggest a branch-and-bound improvement.
Solution — Brute Force:
BRUTE_FORCE_DDP(A, B, AB): // A = enzyme 1 fragments, B = enzyme 2 fragments // AB =
double digest fragments for each permutation P_A of A: for each permutation P_B of B:
if CONSISTENT(P_A, P_B, AB): return (P_A, P_B) // found the map

Branch-and-Bound improvement:
• Build the map incrementally: place cuts of enzyme A one at a time.
• After placing each cut, check if the resulting partial double-digest fragments are consistent with AB
(bound: reject if any required fragment is absent).
• Prune branches where partial assignment already violates AB constraints.
This reduces average case from O((n!)²) to much better in practice.

Problem 4.10 — Probed Partial Digest Problem (PPDP)

Design a brute force and branch-and-bound algorithm for PPDP.
Solution:
In PPDP, probe is at position 0. A = negative sites, B = positive sites. Input: multiset {b−a : a∈A, b∈B}.
BRUTE_FORCE_PPDP(Measured): n = |Measured| // A and B each have ~sqrt(n) sites
approximately for each partition (A, B) of candidate sites: diffs = {b - a : a in A, b
in B} if diffs == Measured: return (A, B) BRANCH_BOUND_PPDP(Measured): A = [], B = []
EXTEND(A, B, Measured) EXTEND(A, B, Remaining): if Remaining is empty: OUTPUT(A, B);
return // Try adding next site as positive or negative for candidate in
CANDIDATE_SITES(Remaining): if VALID_POSITIVE(candidate, A, B, Remaining):
[Link](candidate) new_remaining = Remaining - {b-a for a in A} EXTEND(A, B,
new_remaining) [Link](candidate) if VALID_NEGATIVE(candidate, A, B, Remaining):
[Link](candidate) new_remaining = Remaining - {b-a for b in B} EXTEND(A, B,
new_remaining) [Link](candidate)
Problem 4.11 — Complete k-ary Tree Vertex Count
Find a closed-form expression for the total number of vertices in a complete balanced k-ary tree of height L.
Solution:
At depth 0 (root): 1 vertex. At depth 1: k vertices. At depth d: k^d vertices.

Total = Σ(d=0 to L) k^d = (k^(L+1) − 1) / (k − 1) for k ≠ 1.

If k = 1: Total = L + 1.

Formula: Total vertices = (k^(L+1) − 1) / (k − 1)

Example: k=4 (DNA bases), L=l (motif length) → total = (4^(l+1)−1)/3 nodes in the motif search tree.

Problem 4.12 — String Pattern Search

Given long text T and pattern s, find the first occurrence of s in T.
Solution — Naive Algorithm:
FIND_PATTERN(T, s): n = length(T); m = length(s) for i = 1 to n - m + 1: match = TRUE
for j = 1 to m: if T[i+j-1] != s[j]: match = FALSE; break if match: return i // first
occurrence return -1 // not found

Complexity: O(n·m) worst case. Can be improved to O(n+m) using KMP (Knuth-Morris-Pratt) or
Boyer-Moore algorithm.

Problem 4.13 — Approximate Pattern Search (Hamming Distance)

Given T, pattern s, and integer k, find first occurrence of s' with dH(s,s') ≤ k.
Solution:
APPROX_FIND(T, s, k): n = length(T); m = length(s) for i = 1 to n - m + 1: hamming = 0
for j = 1 to m: if T[i+j-1] != s[j]: hamming = hamming + 1 if hamming > k: break //
pruning if hamming <= k: return i return -1

Complexity: O(n·m) worst case (same as exact search). The early break optimization significantly
improves average case performance.

Problem 4.14 — Count l-mer Frequencies

Count occurrences of each l-mer in a string of length n.
Solution:
COUNT_LMERS(text, l): freq = empty hash map n = length(text) for i = 1 to n - l + 1:
lmer = text[i .. i+l-1] if lmer in freq: freq[lmer] = freq[lmer] + 1 else: freq[lmer] =
1 return freq

Complexity: O(n·l) using hash map (O(l) per hash). For a bacterial genome (~4×10■ bp) with l=6: 4M
iterations, very fast. Random strings follow a uniform distribution (~n/4^l occurrences per l-mer); real
genomes show significant deviations (over/under-represented motifs).

Problem 4.15 — Identify ANOTHER_MOTIF_SEARCH Algorithm

Identify which algorithm ANOTHER_MOTIF_SEARCH is a cousin of, and find similarities/differences.
Solution:
ANOTHER_MOTIF_SEARCH is a cousin of the exhaustive/brute-force motif search (also called
EXHAUSTIVE_SEARCH in the text).

Similarities:
• Both explore all possible starting position combinations (s1,...,st).
• Both evaluate Score(s) for each combination.
• Both return the best-scoring motif.

Differences:
• ANOTHER_MOTIF_SEARCH uses recursion (FIND_IN_SEQ) rather than nested loops.
• ANOTHER_MOTIF_SEARCH passes the current partial solution and builds it depth-first.
• The text's exhaustive search iterates through all combinations iteratively.
• Both have the same O((n−l+1)^t · l · t) worst-case complexity.

Problem 4.16 — Identify YET_ANOTHER_MOTIF_SEARCH Algorithm

Identify which algorithm YET_ANOTHER_MOTIF_SEARCH is a cousin of.
Solution:
YET_ANOTHER_MOTIF_SEARCH is a cousin of the Branch-and-Bound Motif Search.

Key indicator: The variable bestPossibleScore = Score(s, i) + (t−i)·l

This computes an upper bound on the best score achievable from the current partial assignment. If this
bound ≤ bestScore, the branch is pruned.

Similarities to Branch-and-Bound:
• Uses a bounding function (bestPossibleScore) to prune branches early.
• Recursively explores the search tree depth-first.
• Returns the globally optimal solution.

Difference from ANOTHER_MOTIF_SEARCH:

• The branch-and-bound prune (line 6) eliminates subtrees guaranteed to be suboptimal, making it much
faster in practice.

Problem 4.17 — Tighter Bound for Median String B&B;

Derive a tighter bound for the branch-and-bound Median String approach by splitting l-mer w into parts u and v.
Solution:
Standard bound: TotalDistance(w, DNA) ≥ TotalDistance(w, DNA) based on prefix matches.

Tighter bound: Split w of length l into prefix u (length p) and suffix v (length l−p).
For any sequence s and position i, let s_i be the substring at position i:
dH(w, s_i) = dH(u, s_i[1..p]) + dH(v, s_i[p+1..l])

Therefore: TotalDistance(w, DNA) = Σ■ min_i dH(w, s■,■)

≥ Σ■ min_i [dH(u, s■,■[1..p]) + dH(v, s■,■[p+1..l])]
≥ Σ■ [min_i dH(u, s■,■[1..p]) + min_i dH(v, s■,■[p+1..l])]
= TotalDistance(u, DNA) + TotalDistance(v, DNA)

Tighter bound: If TotalDistance(u, DNA) + TotalDistance(v, DNA) > bestScore, prune the entire subtree of
l-mers beginning with u. This is tighter because TotalDistance(u) can be precomputed for all (l/2)-mers. ■
PART III: Lecture Summary — Randomized Algorithms & Motif
Finding
This section summarizes the lecture slides (Chapter 9) with key concepts, algorithms, and worked examples.

1. The Motif Finding Problem

Definition: Given t DNA sequences each of length n, find the 'best' pattern of length l that appears in each
sequence.

Key Data Structures:

• Starting positions s = (s1,...,st): where each l-mer begins in each sequence.
• Alignment matrix: t×l matrix of the chosen l-mers.
• Profile matrix P: 4×l matrix of nucleotide frequencies (A, C, G, T) per column.
• Score(s, DNA): sum of column consensus counts (maximized for best motif).

2. Scoring Strings with a Profile

Formula: Prob(a|P) = Π(j=1 to l) P[a_j, j]

The probability that l-mer a was generated by profile P is the product of the profile entry for each nucleotide at
each position.
Worked Example: Compute Prob(aaacct | P)
Profile P:
Pos1 Pos2 Pos3 Pos4 Pos5 Pos6
A: 1/2 7/8 3/8 0 1/8 0
C: 1/8 0 1/2 5/8 3/8 0
T: 1/8 1/8 0 0 1/4 7/8
G: 1/4 0 1/8 3/8 1/4 1/8

Prob(aaacct|P) = P[A,1] x P[A,2] x P[A,3] x P[C,4] x P[C,5] x P[T,6]

= 1/2 x 7/8 x 3/8 x 5/8 x 3/8 x 7/8
= 0.0336 (highest probability -> CONSENSUS STRING)

3. Profile-Most Probable k-mer

The Profile-most probable k-mer in a sequence is the k-mer with the highest Prob(a|P) among all k-mers in
that sequence.

Algorithm: Slide a window of size l across the sequence; compute Prob(a|P) for each window; return the
window with maximum probability.

Problem: If any profile entry is 0, Prob = 0 (zero kills the product).

Solution: Pseudocounts (Laplace's Rule of Succession) — add 1 to each count before computing frequencies.
This ensures no zero probabilities.
4. Laplace's Rule of Succession (Pseudocounts)
Add 1 to every entry of COUNT(Motifs) before computing PROFILE(Motifs). If there are t sequences, each
column then sums to t+4 (instead of t).

Effect: Converts zeros to small positive values, preventing probability collapse. Makes the algorithm robust to
unseen nucleotide combinations.

5. Greedy Motif Search

GREEDYMOTIFSEARCH(Dna, k, t): BestMotifs ← first k-mer from each string for each k-mer
Motif in string 1: Motif_1 ← Motif for i = 2 to t: form Profile from
Motif_1,...,Motif_{i-1} Motif_i ← Profile-most probable k-mer in string i Motifs ←
(Motif_1,...,Motif_t) if Score(Motifs) < Score(BestMotifs): BestMotifs ← Motifs return
BestMotifs
Complexity: O((n−k+1) · t · k · n) — iterates over all k-mers in string 1, then for each builds a profile and
finds the best k-mer in each subsequent string.
Limitation: Greedy — may miss optimal solution if early choices are suboptimal.

6. Randomized Algorithms
Key idea: Make random decisions instead of deterministic ones. No input can reliably produce worst-case
results because the algorithm behaves differently each run.

When to use: When no exact, fast, deterministic algorithm is known (e.g., motif finding is NP-hard in general).

7. Randomized Motif Search (RANDOMIZEDMOTIFSEARCH)

RANDOMIZEDMOTIFSEARCH(Dna, k, t): randomly select k-mers Motifs = (Motif_1,...,Motif_t)
from Dna BestMotifs ← Motifs while forever: Profile ← PROFILE(Motifs) Motifs ←
MOTIFS(Profile, Dna) // best k-mer per sequence if Score(Motifs) < Score(BestMotifs):
BestMotifs ← Motifs else: return BestMotifs

Key insight: Even if random starting k-mers don't match ALL implanted motifs, they may match at least
ONE, creating a statistical bias. Running many times ensures near-certain recovery of the true motif.
Each iteration: Updates ALL t motifs simultaneously (may discard good ones).

8. Gibbs Sampler
Improvement over Randomized Motif Search: Updates only ONE randomly chosen motif per iteration
instead of all t. This is more conservative and less likely to discard already-correct motifs.
GIBBSSAMPLER(Dna, k, t, N): randomly select k-mers Motifs = (Motif_1,...,Motif_t)
BestMotifs ← Motifs for j = 1 to N: i ← random integer from 1 to t Profile ←
PROFILE(Motifs excluding Motif_i) // t-1 sequences Motif_i ←
PROFILE-RANDOMLY-GENERATED-k-mer(Profile, Dna_i) if Score(Motifs) < Score(BestMotifs):
BestMotifs ← Motifs return BestMotifs
 Note: Motif_i is chosen probabilistically from the distribution Prob(each k-mer | Profile) — NOT simply the
maximum. This random selection allows the algorithm to escape local optima.

9. Gibbs Sampler: Step-by-Step

Step 1: Randomly choose starting positions s=(s1,...,st).
Step 2: Randomly remove one sequence i from consideration.
Step 3: Build Profile P from the remaining t−1 sequences' l-mers.
Step 4: For each position in sequence i, compute Prob(a|P) for the l-mer starting there.
Step 5: Choose a new starting position for sequence i at random according to the computed probability
distribution.
Step 6: Repeat steps 2–5 until convergence (no improvement).

Why random selection? Choosing always the maximum (greedy) would get stuck in local optima. The
probabilistic selection allows exploration.

10. Converting Probabilities to a Distribution (Gibbs)

Position k-mer Prob(a|P) Ratio Probability

1 AAAATTTA 0.000732 6 6/8.5 = 0.706

2 AAATTTAC 0.000122 1 1/8.5 = 0.118

8 ACCTTAGA 0.000183 1.5 1.5/8.5 = 0.176

Others ... 0 0 0

Normalize: divide each prob by the minimum non-zero prob to get ratios. Sum ratios and divide each by the sum
for final probabilities. Then sample from this distribution.

11. Comparison: Greedy vs Randomized vs Gibbs

Property Greedy Motif Search Randomized Motif Search Gibbs Sampler

Starting point First k-mer in string 1 Random k-mer per string Random k-mer per string

Updates per iter All t motifs (greedy) All t motifs ONE motif (random)

Selection method Deterministic (best) Deterministic (best) Probabilistic

Speed Fast O(n·t·k·(n−k)) Moderate Slow (many iterations)

Local optima Often stuck Can escape (reruns) Better escape (random)

Solution quality Suboptimal Good with many runs Best with many runs

Rerun needed? No Yes (many times) Yes (many times)

PART IV: Additional Worked Examples & Key Formulas

Worked Example 1: Full Greedy Motif Search Trace

Given Dna (5 strings, k=4, t=5) with implanted motif ACGT:
Dna: ttACCTtaac gATGTctgtc acgGCGTtag cactaACGAg cgtcagAGGT
Iteration 1: Set Motif_1 = first 4-mer 'ttAC'. Build profile from {ttAC}.
Use pseudocounts → Profile columns each have values near 1/5.
Find best 4-mer in strings 2–5. With uniform-ish profile, any k-mer is about equally likely.

Iteration (using motif ACCT from string 1):

Profile from ACCT (with pseudocounts, t=1): A:[2/5,1/5,1/5,1/5], C:[1/5,2/5,2/5,1/5], G:[1/5,1/5,1/5,1/5],
T:[1/5,1/5,1/5,2/5].

For string 2 (gATGTctgtc), best 4-mer = ATGT (probability 4/5^4 = highest).

Continue for strings 3,4,5 → motifs: ACCT, ATGT, GCGT, ACGA, AGGT.

Score = total mismatches from consensus ACGT = 5 (much lower than initial).
After running for all starting k-mers in string 1, return BestMotifs with lowest score.

Worked Example 2: Gibbs Sampler Trace

t=5 sequences, l=8. Starting positions s=(7,11,9,4,1):
Seq 1: GTAAACAATATTTATAGC → l-mer at pos 7: ATATTTAT Seq 2: AAAATTTACCTTAGAAGG → l-mer
at pos 11: TAGAAGG (8-mer) Seq 3: CCGTACTGTCAAGCGTGG → l-mer at pos 9: CAAGCGTG Seq 4:
TGAGTAAACGACGTCCCA → l-mer at pos 4: GTAAACGA Seq 5: TACTTAACACCCTGTCAA → l-mer at pos
1: TACTTAAC

Step 1: Randomly remove Sequence 2.

Step 2: Build Profile P from seqs 1,3,4,5 (their l-mers at chosen positions).
Profile P (from lecture example):
Pos: 1 2 3 4 5 6 7 8 A: 1/4 2/4 2/4 3/4 1/4 1/4 1/4 2/4 C: 0 1/4 1/4 0 0 2/4 0 1/4 T:
2/4 1/4 1/4 1/4 2/4 1/4 1/4 1/4 G: 1/4 0 0 0 1/4 0 3/4 0 Consensus: T A A A T C G A

Step 3: Compute Prob(each 8-mer in Seq 2 | P):

• AAAATTTA (pos 1): 1/4·2/4·2/4·3/4·1/4·1/4·1/4·2/4 = 0.000732
• AAATTTAC (pos 2): 0.000122
• ACCTTAGA (pos 8): 0.000183
• All others: 0 (contain C at position 4 where P[C,4]=0, etc.)

Step 4: Normalize: ratios = 6 : 1 : 1.5

P(pos 1) = 6/8.5 = 0.706, P(pos 2) = 0.118, P(pos 8) = 0.176

Step 5: Sample from this distribution. Most likely → pos 1 (AAAATTTA).

Update s■ = 1. Repeat until convergence.
Key Formulas Quick Reference
Formula Definition

Prob(a|P) = Π■ P[a■,j] Probability l-mer a was generated by Profile P

Score(Motifs) = Σ■ (t − max_b count(b,j)) Total mismatches from consensus

Consensus(Motifs) Most common nucleotide in each column

Laplace: count + 1 before freq Pseudocounts to avoid zero probabilities

Σ■ r^i = (r^(n+1)−1)/(r−1) Geometric series (used in tree/complexity analysis)

C(n,m) = n!/(m!(n−m)!) Number of m-element subsets of n-element set

Tree nodes = (k^(L+1)−1)/(k−1) Vertices in complete k-ary tree of height L

dH(s,s') = |{j: s■≠s'■}| Hamming distance between strings s and s'

TotalDistance(w,DNA) = Σ■ min_i dH(w,s■■) Total distance for Median String problem

Good luck on your midterm! Remember: understand the intuition behind each algorithm, not just the mechanics. For
motif finding — why does randomization help? Because deterministic greedy gets stuck; randomness escapes local
optima.