Efficient computation of distance incorporated codon autocorrelation (DICA) score using fast Fourier transform

The availability of synonymous codons (codons that can translate the same amino acid into protein) enables a protein to be encoded by many different sequences of codons/tRNAs. Autocorrelation measures the reuse of a particular codon/tRNA in succession (instead of choosing a different synonymous one) during the translation of a protein sequence. Studies show that tRNA autocorrelation in a coding sequence has important effects on its translation speed. Two different metrics available in literature to measure autocorrelation are: TPI (tRNA pairing index) and DICA (Distance Incorporated Codon Autocorrelation). TPI measures autocorrelation in sequences by counting successive transitions of tRNA usage, without considering how far apart they are in the sequence, whereas DICA measures autocorrelation by weighing the positional distance between codons in addition to the number of transitions. It has been shown that DICA correlates better to gene expression speed than TPI due to its incorporation of distance in the measure. The naïve algorithm to compute DICA score takes time quadratic in the sequence length n which can be very expensive for long amino acid sequences. This motivates us to propose a faster algorithm for computing DICA. In this paper we show how to transform the problem of computing DICA score of a given sequence of tRNAs to a polynomial multiplication problem, which can then be solved in O(n log n) time using Fast Fourier Transform (FFT). The asymptotic reduction of complexity can improve performance of DICA computation significantly, especially for long sequences. Copyright is held by the author/owner(s).