Bin-specific and hash-based efficient comparison of sequencing results

1. A computer-implemented method of efficiently comparing sequenced outputs, the method including:

accessing a first sequenced output and a second sequenced output, wherein the first and second sequenced outputs contain variants occurring at different carriers and at different carrier positions and are partitioned into bins;

generating a reference array for those carrier positions that are shared between the first and second sequenced outputs;

based on the reference array, generating a first sequence from the first sequenced output and a second sequence from the second sequenced output;

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 between the first and second sequences on a bin-by-bin basis such that a first set of selected window hashes produced for base patterns in a given bin in the first sequenced output are compared only to a second set of selected window hashes produced for base patterns in the given bin in the second sequenced output;

identifying common window hashes for each bin in the first and second sequences based on the comparing; and

determining a similarity measure for each bin based on the common window hashes.

2. The computer-implemented method of claim 1 , further including:

requiring that the selected window hashes in the first set completely match with the corresponding selected window hashes in the second set.

3. The computer-implemented method of claim 1 , further including:

based on bin-wise similarity measures, determining a percentage of shared bases between the first and second sequenced outputs, wherein the percentage of shared bases are determined on a carrier-by-carrier basis.

4. The computer-implemented method of claim 3 , further including:

determining inherited traits based on the percentage of shared bases.

5. The computer-implemented method of claim 3 , further including:

identifying common ancestors and close and distant relatives based on the percentage of shared bases.

6. The computer-implemented method of claim 1 , further including:

based on the bin-wise similarity measures, determining a percentage of shared bases between a given individual's sequence and an ethnicity-specific sequence; and

identifying ethnic ancestry of the given individual based on the percentage of shared bases.

7. The computer-implemented method of claim 6 , further including:

for the bin-wise similarity measures, requiring that selected window hashes in the first and second sets substantially match.

8. The computer-implemented method of claim 1 , wherein the bins are defined for the first and second sequenced outputs on a carrier-by-carrier basis.

9. The computer-implemented method of claim 1 , wherein each bin contains five hundred to thousand variants.

10. The computer-implemented method of claim 1 , wherein each bin spans across one hundred thousand to one million bases.

11. The computer-implemented method of claim 1 , wherein each bin spans across multiple units.

12. The computer-implemented method of claim 1 , further including:

based on the bin-wise similarity measures, generating a distance tree between the first and second sequenced outputs.

13. The computer-implemented method of claim 1 , wherein the variants are those variants that have highest observation frequency.

14. The computer-implemented method of claim 1 , wherein the variants are identified by sixteen phased pairings.

15. The computer-implemented method of claim 1 , wherein the variants are identified by ten unphased pairings.

16. The computer-implemented method of claim 1 , wherein the selected pattern length of positions ranges from fifteen to forty bases.

17. The computer-implemented method of claim 1 , wherein length of the reference array ranges from one hundred thousand to one million base positions.

18. The computer-implemented method of claim 17 , wherein the reference array is ordered by carriers and by carrier positions.

19. The computer-implemented method of claim 17 , wherein the pattern length of positions is selected based on the length of the reference array.

20. The computer-implemented method of claim 1 , wherein the ceiling number of times ranges from one to ten.

21. 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

.

22. A non-transitory computer readable storage medium impressed with computer program instructions to efficiently compare sequenced outputs, the instructions, when executed on a processor, implement a method comprising:

accessing a first sequenced output and a second sequenced output, wherein the first and second sequenced outputs contain variants occurring at different carriers and at different carrier positions and are partitioned into bins;

generating a reference array for those carrier positions that are shared between the first and second sequenced outputs;

based on the reference array, generating a first sequence from the first sequenced output and a second sequence from the second sequenced output;

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 between the first and second sequences on a bin-by-bin basis such that a first set of selected window hashes produced for base patterns in a given bin in the first sequenced output are compared only to a second set of selected window hashes produced for base patterns in the given bin in the second sequenced output;

identifying common window hashes for each bin in the first and second sequences based on the comparing; and

determining a similarity measure for each bin based on the common window hashes.

23. A system including one or more processors coupled to memory, the memory loaded with computer instructions to efficiently compare sequenced outputs, the instructions, when executed on the processors, implement actions comprising:

accessing a first sequenced output and a second sequenced output, wherein the first and second sequenced outputs contain variants occurring at different carriers and at different carrier positions and are partitioned into bins;

generating a reference array for those carrier positions that are shared between the first and second sequenced outputs;

based on the reference array, generating a first sequence from the first sequenced output and a second sequence from the second sequenced output;

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 between the first and second sequences on a bin-by-bin basis such that a first set of selected window hashes produced for base patterns in a given bin in the first sequenced output are compared only to a second set of selected window hashes produced for base patterns in the given bin in the second sequenced output;

identifying common window hashes for each bin in the first and second sequences based on the comparing; and

determining a similarity measure for each bin based on the common window hashes.