Background of the Invention
The invention pertains to the field of analysis of chromatograms to determine the identity and composition of the components in liquid and gas compositions. More particularly, the invention relates to the use of known cross-correlation and moment analysis techniques to analyze chromatograms.
It is useful in the chemical analysis arts to be able to identify the individual components in a solution or a gas and the concentration of each component. For example, if groundwater is found to be polluted with gasoline, a chromatogram of the gasoline can be taken and compared to chromatograms of gasoline samples taken from service stations, oil refineries, pipelines and petroleum facilities in the area that could have contributed the pollution. In the past, such analysis was done by hand by injecting the unknown solution into a chromatography column and detecting the various components in the effluent output stream in a known fashion. The detector output was then converted into a chromatogram. Then samples from the known solutions were then injected into the chromatography column and various chromatograms were developed, one for each known solution. Then the chromatogram for the unknown sample is compared to the chromatograms of the known samples by hand to determine the source of the pollution. This has been done in the past by placing the chromatograms one on top of the other on a light table and comparing the chromatograms peak for peak. Obviously, this is a laborious, time consuming and expensive process.
Therefore, a need has arisen for a computerized method and apparatus where chromatograms from various sources can be compared automatically to generate some indication of the degree of similarity or difference.
Cross-correlation analysis is well-known in the arts, and has for many years been used in signal processing. Cross-correlation is a mathematical method of comparing one signal wave form or function to another to determine the degree of similarity. If a high degree of similarity exists, a very large peak will be observed in the cross correlation function at the moment in time when the two waveforms or functions being compared overlap each other to the greatest extent. In the prior art, cross correlation analysis has been used in the field of spectroscopy to compare spectra of excitation-emission matrices. Such a methodology was described in a paper by T. M. Rossi and I. M. Warner entitled "Pattern Recognition of Two-dimensional Florescence Data Using Cross-Correlation Analysis", Volume 39, Number 6, 1985 of Applied Spectroscopy, at page 949. To date however, no cross-correlation analysis has ever been performed by computer on chromatograms.
Summary of the Invention
According to the teachings of the invention there is provided an apparatus and method for comparing two substances for similarity. The apparatus according to one embodiment of the invention utilizes a pump for injecting two substances into a chromatography column. A detector detects the components in the effluent stream at the output as they appear and generates an analog signal indicative of the concentration of each element in the effluent stream as it appears. This analog signal, if it were plotted, would be a chromatrograph having a plurality of peaks displaced in time, each representing the concentration of one element in the effluent stream. An integrator integrates the analog signal to generate on output signal indicative of the area under each peak in the chromatogram. An analog to digital converter converts the signal from the integrator into a stream of digital data which is read by a ditigtal computer and stored in a file. This digital data is then converted into a histogram, in the preferred embodiment, where the height of each bar on the histogram represents the area under one peak of the chromatogram.
In one embodiment of the invention, histograms are generated in the above manner for each of two samples of unknown composition. In another embodiment the histogram for an unknwon composition can be generated in the above manner and this histogram can be compared to a plurality of histograms previously prepared from a set of known compositions. In still other embodiments either of the above modes of operation are performed on the chromatograms directly without preparing histograms from the chromatograms.
After the pair of histograms or chromatograms are stored in the digital computer, they are used as the two functions for a cross-correlation computation. After the cross-correlation function is calculated, the 0th, 1st, 2nd, and 3rd moments are calculated on the cross-correlation function. These moments define the symmetry and skewness of the cross-correlation function. The ratio of the 3rd moment to the 2nd moment defines the similarity of the two compositions in terms of the difference in the number of peaks in the two chromatograms. This ratio is calculated by the computer and displayed.
Brief Description of the Drawings
FIG. 1 is a block diagram of a system which is capable of doing cross correlation analysis on chromatograms.
FIG. 2 is a flow chart of the process performed by the embodiment of the invention shown in FIG. 1 in performing a cross correlation and moment analysis on chromatograms.
FIG. 3 is a flow chart of the moment analysis performed in the process shown in FIG. 2.
FIG. 4 is the equation which expresses the mathematical relationship for cross-correlation.
FIGS. 5A-5C illustrate the results of cross-correlating two hypothetical chromatograms.
FIGS. 6A-6C illustrate the results of cross-correlating two other hypothetical chromatograms.
FIGS. 7A-7C illustrate the results of cross-correlating another hypothetical pair of chromatograms.
FIG. 8A is an example of an actual chromatogram.
FIG. 8B is a histogram representation of the chromatogram of FIG. 8A where each bar represents a corresponding peak in the chromatogram and has a height which represents the area under the corresponding peak on the chromatogram.
FIGS. 9A-9C represent a typical pair of histograms and the resulting cross-correlation.
FIGS. 10A-10C represent another pair of histograms and the resulting cross-correlation.
FIG. 11 represent a flow chart of the processing steps to perform the cross-correlation analysis of a sample using the system of FIG. 1 to compare the histogram of the unknown sample to the histograms of a plurality of known substances.
FIG. 12 is a flow chart of the process steps for a cross-correlation analysis of the histograms of two different samples against each other.
FIG. 13 is a flow chart of the process steps for cross-correlation and moment analysis comparison between the histograms of an unknown substance and a known substance.
FIG. 14 is a plot of the output similarity numbers generated using the analysis process of the invention on gasoline.
Detailed Description of the Preferred Embodiment
Referring to FIG. 1 there is shown a block diagram of one embodiment of the invention. The embodiment of FIG. 1 is capable of generating chromatograms and analyzing them using cross-correlation and moment analysis to determine the similarity between two different chromatograms. In other embodiments, a chromatogram may be compared to individual ones of sets of chromatograms each representing one set of known compositions. In these embodiments, a chromatogram from the unknown liquid or gas will be analyzed automatically against each of the chromatograms from the set of known compositions to generate a series of numbers where each number represents the degree of similarity in terms of the number of peaks difference. In other alternative embodiments, the system of FIG. 1 can compare a chromatogram from one unknown sample to the chromatogram of another unknown sample to generate and display a number which is indicative of the similarity between those chromatograms.
The system in FIG. 1 is comprised of an injection pump 10 which receives the unknown sample at a sample imput 12. Injection pump 10 pumps the sample via pipe 14 into a known chromatography column 16. The chromatography column 16 may be either of the liquid or gaseous variety. If it is a gas chromatograph, then the liquid in the pipe 14 is vaporized in the chromatography column 16 and the gas is pushed through the column under pressure. The purpose of the chromatography column 16 is to separate the various components in the input composition in time in the effluent stream 18. This well known process causes the various components in a solution or liquid comprised of multiple components to pass through the column 16 at different speeds. Therefore, the effluent and the output line 18 have different concentrations of the individual components from the input solution at different times.
A detector 20 is used to detect the concentration of each individual component in the effluent stream 18 and generate an output signal on a line 22 which is indicative of the concentration of each individual component in the effluent stream 18 as each component reaches the detector 20.
The output signals on line 22, if plotted, would be a chromatogram with the amplitude of each peak representing the concentration of each element in the effluent stream. The time of occurrence of each peak represents the time each element in the effluent stream reaches the detector 20.
The output signals on line 22 are integrated and converted to digital values by an integrator and analytical digital converter 24. The output digital data stream represents the area under the peaks in the chromatogram. The digital output data stream from the converter 24 is coupled to a computer 26 via a data bus 28. The computer 26 can be any type of computer, either general purpose or special purpose. However, in the preferred embodiment, the computer 26 is an IBM personal computer.
The purpose of computer 26 is to store the incoming digital data on bus 28 as a chromatogram and to do the mathematical analysis to be described below. The computer 26 first converts the chromatogram to a histogram and then does cross-correlation on the histogram from the first sample to a similarly generated histogram from a second sample or from a set of histograms generated from known samples in a similar fashion. After the cross-correlation function generated from the histograms is computed, the computer 26 does a conventional moment analysis on the cross-correlation function calculating the first four moments. The cross-correlation function will, by its shape and skewness, indicate the number of peaks which are different between the two histograms used to generate the cross-correlation function.
The process the computer 26 implements in analyzing the similarity of the substances is given in more detail in FIGS. 2 and 3. These figures are flow charts detailing the process that the overall system performs and detailing of the moment analysis which the computer 26 performs on the cross-correlation function. Referring first to FIG. 2, step 28 symbolizes the process of generating the chromatograms including injection of the various samples into the chromatography column 16 and the detection of the components in effluent stream. This step also symbolizes the process of converting the detector output to digital values. Step 28 can represent either the process of generating two chromatograms injecting two substances into the column 16 or the process of generating one such chromatogram in this manner for the unknown substance and recalling the other chromatogram from memory for a known substance.
Step 30 represents the cross-correlation calculation performed by the computer 26 between the two chromatograms. In the preferred embodiment, the chromatogram from the unknown sample and chromatogram from another unknown sample are both converted to histograms. As is well known in the art, chromatograms consist of a plurality of peaks each of which has an amplitude which represents the concentration of the component represented by that peak in the effluent stream at the particular time or during the particular interval covered by that particular peak. The process of converting the chromatograms to histograms is a process of evaluating the area under each peak in the chromatogram and representing that peak by single bar on a histogram with the height of the bar equal to the area of the peak. Part of this process is performed by block 24. That is the output signal from the detector 20 on line 22 has amplitude which represents the amplitude at any particular time of the signal representing one component in the effluent stream which is then arriving at the detector 20. The integrator in block 24 continually integrates this signal thereby generating an output which is equal to the area under the peak. The analog to digital converter then converts the analog output signals from the integrator to digital values and outputs them on bus 28 to the computer 26. The computer 26, in the preferred embodiment then examines this output digital data stream and converts it to a histogram file where one bar of the histogram represents one peak in the chromatogram. The computer 26 then does the same process for the second chromatogram for the second sample, and then performs a cross-correlation calculation on the two histograms so generated. The cross-correlation function is then stored as a digital file for use by step 32.
Step 32 represents the process performed by the computer 26 in doing conventional moment analysis on the cross-correlation function. The computer 26 does this moment analysis by calculating the first four moments in a known manner. As is well known in the art, the 0th moment defines the area under the cross-correlation function. The 1st moment shows the mean value of the cross-correlation function, while the 2nd moment shows the width of the cross-correlation function. The 3rd moment shows the skewness of the cross-correlation function, or the amount of symmetry in the function. Together these moments define the amount of similarity or dissimilarity between the two histograms which where compared in performing the cross-correlation analysis. From these moments, a number defining this similarity in a single easy to grasp concept can be generated. This process of generating the "similarity number" from the moments is symbolized by block 34 in FIG. 2.
Referring to FIG. 3, there is shown a flow chart of the process which computer 26 follows in performing steps 32 and 34 in FIG. 2. The first step, symbolized by block 36, represents the step of calculating the first four moments. Although the similarity number which ultimately will be derived only requires that the 3rd and 2nd moments be calculated, the 3rd and 2nd moments cannot be calculated until the 0th and 1st moments are calculated. Therefore in step 36, the 0th, 1st, 2nd and 3rd moments are all calculated. Step 38 represents the step of reducing the moments calculated in step 36 to a single number which represents a similarity of the two histograms in terms of the number of peaks difference between the two histograms. In step 38, the 3rd moment is divided by the 2nd moment to derive a single "similarity number" having a dimension equal to the variable used in the cross-correlation function. This number has the dimension of number of peaks or u in the cross-correlation function.
The expression for the cross-correlation function h(x) is as shown in FIG. 4. In this case the function f(x) represents one of the histograms while the function g(x) represents the other histogram. As seen from the integral expression, the cross-correlation function is the sum of the products of the two functions f and g for all values of x with a degree of separation equal to the variable u for all variables u from negative infinity to positive infinity. In other words, the two functions are figuratively passed by each other, multiplied by each other at all overlapping values of x and the products are summed over all u where u represents the amount of separation of the functions. The cross-correlations function is the sum of the products of the two functions at all points of separation where there is some overlap between the two functions. The similarity number calculated in block 38 has the dimension u because the 3rd moment has the dimension u.sup.3 while the 2nd moment has the dimension u.sup.2. This similarity number is output as symbolized by block 40 to the display 42 in FIG. 1.
To gain a better understanding of the process disclosed in FIGS. 2 and 3, refer to FIGS. 5A and 5B where two hypothetical chromatograms having an identical number of peaks and identical symmetry are shown. Their cross-correlation function is shown in FIG. 5C. Note that the cross-correlation function in FIG. 5C is symmetrical and has a peak at the point where the chromatograms of FIGS. 5A and 5B exactly coincide.
In contrast refer to FIGS. 6A through 6C. In FIG. 6A there is shown a chromatogram which is different from the chromatogram from FIG. 6B and since the chromatogram of FIG. 6A is missing one peak. FIG. 6C shows the cross-correlation function of the histograms of FIGS. 6A and 6B. Note that this cross-correlation function is asymmetrical and has a subpeak at 44 which is caused by the difference of the chromatographs in FIGS. 6A and 6B. This subpeak at 44 would show up in the 3rd moment of the cross-correlation function of FIG. 6C which defines skewness of the cross-correlation function.
Another example of how differences in numbers and sizes of peaks in chromatograms will cause skewness in the cross-correlation function is in FIGS. 7A through 7C. FIGS. 7A and 7B are chromatograms that differ by one peak. FIG. 7C is the resulting cross-correlation function. This cross-correlation function has a zero at 46, and is asymmetrical about its center point 48.
Thus, it is seen that any difference in the number of peaks between two chromatograms will result in skewness in the resulting cross-correlation function taken between those two chromatograms.
FIG. 8A is an example of an actual chromatogram which can be plotted from the output of the detector on line 22 in FIG. 1. The vertical axis represents the magnitude of the detector output signal, whereas the horizontal axis represents time. FIG. 8B is an example of a histogram prepared from the chromatogram of FIG. 8A by the combination of the integrator and analog to digital converter 24 and the computer 26 in FIG. 1. There is one bar on the histogram for each peak in the chromatogram of FIG. 8A. The vertical axis represents the area under the curve for the corresponding peak. That is, the height of each bar represents the area under the corresponding peak. The horizontal axis in FIG. 8B does not represent time but represents the peak-to-bar correspondence. That is, the first bar on the histogram represents the first peak and the second bar represents the second peak regardless of when that occurs in time.
FIGS. 9A-9C represent a typical computation. FIG. 9A and FIG. 9B represent two histograms which have been prepared from two chromatograms from two very similar substances. FIG. 9C represents the cross-correlation function of the histograms of FIGS. 9A and 9B. Note that the cross-correlation function is highly symmetrical with a very large peak at the center. This indicates that the two histograms are extremely similar which in turn indicates that the two substances are extremely similar.
FIGS. 10A-10C represent a typical calculation where the two substances being compared are not as similar as the two substances used to generate FIGS. 9A-9C. FIGS. 10A and 10B represent the histograms prepared from the chromatograms of the two different substances. FIG. 10C represents the resulting cross-correlation function calculated using FIGS. 10A and 10B as the two functions. Note that a cross-correlation function is asymmetrical, and has much higher values on the right side of the central peak than on the left side. The skewness will show up in the 3rd moment of the cross-correlation function.
FIG. 11 is a more detailed flow diagram of the system or of the process that the system of FIG. 1 performs. Block 50 represents the step of pumping a sample of the unknown gas or liquid into the chromatogram 16. Block 52 represents the process of detecting the components in the output stream from the chromatogram with a detector which is suitable for analyzing the anticipated chemical elements which exist in the input solution. Block 54 represents the operation of the integrator in analog-to-digital converter 24 in integrating and digitizing the output signal from the detector in line 22. Block 56 represents the process of storing the digital data on bus 28 from the output of the analog-to-digital converter. This digital data defines the peak positions, amplitude, and shape of the chromatogram in general.
Block 58 represents the process performed by the digital computer of converting the chromatogram data to a histogram like that shown in FIG. 8B.
In the embodiment of FIG. 11, the histogram of the unknown sample is compared with the histograms of a plurality of known substances whose histograms have been previously prepared and stored in the digital computer. Step 60 in FIG. 11 therefore represents the cross-correlation calculation of the histogram generated in step 58 with one of the histograms from the set of known substances.
Steps 62 and 64 represent the calculation of the first four moments of the cross-correlation function calculated in step 60 and the calculation of the ratio of the 3rd moment to the 2nd moment and a display of this ratio on the output display 42 along with identification information of the known substance to which the second histogram used in the cross-correlation function corresponds. Step 66 represents the repetition of steps 60, 62 and 64 for all of the other histograms for the known substances.
FIG. 12 represents the process performed by the system of FIG. 1 in an embodiment where two unknown samples are compared against each other. In this embodiment, the first sample is injected into the chromatograph as symbolized by step 68 and the data resulting therefrom is converted into a first chromatogram and then into a first histogram symbolized by steps 70 and 72. Steps 74, 76 and 78 represent the process of injecting the second unknown sample into the chromatograph and generating a second histogram from the data resulting therefrom.
Steps 80 and 82 represent the computation of the cross-correlation function between the two histograms in the computation of the first four moments of the cross-correlation function. Finally, in steps 84 and 86 the ratio of the 3rd moment to the 2nd moment is calculated and displayed.
FIG. 13 represents a more detailed flow diagram of the procedure that the computer 26 follows in the case of comparing a chromatogram from an unknown substance to the chromatograms of a series of known substances which have been previously prepared and stored in the computer. Step 88 represents the process of reading in the digital data which defines the chromatogram from the unknown substance, and the process of reading in the chromatogram data from the known substance. Step 90 represents the process of converting each of these two chromatograms to a histogram. The histograms are prepared such that each peak in the chromatogram is represented by one peak on the corresponding histogram. The bar on the corresponding histogram has an area equal to the area under the corresponding peak of the corresponding chromatogram. Step 92 represents the process of computing the cross-correlation function of the two histograms which correspond to the two current chromatograms. Step 94 represents the process of calculating the 0th, 1st, 2nd and 3rd moments of the resulting cross-correlation function. Step 96 represents the calculation of the ratio of the 3rd moment defining the skewness of the resulting cross-correlation function to the 2nd moment which defines the width of the cross-correlation function. Step 98 represents the output of the result in the form of printing the ratio calculated in step 96 along with the identification number of the known chromatogram which was used in the calculation.
Step 100 symbolizes the process of reading in the digital data for the next known substance chromatogram from the set of known chromatograms. Step 102 represents a test to determine if the previous chromatogram was the last chromatogram in the set of known chromatograms. If the answer is "yes" the program is exited as symbolized by block 104. If the answer is "no" processing proceeds back to block 92 to calculate the cross-correlation function of the histogram from the unknown substance to the new histogram taken from the set of known histograms which are stored in the computer.
FIG. 14 represents a plot of the output similarity numbers generated using the process defined herein on gasoline. Each point represents one comparison between a sample of the gasoline at time zero and another sample of the gasoline taken after a certain amount of time has been allowed to pass and certain component members of the gasoline have evaporated. The first point at 106 represents two samples taken at the same time. The second point at 108 represents the sample taken at time zero compared to the sample taken one hour later. The point at 110 represents the comparison between the sample taken at time zero and the sample taken two hours later. The vertical axis represents the similarity number which resulted from the calculation, and the horizontal axis represents the time span between the two samples. As can be seen from FIG. 14, as time between the two samples became larger, the number of peaks difference of the chromatograms as represented by the ratio m3/m2 of the "correlogram" (another term for the cross-correlation function) becomes larger.
Appendix A, attached, is an object code listing of the program run by computer 26 according to the teachings of the invention.
Although the invention has been described in terms of the preferred and alternative embodiments disclosed herein, those skilled in the art will appreciate many modifications which can be made to the above-disclosed apparatus and process. All such modifications are intended to be included within the scope of the claims appended hereto.