Filtering genetic networks to discover populations of interest

Abstract

A computing server generates a graph such as an identity-by-descent (IBD) network. The graph includes a plurality of nodes. Each node represents one of the individuals. Two or more nodes are connected through edges. Each edge connecting two nodes and associated with a weight that is derived from affinity between the genetic data of the two individuals represented by the two nodes. The computing system filters the graph based on features that are associated with the edges or the nodes. The filtered graph includes a subset of nodes. The computing system divides the filtered graph into a plurality of clusters to identify genetic communities that may not be discoverable without filtering. The computing server may also perform a multi-path hierarchical community detection process to assign an individual represented by a node to more than one community.

What is claimed is: 
     
         1 . A computer-implemented method for assigning a target individual to a genetic community, comprising:
 retrieving a genetic dataset for the target individual;   retrieving a reference panel sample comprising a genetic dataset of a reference panel individual;   determining an affinity between the target individual and the reference panel sample based on a comparison between the genetic dataset for the target individual and the genetic dataset of the reference panel individual;   retrieving a classifier for the genetic community;   determining one or more features for the classifier based at least in part on one or more of the affinity and the genetic dataset of the reference panel individual; and   generating a score using the classifier and based on the one or more features, the score representing a likelihood of the target individual belonging to the genetic community.   
     
     
         2 . The computer-implemented method of  claim 1 , further comprising:
 training the classifier by:
 providing a training set comprising features specific to the genetic community, the features corresponding to individuals classified to the genetic community; 
 providing a machine learning model to train the classifier; 
 adjusting one or more weights of the classifier to reduce errors; and 
 concluding training after one or more of the following: a predetermined number of epochs or after an error rate stops improving. 
   
     
     
         3 . The computer-implemented method of  claim 2 , wherein the machine learning model for training the classifier is one or more of a random forest, a support vector machine, logistic regression, and neural network. 
     
     
         4 . The computer-implemented method of  claim 2 , wherein the features of the training set are selected using a machine learning model selected from one or more of sparse penalized regression, forward/stepwise regression, recursive feature elimination, and regularized trees: 
     
     
         5 . The computer-implemented method of  claim 1 , wherein the reference panel sample is determined using a stability metric determined by:
 generating a graph comprising a plurality of nodes and a plurality of edges, wherein each edge connects two nodes;   randomly sampling a plurality of subsets of nodes from the graph;   dividing each of the subsets of nodes into clusters;   determining a ratio of instances where a node is classified into a target cluster representing the genetic community and instances where the node appears in the plurality of subsets of nodes;   selecting as reference panel samples nodes exceeding a predetermined threshold ratio.   
     
     
         6 . A non-transitory computer-readable storage medium comprising instructions that, when executed by a processor, cause the processor to perform operations including:
 retrieve a plurality of genetic datasets;   generate a graph comprising nodes corresponding to individuals and edges connecting two nodes, the edges having a weight based on an affinity between the corresponding nodes;   filter the graph based on a feature of one or both of the nodes and edges to yield a subset of nodes;   divide the subset of nodes into clusters representing distinct genetic communities based on the weights of the edges.   
     
     
         7 . The non-transitory computer-readable storage medium of  claim 6 , wherein the feature is one or more of a birth year of a shared ancestor of two individuals represented by the nodes, an average birth year of shared ancestors, a time frame of birth years of the shared ancestors, a geographical origin of the shared ancestor, an ethnicity of the shared ancestor, surnames of the shared ancestors, an ethnicity composition of individuals represented by the nodes, or a phenotype of the individuals. 
     
     
         8 . The non-transitory computer-readable storage medium of  claim 6 , wherein the feature is ethnicity and nodes below a predetermined threshold of ethnicity attributable to a target ethnicity are filtered. 
     
     
         9 . The non-transitory computer-readable storage medium of  claim 6 , wherein dividing the subset of nodes into clusters includes the operations:
 define a plurality of partitions in the subset of nodes, each partition representing a candidate genetic community;   determine a modularity of the plurality of partitions;   adjust the boundaries of the partitions to increase the modularity.   
     
     
         10 . The non-transitory computer-readable storage medium of  claim 9 , wherein the adjusted partitions each represent a genetic community. 
     
     
         11 . The non-transitory computer-readable storage medium of  claim 6 , wherein the affinity of an edge between two nodes is an IBD affinity determined from a comparison of the genetic datasets corresponding to the nodes. 
     
     
         12 . The non-transitory computer-readable storage medium of  claim 6 , wherein dividing the subset of nodes into clusters is performed using a recursive application of a modularity-based community detection algorithm. 
     
     
         13 . The non-transitory computer-readable storage medium of  claim 6 , wherein the operation:
 divide the subset of nodes into clusters representing distinct genetic communities based on weights of the edges;   is repeated for subsequent levels of genetic communities as long as at least one genetic community has greater than a threshold number of nodes.   
     
     
         14 . A computer-implemented method for detecting a genetic community of a target individual, comprising:
 retrieving first and second genetic datasets,
 wherein the first genetic dataset is associated with a target individual, and 
 wherein the second genetic dataset is associated with a reference panel sample for a genetic community; 
   determining an affinity of the target individual with the reference panel sample based on a comparison between the first and second genetic datasets;   generating a feature vector comprising one or more features selected from at least one of: (i) the affinity, (ii) the first genetic dataset, or (iii) the second genetic dataset;   receiving the feature vector at a community classifier trained to detect the genetic community from the one or more selected features; and   generating a score using the community classifier, the score representing a likelihood the target individual belongs to the genetic community.   
     
     
         15 . The computer-implemented method of  claim 14 , wherein the genetic community is identified by:
 generating a graph comprising nodes corresponding to individuals and edges connecting two nodes, the edges having a weight based on an affinity between the corresponding nodes;   filtering the graph based on a feature of one or both of the nodes and edges to yield a subset of nodes;   dividing the subset of nodes into clusters representing distinct genetic communities based on the weights of the edges; and   further subdividing the clusters until a number of nodes in a subdivision of a cluster or a sub-cluster falls below a threshold number of nodes.   
     
     
         16 . The computer-implemented method of  claim 14 , wherein the target individual is assigned to a single genetic community. 
     
     
         17 . The computer-implemented method of  claim 14 , wherein the target individual is assigned to a plurality of different genetic communities. 
     
     
         18 . The computer-implemented method of  claim 14 , wherein the target individual is assigned to the plurality of different genetic communities based on a stability of an association between the target node and each of the additional genetic communities. 
     
     
         19 . The computer-implemented method of  claim 18 , wherein the stability of the association is determined by:
 randomly sampling a plurality of subsets of nodes;   dividing the subsets of nodes into clusters;   determining a ratio of instances where the target individual is classified into a target cluster representing an additional community and instances where the target individual appears in the plurality of subsets of nodes;   assigning the target individual to the target cluster representing the additional community upon determining that the ratio of instances is above a predetermined stability threshold.   
     
     
         20 . The computer-implemented method of  claim 19 , wherein the reference panel sample is determined for the genetic community based on exceeding a second predetermined stability threshold; and
 wherein the second predetermined stability threshold is greater than the predetermined stability threshold for the target individual.