Haplotype phasing models
Novel haplotype cluster Markov models are used to phase genomic samples. After the models are built, they rapidly and accurately phase new samples without requiring that the new samples be used to re-build the models. The models set transition probabilities such that the probability for an appearance of any allele within any haplotype is a non-zero number. Furthermore, the most unlikely pairs of haplotypes are discarded from each model at each level until ε of the likelihood mass at each level is discarded. The models are also constructed such that contributing windows of SNPs partially overlap so that phasing decisions near one of the extreme ends of any model is are not significantly determinative of the phase. Additionally, the models are configured such that two or more nodes can be merged during the building/updating procedure to consolidate haplotype clusters having similar distributions.
1. A computer-implemented method for phasing diploid genotypes, the computer-implemented method comprising:
accessing a set of reference haplotypes corresponding to reference diploid genotypes that have already been phased;
accessing an input sample of a diploid genotype;
iteratively updating, using one or more processors, a set of directed acyclic models based on the diploid genotype and the reference haplotypes, each directed acyclic model corresponding to a different window of single nucleotide polymorphisms (SNPs), at least one of the directed acyclic models comprising a set of nodes, wherein at least one node at a first level is a parent node that represents a particular haplotype sequence at the first level, the parent node having a first edge connected to a first sub node at a second level and a second edge connected to a second sub node at the second level, the first sub node representing a major allele at the second level and the second sub node representing a minor allele at the second level, and wherein iteratively updating the set of directed acyclic models comprises:
in each iteration,
applying the set of directed acyclic models to the input sample of the diploid genotype;
obtaining phasings of the input sample of the diploid genotype, the obtained phasing comprising a set of pairs of haplotypes of the input sample;
selecting, from the set of pairs of haplotypes of the input samples, a subset of pairs of haplotypes of the input samples;
updating the set of reference haplotypes by adding the selected subset of pairs of haplotypes of the input samples; and
updating at least one of the set of directed acyclic models using the updated set of reference haplotypes;
determining phasings of the diploid genotype using the one or more processors executing the set of directed acyclic models, the determining comprising:
applying the set of updated directed acyclic models to the input sample;
receiving output from each of the set of updated directed acyclic models, each output comprising at least a pair of phased haplotypes for the input sample; and
concatenating the received pairs of phased haplotypes to generate a single pair of phased haplotypes for the input sample; and
returning phased haplotypes for the input sample of the diploid genotype.
2. The computer-implemented method of claim 1 , wherein determining phasings of the diploid genotype comprises:
generating, for each window, one or more haplotype phasing segments for the diploid genotype of that window based on one or more paths traversing the directed acyclic model for that window; and
combining the haplotype phasing segments for the windows into the phased haplotypes.
3. The computer-implemented method of claim 1 , wherein each directed acyclic model is a Markov model.
4. The computer-implemented method of claim 1 , wherein the at least one of the directed acyclic models comprises a merged node at the second level that is merged from two or more nodes at the second level.
5. The computer-implemented method of claim 4 , wherein generating the merged node comprises:
accessing a plurality of candidate sub nodes at the second level;
for each pair of candidate sub nodes at the second level:
determining a first probability that a reference haplotype belongs to a first candidate sub node of the pair;
determining a second probability that the reference haplotype belongs to a first candidate sub node of the pair;
determining a difference between the first probability and the second probability; and
responsive to the difference being smaller than a threshold, merging the pair of candidate sub nodes into the merged node, the merged node comprising subsets of reference haplotypes represented by the first candidate sub node and the second candidate sub node.
6. The computer-implemented method of claim 5 , further comprising:
responsive to the difference being at or larger than the threshold, not merging the pair of candidate sub nodes into the merged node.
7. The computer-implemented method of claim 1 , wherein each edge is associated with a transition probability that represents a likelihood of an allele value associated with the edge.
8. The computer-implemented method of claim 7 , wherein the transition probability of each edge is a value greater than 0.
9. The computer-implemented method of claim 7 , wherein the transition probability of an edge of a sub node with a haplotype count of zero is nonzero.
10. A non-transitory computer readable medium for storing computer code comprising instructions, the instructions, when executed by one or more processors, cause the one or more processors to:
access a set of reference haplotypes corresponding to reference diploid genotypes that have already been phased;
access an input sample of a diploid genotype;
iteratively update, using one or more processors, a set of directed acyclic models based on the diploid genotype and the reference haplotypes, each directed acyclic model corresponding to a different window of single nucleotide polymorphisms (SNPs), at least one of the directed acyclic models comprising a set of nodes, wherein at least one node in a first level is a parent node that represents a particular haplotype sequence at the first level, the parent node having a first edge connected to a first sub node at a second level and a second edge connected to a second sub node at the second level, the first sub node representing a major allele for the second level and the second sub node representing a minor allele at the second level, and wherein iteratively updating the set of directed acyclic models comprises:
in each iteration,
applying the set of directed acyclic models to the input sample of the diploid genotype;
obtaining phasings of the input sample of the diploid genotype, the obtained phasing comprising a set of pairs of haplotypes of the input sample;
selecting, from the set of pairs of haplotypes of the input samples, a subset of pairs of haplotypes of the input samples;
updating the set of reference haplotypes by adding the selected subset of pairs of haplotypes of the input samples; and
updating at least one of the set of directed acyclic models using the updated set of reference haplotypes;
determine phasings of the diploid genotype using the one or more processor executing the set of directed acyclic models, wherein determining comprising:
applying the set of updated directed acyclic models to the input sample;
receiving output from each of the set of updated directed acyclic models, each output comprising at least a pair of phased haplotypes for the input sample; and
concatenating the received pairs of phased haplotypes to generate a single pair of phased haplotypes for the input sample; and
return phased haplotypes for the input sample of the diploid genotype.
11. The non-transitory computer readable medium of claim 10 , wherein the instructions that cause the one or more processors to determine phasings of the diploid genotype comprise instructions that cause the one or more processors to:
generate, for each window, one or more haplotype phasing segments for the diploid genotype of that window based on one or more paths traversing the directed acyclic model for that window; and
combine haplotype phasing segments for the windows into the phased haplotypes.
12. The non-transitory computer readable medium of claim 10 , wherein each directed acyclic model is a Markov model.
13. The non-transitory computer readable medium of claim 10 , wherein the at least one of the directed acyclic models comprises a merged node at the second level that is merged from two or more nodes at the second level.
14. The non-transitory computer readable medium of claim 13 , further comprising instructions that cause the one or more processors to:
access a plurality of candidate sub nodes at the second level;
for each pair of candidate sub nodes at the second level:
determine a first probability that a reference haplotype belongs to a first candidate sub node of the pair;
determine a second probability that the reference haplotype belongs to a first candidate sub node of the pair;
determine a difference between the first probability and the second probability; and
responsive to the difference being smaller than a threshold, merge the pair of candidate sub nodes into the merged node, the merged node comprising subsets of reference haplotypes represented by the first candidate sub node and the second candidate sub node.
15. The non-transitory computer readable medium of claim 14 , further comprising:
responsive to the difference being at or larger than the threshold, not merging the pair of candidate sub nodes into the merged node.
16. The non-transitory computer readable medium of claim 10 , wherein each edge is associated with a transition probability that represents a likelihood of an allele value associated with the edge.
17. The non-transitory computer readable medium of claim 16 , wherein the transition probability of each edge is a value greater than 0 .
18. The non-transitory computer readable medium of claim 16 , wherein the transition probability of an edge of a sub node with a haplotype count of zero is nonzero.
19. A system comprising:
one or more processors; and
a memory storing instructions that when executed by the one or more processors cause the one or more processors to perform steps comprising:
accessing a set of reference haplotypes corresponding to reference diploid genotypes that have already been phased;
accessing an input sample of a diploid genotype;
iteratively updating, using one or more processors, a set of directed acyclic models based on the diploid genotype and the reference haplotypes, each directed acyclic model corresponding to a different window of single nucleotide polymorphisms (SNPs), at least one of the directed acyclic models comprising a set of nodes, wherein at least one node in a first level is a parent node that represents a particular haplotype sequence at the first level, the parent node having a first edge connected to a first sub node at a second level and a second edge connected to a second sub node at the second level, the first sub node representing a major allele for the second level and the second sub node representing a minor allele at the second level, and wherein iteratively updating the set of directed acyclic models comprises:
in each iteration,
applying the set of directed acyclic models to the input sample of the diploid genotype;
obtaining phasings of the input sample of the diploid genotype, the obtained phasing comprising a set of pairs of haplotypes of the input sample;
selecting, from the set of pairs of haplotypes of the input samples, a subset of pairs of haplotypes of the input samples;
updating the set of reference haplotypes by adding the selected subset of pairs of haplotypes of the input samples; and
updating at least one of the set of directed acyclic models using the updated set of reference haplotypes;
determining phasings of the diploid genotype using the one or more processor executing the set of directed acyclic models, the determining comprising:
applying the set of updated directed acyclic models to the input sample;
receiving output from each of the set of updated directed acyclic models, each output comprising at least a pair of phased haplotypes for the input sample; and
concatenating the received pairs of phased haplotypes to generate a single pair of phased haplotypes for the input sample; and
returning phased haplotypes for the input sample of the diploid genotype.
20. The system of claim 19 , wherein the instructions that cause the one or more processors to determine phasings of the diploid genotype comprise instructions that cause the one or more processors to perform steps comprising:
generating, for each window, one or more haplotype phasings segments for the diploid genotype of that window based on one or more paths traversing the directed acyclic model for that window; and
combining the haplotype phasing segments for the windows into the phased haplotypes.