SYSTEMS AND METHODS FOR ALIGNING SEQUENCES TO PERSONALIZED REFERENCES

1 . A system, comprising:

at least one hardware processor; and

at least one non-transitory computer-readable storage medium storing processor-executable instructions that, when executed by the at least one hardware processor, cause the at least one hardware processor to perform:

obtaining a plurality of sequence reads for an individual;

obtaining information identifying a plurality of locations;

genotyping the plurality of sequence reads for the plurality of locations to obtain a first set of variants for the individual for at least some of the plurality of locations;

identifying a second set of variants associated with the first set of variants;

generating a personalized reference sequence construct using the second set of variants; and

aligning the plurality of sequence reads to the personalized reference sequence construct.

2 . The system of claim 1 , wherein identifying the second set of variants associated with the first set of variants comprises identifying one or more variants correlated with variants in the first set of variants.

3 . The system of claim 1 , wherein identifying the second set of variants comprises:

accessing a model for identifying one or more subpopulations in a plurality of sub-populations to which the individual likely belongs;

identifying, using the first set of variants and the model, a first subpopulation in the plurality of subpopulations to which the individual likely belongs; and

identifying the second set of variants as variants associated with the first subpopulation.

4 . The system of claim 3 , wherein the at least one processor is further configured to perform:

identifying a third set of variants associated with the first set of variants,

wherein generating the personalized reference sequence construct is performed by using the third set of variants.

5 . The system of claim 4 , wherein identifying the third set of variants comprises:

identifying, using the first set of variants and the model, a second subpopulation in the plurality of subpopulations to which the individual likely belongs; and

identifying the third set of variants as variants associated with the second subpopulation.

6 . The system of claim 3 ,

wherein the model comprises information indicating subpopulation-specific variant occurrence frequencies for at least some of the plurality of locations; and

wherein identifying the first subpopulation is performed by comparing the subpopulation-specific variant occurrence frequencies with the first set of variants.

7 . The system of claim 3 , wherein genotyping the plurality of sequence reads for the plurality of locations is performed using a reference construct different from the personalized reference sequence construct.

8 . The system of claim 7 , wherein the reference construct comprises a linear reference sequence.

9 . The system of claim 8 , wherein the genotyping comprises:

identifying a set of locations in the linear reference sequence; and

aligning the plurality of sequence reads to locations in the linear reference sequence that are not in the identified set of locations.

10 . The system of claim 7 ,

wherein the reference construct comprises a plurality of sets of alternative sequences, each of the plurality of sets of alternative sequences corresponding to a respective subpopulation in the plurality of subpopulations, and

wherein the genotyping comprises comparing the plurality of sequence reads to sequences in each of the plurality of sets of alternative sequences.

11 . The system of claim 10 , wherein identifying the first subpopulation comprises:

identifying, among the plurality of sets of alternative sequences, a set of alternative sequences that best matches the plurality of sequence reads based on results of the comparing; and

identifying, among the plurality of subpopulations, a subpopulation corresponding to the identified set of alternative sequences.

12 . The system of claim 1 , wherein the personalized reference sequence construct comprises a directed acyclic graph through which there are multiple paths.

13 . The system of claim 1 , wherein generating the personalized reference sequence construct comprises:

obtaining an initial reference sequence construct; and

updating the initial reference sequence construct to reflect variants in the second set of variants.

14 . The system of claim 13 , wherein the initial reference sequence construct comprises a linear reference sequence and wherein updating the initial reference sequence construct comprises generating a directed acyclic graph by transforming the linear reference sequence into an initial graph and adding nodes and edges to the initial graph to obtain a directed acyclic graph reflecting the linear reference sequence and the second set of variants.

15 . The system of claim 13 , wherein the initial reference sequence construct comprises a linear reference sequence, and wherein updating the initial reference sequence construct comprises adding, to the initial reference sequence construct, a set of one or more alternative sequences reflecting the second set of variants.

16 . The system of claim 3 , further comprising:

identifying the plurality of subpopulations by applying one or more statistical techniques to genomic data.

17 . The system of claim 3 , wherein obtaining the information identifying the plurality of locations comprises:

identifying locations at which frequencies of variant occurrence vary among at least some subpopulations in a plurality of subpopulations.

18 . The system of claim 1 , wherein the plurality of locations consists of less than 100,000 locations.

19 . The system of claim 1 , wherein the plurality of locations consists of between 1 and 1.5 million locations.

20 . At least one non-transitory computer-readable storage medium storing processor-executable instructions that, when executed by at least one hardware processor, cause the at least one hardware processor to perform:

obtaining a plurality of sequence reads for an individual;

obtaining information identifying a plurality of locations;

genotyping the plurality of sequence reads for the plurality of locations to obtain a first set of variants for the individual for at least some of the plurality of locations;

identifying a second set of variants associated with the first set of variants;

generating a personalized reference sequence construct using the second set of variants; and

aligning the plurality of sequence reads to the personalized reference sequence construct.