I am wondering how and if it is possible to define a Fourier transform or Wavelet transform on DNA sequences which are basically arrays with the values $\{T,C,G,A\}$ in them.

I have found a paper which uses a "Voss 4D binary indicator representation":

Yin, C., Chen, Y. and Yau, S.S.T., 2014. A measure of DNA sequence similarity by Fourier Transform with applications on hierarchical clustering. Journal of theoretical biology, 359, pp.18-28.

Their code is supposed to be available online FFTDNA4D.m, but the link is broken.

The general idea is to define an indicator mapping per nucleotide type ($\alpha \in \{T,C,G,A\}$) for the DNA sequence $s(0), s(1), \dots, s(N-1)$

$$ \begin{equation} u_{\alpha}(n)=\begin{cases} 1, & \text{if $s(n)=\alpha$}\\ 0, & \text{otherwise} \end{cases} \end{equation} $$

Then the DFT is given by:

$$ U_x(k) = \sum_{n=0}^{N-1} u_x(n) e^{-2\pi i \frac{kn}{N}} $$

the power spectrum is then given by:

$$ \Phi(k) = \sum_{x\in \{ A, T, G, C\}} |U_x(k)|^2 \quad k = 0,1, \dots, N-1 $$

Is there a better way to do it? This method masks out the differences between the different types of DNA bases.

  • $\begingroup$ huh, I'd say to be overly sensible, you'd want your input and result spaces (here: vectors from {T,C,G,A}) to at least be a vector spaces, otherwise you'll miss the operations necessary to define a (discrete) integral transform... and I don't think saying "(T, A, C)+0.5·(A, C, C ) = (C,G, T)" (or some other element from the vector space) makes sense, since you can't meaningfully scale and add gene sequences as far as I know. But maybe we should approach this the other way around: what is it that you hope to gain from this? I bet there's a mathematical method close to what you want to do. $\endgroup$ Nov 26 '20 at 21:46
  • $\begingroup$ You can get a code at https://github.com/cyinbox/GenomeDFT $\endgroup$ Nov 27 '20 at 10:43

First, a code for paper A measure of DNA sequence similarity by Fourier Transform with applications on hierarchical clustering. Journal of theoretical biology is available at GenomeDFT (github).

Then, on the transforms. Discrete Fourier transforms can be defined on other domains than vector spaces. There are Fourier transforms on groups, rings or finite fields. On the latter, it is commonly called a number-theoretic transform (NTT). This possibility entails to making sense of group/ring/field axioms for the nucleotides. For instance, it should be possible to use a finite field of characteristic four. Apparently weird mathematical structures could be interesting when considering (C,G) or (A,T) patterns, or the redundancy in the codon/amino-acid correspondence.

Some papers mention the Ramanujan-Fourier transform (A Novel Method for Comparative Analysis of DNA Sequences by Ramanujan-Fourier Transform, apparently with the same first author of the paper you mentioned). With less structured transformations, it is also possible to evaluate periodicity, as for instance in Categorical spectral analysis of periodicity in nucleosomal DNA.

There also were some works on wavelets, either continuous or discrete. On the first flavor, by A. Arneodo and colleagues, and more recently in 2019 with Wavelet-Based Genomic Signal Processing for Centromere Identification and Hypothesis Generation. With discrete wavelet transform, there is for instance Identification of exonic regions in DNA sequences using cross-correlation and noise suppression by discrete wavelet transform, Application of discrete wavelet transform for analysis of genomic sequences of Mycobacterium tuberculosis, Wavelet analysis of DNA sequences.

Finally, on the mappings. There is for instance Digital signal processing methods for biosequence comparison, 1991 or Mapping Equivalence for Symbolic Sequences: Theory and Applications, 2009.

As asked by Marcus, your actual purpose might direct you to an appropriate combination.

  • $\begingroup$ You don't need to summon number theoretic transforms for this. In fact, it wouldn't even work because they transform maps from the group to a field (usually $\mathbb{C}$) to maps from representations of the group to the same field. In this case, however, we would like to have a map from $\mathbb{Z}$ to a field transformed. But you could use the finite field of order 4 as the target field and be set. This would however be not very meaningful, as the linear structure of the field does not translate to any meaningful structure of the set of bases. $\endgroup$
    – Jazzmaniac
    Nov 27 '20 at 17:10
  • $\begingroup$ In other words, the result would depend on the arbitrary choice of the map from {0,1,2,3} to {T,C,G,A}. And neither of those maps would induce any meaningful interpretation of the resulting Fourier coefficients. What would be meaningful is to look at the Fourier transform of a vector valued function on $\mathbb{Z}_2$, where a vector entry comes from the index function of the occurence of a finite base-sequence. I.e. the first component would contain the index function of (T), then (C), (G) and (A), followed by all sequences of order 2, namely (T,T), (T,C),(T,G),(T,A),(C,T),(C,C),(C,G),(C,A),.. $\endgroup$
    – Jazzmaniac
    Nov 27 '20 at 17:16
  • $\begingroup$ You can extend this scheme to any sensible finite sequence order. The corresponding vector-Fourier transform is then easy to interpret and the arbitrary choice of the base order is just a permutation on both the input and output vectors without any structural change of the result. $\endgroup$
    – Jazzmaniac
    Nov 27 '20 at 17:17
  • $\begingroup$ I don't claim finite fields SHOULD be summoned. Meanwhile, I started from Fourier extensions outside vector spaces. Then, due to interplay between the four bases (A-T and C-G), and redundancy in the codons, there might be useful to enforce some structure. I have briefly seen works on DNA-computing that use field axioms $\endgroup$ Nov 28 '20 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.