Fast approximate computation of non-uniform DFTs for biological sequence analysis

摘要: Periodicity is emerging as a useful method for characterising the structure within biological sequences such DNA. For sequence data, integer periods are usually of most interest, which poses problem fast computation if conventional Fourier-based analyses applied. An existing complex polynomial re-evaluation algorithm adapted, and approximation rule applicable to any discrete Fourier transform-based analysis proposed, where frequencies be evaluated not uniformly spaced. Experiments evaluating binary signals on an integer-period frequency scale show that magnitude spectrum approximations differing from exact by less than 1-3- can obtained with reduction in complexity 3-10 times.