A More Efficient Dynamic Programming Algorithm for Designing a Coding Sequence by Jointly Optimizing Its Structural...

Currently, a dynamic programming (DP) algorithm CDSfold has been proposed to design a CDS by minimizing the minimum free energy (MFE) of its secondary structure. However, it has been questioned recently that such a DP algorithm is difficult to be modified to design a CDS when attempting to jointly optimize its secondary structure stability and codon adaptation index (CAI). In this study, we successfully modify the DP algorithm of CDSfold to exactly solve this kind of CDS design problem in $\mathcal {O}(L^{3})$ time and $\mathcal {O}(L^{2})$ space, where $L$ is the CDS length. We further accelerate this DP algorithm by beam search, enabling it to design a high-quality approximate CDS in $\mathcal {O}(L)$ time, and implement it as the program LinearCDSfold. Our experimental results show that when running with exact search, LinearCDSfold has comparable accuracy to two state-of-the-art CDS design tools LinearDesign and DERNA in terms of both MFE and CAI. In terms of running time, however, LinearCDSfold is slower than LinearDesign, but significantly faster than DERNA, even though they all run in $\mathcal {O}(L^{3})$ time and $\mathcal {O}(L^{2})$ space. Moreover, LinearCDSfold using beam search can design an approximate CDS in very short time with very high quality in terms of both MFE and CAI.