# US 2020/0286579 A1 · Global ancestry determination system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2020/0286579 A1
- Document ID: US20200286579A1
- Status: Published application
- Kind: A1
- Application number: 15/931,009
- Filed: 2020-05-13
- Published: 2020-09-10
- Earliest claimed: 2018-09-11
- Assignees: Ancestry.com DNA, LLC
- Applicants: Ancestry.com DNA, LLC
- Inventors: Shiya Song; Keith D. Noto; Yong Wang
- Web page: https://patentgrep.com/patent/US20200286579A1

## CPC

- C12Q 1/6869: Methods for sequencing
- G16B 5/20: Probabilistic models
- C12Q 1/6827: for detection of mutation or polymorphism
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G16B 5/00: ICT specially adapted for modelling or simulations in systems biology, e.g. gene-regulatory networks, protein interaction networks or metabolic networks
- G16B 10/00: ICT specially adapted for evolutionary bioinformatics, e.g. phylogenetic tree construction or analysis
- G16B 20/20: Allele or variant detection, e.g. single nucleotide polymorphism [SNP] detection
- G16B 20/40: Population genetics; Linkage disequilibrium
- G16B 30/00: ICT specially adapted for sequence analysis involving nucleotides or amino acids
- G16B 40/00: ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
- G16B 40/20: Supervised data analysis
- G16B 40/30: Unsupervised data analysis
- G16B 50/10: Ontologies; Annotations
- G16H 10/40: for data related to laboratory analysis, e.g. patient specimen analysis
- G16H 10/60: for patient-specific data, e.g. for electronic patient records
- G06F 17/18: for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)}
- G06N 20/00: Machine learning
- G06N 20/20: Ensemble learning
- Y02A 90/10: Information and communication technologies [ICT] supporting adaptation to climate change, e.g. for weather forecasting or climate simulation
- C12Q: MEASURING OR TESTING PROCESSES INVOLVING ENZYMES, NUCLEIC ACIDS OR MICROORGANISMS (immunoassay G01N33/53); COMPOSITIONS OR TEST PAPERS THEREFOR; PROCESSES OF PREPARING SUCH COMPOSITIONS; CONDITION-RESPONSIVE CONTROL IN MICROBIOLOGICAL OR ENZYMOLOGICAL PROCESSES
- G16B: BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G16H: HEALTHCARE INFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR THE HANDLING OR PROCESSING OF MEDICAL OR HEALTHCARE DATA
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y02A: TECHNOLOGIES FOR ADAPTATION TO CLIMATE CHANGE

## Abstract

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.

## Claims

### Claim 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, and
(2) a second parent label, and
(ii) a plurality of edges, at least one edge connecting a first node to a second node and representing a transition from the first node to the second node; and
generating information on the individual using the directed acyclic graph.

### Claim 2 (depends on 1)

The computer implemented method of claim 1, wherein the information on the individual comprises one or more of: a set of possible ethnic origins of the individual and percentage compositions of the set of the possible ethnic origins, a set of possible paternal origins and percentage compositions of the set of possible paternal origins, or a set of possible maternal origins and percentage compositions of the set of possible maternal origins.

### Claim 3 (depends on 1)

The computer implemented method of claim 1, wherein the information on the individual comprises one or more of: a visualization of the individual's ancestry composition by chromosome painting, information about a particular trait of the individual, a percentage of DNA shared with a relative of the individual, a set of similarities and differences in a first genotype dataset of a first parent of the individual and a second genotype dataset of a second parent of the individual, or information on individuals genetically related to the individual.

### Claim 4 (depends on 1)

The computer implemented method of claim 1, wherein the plurality of nodes in each node group represents permutations of different first parent labels and second parent labels.

### Claim 5 (depends on 1)

The computer implemented method of claim 1, wherein a 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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 1)

The computer implemented method of claim 1, wherein each node is associated with an emission probability based on the pair of phased haplotype datasets.

### Claim 8

A non-transitory computer-readable storage medium storing executable computer program instructions, the computer program instructions, when executed by one or more processors, cause the one or more processors to perform steps 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 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, and
(2) a second parent label, and
(ii) a plurality of edges, at least one edge connecting a first node to a second node and representing a transition from the first node to the second node; and
generating information on the individual using the directed acyclic graph.

### Claim 9 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein the information on the individual comprises one or more of: a set of possible ethnic origins of the individual and percentage compositions of the set of the possible ethnic origins, a set of possible paternal origins and percentage compositions of the set of possible paternal origins, or a set of possible maternal origins and percentage compositions of the set of possible maternal origins.

### Claim 10 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein the information on the individual comprises one or more of: a visualization of the individual's ancestry composition by chromosome painting, information about a particular trait of the individual, a percentage of DNA shared with a relative of the individual, a set of similarities and differences in a first genotype dataset of a first parent of the individual and a second genotype dataset of a second parent of the individual, or information on individuals genetically related to the individual.

### Claim 11 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein the plurality of nodes in each node group represents permutations of different first parent labels and second parent labels.

### Claim 12 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein a 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.

### Claim 13 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, 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.

### Claim 14 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein each node is associated with an emission probability.

### Claim 15

A system comprising:
one or more computer processors; and
memory storing executable computer program instructions, the computer program instructions, when executed by the one or more computer processors, cause the one or more computer processors to perform steps 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 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, and
(2) a second parent label, and
(ii) a plurality of edges, at least one edge connecting a first node to a second node and representing a transition from the first node to the second node, and
generating information on the individual using the directed acyclic graph; and
a graphical interface configured to display the information.

### Claim 16 (depends on 15)

The system of claim 15, wherein the information on the individual comprises one or more of: a set of possible ethnic origins of the individual and percentage compositions of the set of the possible ethnic origins, a set of possible paternal origins and percentage compositions of the set of possible paternal origins, or a set of possible maternal origins and percentage compositions of the set of possible maternal origins.

### Claim 17 (depends on 15)

The system of claim 15, wherein the information on the individual comprises one or more of: a visualization of the individual's ancestry composition by chromosome painting, information about a particular trait of the individual, a percentage of DNA shared with a relative of the individual, a set of similarities and differences in a first genotype dataset of a first parent of the individual and a second genotype dataset of a second parent of the individual, or information on individuals genetically related to the individual.

### Claim 18 (depends on 15)

The system of claim 15, wherein the plurality of nodes in each node group represents permutations of different first parent labels and second parent labels.

### Claim 19 (depends on 15)

The system of claim 15, wherein a 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.

### Claim 20 (depends on 15)

The system of claim 15, 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.
