Periodicity measurement using cost-effective multirate DSP models of discrete Fourier and trigonometric transforms

The detection of different forms of periodicities in symbolic sequences and specifically in DNA sequences has been an active area of research in recent years. Hidden periodicity components can be used to locate pattern repetitions, motifs, coding regions, and to characterize other important biological features. Several digital signal processing (DSP) methods were introduced for this purpose. After mapping the symbolic DNA sequence into numeric sequence(s), spectral analysis tools such as the short-time discrete Fourier transform (ST-DFT) can be applied to locate these components. In this work, novel multirate DSP models to decompose the ST-DFT are introduced and shown to result in better periodicity measurement performance. One key application of DNA periodicity finding has been in the identification of the protein coding regions in DNA sequences by tracking the so-called period-3 component using the DNA spectrum. The proposed analysis explains the underlying mechanism of the period-3 component, completely characterizes the DNA spectrum and phase by a set of numerical sequences termed the filtered polyphase sequences, and shows how digital filters can substantially enhance the detection of this periodicity component. Moreover, we provide generalized models to incorporate the detection of a general period-R component, using the ST-DFT and general discrete transformations such as the short-time discrete cosine transform (ST-DCT), sine transform (ST-DST), and Hartley transform (ST-DHT). Next, a matrix-based analytical approach for the computation of the 2 DNA spectrum is derived. This approach (i) is invariant to the symbolic-to-numeric mapping used; (ii) provides a simple definition of the DNA spectrum in terms of interleaved versions of the mapped numeric windows and a constant generally-complex matrix; (iii) relates a number of popular mappings and proves that they share the same normalized DNA spectrum; (vi) provides easy ways to incorporate digital filters and/or alternative discrete trigonometric transforms for better detection performance; and (v) is very efficient computationally for processing long DNA sequences, since it can be completely constructed using real arithmetic. Finally, we show how some of the previous ideas can be extended to the problems of CpG islands identification in DNA sequences, and PAPR reduction in OFDM communication systems.