Profile searching in nucleic acid sequences using the fast fourier transformation
View Patent ↗One embodiment of the present invention provides methods for detecting known blocks of functionally aligned protein sequences in a test nucleic acid sequence, e.g., in an uncharacterized EST. The method can include the following steps. A) Reverse translate the set of protein sequences to a set of functionally aligned nucleic acid sequences using codon-usage tables and create a profile from the set of functionally aligned nucleic acid sequences. B) Construct a first indicator function for the profile. The first indicator function corresponds to adenine. The first indicator function allows the value at a given position to be continuous between 0 and 1 as a function of the percentage presence of adenine at a particular position. C) Construct a second indicator function for the test nucleic acid sequence. The second indicator function also corresponds to adenine. D) Compute the Fourier transform of each of the indicator functions. E) Complex conjugate the Fourier transform of the second indicator function. F) Multiply the Fourier transform of the first indicator function and the complex conjugated Fourier transform of the second indicator function to obtain a Fourier transform of the number of matches of adenine bases. G) Repeat steps B-F above for guanine, thymine, and cytosine. H) Sum the Fourier transforms of the number of matches for each base, respectively, to obtain the total Fourier transform. I) Compute the inverse Fourier transform of the total Fourier transform to obtain a complex series. J) Take the real part of the series to determine the total number of base matches for the variety of possible lags of the profile relative to the test sequence. The method can then detect the presence of known blocks of functionally aligned protein sequences in a test nucleic acid sequence based on the total number of base matches for the variety of possible lags.
1. A system comprising:
a computer-readable memory including computer-executable instructions; and
a processor coupled to the computer-readable memory and configured to read the computer-executable instructions to cause the processor to:
provide a first indicator for a known nucleic acid profile, the first indicator corresponding to a first base, the first indicator including values that are related to frequencies of presence of the first base at associated positions in the profile,
provide a second indicator for a test nucleic acid sequence, the second indicator corresponding to the first base,
compute a Fourier transform of each of the indicators, and
use the Fourier transform of each of the indicators to determine a number of base matches between the profile and the test sequence.
2. The system of claim 1 wherein the first indicator is adapted to include at least three different values related to frequencies of presence of the first base for each position in the profile.
3. The system of claim 2 wherein the first indicator is adapted to include values ranging from 0 to 1, inclusive.
4. The system of claim 3 wherein the first indicator is adapted to include values ranging from 0 to 1 continuously in at least increments of 0.01.
5. The system of claim 1 wherein the computer-executable instructions for causing the computer to use the Fourier transform of each of the indicators cause the computer to complex conjugate the Fourier transform of the second indicator and multiply the Fourier transform of the first indicator and the complex conjugated Fourier transform of the second indicator to obtain a Fourier transform for the first base indicative of a number of matches of the first base in the profile and the test sequence, the memory further comprising instructions for causing the processor to provide the first and second indicators, to compute the Fourier transforms, to complex conjugate the Fourier transform of the second indicator and to multiply the Fourier transform of the first indicator and the complex conjugated Fourier transform of the second indicator for at least a second base.
6. The system of claim 5 wherein the computer-executable instructions further cause the processor to:
sum the Fourier transforms of the number of matches for each base, respectively, to obtain a total Fourier transform;
compute an inverse Fourier transform of the total Fourier transform to obtain a complex series having a real part and an imaginary part; and
use the real part of the complex series to determine a total number of base matches for possible lags of the profile relative to the test sequence;
wherein an increase in the total number of base matches indicates an increased likelihood of the presence of the profile in the test sequence.
7. The system of claim 5 wherein the values of the first indicator are dependent on frequencies of presence of each base relative to each other for each position in the profile.