.png){kind=icon}
Return
A More Efficient Dynamic Programming Algorithm for Designing a Coding Sequence by Jointly Optimizing Its Structural Stability and Codon Usage
.png){kind=icon}
PRE
AI
DOI：10.1109/TCBBIO.2025.3596771.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 O(L-3) time and 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 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 O(L-3) time and 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.
Keywords:
Codons
Heuristic algorithms
Amino acids
Dynamic programming
Stability criteria
Approximation algorithms
Encoding
Indexes
Complexity theory
Protein sequence
Dynamic programming (DP) algorithm
CDS design
secondary structure
MFE
codon usage
CAI
Journal
I
IF:
0
Papers:
151
Citations:
0
Organization
Cited Papers
ShareSaveShareSaveShareSaveShareSaveCodon usage tabulated from international DNA sequence databases: status for the year 2000.png)
NUCLEIC ACIDS RESEARCH
OAAI
NUCLEIC ACIDS RESEARCHIF13.1
OAAIShareSave
ShareSaveShareSave
View more