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