Back to results
US 12,724,831 B2Granted
Segment-specific shared data inheritance determination
AssigneeAncestry.com DNA, LLC
InventorYong Wang
Life of this patent
Estimating the term…
Abstract
A computing server may receive a target data instance. The computing server may scan through a data store to identify a related data instance that shares one or more matched data strings with the target data instance. The computing server may determine one or more windows of data locality to which the one or more matched data strings belong. The computing server may determine one or more data group labels for the one or more windows of data locality that includes the one or more matched data strings. The computing server may store data group information of the matched data strings between the target data instance and the related data instance.
Claims20
A computer-implemented method, comprising:
- receiving a target genetic dataset of a target individual;
- scanning through a genetic data store comprising over 10,000 genetic data instances to identify one or more related individuals who share one or more identity-by-descent (IBD) segments with the target individual, each shared IBD segment having a length that satisfies a threshold length measured in centimorgans (cM);
- determining, for the one or more shared IBD segments, one or more windows of genomic locality to which the one or more shared IBD segments belong;
- and
- determining one or more ethnicity labels for each shared IBD segment of the one or more shared IBD segments based on the one or more windows of genomic locality, wherein determining the one or more ethnicity labels comprises:
- for each window of genomic locality of the one or more windows of genomic locality, computing an emission probability for each candidate ethnicity label;
- representing an inter-window hidden Markov model (HMM) as a directed acyclic graph comprising node groups corresponding to respective windows of genomic locality, each node in a node group representing a candidate ethnicity label and an associated likelihood derived from the emission probabilities, and edges between node groups representing transition probabilities between candidate ethnicity labels for adjacent windows of genomic locality;
- and
- selecting, from the directed acyclic graph, a sequence of candidate ethnicity labels across the one or more windows of genomic locality using a dynamic programming algorithm;
- and
- storing the one or more ethnicity labels of the shared IBD segments between the target individual and the related individual, each of the ethnicity labels being a local ethnicity label that is assigned to a window of genomic locality.
8 more elements
A system, comprising:
- a computing server comprising memory and one or more processors, the memory configured to store code comprising instructions, wherein the instructions, when executed by the one or more processors, cause the one or more processors to perform steps comprising:
- receiving a target genetic dataset of a target individual;
- scanning through a genetic data store comprising over 10,000 genetic data instances to identify one or more related individuals who share one or more identity-by-descent (IBD) segments with the target individual, each shared IBD segment having a length that satisfies a threshold length measured in centimorgans (cM);
- determining, for the one or more shared IBD segments, one or more windows of genomic locality to which the one or more shared IBD segments belong;
- determining one or more ethnicity labels for each shared IBD segment of the one or more shared IBD segments based on the one or more windows of genomic locality, wherein determining the one or more ethnicity labels comprises:
- for each window of genomic locality of the one or more windows of genomic locality, computing an emission probability for each candidate ethnicity label;
- representing an inter-window hidden Markov model (HMM) as a directed acyclic graph comprising node groups corresponding to respective windows of genomic locality, each node in a node group representing a candidate ethnicity label and an associated likelihood derived from the emission probabilities, and edges between node groups representing transition probabilities between candidate ethnicity labels for adjacent windows of genomic locality;
- and
- selecting, from the directed acyclic graph, a sequence of candidate ethnicity labels across the one or more windows of genomic locality using a dynamic programming algorithm;
- and
- storing the one or more ethnicity labels of the shared IBD segments between the target individual and the related individual, each of the ethnicity labels being a local ethnicity label that is assigned to a window of genomic locality;
- and
- a graphical user interface in communication with the computing server, the graphical user interface configured to display the one or more ethnicity labels of the shared IBD segments between the target individual and the related individual.
10 more elements
A non-transitory computer readable medium configured to store code comprising instructions, wherein the instructions, when executed by one or more processors, cause the one or more processors to perform steps comprising:
- receiving a target genetic dataset of a target individual;
- scanning through a genetic data store comprising over 10,000 genetic data instances to identify one or more related individuals who share one or more identity-by-descent (IBD) segments with the target individual, each shared IBD segment having a length that satisfies a threshold length measured in centimorgans (cM);
- determining, for the one or more shared IBD segments, one or more windows of genomic locality to which the one or more shared IBD segments belong;
- and
- determining one or more ethnicity labels for each shared IBD segment of the one or more shared IBD segments based on the one or more windows of genomic locality, wherein determining the one or more ethnicity labels comprises:
- for each window of genomic locality of the one or more windows of genomic locality, computing an emission probability for each candidate ethnicity label;
- representing an inter-window hidden Markov model (HMM) as a directed acyclic graph comprising node groups corresponding to respective windows of genomic locality, each node in a node group representing a candidate ethnicity label and an associated likelihood derived from the emission probabilities, and edges between node groups representing transition probabilities between candidate ethnicity labels for adjacent windows of genomic locality;
- and
- selecting, from the directed acyclic graph, a sequence of candidate ethnicity labels across the one or more windows of genomic locality using a dynamic programming algorithm;
- and
- storing the one or more ethnicity labels of the shared IBD segments between the target individual and the related individual, each of the ethnicity labels being a local ethnicity label that is assigned to a window of genomic locality.
8 more elements
Dependencies are inferred from the claim text.