Discovering population structure from patterns of identity-by-descent
AssigneeAncestry.com DNA, LLC
InventorsEunjung Han, Ross E. Curtis, Peter Carbonetto
Life of this patent
Estimating the term…
Abstract
Described are techniques for determining population structure from identity-by-descent (IBD) of individuals. The techniques may be used to predict that an individual belongs to zero, one or more of a number of communities identified within an IBD network. Additional data may be used to annotate the communities with birth location, surname, and ethnicity information. In turn, these data may be used to provide to an individual a prediction of membership to zero, one or more communities, accompanied by a summary of the information annotated to those communities.
Claims18
A computer-implemented method comprising:
- receiving DNA datasets of a plurality of individuals;
- generating, based on the DNA datasets, a network comprising a plurality of nodes, each node representing an individual of the plurality of individuals;
- connecting two or more nodes in the network with edges, each edge connecting a first node and a second node and having a weight that is determined based on affinity between the DNA dataset of the two individuals respectively represented by the first and the second nodes;
- and
- identifying one or more genetic communities in the network, each genetic community comprising a subset of nodes, at least one of the genetic communities identified based on the weights of the edges connected the nodes in the subset, wherein identifying one or more genetic communities in the network comprises:
- identifying a network partition in the network, the network partition representing a candidate genetic community;
- determining a modularity of the network partition, the modularity being a measurement that increases with the edges connected among the nodes classified to the network partition and that decreases with the edges connected from the nodes in the network partition to the nodes outside the network partition;
- and
- adjusting the network partition to increase the modularity of the network partition.
A system, comprising:
- a processor;
- and
- a memory comprising instructions, when executed by the processor, cause the processor to:
- receive DNA datasets of a plurality of individuals;
- generate, based on the DNA datasets, a network comprising a plurality of nodes, each node representing an individual of the plurality of individuals;
- connect two or more nodes in the network with edges, each edge connecting a first node and a second node and having a weight that is determined based on affinity between the DNA dataset of the two individuals respectively represented by the first and the second nodes;
- and
- identify one or more genetic communities in the network, each genetic community comprising a subset of nodes, at least one of the genetic communities identified based on the weights of the edges connected the nodes in the subset, wherein identify one or more genetic communities in the network comprises;
- identify a network partition in the network, the network partition representing a candidate genetic community;
- determine a modularity of the network partition, the modularity being a measurement that increases with the edges connected among the nodes classified to the network partition and that decreases with the edges connected from the nodes in the network partition to the nodes outside the network partition;
- and
- adjusting the network partition to increase the modularity of the network partition.
Dependencies are inferred from the claim text.