Abstract:
The recovery of the sequence of bases in a dideoxyribonucleic acid (DNA) molecule is important for both research and medical applications. The standard processing techniques are prone to error. This invention creates from the template a new set of molecules which introduce an error correcting code as might be used in data communications. After the usual processing associated with DNA sequencing, the code can be used to reduce the errors in the estimated sequence.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This patent application claims the foreign priority of Canadian Patent Application Number 2,256,128, Dec. 29, 1998. 
     STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
     United States Federal sponsorship was not involved in this work. 
     REFERENCE TO A MICROFICHE APPENDIX 
     Not applicable. 
     BACKGROUND OF THE INVENTION 
     References 
     1. Brown, T. A., “DNA Sequencing: The Basics”, Oxford University Press, New York, 1994. 
     2. Tibbetts, C., Bowling, J., “Method and Apparatus for Automatic Nucleic Acid Sequence Determination”, U.S. Pat. No. 5,365,455, Nov. 15, 1994. 
     3. Lee, E., Messerschchmitt, D., “Digital Communication”, (2nd Ed.), Kluwer, New York, 1994. 
     4. Proakis, J. G., “Digital Communications”, (3rd Ed.), McGraw-Hill Inc., New York, 1995. 
     5. Blahut, R. E., “Theory and Practice of Error Control Codes”, Addison-Wesley Publishing Co., Reading, Mass., 1983. 
     DeoxyriboNucleic Acid (DNA) encodes genetic information by specific base type at each point in a sequence of bases. For research and medical purposes it is desirable to recover the sequence,  x ={x i ,i=1, . . . , N}, where x i  is one of the four bases {adenine(A), cytosine(C), guanine(G), thymine(T)} that encode the genetic information; for some medical tests, it is not necessary to recover the whole sequence but rather identify the base type at certain key locations in the sequence. 
     In Sanger sequencing [1], the DNA template to be sequenced is chemically processed to encode sequence position by molecular weight and base type by the presence or absence of a fluorescent or radioactive marker. Gel electrophoresis is used to separate the molecules by length, translating molecular size into time of passage past a detector in the case of automated DNA sequencing [2]. Four time-series y n,k , where n={A,C,G,T} and k is the time sample index, are recorded, each of which corresponds to one of the four possible chemical base types. At a given time, a high-level signal (peak) should appear in only one of the series; this indicates the base type at that point in the sequence. We shall refer to the recorded time series as the ‘DNA time-series’ for the remainder of this document. 
     The fragment of DNA to be sequenced and the starting position for sequencing are identified through the use of primers [1]. Primers are short strands of DNA that are complementary to the target DNA sequence at the point of interest. Primers bind to the DNA template at that point and permit copying of the DNA using a DNA polymerase. This copying process is used in fragment selection and in sequencing as part of the process that encodes sequence position by molecular weight. In the later case, the recovered sequence position would be relative to the primer&#39;s location with respect to the original DNA template. 
     In practice, the recovery of the sequence is complicated by undesirable signal features. Errors in DNA sequencing can have dangerous implications for the pharmaceutical and medical communities. To reduce errors, the entire sequencing process is repeated until a consensus sequence may be reached. This process is costly. Thus, there exists a need for a method to reduce error rate so that the costs and risks of DNA sequencing and testing may be minimized. 
     In data communications [3],[4] time-series similar to the DNA time-series described above are used to represent sequential information such as the text of a document. A receiving device will examine the time-series to recover an estimate of the original text. However, noise and distortion imposed on the time-series during its passage through a transmission medium such as a radio link or telephone wires can lead to errors in the recovery of the original information. To reduce the chance of error, the original data may first be passed through a coder that imposes a mathematical code on the data [3][5]. This introduces redundant information that a decoder added to the receiver uses to identify and correct errors. A large variety of codes have been created [5]. 
     BRIEF SUMMARY OF THE INVENTION 
     With a goal of reducing errors, this invention imposes a code by creating a new family of molecules from the DNA fragment of interest. This new family of molecules consists of fragments offset from the start of the original fragment by using different primers to achieve different offsets. 
     Standard codes may then be implemented by combining different proportions of the different fragments. This mixture is then used in the usual testing or sequencing process, such as gel electrophoresis, to recover the coded DNA time-series. The sequencer or tester then decodes the time-series by hypothesizing what the time series should have been for each possible sequence and choosing the sequence that yields the best match to the observed time-series. 
     BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING 
     Not applicable. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The overall processing is best illustrated by a simple example. The extensions to the general case will be discussed after the example. 
     Consider an original DNA template 
     SEQ ID NO:1 CAAGTACCGAGCTGA 
     where the letters A, C, G and T correspond to the four possible base types. Consider sequencing starting with the ninth base in the sequence. An appropriate primer for the sequencing reactions would then be complementary to 
     GTACC 
     and given this primer the sequencing process may be carried out as is common to the art. The sequence thus obtained if no errors occurred would be 
     GAGCTGA. 
     To add coding in this example, two additional primers are included which are complementary to the fragments 
     CAAGT 
     AGTAC 
     respectively. These primers, if used separately, would then lead to obtaining the following sequences 
     SEQ ID NO:2 ACCGAGCTGA 
     CGAGCTGA 
     respectively, if the common sequencing process was carried out. These correspond to priming for sequences starting at the sixth and eighth positions in the original sequence. For our coding example, however, all three primers are used, either in the same reaction vessel or separately with the products then combined in to the same reaction vessel. Now on sequencing the combination, rather than seeing a single peak at each base position corresponding to a single base type, it is possible for several base types to be indicated simultaneously. The three primers lead to the superposition of the three sequences 
     SEQ ID NO:2 ACCGAGCTGA 
     CGAGCTGA 
     GAGCTGA. 
     For example, in the second base position, peaks should appear in the time-series corresponding to the bases C, G and A while no peak should appear in the second base position for the T time-series. At locations where two of these sequences have a common base type, the corresponding peak height should be double that of the case where only one sequence had a base of that type at that position. At locations where three of these sequences have a common base type, the corresponding peak height should be thrice that of the case where only one sequence had a base of that type at that position. This leads to an idealized representation of the peak heights of the four channels of the DNA time-series as a function of sequence position as 
     
       
         
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                   
               
             
             
               
                 A 
                 1 
                 1 
                 1 
                 0 
                 1 
                 0 
                 1 
                 1 
                 0 
                 1 
               
               
                 C 
                 1 
                 1 
                 1 
                 1 
                 1 
                 0 
                 1 
                 0 
                 0 
                 0 
               
               
                 G 
                 1 
                 1 
                 1 
                 2 
                 0 
                 2 
                 1 
                 0 
                 1 
                 0 
               
               
                 T 
                 0 
                 0 
                 0 
                 0 
                 1 
                 1 
                 0 
                 1 
                 0 
                 0. 
               
               
                   
               
             
          
         
       
     
     To illustrate the error correcting ability of this code, consider an error occurring in the reactions (or electrophoresis and detection) associated with the primer GTACC such that the corresponding sequence was GAACTGA rather than GAGCTGA. Then, assuming the other reactions were error free, the three primers lead to the superposition of the three sequences 
     SEQ ID NO:2 ACCGAGCTGA 
     CGAGCTGA 
     GAACTGA 
     and the peak heights of the four channels of the DNA time-series as a function of sequence position are 
     
       
         
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                   
               
             
             
               
                 A 
                 1 
                 1 
                 2 
                 0 
                 1 
                 0 
                 1 
                 1 
                 0 
                 1 
               
               
                 C 
                 1 
                 1 
                 1 
                 1 
                 1 
                 0 
                 1 
                 0 
                 0 
                 0 
               
               
                 G 
                 1 
                 1 
                 0 
                 2 
                 0 
                 2 
                 1 
                 0 
                 1 
                 0 
               
               
                 T 
                 0 
                 0 
                 0 
                 0 
                 1 
                 1 
                 0 
                 1 
                 0 
                 0 
               
               
                   
               
             
          
         
       
     
     This differs from the original table of peak heights only in at the third base position. However, the hypothesized peak table corresponding to our error having in fact been the right sequence (i.e. the original template being SEQ ID NO:1 CAAGTACCGAACTGA) is 
     
       
         
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                   
               
             
             
               
                 A 
                 1 
                 1 
                 2 
                 1 
                 1 
                 1 
                 1 
                 1 
                 0 
                 1 
               
               
                 C 
                 1 
                 1 
                 1 
                 1 
                 1 
                 0 
                 1 
                 0 
                 0 
                 0 
               
               
                 G 
                 1 
                 1 
                 0 
                 1 
                 0 
                 1 
                 1 
                 0 
                 1 
                 0 
               
               
                 T 
                 0 
                 0 
                 0 
                 0 
                 1 
                 1 
                 0 
                 1 
                 0 
                 0 
               
               
                   
               
             
          
         
       
     
     This differs from the observation at the fourth and sixth base positions. In the language of coding theory, these two differences correspond to a Hamming distance of two where as the correct hypothesis differs only at the third base and thus has a Hamming distance of one. The rule to be used in the simple decoder is to choose the hypothesis with the least Hamming distance. Thus, for this case of a single error associated with one primer, the decoder would in fact choose the correct sequence, GAGCTGA, where as the standard processing using only a single primer (GTACC) would have erroneously estimated the sequence to be GAACTGA. 
     Note that this example assumed exact estimates of the peak heights were available. As is well known in the art of communications, this presumption corresponds to “hard decoding”. If the actual time-series had been compared with hypothesized idealized time-series then the decoding process would in communications be referred to as “soft decoding”. 
     Extending this example to the general case yields the preferred description of the invention as described in the following three steps. 
     Step 1—Conduct sequencing reactions using multiple primers pointing to different points in the sequence. By changing the relative proportions of the primers, it is possible to compensate for different reactivities of the primer, polymerase and template complex. Also, fractional weights, as might be utilized in sophisticated coding schemes, may be obtained. Select a code from the literature with the desired error correcting characteristics. Note that a wide variety of such codes are available and that this invention does not refer to a specific code but rather the process by which codes common to the art of communications may be used in DNA sequencing. The general class of convolutional codes are directly applicable as they correspond to weighted sums of sequences with different offsets into the original information sequence. 
     Step 2—Through the usual art of DNA sequencing obtain time-series corresponding to the four base types. Use these series directly if soft decoding is to be employed. If hard decoding is to be employed, process the time-series to recover peak heights at each base position. 
     Step 3—Compare the time-series (or peak heights in the case of hard decoding) to the ideal time-series (or peak heights in the case of hard coding) for different hypothesized sequences. The model used in generation of these time-series may account for effects inherent in the electrophoresis process such as varying peak shape with sequence position. Choose as the estimated sequence the hypothesized sequence that yields the time-series (or peak heights) closest in Euclidian distance (or Hamming distance in the case of hard coding). 
     
       
         
           
             2 
           
           
             1 
             15 
             DNA 
             Artificial Sequence 
             
               arbitrary random sequence chosen to illustrate
      concept 
             
           
            1
caagtaccga gctga                                                      15
 
           
             2 
             10 
             DNA 
             Artificial Sequence 
             
               last ten bases of sequence 1 
             
           
            2
accgagctga                                                            10