Identifying ancestral relationships using a continuous stream of input
View Patent ↗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.
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 the 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.
9. The method of claim 3 wherein the threshold length is at least 1 centimorgan.
10. The non-transitory computer readable medium of claim 7 wherein the threshold length is at least 1 centimorgan.
11. The non-transitory computer readable storage medium of claim 5 wherein a haplotype is a haplotype value, a haplotype value representing particular genetic data present in a particular genomic window.
12. The non-transitory computer readable storage medium of claim 5 , wherein the first table comprises a column for storing identifiers of samples, wherein a presence of an identifier of a sample in an entry at an intersection of the column and a row indexed by a haplotype indicates that the sample includes the haplotype that indexes the row.
13. The non-transitory computer readable storage medium of claim 5 , wherein the second table comprises a column for each of a plurality of genomic windows; and wherein an entry at each row and column location in the second table indicates the haplotype for the sample of that row and for the genomic window of that column.
14. The non-transitory computer readable storage medium of claim 5 , wherein the third table comprises a column for each of the samples; and wherein an entry at each row and column location in the third table indicates the range of haplotype matches generated between a segment of the sample of that row and the sample of that column.
15. The non-transitory computer readable storage medium of claim 5 , wherein a range of haplotype matches includes a plurality of haplotype values that are sequential in position within or between genomic windows.
16. The method of claim 1 wherein a haplotype is a haplotype value, a haplotype value representing particular genetic data present in a particular genomic window.
17. The method of claim 1 , wherein the first table comprises a column for storing identifiers of samples, wherein a presence of an identifier of a sample in an entry at an intersection of the column and a row indexed by a haplotype indicates that the sample includes the haplotype that indexes the row.
18. The method of claim 1 , wherein the second table comprises a column for each of a plurality of genomic windows; and wherein an entry at each row and column location in the second table indicates the haplotype for the sample of that row and for the genomic window of that column.
19. The method of claim 1 , wherein the third table comprises a column for each of the samples; and wherein an entry at each row and column location in the third table indicates the range of haplotype matches generated between a segment of the sample of that row and the sample of that column.
20. The method of claim 1 , wherein a range of haplotype matches includes a plurality of haplotype values that are sequential in position within or between genomic windows.
21. The method of claim 1 ,
wherein identifying the initial haplotype match comprises identifying a match between the haplotype in the subset and a haplotype from one sample from either the first or second received set based on an inclusion of an identifier of the sample and an inclusion of an identifier of the one sample in the common row indexed by the haplotype of the updated first table;
wherein identifying ranges of haplotype matches between the segment of the sample and each other sample from the first received set and the second received set further comprises, for each haplotype in the subset, determining whether a nucleotide base of the adjacent haplotype beyond a first flank of the haplotype matches a corresponding sequence beyond a first flank of a haplotype in the accessed row of the updated second table; and
wherein extending the initial haplotype match comprises extending the identified match to an extended genomic window responsive to determining that the sequence beyond the first flank of the haplotype in the subset matches the corresponding sequence beyond a first flank of the haplotype in the accessed row of the updated second table.
22. The non-transitory computer readable storage medium of claim 5 , wherein identifying the initial haplotype match comprises identifying a match between the haplotype in the subset and a haplotype from one sample from either the first or second received set based on an inclusion of an identifier of the sample and an inclusion of an identifier of the one sample in the common row indexed by the haplotype of the updated first table;
wherein identifying ranges of haplotype matches between the segment of the sample and each other sample from the first received set and the second received set further comprises, for each haplotype in the subset, determining whether a nucleotide base of the adjacent haplotype beyond a first flank of the haplotype matches a corresponding sequence beyond a first flank of a haplotype in the accessed row of the updated second table; and
wherein extending the initial haplotype match comprises extending the identified match to an extended genomic window responsive to determining that the sequence beyond the first flank of the haplotype in the subset matches the corresponding sequence beyond a first flank of the haplotype in the accessed row of the updated second table.