1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\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$
    – Marcus Müller
    Nov 26, 2020 at 21:46
  • 1
    $\begingroup$ You can get a code at https://github.com/cyinbox/GenomeDFT $\endgroup$
    – Laurent Duval
    Nov 27, 2020 at 10:43

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\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, 2020 at 17:10
  • 1
    $\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, 2020 at 17:16
  • 1
    $\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, 2020 at 17:17
  • 1
    $\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$
    – Laurent Duval
    Nov 28, 2020 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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