PHASING ANALYSIS WITH DYNAMIC PROGRAMMING ALGORITHM
Provided herein are methods and systems useful for the determination and assignment of haplotypes for genetic loci.
1 . A method for assigning a partial haplotype to a genetic locus comprising:
a. providing sequence reads for said genetic locus;
b. processing said sequence reads into an assembly read;
c. generating a consensus sequence from said assembly read comprising only polymorphic sites within said genetic locus to produce a polyread;
d. constructing a scoring matrix by converting said polyread into a binary string;
e. processing said scoring matrix by generating a score that minimizes the total number of discrepancies between the consensus sequence and said sequence reads at only said polymorphic sites; and
f. assigning said partial haplotype to said genetic locus by reconstructing said locus using the score from step (e).
2 . The method of claim 1 , wherein said sequence reads are paired-end sequence reads.
3 . The method of claim 1 , wherein said binary string comprises a value of 0 or 1 for each polymorphic site within said polyread.
4 . The method of claim 1 , wherein said polyread is represented as X i ϵ{0,1,−} n , where “−” indicates a gap in a position is not covered by the polyread.
5 . The method of claim 4 , wherein said polyread does not comprise a gap at either end of said polyread.
6 . The method of claim 1 , wherein said scoring matrix is represented by a k-mer of said binary string and s(i,r) as the score for a partial haplotype starting at position 0 and ending at position i+k−1 with suffix r.
7 . The method of claim 6 , wherein said s(i,r)=min b=0,1 (s(i−1, (b, r[0, k−2]))+h(i,r)) where b is a binary number of 0 or 1, r[0, k−2] is the length k−1 prefix of r, (b, r[0, k−2]) is a k-mer binary string generated by concatenating b with r[0, k−2], h(i,r) is the minimum of the total number of discrepancies between r or the complement of r and all reads starting at position i.
8 . The method of claim 7 , wherein r comprises either r or the complement of r.
9 . The method of claim 7 , wherein said result for s(i,r) represents the minimum error correction (“MEC”) score.
10 . The method of claim 7 , wherein said s(i,r) excludes gaps in the polyread.
11 . The method of claim 7 further comprising said partial haplotype is generated by iteratively from the solution r n which represents a minimal value of s(n−k,r) over all r.
12 . The method of claim 11 further comprising where s(n−k−1, (b,r n [0, k−2])), where b is the recorded symbol for computing s(n−k, r n ).
13 . The method of claim 12 , further comprising obtaining a partial haplotype (b,r n ) iteratively from position n−k−1.
14 . A method of generating a complete haplotype for a genetic locus by sequentially processing partial haplotypes for said locus generated by the method according to any one of claims 1 - 13 .
15 . The method according to any one of claims 1 - 14 , wherein said method performed on a digital computer.
16 . The method according to any one of claims 1 - 15 , wherein said genetic locus is an HLA locus.
17 . The method of claim 16 , wherein said genetic locus is selected from the group consisting of HLA-A, HLA-B, HLA-C, HLA-DRB1, HLA-DRB3, HLA-DRB4, HLA-DRB5, HLA-DQB1, HLA-DQA1, HLA-DPB1, and HLA-DPA1.
18 . The method of claim 1 , wherein said method employs a Bayesian model in identifying said polymorphic sites.
19 . The method of claim 1 , wherein said method employs a minor allele frequency determination comprising assessing the frequency of the 2 nd most abundant base at a polymorphic site in said locus.
20 . The method of claim 19 , wherein step (b) further comprises generating the consensus sequence using a threshold cutoff of minor allele frequency.
21 . The method of claim 1 , wherein said locus comprises at least 10 polymorphic sites.
22 . The method of claim 1 , wherein said locus comprises at least 50 polymorphic sites.
23 . The method of claim 1 , further comprising between step (c) and step (d):
(c1) performing Bayesian estimates for at least one sequence read on said assembly read; and
(c2) adjusting said at least one sequence read and said polyread based on the result of said Bayesian estimates.
24 . The method of claim 1 , wherein said score in step (e) is a weighted score and wherein a weight is assigned to each position in the polyread based on a quality measurement of said position.
25 . A method for assigning a haplotype to a genetic locus comprising:
a. providing sequence reads for said genetic locus;
b. processing said sequence data into an assembly read;
c. generating a consensus sequence from said assembly read comprising only polymorphic sites within said genetic locus to produce a polyread;
d. partitioning said polyread into at least two subsets, wherein each subset comprises at least two polymorphic sites;
e. obtaining, for each subset, a pair of partial haplotypes by
i. constructing a scoring matrix by converting said polyread into a binary string;
ii. processing said scoring matrix by generating a score that minimizes the total number of discrepancies between the consensus sequence and said sequence reads at only said polymorphic sites;
iii. assigning said partial haplotype to said genetic locus by reconstructing said locus using the score from step (i);
f. concatenating each partial haplotype from each subset with all other partial haplotypes from all other subsets to produce a collection of haplotype pairs spanning all polymorphic sites within the gene locus; and
g. assigning a haplotype pair to the genetic locus from said collection of haplotype pairs, wherein said haplotype pair minimizes the discrepancies between the consensus sequence and said sequence reads.
26 . The method of claim 25 , wherein said genetic locus is an HLA locus.
27 . The method of claim 26 , wherein said genetic locus is selected from the group consisting of HLA-A, HLA-B, HLA-C, HLA-DRB1, HLA-DRB3, HLA-DRB4, HLA-DRB5, HLA-DQB1, HLA-DQA1, HLA-DPB1, and HLA-DPA1.
28 . A data processing system for generating a partial haplotype for a genetic locus comprising:
a. a digital computer with processing and information storage capabilities; and
b. a processing system for assigning at least one partial haplotype to a genetic locus, wherein said processing system is capable of performing the method according to any one of claims 1 - 27 .
29 . The method of claim 28 , wherein said genetic locus is an HLA locus.
30 . The method of claim 29 , wherein said genetic locus is selected from the group consisting of HLA-A, HLA-B, HLA-C, HLA-DRB1, HLA-DRB3, HLA-DRB4, HLA-DRB5, HLA-DQB1, HLA-DQA1, HLA-DPB1, and HLA-DPA1.