Read-Based Phasing by MEC

Each read comes from one of the two haplotypes of a diploid sample and shows the reference (R) or alternate (A) allele at the heterozygous SNPs it covers. The page phases the SNPs by minimising the number of read bases that disagree with the two haplotypes. It does this by alternating between choosing the best phase for every read given the SNP phases, and the best phase for every SNP given the read phases. Random restarts help it escape local optima. Keys: → step, ← back, f run all, r reset, s random reset (new initial SNP phases).

1 Reads

One read per line: R = reference allele, A = alternate allele, - = SNP not on the read

Restarts Seed

Haplotype 1 to start restart 1 from (R/A per SNP; empty = random)

2 Model and algorithm

δ_i ∈ {1, −1} is the phase of SNP i: 1 if haplotype 1 carries the reference allele, −1 if it carries the alternate. σ_k ∈ {1, −1} is the phase of read k: 1 if it comes from haplotype 1, −1 from haplotype 2. Coding R as 1 and A as −1, read k should show δ_iσ_k at SNP i, and each disagreement is an error: q_ki(δ_iσ_k) = 0 if the read base b_ki = δ_iσ_k, and 1 otherwise.

MEC: find δ and σ that minimise Σ_k Σ_{i∈I_k} q_ki(δ_iσ_k), where I_k is the set of SNPs on read k. The problem is NP-hard, but the read phases are easy given the SNP phases, and vice versa:

Randomly assign SNP phase
Infer optimal read phase
If flipping the phases of some SNPs improves, flip them and go to step 2
Go to step 1 for enough iterations (to avoid local optima)

Read-based phasing: minimum error correction (MEC)

1 Reads

2 Model and algorithm

3 Reads, read phases and SNP phases

4 Restarts