Haplotype determination
Haplotypes for phased genotypic information are determined from unphased genotypic information. One exemplary method includes separating a dataset that includes genotypic information for a plurality of markers for each of a plurality of individuals into subdatasets, each subdataset including the genotypic information for a subset of the plurality of markers; for each subdataset, identifying haplotypes compatible with marker information for each marker of the subset and for each individual of the plurality; and for each individual, assembling the haplotypes from each of the subsets to provide the individual's haplotype with respect to the plurality of markers.
1. A method comprising:
separating a dataset that includes genotypic information for a plurality of markers for each of a plurality of individuals into subdatasets, each subdataset including the genotypic information for a subset of the plurality of markers;
for each subdataset, identifying haplotypes compatible with marker information for each marker of the subset and for each individual of the plurality; and
for each individual, assembling the haplotypes from each of the subsets to provide the individual's haplotype with respect to the plurality of markers.
2. The method of claim 1 wherein the separating and/or assembling is effected recursively.
3. The method of claim 1 wherein the dataset is separated into a number of subsets, the number being a power of two (2 x ).
4. The method of claim 1 wherein the identifying comprises maximizing the likelihood of haplotype frequencies in a population.
5. The method of claim 1 wherein the identifying comprises the Gibbs sampling methods or the Expectation-Maximization (EM) algorithm.
6. The method of claim 5 wherein the identifying comprises a Markov chain Monte Carlo algorithm.
7. The method of claim 5 wherein the identifying comprises a parsimony method.
8. The method of claim 1 wherein the identifying comprises assigning pseudocounts corresponding to a plurality of possible haplotypes and iteratively reducing the pseudocounts.
9. The method of claim 1 further comprising outputting a result based on the haplotype of at least one individual of the plurality.
10. The method of claim 1 wherein at least some of the subsets are overlapping.
11. The method of claim 1 wherein at least one of the subsets is interleaved with another subset.
12. The method of claim 1 wherein the dataset includes missing or ambiguous marker information and an allele is assigned to the missing or ambiguous marker.
13. The method of claim 1 wherein the dataset includes marker information for at least ten markers.
14. The method of claim 1 wherein the markers comprise biallelic SNPs.
15. A method comprising:
sending, to a computer unit, unphased genotypic information about a plurality of gene markers for a plurality of individuals; and
receiving, from the computer unit, phased genotypic information about the plurality of gene markers for the individual, wherein the computer unit determined the phased genotypic information using a method according to claim 1 .
16. The method of claim 1 wherein the individuals are human individuals.
17. An article of machine readable medium, having encoded thereon instructions causing a processor to effect a method comprising:
separating a dataset that includes genotypic information for a plurality of markers for each of a plurality of individuals into subdatasets, each subdataset including the genotypic information for a subset of the plurality of markers;
for each subdataset, identifying haplotypes compatible with marker information for each marker of the subset and for each individual of the plurality; and
for each individual, assembling the haplotypes from each of the subsets to provide the individual's haplotype with respect to the plurality of markers.
18. The article of claim 17 wherein the separating and/or assembling is effected recursively.
19. The article of claim 17 wherein the dataset is separated into a number of subsets, the number being a power of two (2 x ).
20. The article of claim 17 wherein the identifying comprises maximizing the likelihood of haplotype frequencies in a population.
21. The article of claim 17 wherein the identifying comprises the Gibbs sampling methods or the Expectation-Maximization (EM) algorithm.
22. The article of claim 21 wherein the identifying comprises a Markov chain Monte Carlo algorithm.
23. The article of claim 21 wherein the identifying comprises a patsimony method.
24. The article of claim 17 wherein the identifying comprises assigning pseudocounts corresponding to a plurality of possible haplotypes and iteratively reducing the pseudocounts.
25. The article of claim 17 wherein at least one of the subsets are overlapping.
26. The article of claim 17 wherein at least one of the subsets is interleaved with another subset.
27. The article of claim 17 wherein the dataset includes missing ambiguous marker information and an allele is assigned to the missing or ambiguous marker.