.png){kind=icon}
Return
A Sparse Dynamic Programming Algorithm for Solving the Coding Sequence Design Problem
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-0218-9_24.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this work, we study the coding sequence design problem, which involves designing a coding sequence to encode a given amino acid sequence by optimizing both its secondary structure stability and codon usage. The structural stability and codon usage are quantified by minimum free energy and codon adaptation index, respectively. The coding sequence design problem is important since it has significant potential for the development of mRNA-based vaccines. Previously, we proposed an O(L-3) time and O(L-2) space dynamic programming algorithm to solve the coding sequencing design problem, where L is the length of the coding sequence to be designed. In this study, we utilize the sparsification technique to further reduce the time complexity of this dynamic programming algorithm from O(L-3) to O(L-2 + ZP) for the problem under the base pair-based energy model, where Z and P are two sparsity parameters satisfying Z <= L(6 + P) and P <= 36L.
Keywords:
computational biology
sparsification
dynamic programming
coding sequence design
Journal
C
IF:
0
Papers:
24
Citations:
0
Organization
Cited Papers
No cited papers available