Identity-by-descent (IBD) analysis finds stretches of DNA that two people inherited from the same recent ancestor — a shared block is a fossil of a common ancestor, and its length roughly tells you how long ago (a 10 cM block means a much more recent shared ancestor than a 2 cM block). Modern detectors scan biobank-scale cohorts pairwise and output, for every pair of individuals, a list of shared genomic intervals. The problem is that these pairwise outputs are mutually inconsistent. Detector A says persons 1 and 2 share chromosome position x; detector claims for pairs (2,3) and (1,3) at x may contradict this, because "shares an ancestor at position x" is mathematically an equivalence relation — it must partition people into disjoint groups — yet independent pairwise calls routinely violate it. These violations are the genetics analogue of "ghost geometry" in 3D vision, where faulty 2D masks propagate into floating, impossible 3D fragments (Yang et al., ShapeR): a false pairwise segment is a ghost ancestor that no real pedigree can realize.
This proposal treats cohort-level IBD inference as a segmentation-dependent reconstruction problem and fixes it with joint topological constraints. Per-pair segment calls are the noisy segmentation; the object being reconstructed is the cohort's inheritance structure — who descends from whom, where. The core claim: by enforcing, inside a single combinatorial optimization, the constraints that any valid inheritance pattern must satisfy, we can remove false segments, sharpen tract boundaries, and recover consistent ancestor-sharing cliques that pairwise pipelines cannot, at near-linear added cost.
Core Claim
No existing method enforces cross-individual consistency on IBD tracts. RaPID-Query answers single-pair queries fast (2.76 seconds against 487,409 UK Biobank individuals) but treats each pair independently. ChromoPainter/fineSTRUCTURE paint each individual as a mosaic of copied chunks and cluster the results, but the authors themselves note the resulting trees are summary clusters, not genealogies — and painting degrades under phasing switch errors. SparsePainter scales the copying model but keeps it per-individual. The closest structural precedent is Moral Lineage Tracing, which formulated cell lineage reconstruction as an integer linear program over a hypothesis graph and showed that topological cycle constraints beat sequential pipelines decisively (segmentation score 0.9722 vs. 0.7980; tracking score 0.9813 vs. 0.9206 on flywing data). But its "morality" constraint — cells divide, never merge — is precisely the wrong polarity for meiosis: going backward in time, two lineages must be allowed to coalesce into one common ancestor, while recombination splits one lineage into two ancestral donors. We import the cycle-inequality machinery but invert and redesign the genealogical constraints for sexual reproduction. This differs equally from Dip3D, which reconstructs the physical 3D folding of chromosomes from segmented sequencing reads with heuristic imputation rules — a spatial-contact problem, not a cohort genealogy problem, and with no topological guarantees on its output.
Research Program
We build a hypothesis graph whose nodes are candidate (haplotype, genomic interval) segments produced by an off-the-shelf PBWT-style detector, and whose edges assert "these two haplotypes share an ancestor across this interval." We then select a consistent subgraph by integer linear programming with three families of constraints.
First, equivalence constraints. For any three individuals $i, j, k$ and genomic position $x$, let $A_{ij}(x) \in \{0,1\}$ indicate selected shared ancestry. Consistency requires transitivity:
$$A_{ij}(x) + A_{jk}(x) - A_{ik}(x) \le 1$$
together with its two permutations. These are exactly the multicut-style cycle inequalities of Moral Lineage Tracing, applied along the genomic axis instead of the time axis: ancestor-sharing at a locus must decompose the cohort into disjoint cliques, one per ancestral haplotype copy. This is our "watertightness by construction" — the guarantee that no ghost clique survives, in the spirit of Chen et al.'s guaranteed single connected component, though our topology is combinatorial (an equivalence structure) rather than geometric manifoldness.
Second, partition constraints: the intervals selected on any one haplotype must form a non-overlapping tiling — each piece of a chromosome descends from exactly one ancestral path. Third, clique-coherence constraints: all members of one clique at one locus descend from a single ancestral copy, so their pairwise tract lengths around that locus must be mutually consistent with a single coalescence time; a clique mixing 12 cM and 1.5 cM claims is combinatorially suspect and gets penalized. Boundary evidence enters as a soft term adapted from CrossSDF's symmetric difference loss, which penalizes only inside/outside disagreements and is what let it fix boundary "laddering" on sparse cross-sections — here it regularizes where segment endpoints sit without dictating them. Because IBD cliques at nearby loci share members, the program decomposes into overlapping genomic windows solvable in parallel, keeping cohort cost near-linear; PBWTpaint's 41 CPU hours for >400,000 UK Biobank samples is the scalability reference the consistency stage must not dominate.
Baselines
The naive reference point is raw pairwise detector output with no consistency handling — the RaPID-Query pipeline as published, which reports a false negative rate of 0.016 and false positive rate of 0.012 on chromosome 20 of its simulated out-of-Africa panel; we rerun the same detector on the same data so the only difference is our post-detection consistency layer, and beating the reference means strictly lower false positive rate at false negative rate ≤ 0.016 while driving transitivity violations to zero by construction. The strongest existing competitor is the same RaPID-Query system taken at face value, because it is the accuracy and speed leader on this exact benchmark (2.76-second queries; 97.28% AUC separating 2nd- from 3rd-degree relatives; ≥97% correct categorization up to 4th degree) — we match its detector, its data, and its tuning budget, and count ourselves successful only if consistency filtering improves its own operating point. The strongest pipeline competitor is the natural simple alternative: a post-hoc transitivity filter that breaks or deletes segments wherever the raw output violates equivalence, run on identical raw output with equal compute — this isolates whether joint optimization (which can rescue evidence a filter destroys) or merely any correction is doing the work. Finally, an ablation removes the hard combinatorial constraints and keeps only the CrossSDF-style soft boundary penalty, isolating the topological ingredient itself; if the soft-only variant matches the full method, the combinatorial machinery is not earning its complexity.
Why not just…?
Why not just filter the inconsistent segments post-hoc? This is the sequential-pipeline alternative, and it is a real threat because it is cheap. The evidence against it is direct: Moral Lineage Tracing compared joint constrained optimization against a strong sequential baseline and joint won by large margins (0.9813 vs. 0.9206 tracking), because a post-hoc step cannot recover evidence — deleting a segment destroys true boundary information that joint inference could have used to move the boundary instead. Our own comparison against the post-hoc filter on the simulated panel is the decisive test; if the filter matches us, we will report that the simple route suffices.
Why not just use chromosome painting (ChromoPainter/SparsePainter), which already produces coherent per-individual mosaics? Painting is joint only within one individual; it never asserts cross-individual equivalence, so it cannot produce shared-ancestor cliques at all, and fineSTRUCTURE explicitly disclaims genealogical interpretation of its output. Painting also degrades under phasing switch errors, a known limitation we test directly by injecting switch errors. Still, SparsePainter is a serious competitor for downstream structure (haplotype PCs place UK birthplaces within 39.7 km vs. 77.4 km for SNP PCs), so we compare our consistency-corrected coancestry matrix against its painting matrix in the HGDP experiment on equal compute.
Why not just add a continuous smoothing or boundary loss (the direct CrossSDF transfer)? Smoothing fixes boundary jitter but cannot fix combinatorial infeasibility — a ghost clique of three mutually inconsistent pairwise segments is not a boundary problem, and no penalty on endpoints will remove it. But this alternative could plausibly capture most of the boundary-accuracy gains, which is why it appears as the designated ablation rather than an argument: the soft-only run quantifies exactly how much the hard equivalence constraints contribute beyond regularization.
Proposed Experiments
Experiment 1 runs on the simulated out-of-Africa whole-genome panel used by RaPID-Query (1,000 individuals, 86,265 bi-allelic sites), sweeping genotyping error and phasing switch rates. We measure transitivity violations in raw detector output (expectation: numerous, and correlated with false positives — if violations turn out rare and harmless, the proposal fails and we will say so), then false positive/negative rates against the reported 0.012/0.016, mean boundary displacement of surviving tracts, and clique length-homogeneity. Experiment 2 tests kinship degree classification, targeting an AUC above RaPID-Query's 97.28% for 2nd- versus 3rd-degree separation, since consistent cliques should sharpen degree signals. Experiment 3 runs on the HGDP panel (938 individuals, 53 labeled populations), where fineSTRUCTURE recovered 226 distinct populations; we ask whether clustering on the consistency-corrected coancestry matrix recovers comparable fine structure while remaining robust to injected phasing switch errors that break painting, using identical compute and MCMC budgets. Experiment 4 scales the consistency stage on synthetic UK Biobank-sized input, requiring it to add no more than a small constant factor to the detector's runtime, with PBWTpaint's 41 CPU hours as the reference point. The decisive check across all four: hard-constraint inference must beat both the raw output and the post-hoc filter on the same data — otherwise the honest conclusion is that topological consistency, however elegant, is not needed here.
References
- Automatic 3D Indoor Scene Modeling From Single Panorama
- ShapeR: Robust Conditional 3D Shape Generation from Casual Captures
- RaPID-Query for fast identity by descent search and genealogical analysis
- Inference of Population Structure using Dense Haplotype Data
- Sparse haplotype-based fine-scale local ancestry inference at scale reveals recent selection on immune responses
- Moral Lineage Tracing
- Reconstruction of Diploid High-Order 3D Genome Interactions from Long Noisy Concatemers
- Guaranteed Simply Connected Mesh Reconstruction from an Unorganized Point Cloud
- CrossSDF: 3D Reconstruction of Thin Structures From Cross-Sections