EXACT HAPLOTYPE RECONSTRICTION OF F2 POPULATIONS

• US 20130345987A1
• Filed: 02/07/2013
• Published: 12/26/2013
• Est. Priority Date: 06/21/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: PARIDA, Laxmi P., HAIMINEN, Niina S., UTRO, Filippo
• Granted Patent: US 10,460,832 B2
• Time in Patent Office: Days
• US Class Current: 702/19
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G16B 20/00 ICT specially adapted for functional genomics or proteomics, e.g. genotype-phenotype associations
• CPC Class Codes: G16B 20/20 Allele or variant detection, e.g. single nucleotide polymorphism [SNP] detection
• CPC Class Codes: G16B 45/00 ICT specially adapted for bioinformatics-related data visualisation, e.g. displaying of maps or networks

Abstract

A system for reconstructing haplotypes from genotype data includes a memory, a processor, and a reconstruction module. The reconstruction module is configured to access a set of progeny genotype data including n progenies encoded with m genetic markers. A first set of parent haplotypes associated with a first parent of the n progenies and a second set of parent haplotypes associated with a second parent of the n progenies are identified based on at least the set of progeny genotype data. An agglomerate data structure including a collection of sets of haplotype sequences characterizing the n progenies is constructed based on the set of progeny genotype data and the first and second sets of parent haplotypes. Each set of haplotype sequences includes a number of crossovers equal to a total minimum number of observable crossovers in the n progenies.

Claims

1. A system for reconstructing haplotypes from genotype data, the system comprising:

a memory;

a processor communicatively to the memory; and

a reconstruction module communicatively coupled to the memory and processor, the reconstruction module configured to perform a method comprising;

accessing a set of progeny genotype data comprising n progenies encoded with m genetic markers, wherein each of the m genetic markers comprises two values, and wherein a combination of each of the m genetic markers associated with a progeny represents a genotype sequence of the progeny;

identifying, based on at least the set of progeny genotype data, a first set of parent haplotypes associated with a first parent of the n progenies and a second set of parent haplotypes associated with a second parent of the n progenies;

determining a total minimum number of observable crossovers in the n progenies; and

constructing, based on the set of progeny genotype data and the first and second sets of parent haplotypes, an agglomerate data structure comprising a collection of sets of haplotype sequences characterizing the n progenies in terms of the first and second sets of parent haplotypes, wherein each set of haplotype sequences comprises a number of observable crossovers equal to the total minimum number of observable crossovers in the n progenies.

2. The system of claim 1, wherein the method further comprises:

determining a preciseness of the agglomerate data structure in terms of statistical measures.

3. The system of claim 1, wherein the set of progeny genotype data is represented as a matrix comprising rows i and columns j, wherein each row i, 1≦

i≦

n represents a progeny in the n progenies and each column j, 1≦

j≦

m represents a marker in the m markers, and where the m genetic markers are biallelic markers,

wherein identifying the first set of parent haplotypes and the second set of parent haplotypes comprises;

constructing matrices M_ij^p, where

4. The system of claim 3, wherein V_j^p(1), p=a,b, is computed based on j∈

J_p and j′

∈

J_{{tilde over (p)}}, for some p, where J_p is a set of markers with exactly one heterozygous parent, where for parents p=a,b, if p=a, then {tilde over (p)}=b and vice-versa, and where, if k=0, then {tilde over (k)}=1 and vice-versa, and where M^a={tilde over (M)}^b (and M^b={tilde over (M)}^a), and, {tilde over (V)}^p(0)=V^p(1) and {tilde over (V)}^p(1) =V^p(0) for parents p=a,b.

5. The system of claim of 4, further comprising updating each M_ij^p≠

X according to V^p and each M_ij^p=X based on

6. The system of claim 5, wherein the method further comprises:

transforming each of the updated matrices M_ij^p to F(M^a) and F(M^b), respectively, using a set of monotonic state transitions based on functions Lt(M_ij) and Rt(M_ij), where

7. The system of claim 6, wherein R_ij^p is generated based on, for each progeny i:

if F_ij=−

1 for some j, then R_ij←

0 and {tilde over (R)}_ij←

1, for all j;

if F_ij∈

{0,1}, then R_ij←

F_ij;

for each j, if {tilde over (F)}_ij numeric and F_ij is not, then R_ij←

q; and

for each j, where F_ij and {tilde over (F)}_ij are both not numeric, then

8. The system of claim 7, wherein the method further comprises:

determining an error estimate in as N/mn, where N is a number of genotype data mismatches in R_ij^p, where a position ij has a mismatch if {V(R_ij),{tilde over (V)}({tilde over (R)}_ij)} and R_ij,{tilde over (R)}_ij∈

{0,1}.

9. The system of claim of claim 7, wherein the method further comprises:

determining a haplotype frequency distribution for the collection of the set of haplotype sequences in the agglomerate data structure, wherein the determining is based on

k₁,k₂=0,1 being a haplotype pair, and

if R_ij is non-numeric, let R_ij=α

hold, where for each marker j for x, y=0,1,α

,

c_xy=|{i|R_ij^a=x and R_ij^b=y}|, and an expected count ĉ

_k1k2 of each haplotype pair is ĉ

_k1k2=c_k1k2+Δ

_k1k2, where Δ

_k1k2=c<sub>α

k2</sub>/2+c_k1α

/2+c<sub>α

α</sub>

/4.

10. The system of claim 9, wherein the method further comprises:

determining a variance σ

_k1,k2² of haplotype frequency distribution as Δ

_k1k2.

11. A computer program storage product for reconstructing haplotypes from genotype data, the computer program storage product comprising instructions configured to perform a method comprising:

accessing a set of progeny genotype data comprising n progenies encoded with m genetic markers, wherein each of the m genetic markers comprises two values, and wherein a combination of each of the m genetic markers associated with a progeny represents a genotype sequence of the progeny;

identifying, based on at least the set of progeny genotype data, a first set of parent haplotypes associated with a first parent of the n progenies and a second set of parent haplotypes associated with a second parent of the n progenies;

determining a total minimum number of observable crossovers in the n progenies; and

constructing, based on the set of progeny genotype data and the first and second sets of parent haplotypes, an agglomerate data structure comprising a collection of sets of haplotype sequences characterizing the n progenies in terms of the first and second sets of parent haplotypes, wherein each set of haplotype sequences comprises a number of observable crossovers equal to the total minimum number of observable crossovers in the n progenies.

12. The computer program storage product of claim 11, wherein the method further comprises:

determining a preciseness of the agglomerate data structure in terms of statistical measures.

13. The computer program storage product of claim 11, wherein the set of progeny genotype data is represented as a matrix comprising rows i and columns j, wherein each row i, 1≦

i≦

n represents a progeny in the n progenies and each column j, 1≦

j≦

m represents a marker in the m markers, and where the m genetic markers are biallelic markers,

wherein identifying the first set of parent haplotypes and the second set of parent haplotypes comprises;

constructing matrices M_ij^p, where

14. The computer program storage product of claim 13, wherein V_j^p(1), p=a,b, is computed based on j∈

J_p and j′

∈

J_{{tilde over (p)}}, for some p, where J_p is a set of markers with exactly one heterozygous parent, where

for parents p=a,b, if p=a, then {tilde over (p)}=b and vice-versa., and where, if k=0, then {tilde over (k)}=1 and vice-versa, and where M^a={tilde over (M)}^b (and M^b={tilde over (M)}^a), and, {tilde over (V)}^p(0)=V^p(1) and {tilde over (V)}^p=V^p(0) for parents p=a,b.

15. The computer program storage product of claim of 14, further comprising updating each M_ij^p≠

X according to V^p and each M_ij^p=X based on

16. The computer program storage product of claim 15, wherein the method further comprises:

transforming each of the updated matrices M_ij^p to F(M^a) and F(M^b), respectively, using a set of monotonic state transitions based on functions Lt(M_ij) and Rt(M_ij), where

17. The computer program storage product of claim 16, wherein R_ij^p is generated based on, for each progeny i:

if F_ij=−

1 for some j, then R_ij←

0 and {tilde over (R)}_ij←

1, for all j;

if F_ij∈

{0,1}, then R_ij←

F_ij;

for each j, if {tilde over (F)}_ij is numeric and F_ij is not, then R_ij←

q; and

for each j, where F_ij and F_ij both not numeric, then

18. The computer program storage product of claim 17, wherein the method further comprises:

determining an error estimate in as N/mn, where N is a number of genotype data mismatches in R_ij^p, where a position ij has a mismatch if {V(R_ij), V({tilde over (R)}_ij)}_ij and R_ij,{tilde over (R)}_ij∈

{0,1}.

19. The computer program storage product of claim of claim 17, wherein the method further comprises:

determining a haplotype frequency distribution for the collection of the set of haplotype sequences in the agglomerate data structure, wherein the determining is based on

k₁, k₂=0,1 being a haplotype pair, and

if R_u is non-numeric, let R_u =a hold, where for each marker j for x, y =0,1,α

,

c_xy=|{i|R_ij^a=x and R_ij^b=y}|, and an expected count ĉ

_k1k2 of each haplotype pair is ĉ

_k1k2=c_k1k2+Δ

_k1k2, where Δ

_k1k2=c<sub>α

k2</sub>/2+c_k1α

/2+c<sub>α

α</sub>

/4.

20. The computer program storage product of claim 19, wherein the method further comprises:

determining a variance σ

_k1,k2² of haplotype frequency distribution as Δ

_k1k2.