Methods and system for efficient indexing for genetic genealogical discovery in large genotype databases
A system for indexing, updating, and search haplotypes for genetic genealogical discovery in genotype databases. The system includes a pool of genetic indexes, a haplotype ingestion engine, and a haplotype query engine. The haplotypes of a number of individuals in a genotype database are indexed by a pool of multiple panels, and each panel pool can be dynamically updated by the insertion or deletion of individual haplotypes. A genetic genealogical search of a query haplotype against the database is achieved by first projecting the query onto a subset of panels in the pool, then conducting long match queries over each panel, and finally aggregating the identified long matches into Identical-by-Descent segments, i.e., DNA matches, between the query and the haplotypes in the database.
1. A genealogical indexing system comprising:
a processor;
a haplotype panel pool in electronic communication with a non-transitory computer-readable medium that is operably coupled to the processor, the haplotype panel pool including a plurality of panels that is indexed by a positional Burrows-Wheeler transform (PBWT) representation, each of the plurality of panels including a plurality of haplotypes, the haplotype panel pool having a set of variant sites, wherein each of the plurality of haplotypes is indexed by the PBWT representation in a reversed prefix order; and
the non-transitory computer-readable medium having computer-readable instructions stored thereon that, when executed by the processor, cause the genealogical indexing system to automatically identify a genealogical match with an input genetic sequence by executing instructions comprising:
selecting, via a computing nodule in electronic communication with the haplotype panel pool, a minimum identity-by-descent segment length value of at least one million base pairs, such that haplotype matches greater than or equal to the minimum identity-by-descent segment length indicate a match between the input genetic sequence and the haplotype panel pool, and such that haplotype matches lesser than the minimum identity-by-descent segment length indicate a lack of a match between the input genetic sequence and the haplotype panel pool;
selecting, via the computing nodule in electronic communication with the haplotype panel pool, a plurality of portions of each of the plurality of panels to sample each of the plurality of panels;
projecting, via the computing nodule in electronic communication with the haplotype panel pool, the sample to the set of variant sites for each of the plurality of panels in the haplotype panel pool, such that the sample can be compared against the samples in the haplotype panel pool via the set of variants;
receiving, via the computing nodule in electronic communication with the haplotype panel pool, the input genetic sequence;
automatically indexing, via a haplotype querying engine of the computing nodule in electronic communication with the haplotype panel pool, executable by the processor, the input genetic sequence by the PBWT representation, thereby transforming the input genetic sequence into a PBWT indexed input genetic sequence including the reversed prefix order;
activating, via the haplotype querying engine of the computing nodule in electronic communication with the haplotype panel pool, an amount of the plurality of panels from the haplotype panel pool for testing;
comparing, via the haplotype querying engine of the computing nodule in electronic communication with the haplotype panel pool, the PBWT indexed input genetic sequence with the amount of the plurality of panels by comparing the PBWT indexed input genetic sequence with the set of variant sites; and
via the haplotype querying engine of the computing nodule in electronic communication with the haplotype panel pool, automatically identifying, in real-time and independent of a total number of haplotypes in the plurality of haplotypes, the genealogical match between the input genetic sequence and the haplotype pool by:
based on a determination that the PBWT indexed input genetic sequence matches the amount of the plurality of panels by a value greater than or equal to the minimum identity-by-descent segment length of at least one million base pairs, determining the genealogical match between the input genetic sequence and the haplotype panel pool; and
based on a determination that the PBWT indexed input genetic sequence does not match the amount of the plurality of panels by a value greater than or equal to the minimum identity-by-descent segment length of at least one million base pairs, determining a lack of the genealogical match between the input genetic sequence and the haplotype panel pool.
2. The genealogical indexing system of claim 1 , wherein the instructions of automatically identifying the genealogical match between the input genetic sequence and the haplotype panel pool further comprise utilizing a long match query algorithm to compare the PBWT indexed input genetic sequence with the amount of the plurality of panels and determine if the PBWT indexed input genetic sequence matches the amount of the plurality of panels by a value greater than or equal to the minimum identity-by-descent segment length of at least one million base pairs.
3. The genealogical indexing system of claim 1 , wherein the instructions further comprise, after projecting the sample to the set of variant sites for each of the plurality of panels in the haplotype panel pool, weighing, via the computing nodule in electronic communication with the haplotype panel pool, the set of variant sites to emphasize minor allele frequencies.
4. The genealogical indexing system of claim 1 , wherein the PBWT representation is a dynamic representation providing for updating the haplotype panel pool.
5. The genealogical indexing system of claim 4 , wherein the instructions further comprise dynamically updating, in real-time, via a haplotype ingestion engine of the computing nodule in electronic communication with the haplotype panel pool, executable by the processor, the haplotype panel pool.
6. The genealogical indexing system of claim 5 , wherein the instructions further comprise adding, via the haplotype ingestion engine of the computing nodule in electronic communication with the haplotype panel pool, a new haplotype into the haplotype panel pool by:
indexing the new haplotype by the PBWT representation, thereby transforming the new haplotype into a PBWT indexed new haplotype including the reversed prefix order; and
inserting the PBWT indexed new haplotype into at least one of the plurality of panels.
7. The genealogical indexing system of claim 6 , wherein the instructions further comprise adding the PBWT indexed new haplotype into at least one of the plurality of panels by inserting the PBWT indexed new haplotype into a correct position at each variant site of the set of variants and calculating divergence values at positions forward from the inserted PBWT indexed new haplotype.
8. The genealogical indexing system of claim 6 , wherein the PBWT indexed new haplotype is from the input genetic sequence.
9. The genealogical indexing system of claim 5 , wherein the instructions further comprise adding, via the haplotype ingestion engine of the computing nodule in electronic communication with the haplotype panel pool, a new haplotype into each of the plurality of panels by:
indexing the new haplotype by the PBWT representation, thereby transforming the new haplotype into a PBWT indexed new haplotype including the reversed prefix order; and
inserting the PBWT indexed new haplotype into a correct position at each variant site of the set of variants and calculating divergence values at positions forward from the inserted PBWT indexed new haplotype.
10. The genealogical indexing system of claim 4 , wherein the instructions further comprise deleting, via a haplotype ingestion engine of the computing nodule in electronic communication with the haplotype panel pool, executable by the processor, a haplotype from the haplotype panel pool by removing the haplotype from at least one of the plurality of panels.
11. The genealogical indexing system of claim 1 , wherein the instructions further comprise retrieving, via the computing nodule in electronic communication with the haplotype panel pool, a pre-computed genealogical match between the haplotype panel pool and the PBWT indexed input genetic sequence after the step of automatically indexing the input genetic sequence by the PBWT representation, such that the pre-computed genealogical match is displayed before the step of comparing the PBWT indexed input genetic sequence with the amount of the plurality of panels to find a match of the minimum identity-by-descent segment length of at least one million base pairs.
12. The genealogical indexing system of claim 1 , wherein the instructions of determining the minimum identity-by-descent segment length value of at least one million base pairs further comprise determining, via the computing nodule in electronic communication with the haplotype panel pool, at least one of a physical distance and a genetic distance between divergence value updates of a long match query algorithm.
13. A genealogical indexing system comprising:
a processor;
a haplotype panel pool in electronic communication with a non-transitory computer-readable medium that is operably coupled to the processor; and
the non-transitory computer-readable medium having computer-readable instructions stored thereon that, when executed by the processor, cause the genealogical indexing system to automatically identify a genealogical match with an input genetic sequence by executing instructions comprising:
indexing the haplotype panel pool including a plurality of panels that via a dynamic positional Burrows-Wheeler transform (PBWT) representation, each of the plurality of panels including a plurality of haplotypes, the haplotype panel pool having a set of variant sites, wherein each of the plurality of haplotypes is indexed by the dynamic PBWT representation in a reversed prefix order;
selecting, via a computing nodule in electronic communication with the haplotype panel pool, a minimum identity-by-descent segment length value of at least one million base pairs, such that haplotype matches greater than or equal to the minimum identity-by-descent segment length indicate a match between the input genetic sequence and the haplotype panel pool, and such that haplotype matches lesser than the minimum identity-by-descent segment length indicate a lack of a match between the input genetic sequence and the haplotype panel pool;
selecting, via a computing nodule in electronic communication with the haplotype panel pool, a plurality of portions of each of the plurality of panels to sample each of the plurality of panels;
projecting, via a computing nodule in electronic communication with the haplotype panel pool, the sample to the set of variant sites for each of the plurality of panels in the haplotype panel pool, such that the sample can be compared against the samples in the haplotype panel pool via the set of variants;
after projecting the sample to the set of variant sites for each of the plurality of panels in the haplotype panel pool, weighing, via a computing nodule in electronic communication with the haplotype panel pool, the set of variant sites to emphasize minor allele frequencies;
receiving, via a computing nodule in electronic communication with the haplotype panel pool, the input genetic sequence;
automatically indexing, via a haplotype querying engine via a computing nodule in electronic communication with the haplotype panel pool, executable by the processor, the input genetic sequence by the dynamic PBWT representation, thereby transforming the input genetic sequence into a PBWT indexed input genetic sequence including the reversed prefix order;
activating, via the haplotype querying engine of the computing nodule in electronic communication with the haplotype panel pool, an amount of the plurality of panels from the haplotype panel pool for testing;
comparing, via the haplotype querying engine of the computing nodule in electronic communication with the haplotype panel pool, the PBWT indexed input genetic sequence with the amount of the plurality of panels by comparing the PBWT indexed input genetic sequence with the set of variant sites; and
via the haplotype querying engine of the computing nodule in electronic communication with the haplotype panel pool, automatically identifying, in real-time and independent of a total number of haplotypes in the plurality of haplotypes, the genealogical match between the input genetic sequence and the haplotype pool by:
based on a determination that the PBWT indexed input genetic sequence matches the amount of the plurality of panels by a value greater than or equal to the minimum identity-by-descent segment length of at least one million base pairs, determining the genealogical match between the input genetic sequence and the haplotype panel pool; and
based on a determination that the PBWT indexed input genetic sequence does not match the amount of the plurality of panels by a value greater than or equal to the minimum identity-by-descent segment length of at least one million base pairs, determining a lack of the genealogical match between the input genetic sequence and the haplotype panel pool.
14. The genealogical indexing system of claim 13 , wherein the instructions of determining the genealogical match between the input genetic sequence and the haplotype panel pool further comprise utilizing a long match query algorithm to compare the PBWT indexed input genetic sequence with the amount of the plurality of panels and determine if the PBWT indexed input genetic sequence matches the amount of the plurality of panels by a value greater than or equal to the minimum identity-by-descent segment length of at least one million base pairs.
15. The genealogical indexing system of claim 13 , wherein the instructions further comprise adding, via a haplotype ingestion engine of the computing nodule in electronic communication with the haplotype panel pool, executable by the processor, a new haplotype into the haplotype panel pool by:
indexing the new haplotype by the dynamic PBWT representation, thereby transforming the new haplotype into a PBWT indexed new haplotype including the reversed prefix order; and
inserting the PBWT indexed new haplotype into at least one of the plurality of panels.
16. The genealogical indexing system of claim 15 , wherein the instructions further comprise adding the PBWT indexed new haplotype into at least one of the plurality of panels by inserting the PBWT indexed new haplotype into a correct position at each variant site of the set of variants and calculating divergence values at positions forward from the inserted PBWT indexed new haplotype.
17. The genealogical indexing system of claim 13 , wherein the instructions further comprise deleting, via a haplotype ingestion engine of the computing nodule in electronic communication with the haplotype panel pool, executable by the processor, a haplotype from the haplotype panel pool by removing the haplotype from at least one of the plurality of panels.
18. The genealogical indexing system of claim 13 , wherein the instructions of determining the minimum identity-by-descent segment length value of at least one million base pairs further comprise determining, via the computing nodule in electronic communication with the haplotype panel pool, at least one of a physical distance and a genetic distance between divergence value updates of a long match query algorithm.
19. A genealogical indexing system comprising:
a processor;
a haplotype panel pool in electronic communication with a non-transitory computer-readable medium that is operably coupled to the processor, the haplotype panel pool including a plurality of panels that are indexed by a dynamic positional Burrows-Wheeler transform (PBWT) representation, each of the plurality of panels including a plurality of haplotypes, the haplotype panel pool having a set of variant sites; and
the non-transitory computer-readable medium having computer-readable instructions stored thereon that, when executed by the processor, cause the genealogical indexing system to automatically identify a genealogical match with an input genetic sequence by executing instructions comprising:
indexing each of the plurality of haplotypes of the haplotype panel pool in a reversed prefix order via the dynamic PBWT representation;
selecting, via a computing nodule in electronic communication with the haplotype panel pool, a minimum identity-by-descent segment length value of at least one million base pairs, such that haplotype matches greater than or equal to the minimum identity-by-descent segment length indicate a match between the input genetic sequence and the haplotype panel pool, and such that haplotype matches lesser than the minimum identity-by-descent segment length indicate a lack of a match between the input genetic sequence and the haplotype panel pool;
selecting, via the computing nodule in electronic communication with the haplotype panel pool, a plurality of portions of each of the plurality of panels to sample each of the plurality of panels;
projecting, via the computing nodule in electronic communication with the haplotype panel pool, the sample to the set of variant sites for each of the plurality of panels in the haplotype panel pool, such that the sample can be compared against the samples in the haplotype panel pool via the set of variants;
after projecting the sample to the set of variant sites for each of the plurality of panels in the haplotype panel pool, weighing, via the computing nodule in electronic communication with the haplotype panel pool, the set of variant sites to emphasize minor allele frequencies;
receiving, via the computing nodule in electronic communication with the haplotype panel pool, the input genetic sequence;
automatically indexing, via a haplotype querying engine of the computing nodule in electronic communication with the haplotype panel pool, executable by the processor, the input genetic sequence by the dynamic PBWT representation, thereby transforming the input genetic sequence into a PBWT indexed input genetic sequence including the reversed prefix order;
activating, via the haplotype querying engine of the computing nodule in electronic communication with the haplotype panel pool, an amount of the plurality of panels from the haplotype panel pool for testing; and
utilizing a long match query algorithm, comparing, via the haplotype querying engine of the computing nodule in electronic communication with the haplotype panel pool, the PBWT indexed input genetic sequence with the amount of the plurality of panels by comparing the PBWT indexed input genetic sequence with the set of variant sites, to automatically identify, in real-time and independent of a total number of haplotypes in the plurality of haplotypes, the genealogical match between the input genetic sequence and the haplotype pool by:
based on a determination that the PBWT indexed input genetic sequence matches the amount of the plurality of panels by the value greater than or equal to the minimum identity-by-descent segment length of at least one million base pairs, determining the genealogical match between the input genetic sequence and the haplotype panel pool; and
based on a determination that the PBWT indexed input genetic sequence does not match the amount of the plurality of panels by a value greater than or equal to the minimum identity-by-descent segment length of at least one million base pairs, determining a lack of the genealogical match between the input genetic sequence and the haplotype panel pool.