Align portion part 1

Alignment

Detects Homology. Including how function, history and mechanism get transferred between them

1. X is a few plausible edits away from Y ?

2. If we trim off the ends, X and Y are similar in the sense of #1?

3. If we mask out the “boringly similar” parts (runs of repeated characters), they are similar in thesense of #2?

1. Global alignment

2. Local alignment

3. Masked local alignment

uninformative DNA, runs like AAAAAAAA or CACACACA are

common. Protein motifs like coiled-coils, Ser/Pro rich linkers, or poly-glutamine tracts happen due to mutational instability and convergent selection. How to fix?

Low-complexity sequence has low entropy. It scores high while carrying no homology. two proteins can share a coiled-coil and be otherwise unrelated. Standard practice is to mask it out (dust for DNA, seg for protein) first.

Masking Mechanically

Slide a 30 base window along & score entropy. Uniform DNA sits near 2 bits/base; the AAAAA run reads 0 (because one letter is certain). Everything under a threshold is masked before the search. Entropy is understimated. Same with proteins sequence

Masking for coiled coil

A coiled coil is compositionally ordinary and periodic, (score 0 throws the ordering away). Score the heptad instead (7 base repeat)

Horizontal VS Vertical slices

horizontal slice = 1 seq, many positions (TTTTTTT). No alignment

vertical slice = one position, many seq. (C Alignemnt needed.

C

C)

Run of 1 letter (horizontal) = low colpexity = mask it out

Same base in many copies (vertical) = conserved

Total Score

Total score = Sum of [substitution score(column) - gap penalties]

Summing column by column assumes positions evolve independently.

account for varying divergence in DNA vs Proteins

• Two Tc1 copies (DNA): simple match / mismatch scores. Extension: time dependent nucleotide subs models (Jukes–Cantor, Kimura, HKY).

• Two transposase proteins: a distance binned scoring matrix such as BLOSUM62, or a time dependent model like Dayhoff’s PAM, or LG08.

BLOSUM n% matrix

fits divergence. collaps sequences more thsan n% identical. BLOSUM45, 50, 62, 80, 90. blocky structure clusters amino acids into groups (hydrophobic, small, charged).

For PYLO data

don’t bin the data: model the process. Fit a single continuous time substitution process to all the data at once, then evaluate

it at whatever divergence t

Gap penalty

Each gap residue costs −d. A linear gap of length g scores

γ(g) = − g · d

ex: 2 gaps here, each of length g = 1. With d = 2 they cost γ(1) = −2 apiece, −4 across the alignment.

edit distances measures dissimilarity between strings

Hamming distance between two equal-length strings is the number of positions at which they differ

Levenshtein distance between two strings is the minimum number of single character insertions, deletions, or substitutions

How do we make sure growth remians linear?

f (n) = Og(n) means: constant c > 0 such that f (n) ≤ c g(n) for all

large enough n. It is an upper bound on growth: constants and lower-order terms dropped, because they stop mattering as n grows.

Diagonal Alignment path

The path is rewarded for running diagonally through good cells and pays for every sideways detour. The best path into a cell must arrive from one of its three neighbours.

Sore values

Match = +1

Mismatch = -1

Gap = d = -2

Needleman–Wunsch

Matrix with +1, -1, -2 scores that add up and show worst/best paths. Global

Which path is alignemnt?

arg-max direction in each cell while filling; then follow those pointers from the bottom-right corner (m, n) back to the origin (0, 0). That path is the alignment. (basically read reverse)

doing O(1) work per cell: O(mn) time and memory.

Hirschberg’s divide-and-conquer trick gets the optimal alignment in O(min(m, n)) space

wavefront algorithms run in O(ns) time for alignment score s

Smith–Waterman

Local alignment. All positive. Path is 1234567….

Affine penalty

To account for InDel runs (T——-C) not just singular(T-A) position.

γ(g) = − A − B (g − 1)

gap gap

opening extension

A is the cost of the first gap residue (open), B the cost of each extension after it. The first residue is high; the rest are cheap.

g = d = length of gap.

Keep three matrices, one per state:

• M — last column was a match / mismatch,

• Ix — an insertion in x (xi aligned to nothing)

• Iy — an insertion in y (yj aligned to nothing)