A Hi-C read pair links two heterozygous SNPs that may be far apart. If both of its bases sit on the same haplotype, it is consistent with the phasing; otherwise it counts as one error. The SNPs form a graph whose edges carry the read counts. Flipping the SNPs on one side of a cut changes the number of errors by the total weight of the edges the cut crosses. The algorithm therefore repeatedly finds a cut through the most negative weight and flips it. Drag the SNPs in the graph to rearrange it. Keys: → step, ← back, f run all, r reset, s random reset (new initial SNP phases).
δi ∈ {1, −1} is the phase of SNP i: 1 if haplotype 1 carries the reference allele, −1 if it carries the alternate. Read k links SNPs i and j with bases bki, bkj (R = 1, A = −1). It is consistent if bkibkjδiδj = 1: R-R or A-A at two SNPs of the same phase, or R-A or A-R at two SNPs of opposite phase. Otherwise it is one error.
Graph. Nodes are SNPs, and an edge joins two SNPs linked by at least one read. With Wij = Σk bkibkj over those reads, edge i–j has weight wij = δiδjWij, which is +1 for each consistent read and −1 for each inconsistent one under the current phase. Flipping a set S of SNPs negates every edge between S and the rest, so it changes the error count by the total weight of that cut. The best flip is the cut of most negative weight. With negative weights this minimum cut is a max-cut problem, which is NP-hard, so the cut is found greedily: