Error correction in ancestry classification

1. A method of determining ancestry origin of a first chromosome and a second chromosome of a chromosome pair of autosomal chromosomes of an individual, comprising:

(a) obtaining, from a data source and for the first chromosome and the second chromosome of the chromosome pair of autosomal chromosomes of the individual, unphased genotype data comprising a plurality of genetic markers associated with the first chromosome and the second chromosome of the chromosome pair;

(b) applying, using one or more computer processors, a phasing method to the unphased genotype data of the first and second chromosomes of the chromosome pair of autosomal chromosomes of the individual to generate a first set of phased haplotype data for the first chromosome of the chromosome pair and a second set of phased haplotype data for the second chromosome of the chromosome pair;

(c) dividing, using one or more computer processors and based on the plurality of genetic markers, the first set of phased haplotype data of the first chromosome of the chromosome pair into a first sequence of non-overlapping haplotype windows and the second set of phased haplotype data of the second chromosome of the chromosome pair into a second sequence of non-overlapping haplotype windows,

wherein each haplotype window at a chromosome location of the first sequence of non-overlapping haplotype windows of the first chromosome of the chromosome pair is paired with a haplotype window at a same chromosome location of the second sequence of non-overlapping haplotype windows of the second chromosome of the chromosome pair;

(d) assigning, using a classifier model and one or more computer processors, an initial ancestry classification to each haplotype window of the first sequence of non-overlapping haplotype windows of the first chromosome of the chromosome pair and to each haplotype window of the second sequence of non-overlapping haplotype windows of the second chromosome of the chromosome pair, wherein each initial ancestry classification classifies each haplotype window as originating from an ancestry associated with a single geographical region or a single ethnicity, thereby generating a sequence of observed states, wherein each observed state is an ordered pair of initial ancestry classifications at a given chromosome location;

(e) inputting, using one or more computer processors, the sequence of observed states of (d) to an Autoregressive Pair Hidden Markov Model (APHMM); and

(f) performing dynamic programming, by one or more computer processors, to apply the APHMM to the sequence of observed states of (d) to produce a likely sequence of hidden states for the chromosome pair,

wherein each observed state at a position in the sequence of observed states depends on its underlying hidden state and depends on at least one observed state at a previous position in the sequence of observed states,

and wherein each hidden state is an ordered pair of likely ancestry classifications for a pair of haplotype windows of the first and second chromosomes of the chromosome pair at a given chromosome location, and wherein each hidden state at a position in the likely sequence of hidden states depends on the hidden state at a previous position in the likely sequence of hidden states, and

wherein at least one error in the initial ancestry classification and/or phasing of the first and second chromosome of the chromosome pair is corrected,

thereby determining ancestry origin of the first chromosome and the second chromosome of the chromosome pair of autosomal chromosomes of the individual.

2. The method of claim 1 , wherein the at least one observed state at the previous position in the sequence of observed states is the immediately previous observed state in the sequence of observed states.

3. The method of claim 2 , wherein a probability of a sequence of hidden states of the APHMM is calculated according to the following equation:

Pr ( H 1 ,H 2 ,H 3 , . . . ,O 1 ,O 2 ,O 3 , . . . )= Pr ( H 1 ) Pr ( O 1 |H 1 ) Pr ( H 2 |H 1 ) Pr ( O 2 |H 2 ,O 1 ) Pr ( H 3 |H 2 ) Pr ( O 3 |H 3 ,O 2 ) . . .

wherein:

O i is an i th observed state of the sequence of observed states;

H i is an i th hidden state of the sequence of hidden states of the APHMM;

Pr(H 1 , H 2 , H 3 , . . . , O 1 , O 2 , O 3 , . . . ) is a probability of hidden states H 1 , H 2 , H 3 , . . . , H i given observed states O 1 , O 2 , O 3 , . . . , O i ;

Pr(H i |H i-1 ) is a probability of H i given H i-1 ; and

P(O j |H j , O j-1 ) is a probability of O j given H j and O j-1 .

4. The method of claim 1 , wherein correcting at least one error in the initial ancestry classification comprises: providing at least one likely ancestry classification of an ordered pair of likely ancestry classifications for at least one hidden state in the likely sequence of hidden states, wherein the at least one likely ancestry classification is different from the initial ancestry classification.

5. The method of claim 1 , wherein at least one error in the initial ancestry classification of the first and second chromosome of the chromosome pair is corrected.

6. The method of claim 1 , wherein each initial ancestry classification classifies each haplotype window as originating from an ancestry associated with a single geographical region.

7. The method of claim 1 , wherein the APHMM comprises a plurality of transition parameters and a plurality of emission parameters, each transition parameter being a probability of a hidden state at a position in a sequence of hidden states given a hidden state at a previous position in the sequence of hidden states, and each emission parameter being a probability of an observed state at a position in a sequence of observed states given its underlying hidden state and at least one observed state at a previous position in the sequence of observed states.

8. A computer system, comprising:

one or more processors;

system memory; and

one or more computer-readable storage media having stored thereon computer-executable instructions that, when executed by the one or more processors, cause the computer system to:

(a) obtain, from a data source and for a first chromosome and a second chromosome of a chromosome pair of autosomal chromosomes of an individual, unphased genotype data comprising a plurality of genetic markers associated with the first chromosome and the second chromosome of the chromosome pair;

(b) apply a phasing method to the unphased genotype data of the first and second chromosomes of the chromosome pair of autosomal chromosomes of the individual to generate a first set of phased haplotype data for the first chromosome of the chromosome pair and a second set of phased haplotype data for the second chromosome of the chromosome pair;

(c) divide, based on the plurality of genetic markers, the first set of phased haplotype data of the first chromosome of the chromosome pair into a first sequence of non-overlapping haplotype windows and the second set of phased haplotype data of the second chromosome of the chromosome pair into a second sequence of non-overlapping haplotype windows,

wherein each haplotype window at a chromosome location of the first sequence of non-overlapping haplotype windows of the first chromosome of the chromosome pair is paired with a haplotype window at a same chromosome location of the second sequence of non-overlapping haplotype windows of the second chromosome of the chromosome pair;

(d) assign, using a classifier model, an initial ancestry classification to each haplotype window of the first sequence of non-overlapping haplotype windows of the first chromosome of the chromosome pair and to each haplotype window of the second sequence of non-overlapping haplotype windows of the second chromosome of the chromosome pair, wherein each initial ancestry classification classifies each haplotype window as originating from an ancestry associated with a single geographical region or a single ethnicity, thereby generating a sequence of observed states, wherein each observed state is an ordered pair of initial ancestry classifications at a given chromosome location;

(e) input the sequence of observed states of (d) to an Autoregressive Pair Hidden Markov Model (APHMM); and

(f) perform dynamic programming, by one or more processors, to apply the APHMM to the sequence of observed states of (d) to produce a likely sequence of hidden states for the chromosome pair,

wherein each observed state at a position in the sequence of observed states depends on its underlying hidden state and depends on at least one observed state at a previous position in the sequence of observed states,

and wherein each hidden state is an ordered pair of likely ancestry classifications for a pair of haplotype windows for of the first and second chromosomes of the chromosome pair at a given chromosome location, and wherein each hidden state at a position in the likely sequence of hidden states depends on the hidden state at a previous position in the likely sequence of hidden states, and

wherein at least one error in the initial ancestry classification and/or phasing of the first and second chromosome of the chromosome pair is corrected,

to thereby determine ancestry origin of the first chromosome and the second chromosome of the chromosome pair of autosomal chromosomes of the individual.

9. The system of claim 8 , wherein the at least one observed state at the previous position in the sequence of observed states is the immediately previous observed state in the sequence of observed states.

10. The system of claim 9 , wherein a probability of a sequence of hidden states of the APHMM is calculated according to the following equation:

Pr ( H 1 ,H 2 ,H 3 , . . . ,O 1 ,O 2 ,O 3 , . . . )= Pr ( H 1 ) Pr ( O 1 |H 1 ) Pr ( H 2 |H 1 ) Pr ( O 2 |H 2 ,O 1 ) Pr ( H 3 |H 2 ) Pr ( O 3 |H 3 ,O 2 ) . . .

wherein:

O i is an i th observed state of the sequence of observed states;

H i is an i th hidden state of the sequence of hidden states of the APHMM;

Pr(H 1 , H 2 , H 3 , . . . , O 1 , O 2 , O 3 , . . . ) is a probability of hidden states H 1 , H 2 , H 3 , . . . , H i given observed states O 1 , O 2 , O 3 , . . . , O i ;

Pr(H i |H i-1 ) is a probability of H i given H i-1 ; and

P(O j |H j , O j-1 ) is a probability of O j given H j and O j-1 .

11. The system of claim 8 , wherein the computer-executable instructions further comprises instructions that cause the computer system to: provide at least one likely ancestry classification of an ordered pair of likely ancestry classifications for at least one hidden state in the likely sequence of hidden states, wherein the at least one likely ancestry classification is different from the initial ancestry classification.

12. The system of claim 8 , wherein at least one error in the initial ancestry classification of the first and second chromosome of the chromosome pair is corrected.

13. The system of claim 8 , wherein each initial ancestry classification classifies each haplotype window as originating from an ancestry associated with a single geographical region.

14. The system of claim 8 , wherein the APHMM comprises a plurality of transition parameters and a plurality of emission parameters, each transition parameter being a probability of a hidden state at a position in a sequence of hidden states given a hidden state at a previous position in the sequence of hidden states, and each emission parameter being a probability of an observed state at a position in a sequence of observed states given its underlying hidden state and at least one observed state at a previous position in the sequence of observed states.

15. A computer program product for determining ancestry origin of a first chromosome and a second chromosome of a chromosome pair of autosomal chromosomes of an individual, the computer program product being embodied in a non-transitory tangible computer readable storage medium and comprising computer instructions for:

(a) obtaining, from a data source and for the first chromosome and the second chromosome of the chromosome pair of autosomal chromosomes of the individual, unphased genotype data comprising a plurality of genetic markers associated with the first chromosome and the second chromosome of the chromosome pair;

(b) applying a phasing method to the unphased genotype data of the first and second chromosomes of the chromosome pair to generate a first set of phased haplotype data for the first chromosome of each chromosome pair and a second set of phased haplotype data for the second chromosome of the chromosome pair;

(c) dividing, based on the plurality of genetic markers, the first set of phased haplotype data of the first chromosome of the chromosome pair into a first sequence of non-overlapping haplotype windows and the second set of phased haplotype data of the second chromosome of the chromosome pair into a second sequence of non-overlapping haplotype windows,

wherein each haplotype window at a chromosome location of the first sequence of non-overlapping haplotype windows of the first chromosome of the chromosome pair is paired with a haplotype window at a same chromosome location of the second sequence of non-overlapping haplotype windows of the second chromosome of the chromosome pair;

(d) assigning, using a classifier model, an initial ancestry classification to each haplotype window of the first sequence of non-overlapping haplotype windows of the first chromosome of the chromosome pair and to each haplotype window of the second sequence of non-overlapping haplotype windows of the second chromosome of the chromosome pair, wherein each initial ancestry classification classifies each haplotype window as originating from an ancestry associated with a single geographical region or a single ethnicity, thereby generating a sequence of observed states, wherein each observed state is an ordered pair of initial ancestry classifications at a given chromosome location;

(e) inputting the sequence of observed states of (d) to an Autoregressive Pair Hidden Markov Model (APHMM); and

(f) performing dynamic programming, by one or more computer processors, to apply the APHMM to the sequence of observed states of (d) to produce a likely sequence of hidden states for the chromosome pair,

wherein each observed state at a position in the sequence of observed states depends on its underlying hidden state and depends on at least one observed state at a previous position in the sequence of observed states,

and wherein each hidden state is an ordered pair of likely ancestry classifications for a pair of haplotype windows of the first and second chromosomes of the chromosome pair at a given chromosome location, and wherein each hidden state at a position in the likely sequence of hidden states depends on the hidden state at a previous position in the likely sequence of hidden states, and

wherein at least one error in the initial ancestry classification and/or phasing of the first and second chromosome of the chromosome pair is corrected,

thereby determining ancestry origin of the first chromosome and the second chromosome of the chromosome pair of autosomal chromosomes of the individual.

16. The computer program product of claim 15 , wherein the at least one observed state at the previous position in the sequence of observed states is the immediately previous observed state in the sequence of observed states.

17. The computer program product of claim 16 , wherein a probability of a sequence of hidden states of the APHMM is calculated according to the following equation:

Pr ( H 1 ,H 2 ,H 3 , . . . ,O 1 ,O 2 ,O 3 , . . . )= Pr ( H 1 ) Pr ( O 1 |H 1 ) Pr ( H 2 |H 1 ) Pr ( O 2 |H 2 ,O 1 ) Pr ( H 3 |H 2 ) Pr ( O 3 |H 3 ,O 2 ) . . .

wherein:

O i is an i th observed state of the sequence of observed states;

H i is an i th hidden state of the sequence of hidden states of the APHMM;

Pr(H 1 , H 2 , H 3 , . . . , O 1 , O 2 , O 3 , . . . ) is a probability of hidden states H 1 , H 2 , H 3 , . . . , H i given observed states O 1 , O 2 , O 3 , . . . , O i ;

Pr(H i |H i-1 ) is a probability of H i given H i-1 ; and

P(O j |H j , O j-1 ) is a probability of O j given H j and O j-1 .

18. The computer program product of claim 15 , further comprising computer instructions to: provide at least one likely ancestry classification of an ordered pair of likely ancestry classifications for at least one hidden state in the likely sequence of hidden states, wherein the at least one likely ancestry classification is different from the initial ancestry classification.

19. The computer program product of claim 15 , wherein at least one error in the initial ancestry classification of the first and second chromosome of the chromosome pair is corrected.

20. The computer program product of claim 15 , wherein each initial ancestry classification classifies each haplotype window as originating from an ancestry associated with a single geographical region.