Determining Data Inheritance of Data Segments

1 . A computer-implemented method for determining inheritance of genomic segments of a target individual, the computer-implemented method comprising:

receiving a target genotype dataset that is diploid;

applying an identity-by-descent (IBD) phasing algorithm to separate the target genotype dataset into a first haplotype dataset and a second haplotype dataset, at least the first haplotype dataset has a cross-chromosome haplotype separation, wherein the IBD phasing algorithm comprises:

identifying a plurality of matched genomic segments that match to the target genotype dataset for at least a threshold length;

defining, based on overlapping of the matched genomic segments, the target genotype dataset as a plurality of genomic ranges, wherein each divided genomic range is matched to a set of overlapping matched genomic segments;

applying the IBD phasing algorithm phasing algorithm to separate the first haplotype dataset into a first subset of haploid sequences that belong to a first inheritance from a first grandparent and a second subset of haploid sequences that belong to a second inheritance from a second grandparent; and

storing the first haplotype dataset, the second haplotype dataset, the first subset of haploid sequences, and the second subset of haploid sequences as being associated with the target genotype dataset.

2 . The computer-implemented method of claim 1 , wherein identifying the plurality of matched genomic segments that match to the target genotype dataset for at least the threshold length comprises:

retrieving the matched genomic segments from a database of close matches, each close match sharing identity-by-descent (IBD) with the target genotype dataset for at least a second threshold length that is larger than the threshold length; and

filtering the matched genomic segments to remove one or more matched genomic segments belonging to potential descendants of two or more inheritances.

3 . The computer-implemented method of claim 1 , wherein defining the target genotype dataset as the plurality of genomic ranges comprises:

identifying a plurality of informative sites, an informative site being a site with heterozygous allele values in the target genotype dataset and a homozygous allele value in two or more matched genomic segments;

identifying a conflicting informative site, the conflicting informative site being an informative site where the two or more matched genomic segments have contradicting homozygous allele values at the conflicting informative site;

breaking up at least one of the matched genomic segments of the two or more matched genomic segments at a breakpoint based on the conflicting informative site; and

delimiting two genomic ranges of the target genotype dataset at the breakpoint.

4 . The computer-implemented method of claim 1 , wherein applying the IBD phasing algorithm to separate the first haplotype dataset into the first subset of haploid sequences and the second subset of haploid sequences comprises:

constructing a similarity matrix for the plurality of genomic ranges, the similarity matrix comprising values of a similarity metric of two given genomic ranges;

constructing a clustering tree that assigns, based on the values in the similarity matrix, the plurality of genomic ranges into positions of nodes in the clustering tree;

dividing the clustering tree into two or more branches, each branch comprising a plurality of nodes and corresponding to a group assignment; and

refining the group assignments by iteratively swapping one or more genomic ranges from one group to another to improve an objective function based on the similarity metric.

5 . The computer-implemented method of claim 4 , wherein the objective function is further based on a probability density of a total amount of genomic ranges assigned to each inheritance, modeled as a Gaussian distribution with a mean corresponding to an expected fractional DNA contribution from each grandparent, and a probability density of a number of recombination events of each inheritance, modeled as a Gaussian distribution with a mean corresponding to an expected number of recombination events in a population.

6 . The computer-implemented method of claim 4 , wherein a value of the similarity metric of two given genomic ranges is determined based on: (1) a first length of IBD matched segment corresponding to a matched individual in the first genomic range of the two given genomic ranges; and (2) a second length of IBD matched segment corresponding to the matched individual's second-degree relative in the second genomic range of the two given genomic ranges.

7 . The computer-implemented method of claim 6 , wherein constructing the similarity matrix comprises weighing lengths of matched segments associated with extra-informative matches more heavily than lengths of matched segments associated with regular matches.

8 . The computer-implemented method of claim 4 , wherein the objective function is further based on a probability density of a total amount of genomic ranges assigned to each inheritance modeled as a Gaussian distribution with a mean corresponding to an expected fractional DNA contribution from each grandparent, and a probability density of a number of recombination events of each inheritance modeled as a Gaussian distribution with a mean corresponding to an expected number of recombination events in a population.

9 . The computer-implemented method of claim 1 , further comprising:

identifying a phenotype of the target individual; determining the phenotype is attributable to alleles in the first subset of haploid sequences; and

reporting that the phenotype of the target individual is passed down from the first grandparent.

10 . The computer-implemented method of claim 1 , wherein identifying the plurality of matched genomic segments that match to the target genotype dataset for at least the threshold length comprises retrieving the matched genomic segments from a database of close matches, each close match sharing identity-by-descent (IBD) with the target genotype dataset for at least a second threshold length that is larger than the threshold length, and filtering the matched genomic segments to remove one or more matched genomic segments belonging to potential descendants of two or more inheritances.

11 . The computer-implemented method of claim 1 , wherein defining the target genotype dataset as the plurality of genomic ranges comprises identifying a plurality of informative sites, identifying a conflicting informative site, breaking up at least one of the matched genomic segments at a breakpoint based on the conflicting informative site, and delimiting two genomic ranges of the target genotype dataset at the breakpoint.

12 . A system for determining inheritance of genomic segments of a target individual, the system comprising:

one or more processors;

memory storing code comprising instructions, wherein the instructions, when executed by the one or more processors, cause the one or more processors perform steps comprising:

receiving a target genotype dataset that is diploid;

applying an identity-by-descent (IBD) phasing algorithm to separate the target genotype dataset into a first haplotype dataset and a second haplotype dataset, at least the first haplotype dataset has a cross-chromosome haplotype separation, wherein the IBD phasing algorithm comprises:

identifying a plurality of matched genomic segments that match to the target genotype dataset for at least a threshold length;

defining, based on overlapping of the matched genomic segments, the target genotype dataset as a plurality of genomic ranges, wherein each divided genomic range is matched to a set of overlapping matched genomic segments;

applying the IBD phasing algorithm phasing algorithm to separate the first haplotype dataset into a first subset of haploid sequences that belong to a first inheritance from a first grandparent and a second subset of haploid sequences that belong to a second inheritance from a second grandparent; and

storing the first haplotype dataset, the second haplotype dataset, the first subset of haploid sequences, and the second subset of haploid sequences as being associated with the target genotype dataset.

13 . The system of claim 12 , wherein identifying the plurality of matched genomic segments that match to the target genotype dataset for at least the threshold length comprises:

retrieving the matched genomic segments from a database of close matches, each close match sharing identity-by-descent (IBD) with the target genotype dataset for at least a second threshold length that is larger than the threshold length; and

filtering the matched genomic segments to remove one or more matched genomic segments belonging to potential descendants of two or more inheritances.

14 . The system of claim 12 , wherein defining the target genotype dataset as the plurality of genomic ranges comprises:

identifying a plurality of informative sites, an informative site being a site with heterozygous allele values in the target genotype dataset and a homozygous allele value in two or more matched genomic segments;

identifying a conflicting informative site, the conflicting informative site being an informative site where the two or more matched genomic segments have contradicting homozygous allele values at the conflicting informative site;

breaking up at least one of the matched genomic segments of the two or more matched genomic segments at a breakpoint based on the conflicting informative site; and

delimiting two genomic ranges of the target genotype dataset at the breakpoint.

15 . The system of claim 12 , wherein applying the IBD phasing algorithm to separate the first haplotype dataset into the first subset of haploid sequences and the second subset of haploid sequences comprises:

constructing a similarity matrix for the plurality of genomic ranges, the similarity matrix comprising values of a similarity metric of two given genomic ranges;

constructing a clustering tree that assigns, based on the values in the similarity matrix, the plurality of genomic ranges into positions of nodes in the clustering tree;

dividing the clustering tree into two or more branches, each branch comprising a plurality of nodes and corresponding to a group assignment; and

refining the group assignments by iteratively swapping one or more genomic ranges from one group to another to improve an objective function based on the similarity metric.

16 . The system of claim 15 , wherein the objective function is further based on a probability density of a total amount of genomic ranges assigned to each inheritance, modeled as a Gaussian distribution with a mean corresponding to an expected fractional DNA contribution from each grandparent, and a probability density of a number of recombination events of each inheritance, modeled as a Gaussian distribution with a mean corresponding to an expected number of recombination events in a population.

17 . The system of claim 15 , wherein a value of the similarity metric of two given genomic ranges is determined based on: (1) a first length of IBD matched segment corresponding to a matched individual in the first genomic range of the two given genomic ranges; and (2) a second length of IBD matched segment corresponding to the matched individual's second-degree relative in the second genomic range of the two given genomic ranges.

18 . The system of claim 17 , wherein constructing the similarity matrix comprises weighing lengths of matched segments associated with extra-informative matches more heavily than lengths of matched segments associated with regular matches.

19 . The system of claim 15 , wherein the objective function is further based on a probability density of a total amount of genomic ranges assigned to each inheritance modeled as a Gaussian distribution with a mean corresponding to an expected fractional DNA contribution from each grandparent, and a probability density of a number of recombination events of each inheritance modeled as a Gaussian distribution with a mean corresponding to an expected number of recombination events in a population.

20 . A non-transitory computer-readable medium configured to store code for determining inheritance of genomic segments of a target individual, the code comprising instructions, wherein the instructions, when executed by one or more processors, cause the one or more processors to perform steps comprising:

receiving a target genotype dataset that is diploid;

applying an identity-by-descent (IBD) phasing algorithm to separate the target genotype dataset into a first haplotype dataset and a second haplotype dataset, at least the first haplotype dataset has a cross-chromosome haplotype separation, wherein the IBD phasing algorithm comprises:

identifying a plurality of matched genomic segments that match to the target genotype dataset for at least a threshold length;

defining, based on overlapping of the matched genomic segments, the target genotype dataset as a plurality of genomic ranges, wherein each divided genomic range is matched to a set of overlapping matched genomic segments;

applying the IBD phasing algorithm phasing algorithm to separate the first haplotype dataset into a first subset of haploid sequences that belong to a first inheritance from a first grandparent and a second subset of haploid sequences that belong to a second inheritance from a second grandparent; and

storing the first haplotype dataset, the second haplotype dataset, the first subset of haploid sequences, and the second subset of haploid sequences as being associated with the target genotype dataset.