Finding relatives in a database

Abstract

Determining a relative relationship of people who share a common ancestor within a number of generations includes: obtaining recombinable deoxyribonucleic acid (DNA) sequence information of a first user and recombinable DNA sequence information of a plurality of users; processing, using a plurality of computer processors, the recombinable DNA sequence information of the plurality of users in parallel; and determining, based at least in part on a result of processing the recombinable DNA sequence information of the plurality of users in parallel, a predicted degree of relative relationship between the first user and a user among the plurality of users. The predicted degree of relative relationship corresponds to a number of generations within which the first user and the user among the plurality of users share a common ancestor.

What is claimed is: 
     
         1 . (canceled) 
     
     
         2 . A method of determining a relative relationship of people who share a common ancestor within a number of generations, comprising:
 obtaining recombinable deoxyribonucleic acid (DNA) sequence information of a first user and recombinable DNA sequence information of a plurality of users;   processing, using a plurality of computer processors, the recombinable DNA sequence information of the plurality of users in parallel; and   determining, based at least in part on a result of processing the recombinable DNA sequence information of the plurality of users in parallel, a predicted degree of relative relationship between the first user and a user among the plurality of users; wherein   the predicted degree of relative relationship corresponds to a number of generations within which the first user and the user among the plurality of users share a common ancestor.   
     
     
         3 . The method of  claim 2 , wherein the recombinable DNA sequence information of the first user includes a first Single Nucleotide Polymorphism (SNP) sequence and the recombinable DNA sequence information of the plurality of additional users includes a plurality of SNP sequences. 
     
     
         4 . The method of  claim 2 , wherein processing the recombinable DNA sequence information of the plurality of users in parallel includes encoding zygosity states of a first set of SNPs of the plurality of users and zygosity states of a second set of SNPs of the plurality of users, wherein the first set of SNPs corresponds to a first homozygous SNP of the first user and the second set of SNPs corresponds to a second homozygous SNP of the first user. 
     
     
         5 . The method of  claim 4 , wherein determining the predicted degree of relative relationship includes performing a bit-wise operation on the encoded zygosity states to identify any user among the plurality of users that share an Identical by Descent (IBD) region with the first user. 
     
     
         6 . The method of  claim 4 , wherein encoding the zygosity states of the first set of SNPs of the plurality of users includes using a first binary value to represent a SNP in the first set of SNPs that is a compatible call with respect to the first homozygous SNP of the first user, and using a second binary value to represent a SNP in the first set of SNPs that is not a compatible call with respect to the first homozygous SNP of the first user. 
     
     
         7 . The method of  claim 5 , wherein the bit-wise operation includes a bit-wise OR operation used to identify a DNA segment of the user among the plurality of users that does not have opposite-homozygous calls with respect to the first user within the DNA segment. 
     
     
         8 . The method of  claim 2 , wherein the recombinable DNA sequence information includes phased data, and processing the recombinable DNA sequence information of the plurality of users in parallel includes encoding the recombinable DNA sequence information of the plurality of users as a first set of words. 
     
     
         9 . The method of  claim 8 , further comprising encoding the recombinable DNA sequence information of the first user as a second set of words, and wherein determining the predicted degree of relative relationship includes comparing the first set of words with the second set of words. 
     
     
         10 . A system of determining a relative relationship of people who share a common ancestor within a number of generations, comprising:
 one or more processors configured to:
 obtain recombinable deoxyribonucleic acid (DNA) sequence information of a first user and recombinable DNA sequence information of a plurality of users; 
 process the recombinable DNA sequence information of the plurality of users in parallel; and 
 determine, based at least in part on a result of processing the recombinable DNA sequence information of the plurality of users in parallel, a predicted degree of relative relationship between the first user and a user among the plurality of users; wherein the predicted degree of relative relationship corresponds to a number of generations within which the first user and the user among the plurality of users share a common ancestor; and 
   one or more memories coupled to the one or more processors, configured to provide the one or more processors with instructions.   
     
     
         11 . The system of  claim 10 , wherein the recombinable DNA sequence information of the first user includes a first Single Nucleotide Polymorphism (SNP) sequence and the recombinable DNA sequence information of the plurality of additional users includes a plurality of SNP sequences. 
     
     
         12 . The system of  claim 10 , wherein to process the recombinable DNA sequence information of the plurality of users in parallel includes to encode zygosity states of a first set of SNPs of the plurality of users and zygosity states of a second set of SNPs of the plurality of users, wherein the first set of SNPs corresponds to a first homozygous SNP of the first user and the second set of SNPs corresponds to a second homozygous SNP of the first user. 
     
     
         13 . The system of  claim 12 , wherein to determine the predicted degree of relative relationship includes to perform a bit-wise operation on the encoded zygosity states to identify any user among the plurality of users that share an Identical by Descent (IBD) region with the first user. 
     
     
         14 . The system of  claim 12 , wherein to encode the zygosity states of the first set of SNPs of the plurality of users includes to use a first binary value to represent a SNP in the first set of SNPs that is a compatible call with respect to the first homozygous SNP of the first user, and to use a second binary value to represent a SNP in the first set of SNPs that is not a compatible call with respect to the first homozygous SNP of the first user. 
     
     
         15 . The system of  claim 13 , wherein the bit-wise operation includes a bit-wise OR operation used to identify a DNA segment of the user among the plurality of users that does not have opposite-homozygous calls with respect to the first user within the DNA segment. 
     
     
         16 . The system of  claim 10 , wherein the recombinable DNA sequence information includes phased data, and to process the recombinable DNA sequence information of the plurality of users in parallel includes to encode the recombinable DNA sequence information of the plurality of users as a first set of words. 
     
     
         17 . The system of  claim 16 , wherein the one or more processors are further configured to encode the recombinable DNA sequence information of the first user as a second set of words, and
 wherein to determine the predicted degree of relative relationship includes to compare the first set of words with the second set of words.   
     
     
         18 . A computer program product for determining a relative relationship of people who share a common ancestor within a threshold number of generations, the computer program product being embodied in a tangible non-transitory computer readable storage medium and comprising computer instructions for:
 obtaining recombinable deoxyribonucleic acid (DNA) sequence information of a first user and recombinable DNA sequence information of a plurality of users;   processing, using a plurality of computer processors, the recombinable DNA sequence information of the plurality of users in parallel; and   determining, based at least in part on a result of processing the recombinable DNA sequence information of the plurality of users in parallel, a predicted degree of relative relationship between the first user and a user among the plurality of users; wherein the predicted degree of relative relationship corresponds to a number of generations within which the first user and the user among the plurality of users share a common ancestor.   
     
     
         19 . The computer program product of  claim 18 , wherein the recombinable DNA sequence information of the first user includes a first Single Nucleotide Polymorphism (SNP) sequence and the recombinable DNA sequence information of the plurality of additional users includes a plurality of SNP sequences. 
     
     
         20 . The computer program product of  claim 18 , wherein processing the recombinable DNA sequence information of the plurality of users in parallel includes encoding zygosity states of a first set of SNPs of the plurality of users and zygosity states of a second set of SNPs of the plurality of users, the first set of SNPs correspond to a first homozygous SNP of the first user and the second set of SNPs corresponding to a second homozygous SNP of the first user. 
     
     
         21 . The computer program product of  claim 18 , wherein the recombinable DNA sequence information includes phased data, and processing the recombinable DNA sequence information of the plurality of users in parallel includes encoding the recombinable DNA sequence information of the plurality of users as a first set of words.