Hash-based efficient comparison of sequencing results
The technology disclosed generates a reference array of variant data for locations that are shared between read results which are to be compared, and generates hashes over a selected pattern length of positions in the reference array to independently produce non-unique window hashes for base patterns in the read results. It then selects for comparison window hashes that occur less than a ceiling number of times and compares the selected window hashes to identify common window hashes between the read results. It then determines a similarity measure for the read results based on the common window hashes.
1. A computer-implemented method of efficiently comparing read results, the method including:
generating a reference array of variant data for locations shared between read results to be compared;
generating hashes over a selected pattern length of positions in the reference array to independently produce non-unique window hashes for base patterns in the read results;
selecting for comparison window hashes that occur less than a ceiling number of times;
comparing the selected window hashes to identify common window hashes between the read results; and
determining a similarity measure for the read results based on the common window hashes.
2. The computer-implemented method of claim 1 , wherein the variant data is identified by one selected from sixteen phased pairings and ten unphased pairings.
3. The computer-implemented method of claim 1 , wherein the selected pattern length of positions ranges from fifteen to forty bases.
4. The computer-implemented method of claim 1 , wherein length of the reference array ranges from one hundred thousand to one million base positions.
5. The computer-implemented method of claim 4 , wherein the reference array is ordered by carriers and by carrier positions.
6. The computer-implemented method of claim 4 , wherein the pattern length of positions is selected based on the length of the reference array.
7. The computer-implemented method of claim 1 , wherein the ceiling number of times ranges from one to ten.
8. The computer-implemented method of claim 1 , wherein the similarity measure is determined by a distance formula defined as
1
-
number
of
common
window
hashes
number
of
unique
window
hashes
.
9. The computer-implemented method of claim 1 , further including:
partitioning the read results into bins;
comparing the selected window hashes between the read results on a bin-by-bin basis such that selected window hashes for base patterns occurring in corresponding bins in the read results are compared;
based on the comparing, identifying common window hashes between the corresponding bins; and
determining a similarity measure for the corresponding bins based on the common window hashes.
10. The computer-implemented method of claim 9 , further including:
requiring that the selected window hashes between the corresponding bins completely match.
11. The computer-implemented method of claim 9 , further including:
based on bin-wise similarity measures, determining a percentage of shared bases between the read results, wherein the percentage of shared bases are determined on a carrier-by-carrier basis; and
determining inherited traits based on the percentage of shared bases as determined from the bin-wise similarity measures.
12. The computer-implemented method of claim 9 , further including:
based on bin-wise similarity measures, determining a percentage of shared bases between the read results, wherein the percentage of shared bases are determined on a carrier-by-carrier basis; and
identifying common ancestors and close and distant relatives based on the percentage of shared bases as determined from the bin-wise similarity measures.
13. The computer-implemented method of claim 9 , further including:
based on the bin-wise similarity measures, determining a percentage of shared bases between a given individual's read results and ethnicity-specific read results;
identifying ethnic ancestry of the given individual based on the percentage of shared bases; and
for the bin-wise similarity measures, requiring that the selected window hashes between the corresponding bins substantially match.
14. The computer-implemented method of claim 9 , wherein the bins are defined for the read results on a carrier-by-carrier basis.
15. The computer-implemented method of claim 9 , wherein each bin contains five hundred to thousand variants.
16. The computer-implemented method of claim 9 , wherein each bin spans across one hundred thousand to one million bases.
17. The computer-implemented method of claim 9 , wherein each bin spans across multiple units.
18. The computer-implemented method of claim 9 , further including:
based on the bin-wise similarity measures, generating a distance tree visualization between the read results.
19. The computer-implemented method of claim 1 , wherein the variant data contains those variants that have highest observed frequency.
20. The computer-implemented method of claim 1 , further including:
comparing the selected window hashes between the read results on a starting position basis such that selected window hashes for base patterns having same start positions in the read results are compared;
identifying common window hashes between the read results based on the comparing; and
determining a similarity measure between the read results based on the common window hashes.
21. The computer-implemented method of claim 20 , further including:
based on starting position-wise similarity measures, determining a percentage of shared bases between the read results, wherein the percentage of shared bases are determined on a carrier-by-carrier basis; and
determining inherited traits based on the percentage of shared bases as determined from the starting position-wise similarity measures.
22. The computer-implemented method of claim 20 , further including:
based on starting position-wise similarity measures, determining a percentage of shared bases between the read results, wherein the percentage of shared bases are determined on a carrier-by-carrier basis; and
identifying common ancestors and close and distant relatives based on the percentage of shared bases as determined from the starting position-wise similarity measures.
23. The computer-implemented method of claim 20 , further including:
based on the starting position-wise similarity measures, determining a percentage of shared bases between a given individual's read results and ethnicity-specific read results; and
identifying ethnic ancestry of the given individual based on the percentage of shared bases.
24. The computer-implemented method of claim 20 , further including:
based on the starting position-wise similarity measures, generating a distance tree visualization between the read results.
25. A non-transitory computer readable storage medium impressed with computer program instructions to efficiently compare read results, the instructions, when executed on a processor, implement a method of claim 1 :
generating a reference array of variant data for locations shared between read results to be compared;
generating hashes over a selected pattern length of positions in the reference array to independently produce non-unique window hashes for base patterns in the read results;
selecting for comparison window hashes that occur less than a ceiling number of times;
comparing the selected window hashes to identify common window hashes between the read results; and
determining a similarity measure for the read results based on the common window hashes.
26. A system including one or more processors coupled to memory, the memory loaded with computer instructions to efficiently compare read results, the instructions, when executed on the processors, implement actions comprising:
generating a reference array of variant data for locations shared between read results to be compared;
generating hashes over a selected pattern length of positions in the reference array to independently produce non-unique window hashes for base patterns in the read results;
selecting for comparison window hashes that occur less than a ceiling number of times;
comparing the selected window hashes to identify common window hashes between the read results; and
determining a similarity measure for the read results based on the common window hashes.
27. A computer-implemented method of efficiently comparing sequenced files, the method including:
accessing a first sequenced file and a second sequenced file, wherein the first and second sequenced files contain variants occurring at different carriers and at different carrier positions;
generating a reference array for those carrier positions that are shared between the first and second sequenced files;
based on the reference array, generating a first sequence from the first sequenced file and a second sequence from the second sequenced file;
generating hashes over a selected pattern length of positions in the reference array to independently produce non-unique window hashes for base patterns in the first and second sequences;
selecting for comparison window hashes that occur less than a ceiling number of times;
comparing the selected window hashes to identify common window hashes between the first and second sequences; and
determining a similarity measure between the first and second sequences based on the common window hashes.