Profile searching in nucleic acid sequences using the Fast Fourier Transformation
The 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 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 method of computing the number of matches between a test nucleic acid sequence and a profile for a set of functionally aligned nucleic acid sequences comprising the steps of
A) constructing a first indicator function for the profile, said indicator function corresponding to a first base, said indicator function continuous between 0 and 1 for a value at a given position as a function of the percentage presence of the first base at a particular position,
B) constructing a second indicator function for the test nucleic acid sequence, said indicator function corresponding to the first base,
C) computing in a computer the Fourier transform of each of the indicator functions,
D) complex conjugating the Fourier transform of the second indicator function,
E) multiplying the Fourier transform of the first indicator function and the complex conjugated Fourier transform of the second indicator function to obtain a Fourier transform for adenine base matches,
F) repeating steps A-E above for a second base, a third base, and a fourth base,
G) summing the Fourier transforms of the number of matches for each base, respectively, to obtain the total Fourier transform,
H) computing the inverse Fourier transform of the total Fourier transform to obtain a complex series, said complex series comprising a real part, and
I) taking 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, and
J) displaying said base matches,
wherein said nucleic acid sequence profile is a DNA profile,
wherein said method further comprises the step of reverse-translating a protein profile for a set of protein sequences to obtain said DNA profile, said reverse translation being performed using codon-usage tables, said reverse translation step occurring before step (A).
2. The method according to claim 1 , wherein said protein sequences are selected from the group of protein sequences consisting of transmembrane regions defined by stretches of hydrophobic residues, antigenic regions defined by stretches of hydrophilic regions, EF-hand which occurs in calcium binding proteins, helix-turn-helix motif which occurs in the DNA binding motif, zinc finger which occurs in the DNA binding motif, and glycosylation motif, a post translational protein modification.
3. The method according to claim 1 , wherein said protein profile is weighted by the degree of conservation at each residue position in the alignment.
4. The method according to claim 1 , wherein said DNA profile is weighted by the degree of conservation at each position in the sequence.
5. The method according to claim 1 , wherein said test nucleic acid sequence has a length of from approximately 10 kilobases to approximately 100 kilobases.
6. The method according to claim 1 , wherein said profile consists of from approximately 5 to approximately 30 amino acids.
7. The method according to claim 1 , wherein said DNA profile is selected from the group of DNA profiles consisting of promoters and enhancers.
8. A computer-implemented method of computing the number of matches between a test nucleic acid sequence and a profile for a set of functionally aligned protein sequences comprising the steps of
A) reverse-translating the profile for the set of protein sequences to a DNA profile using codon-usage tables,
B) constructing a first indicator function for the DNA profile, said indicator function corresponding to adenine, said indicator function continuous between 0 and 1 for a value at a given position as a function of the percentage presence of adenine at a particular position,
C) constructing a second indicator function for the test nucleic acid sequence, said indicator function corresponding to adenine,
D) computing in said computer the Fourier transform of the first and second indicator functions,
E) complex conjugating the Fourier transform of the second indicator function,
F) multiplying the Fourier transform of the first indicator function and the complex conjugated Fourier transform of the second indicator function to obtain a Fourier transform for adenine base matches,
G) repeating steps B-F above for guanine, thymine, and cytosine,
H) summing the Fourier transforms of the number of base matches to obtain the total Fourier transform,
I) computing the inverse Fourier transform of the total Fourier transform to obtain a complex series comprising a real series,
J) taking the real part of the series to determine the total number of base matches for the variety of possible lags of the DNA profile relative to the test sequence, and
K) displaying said base matches,
wherein said method further comprises the step of detecting 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 between the DNA profile and the test sequence, said detecting step occurring after step (J).
9. A system for computing the number of matches between a test nucleic acid sequence and a profile for a set of functionally aligned nucleic acid sequences comprising
a central processing unit for executing instructions,
a memory unit comprising an operating system
a first indicator construction module for constructing four first indicator functions for the profile, said indicator functions corresponding to adenine, guanine, thymine, and cytosine, said indicator functions continuous between 0 and 1 for a value at a given position as a function of the percentage presence of each of the bases at a particular position,
a second indicator construction module for constructing four second indicator functions for the test nucleic acid sequence, said second indicator functions corresponding to adenine, guanine, thymine, and cytosine,
a Fourier transform module for computing the Fourier transform of each of the indicator functions,
a complex conjugation module for complex conjugating the Fourier transforms of the four second indicator functions,
a multiplication module for multiplying the Fourier transforms of the first indicator functions and the conjugated Fourier transforms of the second indicator functions for each of the bases, respectively, to obtain Fourier transforms for adenine, guanine, thymine, and cytosine matches,
a summation module for summing the Fourier transforms of the number of matches for each base, respectively, to obtain the total Fourier transform, and
a computation module for computing the inverse Fourier transform of the total Fourier transform to obtain a complex series, and for taking 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, and conductive interconnects connecting the central processing unit and the memory to allow portions of the system to communicate and to allow the central processing unit to execute modules in the memory unit,
wherein said nucleic acid sequence profile is a DNA profile wherein said nucleic acid,
wherein said method further comprises the step of reverse-translating a protein profile for a set of protein sequences to obtain said DNA profile, said reverse translation being performed using codon-usage tables, said reverse translation step occurring before step (A); and
wherein said total number of base matches are displayed.
10. The method of claim 1 , wherein said computer comprises
a central processing unit for executing instructions,
a memory unit comprising an operating system,
a first indicator construction module for constructing four first indicator functions for the profile, said indicator functions corresponding to adenine, guanine, thymine, and cytosine, said indicator functions allowing the value at a given position to be continuous between 0 and 1 as a function of the percentage presence of each of the bases at a particular position,
a second indicator construction module for constructing four second indicator functions for the test nucleic acid sequence, said second indicator functions corresponding to adenine, guanine, thymine, and cytosine,
a Fourier transform module for computing the Fourier transform of each of the indicator functions,
a complex conjugation module for complex conjugating the Fourier transforms of the four second indicator functions,
a multiplication module for multiplying the Fourier transforms of the first indicator functions and the conjugated Fourier transforms of the second indicator functions for each of the bases, respectively, to obtain Fourier transforms for adenine, guanine, thymine, and cytosine matches,
a summation module for summing the Fourier transforms of the number of matches for each base, respectively, to obtain the total Fourier transform, and
a computation module for computing the inverse Fourier transform of the total Fourier transform to obtain a complex series, and for taking 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, and conductive interconnects connecting the central processing unit and the memory to allow portions of the system to communicate and to allow the central processing unit to execute modules in the memory unit.