Pattern Finding in DNA

Finding the Replication Origin

Before a cell divides it copies its genome, and copying always starts at a fixed location called the origin of replication (ori). Locating ori in a raw genome string turns out to be a clean computational problem that can be solved by counting just two of the four nucleotides.

As replication proceeds, one of the two template strands is left single-stranded for much longer than the other. Cytosine (C) is chemically fragile in that exposed state: it slowly deaminates into thymine (T), so this strand steadily loses its C's while its G count stays put. Reading along it, G therefore ends up outnumbering C. That imbalance runs one way on the stretch leading into ori and the other way on the stretch leading out, which is what lets us pinpoint it.

Define the skew at each position as the running count of G minus the running count of C, scanning left to right: add $1$ for each G and subtract $1$ for each C. The skew falls along the C-rich stretch leading into ori and rises along the G-rich stretch coming out of it, so the minimum of the skew marks ori.

Press play to walk along a synthetic genome and watch the curve take shape. Green bases (G) push it up, red bases (C) pull it down, and the orange marker tracks the lowest point seen so far, which is the predicted ori. Use New genome for a fresh sequence.

On a real genome the curve is noisier but shows the same overall valley, and its minimum lands very close to the true origin. A single $O(n)$ scan is enough to narrow ori down to a small region, without any alignment or pattern matching, just one running count.

Greedy Motif Search

A transcription factor controls many genes by binding a short pattern, a motif, that recurs with mutations in the regulatory region upstream of each gene. Given one such region per gene as a collection of DNA strings, the goal is to recover the shared motif of length $k$.

A candidate solution is one $k$-mer chosen from each string, aligned into a matrix with one row per string. The score counts, column by column, the letters that differ from the most common one, so a well-conserved motif scores low. We want the candidate with the smallest score, but checking every combination is exponential in the number of strings.

Greedy motif search gives up that guarantee for speed. From a single starting $k$-mer it builds one candidate by scanning the strings in order:

1. Take a $k$-mer of the first string as the seed; it becomes the first row of the candidate.
2. Count each base in each column of the rows chosen so far, then turn the counts into a profile of probabilities. With $m$ rows chosen, a column entry is $(\text{count}+1)/(m+4)$ rather than the plain $\text{count}/m$: the extra $+1$ in every cell, a pseudocount, stops a base that happens to be absent from a column from forcing the whole product to zero and discarding an otherwise strong candidate.
3. Move to the next string and score every $k$-mer by multiplying its profile entries, one per column; add the $k$-mer with the largest product.
4. Repeat steps 2 and 3 down the remaining strings to complete the candidate, then score it.

The whole process runs once for every $k$-mer of the first string as the seed, and the lowest-scoring candidate found over all seeds is the answer.