Global ancestry determination system
An input genotype is divided into a plurality of windows, each including a sequence of SNPs. For each window, a diploid HMM is computed based on genotypes and/or phased haplotypes to determine a probability of a haplotype sequence being associated with a particular label. For example, the diploid HMM for a window is used to determine the emission probability that the window corresponds to a set of labels. An inter-window HMM, with a set of states for each window, is computed. Labels are assigned to the input genotype based on the inter-window HMM. Upper and lower bounds are estimated to produce a range of likely percentage values an input can be assigned to a given label. Confidence values are determined indicating a likelihood that an individual inherits DNA from a certain population. Maps are generated with polygons representing regions where a measure of ethnicity of population falls within specific ranges.
1. A computer implemented method comprising:
accessing a genotype dataset associated with an individual;
dividing the genotype dataset into a plurality of windows, each window comprising a set of single nucleotide polymorphisms (SNPs);
determining a pair of phased haplotype datasets from the plurality of windows of genotype dataset;
generating, using one or more processors and the pair of phased haplotype datasets, a directed acyclic graph that comprises:
(i) a plurality of node groups, each node group representing one of the windows, each node group comprising a plurality of nodes, each node representing a state of the window represented by the node group, the state comprising:
(1) a first parent label,
(2) a second parent label, and
(3) a switch label representing a switching of order of the first parent label and the second parent label,
(ii) a plurality of edges, each edge connecting a first node to a second node, each edge representing a transition from the first node to the second node,
wherein each node is associated with an emission probability determined based on the pair of phased haplotype datasets; and
generating information on ethnic origin of the individual using the directed acyclic graph.
2. The computer implemented method of claim 1 , wherein the emission probability associated with a particular node corresponding to a particular window represents a likelihood of the particular window corresponding to a pair of haplotype sequences given the state having the first parent label, the second parent label, and the switch label.
3. The computer implemented method of claim 2 , wherein the plurality of nodes in each node group represents permutations of different first parent labels, second parent labels, and switch labels.
4. The computer implemented method of claim 1 , wherein the switching of order of the first parent label and the second parent label corresponds to a switching of the first and second parent labels from one node group to a next node group.
5. The computer implemented method of claim 1 , wherein generating the directed acyclic graph further comprises:
initiating label probabilities, each label probability for a particular label representing a probability distribution of the particular label among other possible labels;
initiating label change probabilities, each label change probability representing a likelihood of a change of label from one window to another window;
initiating a label switch probability representing a likelihood of a switching of order of the first parent label and the second parent label from one window to another window;
adjusting the label probabilities, label change probabilities, and the label switch probability through iterations;
determining transition probabilities based on the label probabilities, the label change probabilities, and the label switch probability, each transition probability associated with a particular edge and representing a likelihood of the first node connected by the particular edge from one node group transitioning to the second node connected by the particular edge from another node group; and
connecting the nodes with edges, each edge corresponding to a determined transition probability.
6. The computer implemented method of claim 1 , wherein the information of ethnic origin comprises a set of possible ethnic origins of the individual and percentage compositions of the set of the possible ethnic origins.
7. The computer implemented method of claim 1 , where generating the information on ethnic origin of the individual using the directed acyclic graph comprises:
determining a Viterbi path for the directed acyclic graph based on a likelihood of the pair of phased haplotype datasets of the individual traversing nodes in the directed acyclic graph along the Viterbi path;
determining a likelihood of the individual having a particular ethnic origin based on the Viterbi path; and
displaying the likelihood of the individual having the particular ethnic origin as the information of ethnic origin.
8. A computer implemented method, comprising:
accessing a set of reference panel samples;
dividing each reference panel sample into a plurality of windows, each window comprising a set of single nucleotide polymorphisms (SNPs);
computing, for each window, a diploid hidden Markov model (HMM) based on the set of reference panel samples that correspond to the each window;
calculating, for each diploid state in each diploid HMM, diploid state probabilities using the diploid HMM;
calculating, for each window, a set of annotations based on the diploid state probabilities, each annotation corresponding to a label; and
determining emission probabilities of a pair of phased haplotypes for an inter-window HMM based on the set of annotations and the pair of phased haplotypes.
9. The computer implemented method of claim 8 , wherein the inter-window HMM comprises:
(i) a plurality of node groups, each node group representing one of the windows, each node group comprising a plurality of nodes, each node representing a state of the window represented by the node group, the state comprising:
(1) a first parent label,
(2) a second parent label, and
(3) a switch label representing a switching of order of the first parent label and the second parent label,
(ii) a plurality of edges, each edge connecting a first node to a second node, each edge representing a transition from the first node to the second node,
wherein each node is associated with one of the emission probabilities.
10. The computer implemented method of claim 9 , further comprising:
computing the inter-window HMM based on the emission probabilities; and
using a Viterbi algorithm to determine transition probabilities between the nodes.
11. The computer implemented method of claim 9 , wherein the emission probability associated with a particular node corresponding to a particular window represents a likelihood of the particular window corresponding to a pair of haplotype sequences given the state having the first parent label, the second parent label, and the switch label.
12. The computer implemented method of claim 9 , further comprising:
computing, for each window, a haploid Markov model, wherein each diploid state in the diploid hidden Markov model corresponds to a pair of haploid states from the haploid Markov model.
13. The computer implemented method of claim 10 , wherein using the Viterbi algorithm to determine the transition probabilities between the nodes are iteratively repeated for a predetermined number of times.
14. The computer implemented method of claim 10 , wherein using the Viterbi algorithm to determine the transition probabilities between the nodes comprises:
determining a Viterbi path that traverses the inter-window HMM based on a probability of traversing a particular sequence of nodes that represent the path.
15. A non-transitory computer readable storage medium storing a directed acyclic graph and instructions, when executed by one or more processors, cause the processor to use the directed acyclic graph to assign one or more labels to a sample of genotype data, the directed acyclic graph comprising:
a plurality of node groups, each node group representing a window of genetic segment, each window comprising a set of single nucleotide polymorphisms (SNPs), each node group comprising a plurality of nodes, each node representing a state represented by the node group, the state comprises:
(1) a first parent label,
(2) a second parent label, and
(3) switch label representing a switching of order of the first parent label and the second parent label,
wherein each node is associated with an emission probability representing a likelihood of a pair of haplotypes corresponding to the window given the first parent label, the second parent label, and the switch label for the each node; and
a plurality of edges, each edge connecting a first node of a first node group to a second node of a second node group, each edge being associated with a transition probability representing a likelihood of transition from the first node to the second node.
16. The non-transitory computer readable storage medium of claim 15 , wherein the plurality of nodes in each node group represents permutations of different first parent labels, second parent labels, and switch labels.
17. The non-transitory computer readable storage medium of claim 15 , wherein each of the first parent labels and the second parent labels corresponds to an ethnic origin group.
18. The non-transitory computer readable storage medium of claim 15 , wherein the transition probability is determined based on:
P
(
U
w
(
p
,
q
,
z
)
→
U
w
+
1
(
p
′
,
q
′
,
z
′
)
)
=
{
π
p
′
m
×
π
q
′
f
2
if
C
(
w
)
≠
C
(
w
+
1
)
(
1
-
τ
m
)
×
(
1
-
τ
f
)
×
(
1
-
τ
z
)
if
C
(
w
)
=
C
(
w
+
1
)
,
p
=
p
′
,
q
=
q
′
,
z
=
z
′
(
1
-
τ
m
)
×
(
1
-
τ
f
)
×
τ
z
if
C
(
w
)
=
C
(
w
+
1
)
,
p
=
p
′
,
q
=
q
′
,
z
≠
z
′
τ
m
×
(
1
-
τ
f
)
×
(
1
-
τ
z
)
×
π
p
′
m
Σ
1
p
′
-
1
π
k
m
+
Σ
p
′
+
1
K
π
k
m
if
C
(
w
)
=
C
(
w
+
1
)
,
p
≠
p
′
,
q
=
q
′
,
z
=
z
′
τ
m
×
(
1
-
τ
f
)
×
τ
z
×
π
p
′
m
Σ
1
p
′
-
1
π
k
m
+
Σ
p
′
+
1
K
π
k
m
if
C
(
w
)
=
C
(
w
+
1
)
,
p
≠
p
′
,
q
=
q
′
,
z
≠
z
′
(
1
-
τ
m
)
×
τ
f
×
(
1
-
τ
z
)
×
π
q
′
m
Σ
1
q
′
-
1
π
k
m
+
Σ
q
′
+
1
K
π
k
f
if
C
(
w
)
=
C
(
w
+
1
)
,
p
=
p
′
,
q
≠
q
′
,
z
=
z
′
(
1
-
τ
m
)
×
τ
f
×
τ
z
×
π
q
′
m
Σ
1
q
′
-
1
π
k
f
+
Σ
q
′
+
1
K
π
k
f
if
C
(
w
)
=
C
(
w
+
1
)
,
p
=
p
′
,
q
≠
q
′
,
z
≠
z
′
0
if
C
(
w
)
=
C
(
w
+
1
)
,
p
≠
p
′
,
q
≠
q
′
.
19. The non-transitory computer readable storage medium of claim 18 , wherein τ m , τ ƒ , and τ z are determined based on an iterative process.
20. The non-transitory computer readable storage medium of claim 15 , wherein the emission probability is determined based on:
E
x
,
w
(
p
,
q
,
z
)
=
{
E
x
1
,
w
(
p
)
×
E
x
2
,
w
(
q
)
if
z
=
0
E
x
1
,
w
(
q
)
×
E
x
2
,
w
(
p
)
if
z
=
1
.
21. The computer implemented method of claim 1 , wherein the directed acyclic graph is a hidden Markov model (HMM).
22. The non-transitory computer readable storage medium of claim 15 , wherein the directed acyclic graph is a hidden Markov model (HMM).