Phase-aware determination of identity-by-descent dna segments

Abstract

The disclosed embodiments concern methods, apparatus, systems and computer program products for estimating IBD segments. Some implementations use a templated positional Burrows-Wheeler transform (PBWT) technique and a phase switch error heuristic to correct genotyping errors and phase switch errors to make fast and accurate phase aware IBD estimates. In some implementations a templated PBWT technique and a probabilistic hidden Markov model (HMM) are used to correct genotyping errors and phase switch errors.

What is claimed is: 
     
         1 . A computer implemented method of processing haplotypes to reduce genotyping errors when determining identity by descent (IBD) segments between haplotypes, the method comprising:
 providing a first digital template comprising a first arrangement of masked and unmasked sites in a window of consecutive haplotype sites;   providing a second digital template comprising a second arrangement of masked and unmasked sites in a window of consecutive haplotype sites, wherein the first and second arrangements are different;   providing two or more haplotypes strings for identification of IBD segments therebetween, each of the two or more haplotype strings representing a sequence of allele values at polymorphic sites in a haplotype of an organism; and   computationally identifying IBD segments between the two or more haplotype strings by (i) identifying first matches among alleles of the haplotype strings at unmasked sites produced by applying the first digital template to the two or more haplotype strings, (ii) identifying second matches among alleles of the haplotype at unmasked sites produced by applying the second digital template to the two or more haplotype strings, and (iii) merging the first and second matches among alleles to produce a merged set of IBD segments, wherein the merged set of IBD segments has reduced impact from genotyping errors compared to a set of IBD segments generated without applying the first and second digital templates.   
     
     
         2 . The method of  claim 1 , wherein the first and second templates each have a size of at least four consecutive haplotype sites. 
     
     
         3 . The method of  claim 1 , wherein identifying the first matches among alleles at unmasked sites comprises sequentially applying the first digital template to the two or more haplotype strings, each time moving to a next sequential section of the two or more haplotype strings. 
     
     
         4 . The method of  claim 1 , wherein computationally identifying IBD segments between the two or more haplotype strings further comprises:
 computationally identifying additional matches among alleles at unmasked sites produced by applying one or more additional digital templates to the two or more haplotype strings, wherein the one or more additional digital templates have additional arrangements of masked and unmasked sites in windows of consecutive haplotype sites, and each of the additional arrangements is different from both the first and the second arrangements, and   wherein merging the first and second matches among alleles to produce a merged set of IBD segments further comprises computationally merging the additional matches with the first and second matches to produce the merged set of IBD segments.   
     
     
         5 . The method of  claim 4 , wherein computationally identifying additional matches among alleles at unmasked sites employs a third digital template, a fourth digital template, a fifth digital template, and a sixth digital template. 
     
     
         6 . The method of  claim 1 , wherein the two or more haplotype strings comprise at least one thousand haplotype strings. 
     
     
         7 . The method of  claim 1 , wherein computationally identifying IBD segments between the two or more haplotype strings comprises performing a positional Burrows-Wheeler transform (PBWT) on the unmasked sites produced by applying the first and second templates to the two or more haplotype strings. 
     
     
         8 . The method of  claim 7 , wherein computationally merging the first and second matches among alleles is performed while considering individual polymorphic sites of the two or more haplotype strings using the PBWT. 
     
     
         9 . The method of  claim 1 , wherein applying the first digital template comprises a deterministic process employing the first arrangement of masked and unmasked sites. 
     
     
         10 . A system for processing haplotypes to reduce genotyping errors when determining identity by descent (IBD) segments between haplotypes, the system comprising:
 (a) one or more processors and associated memory;   (b) computer readable instructions for:   providing a first digital template comprising a first arrangement of masked and unmasked sites in a window of consecutive haplotype sites;   providing a second digital template comprising a second arrangement of masked and unmasked sites in a window of consecutive haplotype sites, wherein the first and second arrangements are different;   providing two or more haplotype strings for identification of IBD segments therebetween, each of the two or more haplotype strings representing a sequence of allele values at polymorphic sites in a haplotype of an organism; and   identifying IBD segments between the two or more haplotype strings by (i) identifying first matches among alleles of the haplotype strings at unmasked sites produced by applying the first digital template to the two or more haplotype strings, (ii) identifying second matches among alleles of the haplotype at unmasked sites produced by applying the second digital template to the two or more haplotype strings, and (iii) merging the first and second matches among alleles to produce a merged set of IBD segments, wherein the merged set of IBD segments has reduced impact from genotyping errors compared to a set of IBD segments generated without applying the first and second digital templates.   
     
     
         11 . The system of  claim 10 , wherein the first and second templates each have a size of at least four consecutive haplotype sites. 
     
     
         12 . The system of  claim 10 , wherein the instructions for identifying the first matches among alleles at unmasked sites comprises instructions for sequentially applying the first digital template to the two or more haplotype strings, each time moving to a next sequential section of the two or more haplotype strings. 
     
     
         13 . The system of  claim 10 , wherein the instructions for identifying IBD segments between the two or more haplotype strings further comprise instructions for:
 computationally identifying additional matches among alleles at unmasked sites produced by applying one or more additional digital templates to the two or more haplotype strings, wherein the one or more additional digital templates have additional arrangements of masked and unmasked sites in windows of consecutive haplotype sites, and each of the additional arrangements is different from both the first and the second arrangements, and   wherein merging the first and second matches among alleles to produce a merged set of IBD segments further comprises computationally merging the additional matches with the first and second matches to produce the merged set of IBD segments.   
     
     
         14 . The system of  claim 13 , wherein the instructions for identifying additional matches among alleles at unmasked sites employ a third digital template, a fourth digital template, a fifth digital template, and a sixth digital template. 
     
     
         15 . The system of  claim 14 , wherein the first through sixth digital templates each comprise two masked sites and two unmasked sites. 
     
     
         16 . The system of  claim 10 , wherein the first digital template and the second digital template each have a ratio of masked sites to unmasked sites of between about 2:1 to about 1:2. 
     
     
         17 . The system of  claim 10 , wherein the two or more haplotype strings comprise at least one thousand haplotype strings. 
     
     
         18 . The system of  claim 10 , wherein the two or more haplotype strings comprise at least one million haplotype strings. 
     
     
         19 . The system of  claim 10 , wherein the instructions for identifying IBD segments between the two or more haplotype strings comprise instructions performing a positional Burrows-Wheeler transform (PBWT) on the unmasked sites produced by applying the first and second templates to the two or more haplotype strings. 
     
     
         20 . The system of  claim 19 , wherein the instructions for merging the first and second matches among alleles comprise instructions for performing the merging while considering individual polymorphic sites of the two or more haplotype strings using the PBWT. 
     
     
         21 . The system of  claim 10 , wherein the total number of digital templates is between 2 and k, where k is the number of haplotype sites in the window. 
     
     
         22 . The system of  claim 10 , wherein the total number of digital templates is k!/(m!*(k−m)!), where k is the number of haplotype sites in the window and m is the number of masked sites in the window. 
     
     
         23 . The system of  claim 10 , wherein applying the first digital template comprises a deterministic process employing the first arrangement of masked and unmasked sites. 
     
     
         24 . A method of identifying IBD segments between two or more haplotype strings, each of the two or more haplotype strings representing a sequence of allele values at polymorphic sites in a haplotype of an organism, the method comprising:
 (a) computationally identifying IBD segments between the two or more haplotype strings by (i) identifying first matches among alleles of two or more haplotype strings at unmasked sites produced by applying a first digital template to the two or more haplotype strings, (ii) identifying second matches among alleles of the haplotype at unmasked sites produced by applying a second digital template to the two or more haplotype strings, and (iii) merging the first and second matches among alleles to produce a merged set of IBD segments, wherein the first digital template comprises a first arrangement of masked and unmasked sites in a window of consecutive haplotype sites, wherein the second digital template comprises a second arrangement of masked and unmasked sites in the window of consecutive haplotype sites, and wherein the first and second arrangements are different; and   (b) identifying a potential phase switch error in at least one of the two or more haplotype strings; and   (c) correcting the phase switch error.   
     
     
         25 . The method of  claim 24 , wherein identifying the potential phase switch error comprises identifying proximal IBD segments in at least one pair of the two or more haplotype strings. 
     
     
         26 . A computer implemented method of processing haplotypes to reduce errors when determining identity by descent (IBD) segments between haplotypes, the method comprising:
 providing two or more paired haplotypes strings for identification of IBD segments therebetween, each of the two or more paired haplotype strings representing a sequence of allele values at polymorphic sites in a haplotype of an organism; and   computationally iterating through the two or more paired haplotype strings by:
 (i) identifying a first potential IBD segment between the two or more paired haplotype strings by identifying matches among alleles of the haplotype strings; 
 (ii) comparing the first site of the first potential IBD segment to the last site of a previously identified second potential IBD segment 
 (iii) determining that the last site of the second potential IBD segment and the first site of the first potential IBD segment are within a threshold number of sites of each other; and 
 (iv) merging the first potential IBD segment and the second potential IBD segment to form a combined potential IBD segment. 
   
     
     
         27 . The method of  claim 26 , further comprising, after (a) and before (b), removing some initial IBD segments determined to belong to haplotypes having less than a threshold amount of initial IBD segments, wherein the initial IBD segments provided to the HEIM in (b) have had some initial IBD segments removed. 
     
     
         28 . The method of  claim 27 , wherein the threshold amount of initial IBD segments is less than two initial IBD segments per chromosome. 
     
     
         29 . A computer implemented method of determining identity by descent (IBD) segments, the method comprising:
 determining first potential IBD segments among phased haplotype data for a plurality of individuals, wherein the first potential IBD segments have an end site;   determining second potential IBD segments among haplotype data for the plurality of individuals, wherein the second potential IBD segments have a start site;   determining that the end site of the first potential IBD segments and the start site of the second potential IBD segments are within a threshold number of sites of each other; and   merging the first potential IBD segments and the second potential IBD segments to form a combined potential IBD segment.   
     
     
         30 . The method of  claim 29 , wherein the first potential IBD segments and the second potential IBD segments are on different haplotypes for an individual of the plurality of individuals, and the method further comprises:
 determining that a phase switch error occurred at a site between the first potential IBD segment and the second potential IBD segment for the individual; and   swapping the haplotypes for the individual from the position of the phase switch error onward.   
     
     
         31 . The method of  claim 29 , wherein the first potential IBD segment and the second potential IBD segment each span at least the threshold number of sites. 
     
     
         32 . The method of  claim 29 , wherein the threshold number of sites is between about 0 and 500 SNPs. 
     
     
         33 . A system for determining identity by descent (IBD) segments, the system comprising:
 (a) one or more processors and associated memory; and   (b) computer readable instructions for:   determining first potential IBD segments among phased haplotype data for a plurality of individuals, wherein the first potential IBD segments have an end site;   determining second potential IBD segments among haplotype data for the plurality of individuals, wherein the second potential IBD segments have a start site;   determining that the end site of the first potential IBD segments and the start site of the second potential IBD segments are within a threshold number of sites of each other; and   merging the first potential IBD segments and the second potential IBD segments to form a combined potential IBD segment.   
     
     
         34 . The system of  claim 33 , wherein the first potential IBD segments and the second potential IBD segments are on different haplotypes for an individual of the plurality of individuals, and the computer readable instructs further comprise instructions for:
 determining that a phase switch error occurred at a site between the first potential IBD segment and the second potential IBD segment for the individual; and   swapping the haplotypes for the individual from the position of the phase switch error onward.   
     
     
         35 . The system of  claim 33 , wherein the first potential IBD segments and the second potential IBD segments overlap for an individual of the plurality of individuals. 
     
     
         36 . The system of  claim 33 , wherein the first potential IBD segment and the second potential IBD segment each span at least the threshold number of sites. 
     
     
         37 . The system of  claim 33 , wherein the threshold number of sites is between about 0 and 500 SNPs. 
     
     
         38 . The system of  claim 33 , wherein the plurality of individuals do not share a parent-child relationship. 
     
     
         39 . The system of  claim 33 , wherein the computer readable instructions further comprise instructions for:
 determining a third potential IBD segment among phased haplotype data for a plurality of individuals, wherein the third potential IBD segment has a start site;   determining that the end site of the combined potential IBD segment and the start site of the third potential IBD segments are within the threshold number of SNPs of each other; and   merging the combined potential IBD segments and the third potential IBD segments.   
     
     
         40 . The system of  claim 39 , wherein the combined potential IBD segment and the third potential IBD segment are on different haplotypes for an individual of the plurality of individuals, and the computer readable instructions further comprise instructions for:
 determining that a phase switch error occurred at a site between the combined potential IBD segment and the third potential IBD segment for the individual; and   swapping the haplotypes for the individual from the position of the phase switch error.   
     
     
         41 . The system of  claim 33 , wherein the computer readable instructions further comprise instructions for determining that the combined potential IBD segments have a minimum length in centimorgans and storing the combined potential IBD segments as IBD segments for the plurality of individuals. 
     
     
         42 . A computer implemented method of processing haplotypes to reduce errors when determining identity by descent (IBD) segments between haplotypes, the method comprising:
 (a) computationally identifying initial IBD segments between two or more haplotype strings by identifying first matches among alleles of the haplotype strings using a plurality of templates, each comprising a unique arrangement of masked and unmasked sites in a window of consecutive haplotype sites; and   (b) providing information characterizing the initial IBD segments to a hidden Markov model (HMM) which removes potential phase switch errors to produce final IBD segment, wherein the HMM analyzes the information characterizing the initial IBD segments using distances between consecutive haplotype sites on a chromosome, one or more rates of recombination based on meiosis, and one or more rates of phase switch error based on a phasing method employed to phase the haplotypes.