Chemistry: molecular biology and microbiology – Measuring or testing process involving enzymes or... – Involving nucleic acid
Reexamination Certificate
1999-05-19
2001-09-11
Brusca, John S. (Department: 1631)
Chemistry: molecular biology and microbiology
Measuring or testing process involving enzymes or...
Involving nucleic acid
C435S091500, C435S068100, C536S023100, C536S023400, C530S300000, C530S350000
Reexamination Certificate
active
06287773
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to profile searching in nucleic acid sequences, and more particularly, to detecting known blocks of functionally aligned amino acid sequences in a nucleic acid sequence, e.g., in an uncharacterized expressed sequence tag (EST), using Fast Fourier Transform (FFT) methods.
BACKGROUND OF THE INVENTION
FFT methods can facilitate the determination of the optimal global alignment of two DNA sequences. For example, Felsenstein, Sawyer, and Kochin, in “An Efficient Method for Matching Nucleic Acid Sequences,” Nucleic Acids Research, Volume 10, Number 1, pp. 133-139, incorporated herein by reference, describe a method of computing the fraction of matches between two nucleic acid sequences at all possible alignments. Benson, in Fourier Methods for Biosequence Analysis, Nucleic Acids Research, Vol. 18, No. 21, p. 6305, incorporated herein by reference, and in Digital Signal Processing Methods for Biosequence Comparison, Nucleic Acid Research, Vol. 18, No. 10, p 3001, incorporated herein by reference, describes similar methods. Cheever, Overton, and Searls, in Fast Fourier transform-based correlation of DNA sequences using complex plane encoding, CABIOS, Vol. 7, No. 2, pp. 143-154, incorporated herein by reference, describe yet another variation on the use of FFT methods for the correlation of DNA sequences. These methods all use a means of coding DNA sequences as 4 binary vectors or functions (0 or 1), one vector or function for each of the 4 different bases (A, C, G, or T).
Although FFT methods can facilitate the determination of the optimal global alignment of two DNA sequences, a need remains for an efficient system for detecting known blocks of functionally aligned amino acid sequences in a nucleic acid sequence, e.g., in an uncharacterized EST.
SUMMARY OF THE INVENTION
The present invention concerns methods for detecting known blocks of functionally aligned protein sequences in a test nucleic acid sequence, e.g., in an uncharacterized EST. One embodiment of the invention provides the following steps. A) Reverse translate a set of functionally aligned protein sequences to a set of functionally aligned nucleic acid sequences using codon-usage tables and create a DNA profile from the set of functionally aligned nucleic acid sequences. B) Construct a first indicator function for the DNA 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. In other words if adenine occurs at a particular position in 25 out of 100 sequences, then the adenine indicator function reads 0.25 for that position in the DNA profile. 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 as a function of the total number of base matches for the variety of possible lags of the profile relative to the test sequence.
A second embodiment according to the present invention includes the following steps. A) Construct a first indicator function for a profile corresponding to known blocks of functionally aligned protein sequences. 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. B) Construct a second indicator function for the test nucleic acid sequence. The second indicator function also corresponds to adenine. C) Compute the Fourier transform of each of the indicator functions. C) Complex conjugate the Fourier transform of the second indicator function. E) 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. F) Repeat steps A-E above for guanine, thymine, and cytosine. G) Sum the Fourier transforms of the number of matches for each base, respectively, to obtain the total Fourier transform. H) Compute the inverse Fourier transform of the total Fourier transform to obtain a complex series. I) 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.
A third embodiment according to the present invention provides 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. The system includes a central processing unit for executing instructions, a memory unit, 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. The memory unit includes an operating system, and several modules. A first indicator construction module constructs four first indicator functions for the profile. The indicator functions corresponding to adenine, guanine, thymine, and cytosine. The indicator functions allow 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 constructs four second indicator functions for the test nucleic acid sequence. The second indicator functions correspond to adenine, guanine, thymine, and cytosine. A Fourier transform module computes the Fourier transform of each of the indicator functions. A complex conjugation module complex conjugates the Fourier transforms of the four second indicator functions. A multiplication module multiplies 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 sums the Fourier transforms of the number of matches for each base, respectively, to obtain the total Fourier transform. A computation module computes the inverse Fourier transform of the total Fourier transform to obtain a complex series. The computation module also takes 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 number of computational steps required using an FFT method is proportional to NlogN where N is the number of bases in the longest sequence. The number of computational steps using spatial domain methods is proportional to N
2
. Thus, if N is large enough, FFT methods are computationally more efficient than spatial domain methods for detecting known blocks of functionally aligned amino acid sequences in a nucleic acid sequence. In a preferred embodiment, the test nucleic acid sequence can be any length between an EST and a chromosome. More specifically, the test nucleic acid sequence can have a length of from approximately 10 kilobases to approximately 100 kilobases.
Beattie Ingrid A.
Brusca John S.
Elrifi Ivor R.
Hoeschst-Ariad Genomics Center
Mintz Levin Cohn Ferris Glovsky & Popeo PC
LandOfFree
Profile searching in nucleic acid sequences using the fast... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Profile searching in nucleic acid sequences using the fast..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Profile searching in nucleic acid sequences using the fast... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2460158