Benson D C
Department of Mathematics, University of California, Davis 95616.
Nucleic Acids Res. 1990 May 25;18(10):3001-6. doi: 10.1093/nar/18.10.3001.
A method is discussed for DNA or protein sequence comparison using a finite field fast Fourier transform, a digital signal processing technique; and statistical methods are discussed for analyzing the output of this algorithm. This method compares two sequences of length N in computing time proportional to N log N compared to N2 for methods currently used. This method makes it feasible to compare very long sequences. An example is given to show that the method correctly identifies sites of known homology.
本文讨论了一种使用有限域快速傅里叶变换（一种数字信号处理技术）进行DNA或蛋白质序列比较的方法；并讨论了用于分析该算法输出的统计方法。与目前使用的方法相比，该方法在计算时间与N log N成正比的情况下比较两个长度为N的序列，而目前使用的方法计算时间与N2成正比。该方法使得比较非常长的序列成为可能。给出了一个例子来说明该方法能正确识别已知同源性的位点。
