Granted Patent B2

US 12,260,936 · App. 18/737,679 · Granted Mar 25, 2025

Inventors: William A. Freyman (Menlo Park, CA); Kimberly F. McManus (San Francisco, CA); Suyash S. Shringarpure (Mountain View, CA); Ethan M. Jewett (San Jose, CA); Adam Auton (Menlo Park, CA)

Assignee: 23andMe, Inc.

G16B20/20C12Q1/6827G16B30/00G16B50/30

Abstract

Claims (47)

1. A method comprising:

computationally identifying, by a services platform, identity-by-descent (IBD) segments between a focal string of a focal individual and a reference string of a reference individual,

wherein identifying IBD segments comprises:

in parallel:

(i) masking and unmasking locations of the focal string and the reference string in a sliding window according to a first mask pattern of consecutive locations; and identifying first matches among values of the focal string and the reference string at unmasked locations; and

(ii) masking and unmasking locations of the focal string and the reference string in a sliding window according to a second mask pattern of consecutive locations, wherein the second mask pattern is different from the first mask pattern; and identifying second matches among values of the focal string and the reference string at unmasked locations; and

merging the first matches and the second matches to produce a merged set of IBD segments; and

determining, by the services platform and based on the merged set of IBD segments, a degree of relatedness between the focal individual and the reference individual.

2. The method of claim 1 , wherein the sliding window of the first mask and the sliding window of the second mask are each at least four consecutive locations in size.

3. The method of claim 1 , wherein the focal individual is a user of the services platform.

4. The method of claim 1 ,

wherein computationally identifying IBD segments between the focal string and the reference string further comprises:

masking and unmasking locations of the focal string and the reference string in a sliding window according to a third mask pattern of consecutive locations, wherein the third mask pattern is different from the first mask pattern and the second mask pattern; and

identifying third matches among values of the focal string and the reference string at unmasked locations, and

wherein merging the first matches and the second matches to produce the merged set of IBD segments comprises merging the first matches, the second matches, and the third matches to produce the merged set of IBD segments.

5. The method of claim 1 , wherein the focal individual is a human.

6. The method of claim 1 , wherein each of the focal string and the reference string comprises at least one thousand strings.

7. The method of claim 1 , wherein computationally identifying IBD segments between the focal string and the reference string comprises performing a positional Burrows-Wheeler transform (PBWT) on the unmasked locations produced by:

masking and unmasking locations of the focal string and the reference string in the sliding window according to the first mask pattern of consecutive locations; or

masking and unmasking locations of the focal string and the reference string in the sliding window according to the second mask pattern of consecutive locations.

8. The method of claim 7 , wherein merging the first matches and the second matches is performed while considering individual locations of the focal string and the reference string using the PBWT.

9. The method of claim 1 , wherein the first mask pattern of consecutive locations is determined deterministically.

10. The method of claim 9 , wherein the first mask pattern varies based on a location of the sliding window with respect to the focal string or the reference string.

11. The method of claim 1 , wherein the first mask pattern of consecutive locations is determined using a probabilistic function.

12. A system comprising:

one or more processors and associated memory; and

computer readable instructions that, when executed by the one or more processors, cause the one or more processors to:

computationally identify, by a services platform, identity-by-descent (IBD) segments between a focal string of a focal individual and a reference string of a reference individual, wherein identifying IBD segments comprises:

in parallel:

(i) masking and unmasking locations of the focal string and the reference string in a sliding window according to a first mask pattern of consecutive locations; and identifying first matches among values of the focal string and the reference string at unmasked locations; and

(ii) masking and unmasking locations of the focal string and the reference string in a sliding window according to a second mask pattern of consecutive locations, wherein the second mask pattern is different from the first mask pattern; and identifying second matches among values of the focal string and the reference string at unmasked locations; and

merging the first matches and the second matches to produce a merged set of IBD segments; and

determine, by the services platform and based on the merged set of IBD segments, a degree of relatedness between the focal individual and the reference individual.

13. The system of claim 12 , wherein the sliding window of the first mask and the sliding window of the second mask are each at least four consecutive locations in size.

14. The system of claim 12 ,

wherein computationally identifying IBD segments between the focal string and the reference string further comprises:

masking and unmasking locations of the focal string and the reference string in a sliding window according to a third mask pattern of consecutive locations, wherein the third mask pattern is different from the first mask pattern and the second mask pattern; and

identifying third matches among values of the focal string and the reference string at unmasked locations, and

wherein merging the first matches and the second matches to produce the merged set of IBD segments comprises merging the first matches, the second matches, and the third matches to produce the merged set of IBD segments.

15. The system of claim 12 , wherein the focal individual is a human, and wherein the focal individual is a user of the services platform.

16. The system of claim 12 , wherein each of the focal string and the reference string comprises at least one thousand strings.

17. The system of claim 12 , wherein computationally identifying IBD segments between the focal string and the reference string comprises performing a positional Burrows-Wheeler transform (PBWT) on the unmasked locations produced by:

masking and unmasking locations of the focal string and the reference string in the sliding window according to the first mask pattern of consecutive locations; or

masking and unmasking locations of the focal string and the reference string in the sliding window according to the second mask pattern of consecutive locations.

18. The system of claim 17 , wherein merging the first matches and the second matches is performed while considering individual locations of the focal string and the reference string using the PBWT.

19. The system of claim 12 , wherein the first mask pattern of consecutive locations is determined deterministically.

20. The system of claim 12 , wherein the first mask pattern of consecutive locations is determined using a probabilistic function.

Assignments (4)

Continuity (4)

References Cited (400)