Identifying ancestral relationships using a continuous stream of input

Patent metadata

Field	Value
Publication number	US-10114922-B2
Application number	US-201314029765-A
Country	US
Kind code	B2
Filing date	Sep 17, 2013
Priority date	Sep 17, 2012
Publication date	Oct 30, 2018
Grant date	Oct 30, 2018

Abstract

Identification of inheritance-by-descent haplotype matches between individuals is described. A set of tables including word match, haplotypes and segment match tables are populated. DNA samples are received and stored. A word identification module extracts haplotype values from each sample. The word match table is indexed according to the unique combination of position and haplotype. Each column represents a different sample, and each cell indicates whether that sample includes that haplotype at that position. The haplotypes table includes the raw haplotype data for each sample. The segment match table is indexed by sample identifier, and columns represent other samples. Each cell is populated to indicate for each identified sample pair which position range(s) include matching haplotypes for both samples. The tables are persistently stored in databases of the matching system. As new sample data is received, each table is updated to include the newly received samples, and additional matching takes place.

First claim

We claim:

1. A computer-implemented method comprising:
receiving a first set of genetic data, the first set including a plurality of genetic data samples from a first plurality of human individuals, the first set of genetic data including a set of haplotypes for each of the first plurality of human individuals;
for each sample in the first set:
for each of the haplotypes in the sample, storing an identifier of the sample in an entry of a first table having rows indexed by haplotype, the entry located in a row indexed by the haplotype in the sample;
storing in a second table a plurality of haplotypes included in the sample, the second table having rows indexed by segments of each individual;
identifying a set of ranges of haplotype matches between the sample and each other sample based on the haplotypes;
storing in a third table the ranges of haplotype matches between the sample and each other sample, the third table indexed by segments of each individual;

receiving a second set of genetic data, the second set including a plurality of genetic data samples from a second plurality of human individuals, the second set of genetic data including a set of haplotypes for each of the second plurality of human individuals;
for each sample in the second set:
for each of the haplotypes in the sample, updating the first table by including an identifier of the sample in the second set in a row of the first table indexed by the haplotype contained by the sample;
updating the second table by including one or more additional rows each identifying a segment of the sample, wherein each additional row includes a plurality of haplotypes included in the segment;
for each segment of the sample:
identifying ranges of haplotype matches between the segment and each other sample from the first received set and the second received set by:
accessing a subset of haplotypes included in the additional row from the updated second table, and
for each haplotype in the subset of accessed haplotypes:
 identifying an initial haplotype match by accessing an identifier of the other sample stored in a common row of the updated first table, the common row indexed by the haplotype in the subset;
 accessing a row of the updated second table indexed by the segment of the other sample that is identified by the accessed identifier, the accessed row comprising the haplotype and an adjacent haplotype next to the haplotype; and
 extending the initial haplotype match along nucleotide bases of the adjacent haplotype in the accessed row of the updated second table; and
generating a range of haplotype matches between the segment of the sample and the other sample, the range of haplotype matches comprising extended initial haplotype matches across the haplotypes in the subset;

updating the third table by including an additional row indexed by the segment of the sample to include the ranges of haplotype matches between the segment of the sample and each other sample; and

providing to at least two of the first or second plurality of human individuals an indication that a number of haplotype matches between them exceeds a threshold number of matches.

2. The method of claim 1 wherein updating the first table further comprises:
determining that the haplotype is not in the first table; and
adding an additional row in the first table indexed by the haplotype.

3. The method of claim 1 wherein a range of haplotype matches between two samples of the first or second sets comprises matching segments of the haplotypes from those samples of at least a threshold length.

4. The method of claim 1 wherein the first table is indexed by a hash value of the haplotype and updating the first table further comprises:
identifying a haplotype in the sample;
hashing the haplotype;
identifying in the first table a row indexed by the hashed haplotype; and

storing the identifier of the sample in the row of the first table that is indexed by the hashed haplotype.

5. A non-transitory computer readable medium including instructions configured to cause a processor to execute steps comprising:
receiving a first set of genetic data, the first set including a plurality of genetic data samples from a first plurality of human individuals, the first set of genetic data including a set of haplotypes for each of the first plurality of human individuals;
for each sample in the first set:
for each of the haplotypes in the sample, storing an identifier of the sample in an entry of a first table having rows indexed by haplotype, the entry located in a row indexed by the haplotype in the sample;
storing in a second table a plurality of haplotypes included in the sample, the second table having rows indexed by segments of each individual;
identifying a set of ranges of haplotype matches between the sample and each other sample based on the haplotypes;
storing in a third table the ranges of haplotype matches between the sample and each other sample, the third table indexed by segments of each individual;

receiving a second set of genetic data, the second set including a plurality of genetic data samples from a second plurality of human individuals, the second set of genetic data including a set of haplotypes for each of the second plurality of human individuals;
for each sample in the second set:
for each of the haplotypes in the sample, updating the first table by including an identifier of the sample in the second set in a row of the first table indexed by the haplotype contained by the sample;
updating the second table by including one or more additional rows each identifying a segment of the sample, wherein each additional row includes a plurality of haplotypes included in the segment;
for each segment of the sample:
identifying ranges of haplotype matches between the segment and each other sample from the first received set and the second received set by:
accessing a subset of haplotypes included in the additional row from the updated second table, and
for each haplotype in the subset of accessed haplotypes:
 identifying an initial haplotype match by accessing an identifier of the other sample stored in a common row of the updated first table, the common row indexed by the haplotype in the subset;
 accessing a row of the updated second table indexed by the segment of the other sample that is identified by the accessed identifier, the accessed row comprising the haplotype and an adjacent haplotype next to the haplotype; and
 extending the initial haplotype match along nucleotide bases of the adjacent haplotype in the accessed row of the updated second table; and
generating a range of haplotype matches between the segment of the sample and the other sample, the range of haplotype matches comprising extended initial haplotype matches across the haplotypes in the subset;

updating the third table by including an additional row indexed by the segment of the sample to include the ranges of haplotype matches between the segment of the sample and each other sample; and

providing to at least two of the first or second plurality of human individuals an indication that a number of haplotype matches between them exceeds a threshold number of matches.

6. The non-transitory computer readable medium of claim 5 wherein updating the first table further comprises:
determining that the haplotype is not in the first table; and
adding an additional row in the first table indexed by the haplotype.

7. The non-transitory computer readable medium of claim 5 wherein a range of haplotype matches between two samples of the first or second sets comprises matching segments of the haplotypes from those samples of at least a threshold length.

8. The non-transitory computer readable medium of claim 5 wherein

Assignees

• Ancestry Com Dna Llc

Inventors

• Byrnes Jake Kelly
• Ling Aaron
• Noto Keith D
• Pollack Jeremy
• Ball Catherine Ann
• Chahine Kenneth Gregory

Classifications

• G06F19/28

  Physics · mapped topic

• G06F19/18 Primary

  Physics · mapped topic

• G16B50/30 Primary

  Data warehousing; Computing architectures · CPC title

• G16B20/00

  ICT specially adapted for functional genomics or proteomics, e.g. genotype-phenotype associations · CPC title

• G16B20/40

  Population genetics; Linkage disequilibrium · CPC title