Sampling the space of ancestral recombination graphs
View Patent ↗A method is provided for constructing an ancestral recombination graph. A value K is received representing K extant units. M non-mixing segments are also received. K vertices V are generated. K lineages for each of M trees are associated with each of the K vertices. An ancestral recombination graph is constructed. To construct the ancestral recombination graph, there is repeated, until only one lineage survives for each of the M trees, a process that includes the following. A tree is randomly selected tree. A first vertex v 1 and a second vertex v 2 are randomly selected. Two adjoining segments in the M non-mixing segments of the first and second vertices are combined together into a single vertex. A separate vertex is generated for at least one remaining segment in each of the M non-mixing segments of the first and second vertices. The vertices V are updated to be vertices that are non-interior vertices.
1. 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.
2. The method of claim 1 , wherein the process further comprises increasing a height of the ancestral recombination graph by an increment of 1.
3. The method of claim 1 , wherein the process further comprises determining a waiting time H 2 of the first vertex v 1 and the second vertex v 2 to have a common ancestor, where
H
2
=
min
t
=
1
,
…
,
n
t
H
t
,
n
t
=
T
,
T={1≦t≦M|L t >1}, t=1, 2, . . . , M, and for each t, L t is initialized to K, wherein H t is a value of a random variable, and wherein L t is a number of lineages for a tree t at a given iteration.
4. The method of claim 3 ,
wherein the common ancestor is the single vertex into which the two adjoining segments in the M non-mixing segments of the first vertex v 1 and the second vertex v 2 have been combined, and
the single vertex is placed in the ancestral recombinations graph at a depth corresponding to the waiting time.
5. The method of claim 3 , wherein a probability that the first vertex v 1 and the second vertex v 2 have a common ancestor is
P
(
H
t
≤
x
)
=
1
-
ⅇ
-
(
L
r
2
)
x
,
wherein L r is a number of lineages of a randomly selected tree r.
6. The method of claim 3 , wherein the waiting time H 2 is measured in generations.
7. The method of claim 1 , further comprising:
after the process ends, determining a root node of the ancestral recombination graph based on a probability
P
(
H
n
v
≤
t
)
=
∑
k
=
1
n
v
(
-
1
)
k
-
1
(
2
k
-
1
)
ⅇ
-
k
(
k
-
1
)
t
/
2
(
n
v
-
1
)
…
(
n
v
-
(
k
-
1
)
)
(
n
v
+
1
)
…
(
n
v
+
(
k
-
1
)
)
wherein H n v is a waiting time of n v vertices to have a common ancestor, where n v is assigned K, and t=1, 2, . . . , M.
8. The method of claim 1 , further comprising annotating edges of the ancestral recombination graph with genetic events.
9. 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 v 1 and a second vertex v 2 from the vertices V;
combining two adjoining segments in the M non-mixing segments of the first vertex v 1 and the second vertex v 2 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 v 1 and the second vertex v 2 ; 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.
10. The information processing system of claim 9 , wherein the process further comprises determining a waiting time H 2 of the first vertex v 1 and the second vertex v 2 to have a common ancestor, where
H
2
=
min
t
=
1
,
…
,
n
t
H
t
,
n
t
=
T
,
T={1≦t≦M|L t >1}, t=1, 2, . . . , M, and for each t, L t is initialized to K wherein H t is a value of a random variable, and wherein L t is a number of lineages for a tree t at a given iteration.
11. The information processing system of claim 10 , wherein a probability that the first vertex v 1 and the second vertex v 2 have a common ancestor is
P
(
H
t
≤
x
)
=
1
-
ⅇ
-
(
L
r
2
)
x
,
wherein L r is a number of lineages of a randomly selected tree r.
12. The information processing system of claim 9 , wherein the method performed by the ancestral recombination graph constructor further comprises:
after the process ends, determining a root node of the ancestral recombination graph based on a probability
P
(
H
n
v
≤
t
)
=
∑
k
=
1
n
v
(
-
1
)
k
-
1
(
2
k
-
1
)
ⅇ
-
k
(
k
-
1
)
t
/
2
(
n
v
-
1
)
…
(
n
v
-
(
k
-
1
)
)
(
n
v
+
1
)
…
(
n
v
+
(
k
-
1
)
)
wherein H n v is a waiting time of n v vertices to have a common ancestor, where n v is assigned K, and t=1, 2, . . . , M.
13. 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 v 1 and a second vertex v 2 from the vertices V;
combining two adjoining segments in the M non-mixing segments of the first vertex v 1 and the second vertex v 2 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 v 1 and the second vertex v 2 ; 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.
14. The non-transitory computer-readable medium of claim 13 , wherein the process further comprises increasing a height of the ancestral recombination graph by an increment of 1.
15. The non-transitory computer-readable medium of claim 13 , wherein the process further comprises determining a waiting time H 2 of the first vertex v 1 and the second vertex v 2 to have a common ancestor, where
H
2
=
min
t
=
1
,
…
,
n
t
H
t
,
n
t
=
T
,
T={1≦t≦M|L t >1}, t=1, 2, . . . , M, and for each t, L t is initialized to K wherein H t is a value of a random variable, and wherein L t is a number of lineages for a tree t at a given iteration.
16. The non-transitory computer-readable medium of claim 15 ,
wherein the common ancestor is the single vertex into which the two adjoining segments in the M non-mixing segments of the first vertex v 1 and the second vertex v 2 have been combined, and
the single vertex is placed in the ancestral recombinations graph at a depth corresponding to the waiting time.
17. The non-transitory computer-readable medium of claim 15 , wherein a probability that the first vertex v 1 and the second vertex v 2 have a common ancestor is
P
(
H
t
≤
x
)
=
1
-
ⅇ
-
(
L
r
2
)
x
,
wherein L r is a number of lineages of a randomly selected tree r.
18. The non-transitory computer-readable medium of claim 15 , wherein the waiting time H 2 is measured in generations.
19. The non-transitory computer-readable medium of claim 13 , further comprising:
after the process ends, determining a root node of the ancestral recombination graph based on a probability
P
(
H
n
v
≤
t
)
=
∑
k
=
1
n
v
(
-
1
)
k
-
1
(
2
k
-
1
)
ⅇ
-
k
(
k
-
1
)
t
/
2
(
n
v
-
1
)
…
(
n
v
-
(
k
-
1
)
)
(
n
v
+
1
)
…
(
n
v
+
(
k
-
1
)
)
wherein H n v is a waiting time of n v vertices to have a common ancestor, where n v is assigned K, and t=1, 2, . . . , M.
20. The non-transitory computer-readable medium of claim 13 , further comprising annotating edges of the ancestral recombination graph with genetic events.