A forest is more than its trees: haplotypes and ancestral recombination graphs

Foreshadowing haplotype-based methods of the genomics era, it is an old observation that the "junction" between two distinct haplotypes produced by recombination is inherited as a Mendelian marker. In a genealogical context, this recombination-mediated information reflects the persistence of ancestral haplotypes across local genealogical trees in which they do not represent coalescences. We show how these non-coalescing haplotypes ("locally-unary nodes") may be inserted into ancestral recombination graphs, a compact but information-rich data structure describing the genealogical relationships among recombinant sequences. The resulting ancestral recombination graphs are smaller, faster to compute with, and the additional ancestral information that is inserted is nearly always correct where the initial ancestral recombination graph is correct. We provide efficient algorithms to infer locally-unary nodes within existing ancestral recombination graphs, and explore some consequences for ancestral recombination graphs inferred from real data. To do this, we introduce new metrics of agreement and disagreement between ancestral recombination graphs that, unlike previous methods, consider ancestral recombination graphs as describing relationships between haplotypes rather than just a collection of trees.