Patent ID: 8527547

Claim:
A computer-implemented method for constructing an ancestral recombination graph, the method comprising: 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.