FINDING RELATIVES IN A DATABASE
Determining relative relationships of people who share a common ancestor within at least a threshold number of generations includes: receiving recombinable deoxyribonucleic acid (DNA) sequence information of a first user and recombinable DNA sequence information of a plurality of users; processing, using one or more computer processors, the recombinable DNA sequence information of the plurality of users in parallel; determining, based at least in part on a result of processing the recombinable DNA information of the plurality of users in parallel, a predicted degree of relationship between the first user and a user among the plurality of users, the predicted degree of relative relationship corresponding to a number of generations within which the first user and the second user share a common ancestor.
1 - 20 . (canceled)
21 . A relative finder system comprising a database with hundreds of thousands of genetic markers and one or more processors configured to:
(a) receive deoxyribonucleic acid (DNA) information of a first user and a plurality of other users, wherein the DNA information comprises hundreds of thousands of genetic markers;
(b) process in parallel the hundreds of thousands of genetic markers of the first user and the plurality of other users to estimate one or more identical-by-descent (IBD) segments between the first user and the plurality of other users, wherein the processing in parallel comprises processing data of two or more users or two or more genetic markers in parallel;
(c) estimate a degree of relative relationship between the first user and one or more users among the plurality of users of the database using the one or more identical-by-descent (IBD) segments between the first user and the plurality of other users; and
(d) present an interactive graphical user interface (GUI), wherein the interactive GUI comprises a graphical display structure displaying the first user, the one or more users who may be potential relatives, and information pertaining to each of the one or more users including the estimated degree of relative relationship between the first user and each of the one or more users.
22 . The system of claim 21 , wherein processing in parallel comprises looking up a genetic marker of the first user in one or more hash tables constructed using the genetic marker of the plurality of users, thereby determining that the genetic marker of the first user matches the genetic marker of a second user, the second user being a user in the plurality of users.
23 . The system of claim 22 , the one or more processors are further configured to determine an IBD segment including the genetic marker between the first user and the second user.
24 . The system of claim 22 , wherein the genetic marker is encoded as a part of a word comprising a plurality of genetic markers.
25 . The system of claim 21 , wherein processing in parallel comprises:
comparing the two or more genetic markers between the first user and the plurality of users to obtain opposite homozygous data representing whether each genetic marker comprises an opposite homozygous allele between the first user and each user of the plurality of users; and
encoding the opposite homozygous data in an array comprising two or more rows corresponding to the two or more users and two or more columns corresponding to the two or more genetic markers.
26 . The system of claim 25 , wherein the one or more processors are further configured to perform a bitwise operation on the array to determine an IBD segment.
27 . The system of claim 25 , wherein the two or more users comprise at least 64 users.
28 . The system of claim 21 , wherein (b) is performed responsive to receiving an opt-in election from the first user provided through a user interface to consent to be presented with the potential relatives.
29 . The system of claim 21 , wherein (d) is performed responsive to a request from the first user received through a user interface.
30 . The system of claim 21 , wherein (c) comprises:
estimating a number of shared IBD segments and a length of shared IBD segments between the first user and the plurality of users based on the one or more IBD segments; and
applying a relationship estimate model to the number of shared IBD segments and the length of shared IBD segments between the first user and the plurality of users to estimate a degree of relative relationship between the first user and one or more users among the plurality of users.
31 . The system of claim 30 , wherein the relationship estimate model comprises relationship distributions for combinations of various numbers of shared IBD segments and various lengths of shared IBD segments, the relationship distributions being obtained from a plurality of pedigrees.
32 . The system of claim 31 , wherein application of the relationship estimate model provides an estimated relative relationship based on a 50 th percentile relationship pattern, and an estimated range of relative relationship based on a 95 th percentile relationship pattern and a 5 th percentile relationship pattern.
33 . The system of claim 31 , wherein the plurality of pedigrees comprises computer simulated individuals whose genomes are obtained by mating, by computer simulation, genomes of actual individuals.
34 . The system of claim 30 , wherein the length of shared IBD segments includes a total length of shared IBD segments.
35 . The system of claim 21 , wherein the genetic markers comprise 650,000 genetic markers.
36 . The system of claim 21 , wherein the genetic markers comprise 650,000 Single Nucleotide Polymorphisms (SNPs).
37 . The system of claim 21 , wherein the genetic markers comprise Single Nucleotide Polymorphisms (SNPs).
38 . The system of claim 21 , wherein the information pertaining to each of the one or more users comprises:
an entry of personal details that each of the one or more users has chosen to make public;
the number of the IBD segments shared between the first user and each of the one or more
the length of the IBD segments shared between the first user and each of the one or more users or the length represented as a percentage; and
the estimated degree of relative relationship between the first user and each of the one or more users.
39 . The system of claim 21 , further comprising: estimating a range of possible relative relationships between the first user and each of the one or more users among the plurality of users in the database; and the graphical display structure further comprising: the range of possible relative relationships between the first user and each of the one or more users among the plurality of users in the database.
40 . The system of claim 21 , wherein the graphical display structure comprises a list of the one or more users sorted in descending order with a closest estimated relative positioned at the top of the list.
41 . The system of claim 40 , the graphical display structure further comprising: a family tree representation of the one or more users based on the estimated degree of relative relationship between the first user and each of the one or more users.
42 . The system of claim 21 , wherein each IBD segment exceeds a predetermined genetic distance threshold.
43 . The system of claim 42 , wherein the predetermined genetic distance threshold is 10 centimorgans (10 cM).
44 . The system of claim 21 , wherein the one or more processors are configured to estimate the one or more IBD segments by assessing a genetic distance between consecutive opposite homozygous calls made regarding the first user and the plurality of users in the database.
45 . The system of claim 44 , wherein the genetic distance between the consecutive opposite homozygous calls is estimating by:
estimating a physical distance between the consecutive opposite homozygous calls;
manipulating the physical distance between consecutive opposite homozygous calls to account for recombination; and
estimating the genetic distance between opposite homozygous calls based on the manipulated physical distances between the opposite homozygous calls.
46 . The system of claim 44 , further comprising: encoding the opposite homozygous calls between the first user and the plurality of users in the database in an array comprising a plurality of rows corresponding to the plurality of users in the database and a plurality of columns corresponding to a plurality of calls.
47 . The system of claim 21 , wherein the DNA information includes entire genome sequence data.
48 . A method of operating a relative finder database with hundreds of thousands of genetic markers to display potential relatives among users in the relative finder database, comprising:
(a) receiving deoxyribonucleic acid (DNA) information of a first user and a plurality of other users, wherein the DNA information comprises hundreds of thousands of genetic markers;
(b) processing in parallel, using one or more computer processors, the hundreds of thousands of genetic markers of the first user and the plurality of other users to estimate one or more identical-by-descent (IBD) segments between the first user and the plurality of other users, wherein the processing in parallel comprises processing data of two or more users or two or more genetic markers in parallel;
(c) estimating, using one or more computer processors, a degree of relative relationship between the first user and one or more users among the plurality of users of the database using the one or more identical-by-descent (IBD) segments between the first user and the plurality of other users; and
(d) presenting an interactive graphical user interface (GUI), wherein the interactive GUI comprises a graphical display structure displaying the first user, the one or more users who may be potential relatives, and information pertaining to each of the one or more users including the estimated degree of relative relationship between the first user and each of the one or more users.
49 . A computer product comprising a non-transitory computer readable medium having stored thereon program code that, when executed by one or more processors of a computer system, cause the computer system to perform operations for operating a relative finder database with hundreds of thousands of genetic markers to display a list of potential relatives among users in the relative finder database, said program code comprising code for:
(a) receiving deoxyribonucleic acid (DNA) information of a first user and a plurality of other users, wherein the DNA information comprises hundreds of thousands of genetic markers;
(b) processing in parallel the hundreds of thousands of genetic markers of the first user and the plurality of other users to estimate one or more identical-by-descent (IBD) segments between the first user and the plurality of other users, wherein the processing in parallel comprises processing data of two or more users or two or more genetic markers in parallel;
(c) estimating a degree of relative relationship between the first user and one or more users among the plurality of users of the database using the one or more identical-by-descent (IBD) segments between the first user and the plurality of other users; and
(d) presenting an interactive graphical user interface (GUI), wherein the interactive GUI comprises a graphical display structure displaying the first user, the one or more users who may be potential relatives, and information pertaining to each of the one or more users including the estimated degree of relative relationship between the first user and each of the one or more users.