Abstract:
Raw DNA data is filtered with a multi-component analysis that is applied to the difference of the signal intensity on each of the raw DNA data signals to remove cross talk between the signals. The analysis is done before any baseline adjustment of the raw DNA data. Instead, the baseline adjustment occurs after the raw DNA data has been filtered. Additionally, an additional processing step is applied to the data to account for the non-linear nature of cross talk filtering. The additional processing step involves combining the signal with its derivative to account for the correlation of each of the data signals with the other three data signals.

Description:
BACKGROUND OF THE INVENTION 
     This invention relates in general to DNA data processing and in particular to an algorithm for reducing cross-talk between DNA data streams. 
     The structural analysis of DNA has an increasingly important role in modern molecular biology and is needed to support many research programs, including searching for clues to certain diseases. Accordingly, extensive research into DNA structure is ongoing. One of the most complex programs is the Human Genome Project which has the goal of determining the content of human DNA. 
     DNA is a nucleic acid consisting of chains of nucleotide monomers, or oligomers, that occurs in a specific sequence. The structural analysis of DNA involves determining the sequence of the oligomers. Currently, DNA sequencing begins with the separation of a DNA segment into DNA fragments comprising a stochastic array of the oligomers. The separation involves electrophoresis in DNA sequencing gels, such as denaturing polyacrylamide gels. One of two methods is typically used for the electrophoresis, either a chemical method is used that randomly cleaves the DNA segment or dideoxy terminators are used to halt the biosynthesis process of replication. 
     Each of the oligomers in the resulting stociastic array terminates in one of four identifying nitrogenous bases that are typically referred to by a letter. The bases are: adenine (A), cytosine (C), guanine (G) and thymine (T). Thus, the sequencing of the DNA can be accomplished by identifying the order of the bases A, C, G and T. This process is often referred as “base calling”. However, DNA is extremely complex. For example, there are 3.1 billion biochemical letters in human DNA that spell out some 50,000 genes, automated base calling is highly desirable. 
     One method of automated base calling involves fluorescence detection of the DNA fragments. A schematic drawing of an apparatus for fluorescence detection is shown generally at  10  in FIG.  1 . The apparatus  10  includes an upper buffer reservoir  12  connected to a lower buffer reservoir  14  by a gel tube  16 . The gel tube  16  is formed from glass or quartz and has an inside diameter within the range of one to two mm. A detector  18  is mounted near the bottom of the tube  16 . The detector  18  monitors the gel passing through the tube  16  and transmits the data to a computer  20 . 
     The chemical method described above is used to separate a DNA segment into its base oligomers. A different colored fluorophore dye is used for each of the chemical reactions for the bases A, C, G and T . One of the fluorophore dyes attaches to each of the oligomers as a marker. The reaction mixtures are recombined in the upper reservoir  12  and co-electrophoresed down the gel tube  16 . As the fluorophore dye labeled DNA fragments pass by the detector  18 , they are excited by an argon ion laser that causes the dye to fluoresce. The dye emits a spectrum of light energy that falls within a range of wavelengths. A photo-multiplier tube in the detector  18  scans the gel and records data for the spectrum for each of the dyes. The resulting fluorescent bands of DNA are separated into one of four channels, each of which corresponds to one of the bases. The real time detection of the bases in their associated channels is transferred to the computer  20  which assembles the data into the sequence of the DNA fragment. 
     FIG. 2 illustrates an ideal data stream generated by the apparatus  10 . As shown in FIG. 2, a color is associated with each of the four bases; with green identifying A; blue, C; black, G; and red, T. The data in each of the channels is shown as a horizontal line with the detection of a base appearing in real time as a pulse. The resulting time sequence of pulses received, and hence the DNA sequence, is shown as the top line in FIG.  2 . However, the actual data stream differs from the ideal data stream because of several factors. First of all, the emission spectra of the different dyes overlap substantially. Because of the overlap, peaks corresponding to the presence of a single fluorophore dye can be detected in more than one channel. Additionally, the different dye molecules impart non-identical electrophoretic mobilities to the DNA fragments. Furthermore, as the photo-multiplier tube in the detector  18  scans the gel, data detection does not occur at the same time for the four signals. Finally, imperfections of the chemical separation method can result in substantial variations in the intensity of bands in a given reaction. Thus, a set of typical actual raw data streams is shown in FIG.  3 . The notations along the vertical axis in FIG. 3 refer to wavelengths for the detected colors. As in FIG. 2, four data streams are shown with each data stream corresponding to one of the base identifiers, as indicated by the letters in parenthesis. 
     As illustrated by the flow chart shown in FIG. 4, it is known to enhance the raw data streams by a series of operations following the sampling of the DNA data in functional block  32 . First, in functional block  34 , high frequency noise is removed with a low-pass Fourier filter. Typically, each of the four data streams has a different base line level that varies slowly over time. These variations are corrected by passing the data through a high-pass Fourier filter in functional block  35 . 
     The data streams are corrected with respect to signal strength, or magnitude, in functional block  36 . This process is referred to a baseline adjustment. The data signal in each of the four channels is divided into a number of windows with each of the windows including approximately 30 signal peaks. The minimum signal strength is determined within each of the windows. A succession of segments is constructed connecting the consecutive minimum signal strengths. The absolute minima is determined for the consecutive segments. The minimum in each segment is then set to zero and the non-minimum points in the segment is adjusted by subtracting the difference between the absolute minimum and the minimum value for the segment. This signal strength adjustment is commonly referred to as baseline adjustment. 
     Next, a multicomponent analysis, or data filtering, is performed on each set of four data points, as shown in functional block  38 . The filtering determines the amount of each of the four dyes present in the detector as a function of time. After filtering, the mobility shift introduced by the dyes is corrected in functional block  40  with empirically determined correction factors. Following this, the peaks present in the data are located in functional block  42 . The application of the above series of operations to the raw data streams shown in FIG. 3 results in processed data streams in functional block  44  where the DNA sequence is read. The processed data streams are shown in FIG.  5 . The corresponding DNA sequence is shown below the processed data streams in FIG.  5  and consists of the sequential combination of the four processed data streams A, T, G and C. 
     For the data processing described above, it is assumed that the transformation from raw data to filtered data is linear in order to develop the filter for removing the cross-talk. Assuming a linear transformation, the filtering step, shown in functional block  38  in FIG. 4, utilizes a transformation matrix, M, and involves a multi-component analysis that is embodied in the matrix M. With a multi-component analysis, the relationship between the measured signal s j  and the actual fluorescence intensities f j , with j=1, 2, 3 and 4, is given by the relationship:            s   j     =         ∑   4         j   =   1       i   =   1                m     i   ,   j       ·     f   j           ,                          
     where m i,j  is a constant coefficient indicating the cross talk between intensity signals i and j. Writing the above relationship in matrix form results in: 
     
       
         
             s =M· f , 
         
       
     
     where  s  and  f  are vectors with four elements and M is a 4×4 matrix. 
     Typically, the transformation matrix M is determined by a conventional method that includes an iterative process in which known raw data streams are processed through the matrix M and the matrix coefficients adjusted to provide the best signal separation possible for the data streams. The adjustment of the coefficients of the transformation matrix M is necessary because the data transformation is actually non-linear in nature. 
     To determine the actual intensities of the fluorescence, the matrix M is used to deconvolute the measured signals  s  into the actual fluorescence  f  by the following relationship: 
     
       
         
             f =M 
           −1 
           ∵ s   
         
       
     
     In addition to the non-linearity of the data transformation, use of the transformation matrix M requires that the baseline adjustment of the data be applied to the data streams before filtering the data. The baseline adjustment is necessary because, as described above, the baseline within each fluorescent signal collected at the four different wavelengths typically varies with time. Also, each signal can have a different signal level. The algorithm typically used for the baseline adjustment first divides the entire data sequence in each channel into a number of windows. The baseline adjustment algorithm then finds a minimum value within each of the windows and constructs a line connecting the minimum values for each channel. Finally, the line connecting the minimum values is subtracted from the raw data at each data point in each channel. Unfortunately, the baseline adjustment can result in loss of information contained in the raw data and distort the signals. To regain the original data, additional steps, such as a Fourier-based filter for adjusting the base line or even a baseline cutoff is required. This adds complexity to the data processing. Accordingly, it would be desirable to both compensate for non-linear nature of the cross-talk filtering process and to eliminate the baseline adjustment of the raw data. 
     SUMMARY OF THE INVENTION 
     This invention relates to an algorithm for reducing cross-talk between DNA data streams. 
     The present invention is directed toward a multi-component analysis that is applied to the difference of the signal intensity on each of the four channels. This is done before any baseline adjustment of the raw data. Instead, baseline adjustment occurs after the raw data has been filtered. The present invention also adds an additional processing step to account for the non-linear nature of the cross talk filtering. The additional processing step includes combining the signals with their derivatives and accounts for the correlation of each of the data signals with the other three data signals. 
     The present invention contemplates a method for enhancing DNA raw data that includes providing an apparatus for collecting DNA data from dye-labeled DNA fragments, the DNA data being divided between a plurality of channels. The DNA data is passed through a first filter to reduce any cross-talk between data contained in the channels. The data is then passed through a second filter to reduce any non-linearity remaining after the first filtering process has been applied. 
     The reduction of cross talk between the channels includes determining difference values for the signals in each channel by subtracting the magnitudes of the signals in each channel at two consecutive sampling instants. A first multi-component analysis is applied to the difference values to deconvolute the data contained in the signals. The first multi-component analysis includes multiplying the data by a constant coefficient transformation matrix M. 
     The second filtering process to reduce the non-linearity remaining after the first filtering process includes determining derivative values for the signals obtained from the cross talk reduction filter. A multi-component analysis is applied to the derivative values to remove non-linear effects remaining after the first filtering process and the resulting data is then reconstructed to obtain the signal intensity. Similar to the first filter, the second multi-component analysis includes multiplying the data by a constant coefficient matrix T. 
    
    
     Various objects and advantages of this invention will become apparent to those skilled in the art from the following detailed description of the preferred embodiment, when read in light of the accompanying drawings. 
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a schematic diagram of an automated DNA sequencer for detecting DNA sequences. 
     FIG. 2 is an idealized set of data streams obtained from the DNA sequencer shown in FIG.  1 . 
     FIG. 3 shows a set of actual raw data streams obtained from the DNA sequencer shown in FIG.  1 . 
     FIG. 4 is a flow chart for a prior art method for enhancing the raw DNA data streams shown in FIG.  3 . 
     FIG. 5 shows the data from FIG. 3 after application of the prior art data enhancement method illustrated in FIG.  4 . 
     FIG. 6 is a flow chart for a method to enhance raw DNA data streams in accordance with the invention. 
     FIG. 7 illustrates the enhancement of DNA raw data streams as a result of the method shown in FIG.  6 . 
     FIG. 8 is a flow chart for an alternate embodiment of the method shown in FIG.  6 . 
     FIG. 9 is a flow chart for another alternate embodiment of the method shown in FIG.  6 . 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The inventors have found that accurate adjustment of the data baseline is hindered due to the difficulty of separating three main sources of the baseline variation. One of the sources of variation is variation in background lighting during data collection. Another source is the compound effect of consecutive bases of the same type. A third source is the presence of cross talk between the channels. The inventors believe that applying the baseline adjustment before the filtering of the signals can significantly distort the data. 
     The present invention is directed toward an improved method for enhancing the raw DNA data streams to more accurately separate the streams. The method is illustrated by the flow chart shown in FIG.  6 . Functional blocks shown in FIG. 6 that are the same as functional blocks shown in FIG. 4 have the same numerical designators. Thus, in functional block  32  raw DNA data streams are obtained by monitoring the passage of dye-labeled DNA fragments through the apparatus shown in FIG.  1 . As described above, the raw data is separated into four channels and varies as a function of time. Because the four signals are not recorded at the same time, the information contained on one channel does not correspond to the information contained in the other three channels. Accordingly, the data stream in one of the four channels is selected as a time reference and the other three data streams are shifted in time in functional block  33  according to the position of the gel in the gel tube  16  when the raw data was read in the preceding functional block  32 . As indicated in FIG. 6 this step is optional and is applied for certain test apparatus. For example, the step would be included for data obtained with ABI  373  and  377 , but could be omitted for data obtained with ABI  3700 . The data is then passed through a low pass Fourier filter in functional block  34  to remove high frequency noise. 
     The data points for any sample i at a corresponding point in time can be represented by g i , c i , t i , and a i . In functional block  46 , the difference in the data points between two samples, i and i+1, at two consecutive sample times is determined by the relationships: 
     
       
         Δ g   i   =g   i +1 −g   i ; 
       
     
     
       
         Δ c   i   =c   i +1 −c   i ; 
       
     
     
       
         Δ t   i   =t   i +1 −t   i ; and 
       
     
     
       
         Δ a   i   =a   i +1 −a   i . 
       
     
     The data point differences, or signal variations, are filtered in functional block  48  by applying the transformation matrix M developed for cross-talk removal to obtain signal variation vectors  Δg   i ,  Δc   i ,  Δt   i ,  Δa   i , that represent transformed data point differences as follows: 
     
       
         [   Δg     i   ,  Δc     i   ,  Δt     i   ,  Δa     i   ]T=M   −1   ·[Δg   i   , Δc   i   , Δt   i   , Δa   i   ]T   
       
     
     In the preferred embodiment, a second filtering step is then applied to the data in functional blocks  52  through  56 . The second filtering step is based upon the inventor&#39;s observation that the transformation of the data from “detector space”, or raw data, to “filtered space” is nonlinear in nature. The second filtering is described by the following operation:                Δ                 s       _   _       i     =           Δ                 s     _     i     +           ∑   4       j   =   1         j   ≠   i              t     i   ,   j       ·         Δ                 s     _     j   ′             ;                          
     Where  Δs   i  is the data signal variation and is given by:              Δ                 s     _     i     =                    Δ                 g     _     i                   Δ                 c     _     i                   Δ                 t     _     i                   Δ                 a     _     i                                       
     and  Δs   j ′ is the derivative of the data signal variation and is given by:              Δ                 s     _     j   ′     =                    Δ                 g     _     j   ′                   Δ                 c     _     j   ′                   Δ                 t     _     j   ′                   Δ                 a     _     j   ′                                       
     The above formula can be written in matrix form as: 
     
       
         
             Δs = Δs +T· Δs ′; 
         
       
     
     where:            Δ                 s       _   _       =                  Δ                 g       _   _                   Δ                 c       _   _                   Δ                 t       _   _                   Δ                 a       _   _                                         
     The matrix T is a constant coefficient 4×4 transformation matrix that accounts for the correlation of each of the signals with the other three. The transformation matrix T is determined by the same conventional method that is used to determine the cross talk removal matrix M, except that different known data streams are used. Thus, the determination of T includes an iterative process in which known data streams are processed through the matrix T and the matrix coefficients adjusted to provide the desired output data. Accordingly, in functional block  52 , derivatives  Δs ′ of the signal variation  Δs  are calculated. The signal derivatives are filtered by application of the matrix T in functional block  54  in accordance with the relationships shown above. The result of the second filtering operation is signals,  Δg ,  Δc ,  Δt  and  Δa . 
     The signals  Δg ,  Δc ,  Δt  and  Δa  are used in functional block  56  to reconstruct the signals of the four fluorophores with the following operation: 
     
       
             s     i +1 = Δs     i   + s     i ; 
       
     
     Up to a constant value, the vectors  g   i ,  c   i ,  t   i  and  a   i  included in  s   i  contain recomposted signals with the cross-talk removed and non-linearity corrected. However, the signals are still shifted relative to each other and with respect to a baseline due to variations in the electrophoresis process caused by such things as temperature changes, variation in applied voltages, gel variations and the like. Accordingly, the signals are passed though a high-pass Fourier filter in functional block  57 . Thus, the present invention contemplates separating the high-pass filtering operation from the low-pass filtering operation illustrated in FIG.  4 . 
     The data streams are corrected with respect to signal strength, or magnitude, in functional block  58 . This process is referred to a baseline adjustment. The data signal in each of the four channels is divided into a number of windows, which, in the preferred embodiment will contain approximately 30 peaks each. The minimum signal strength is determined within each of the windows. A succession of segments is constructed connecting the consecutive minimum signal strengths. The absolute minima is determined for the consecutive segments. The minimum in each segment is then set to zero and the non-minimum points in the segment is adjusted by subtracting the difference between the absolute minimum and the minimum value for the segment. 
     As previously described, the peaks of the signals are located in functional block  40  and the DNA sequence read in functional block  44 . 
     EXAMPLE 
     Referring again to the drawings, there is illustrated in FIG. 7, an example of the method for enhancing DNA data shown in FIG.  6  and described above. Part A of FIG. 7 shows a section of a raw DNA data sequence. As described above, the first step in the method involves determining the differences, or changes, in the signal amplitudes. Accordingly, Part B of FIG. 7 illustrates the variation of the four signals after the amplitude shift in functional block  46  of FIG. 6 has been completed. The signals shown in Part B of FIG. 7 are then operated upon the matrix M, which, for this example, is given by:        M   =              1       0       0.47       0.19           0.15       1       0.05       0.36           0.07       0       1       0           0.36       0.14       0.22       1                                     
     The nonlinear transformation correction is applied by operating upon the signals with the matrix T, which, for this example, is given by:        T   =              0       0       0.1         -   0.15               -   0.06         0         -   0.01           -   0.05             0.05       0       0       0           0.13       0.05       0.08       0                                     
     The result of the second filtering step is shown in Part C of FIG. 7. A portion of the curve show in Part C of FIG. 7 is enlarged and labeled  60  in Part D of FIG.  7 . Also shown in FIG. Part D of FIG. 7 is a portion of a corresponding curve  62  that would result without the second filtering step to eliminate the non-linarities. Part D of FIG. 7 demonstrates that the noise in the baseline is clearly attenuated by the second filtering step. The overall result can be compared to that obtained with a highly adaptive filter. The final DNA sequence is shown below Part C of FIG.  7 . 
     Similar experiments carried out by the inventors have shown that by performing the baseline adjustment after filtering out the cross talk between the channels, the data content of the signals is better preserved. The inventors believe that the most important feature of their method is the use of the variation of the signal rather than the actual value for removal of the cross talk. By using the variation of the signal, it is possible to reverse the order in which the cross talk removal and baseline adjustment are performed. To further filter the signals, the inventors have extended their method to account for the nonlinear dependency between the raw data and the actual signals. The method illustrated and described above helps preserve the information contained in the raw DNA data. 
     While the preferred embodiment has been illustrated and described above, it is also possible to practice the invention with an alternate embodiment of the method as shown in FIG.  8 . The functional blocks in FIG. 8 that are the same as the functional blocks shown in FIGS. 4 and 6 have the same numerical identifiers. In the flow chart shown in FIG. 8, the cross talk filtering step shown in functional block  38  in FIG. 4 has been replaced with the use of the variation of the signal rather than the actual value for removal of the cross talk, as shown in functional blocks  46  and  48  in FIG.  6 . Additionally, the high pass filtering, as shown in functional block  57 , and the base line adjustment, as shown in functional block  58  occur after the filtering of the cross talk. Therefore, the method shown in FIG. 8 would produce the data shown in Part D of FIG.  7  and is equivalent to the preferred embodiment with the second filtering operation removed. While the method shown in FIG. 8 will not provide the degree of enhancement obtained with the method shown in FIG. 6, the inventors believe that the method shown in FIG. 8 will provide a degree of enhancement that is better than that obtained with the prior art method shown in FIG.  4 . 
     Similarly, the inventors contemplate a second alternate embodiment of their invention, as illustrated in FIG.  9 . The functional blocks in FIG. 9 that are the same as the functional blocks shown in FIGS. 4 and 6 have the same numerical identifiers. The flow chart in FIG. 9 is similar to the prior art method shown in FIG. 4, except that the optional data time shift correction in functional block  33  and the second filtering step in functional blocks  52  and  54  have been added. Also, the baseline adjustment shown in functional block  58  occurs after signals are reconstructed in functional block  56 . While the method shown in FIG. 9 will not provide the degree of enhancement obtained with the method shown in FIG. 6, the inventors believe that the method shown in FIG. 9 will provide a degree of enhancement that is better than that obtained with the prior art method shown in FIG.  4 . 
     In accordance with the provisions of the patent statutes, the principle and mode of operation of this invention have been explained and illustrated in its preferred embodiment. However, it must be understood that this invention may be practiced otherwise than as specifically explained and illustrated without departing from its spirit or scope.