Sampling the space of ancestral recombination graphs

An information processing system for constructing an ancestral recombination graph, the information processing system comprising:

• memory;
• a processor communicatively coupled to the memory;
• and
• an ancestral recombination graph constructor communicatively coupled to the memory and the processor, the ancestral recombination graph constructor being configured to:
• receive a value K, where K is a positive integer number of extant units representing K individuals of a current generation being studied;
• receive M non-mixing segments in the K extant units, where M is a positive integer number;
• generate K vertices V, each of the K extant units being initially assigned to the K vertices V, and K lineages for each of M trees being associated with each of the K vertices;
• and
• construct an ancestral recombination graph based on at least the K extant units and the M non-mixing segments,
• wherein constructing the ancestral recombination graph comprises repeating, until only one lineage survives for each of the M trees, a process comprising:
• randomly selecting one tree from the M trees;
• randomly selecting a first vertex v1 and a second vertex v2 from the vertices V;
• combining two adjoining segments in the M non-mixing segments of the first vertex v1 and the second vertex v2 together into a single vertex;
• generating a separate vertex for at least one remaining segment in each of the M non-mixing segments of the first vertex v1 and the second vertex v2;
• and
• updating the vertices V to be vertices that are non-interior vertices, an interior vertex being a vertex for which all the lineages being transmitted therethrough have an ancestor.

A non-transitory computer-readable medium encoded with a program for constructing an ancestral recombination graph, the program comprising instructions for:

• receiving a value K, where K is a positive integer number of extant units representing K individuals of a current generation being studied;
• receiving M non-mixing segments in the K extant units, where M is a positive integer number;
• generating K vertices V, each of the K extant units being initially assigned to the K vertices V, and K lineages for each of M trees being associated with each of the K vertices;
• and
• constructing an ancestral recombination graph based on at least the K extant units and the M non-mixing segments,
• wherein constructing the ancestral recombination graph comprises repeating, until only one lineage survives for each of the M trees, a process comprising:
• randomly selecting one tree from the M trees;
• randomly selecting a first vertex v1 and a second vertex v2 from the vertices V;
• combining two adjoining segments in the M non-mixing segments of the first vertex v1 and the second vertex v2 together into a single vertex;
• generating a separate vertex for at least one remaining segment in each of the M non-mixing segments of the first vertex v1 and the second vertex v2;
• and
• updating the vertices V to be vertices that are non-interior vertices, an interior vertex being a vertex for which all the lineages being transmitted therethrough have an ancestor.