Method and apparatus for pattern identification in diploid DNA sequence data
This invention provides methods for identifying mutations and methylation patterns in diploid DNA sequence signal data. In particular, the invention provides methods for (1) obtaining two parental allele sequences from diploid DNA sequence signal data, (2) identifying the mutation and haplotype patterns in the two parental allele sequences, (3) assigning likelihood scores for the mutations thus identified, and (4) identifying patterns of methylation.
1. A method for deriving two haploid DNA sequences from a diploid DNA sequence signal comprising: obtaining two initial base sequences from the diploid DNA sequence signal; determining alignments of each of the two initial base sequences with a reference DNA sequence; and deriving two haploid DNA sequences from the alignments wherein the derived haploid DNA sequences are mutant DNA sequence alleles that correspond to DNA sequence alleles inherited from an individual's parents wherein obtaining two initial base sequences comprises obtaining two initial base sequences from the mutant DNA sequence alleles.
2. A method for deriving two haploid DNA sequences from a diploid DNA sequence signal comprising: obtaining two initial base sequences from the diploid DNA sequence signal; determining alignments of each of the two initial base sequences with a reference DNA sequence; and deriving two haploid DNA sequences from the alignments wherein the diploid DNA sequence signal comprises a sequence of consecutive DNA signal peaks, wherein the amplitude or area of the signal peaks represents the intensity of the diploid DNA sequence signals and some of the DNA signal peaks are overlapping or partially overlapping, wherein obtaining two initial base sequences from the diploid DNA sequence signal comprises assigning the overlapping or partially overlapping DNA signal peaks to the initial base sequences.
3. The method of claim 2 wherein obtaining the two initial base sequences comprises:
filtering out noise level peaks in the diploid DNA sequence signal;
designating a remaining at most two signal peaks at each position as valid bases; and
assigning each of the valid bases to a base sequence for each corresponding base of the two initial base sequences.
4. The method of claim 2 wherein deriving two haploid DNA sequences comprises improving the initial base sequences by applying at least one heuristic search method that improves an objective function over a discrete search space.
5. The method of claim 4 wherein the heuristic search method comprises a selected one of a local search method, a tabu search method, a simulated annealing algorithm, and a genetic algorithm.
6. The method of claim 4 wherein the objective function for the heuristic search methods is a combined alignment score that is constructed as a sum of two alignment scores with each score obtained from aligning one of the initial base sequences with the reference DNA sequence.
7. The method of claim 2 wherein deriving two haploid DNA sequences comprises improving the initial base sequences by applying at least one application of a heuristic search method taken together with a dynamic programming method for sequence alignment that transforms the initial base sequences to derive the two haploid DNA sequences.