A sparse dynamic programming algorithm for solving the coding sequence design problem

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 sequence 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 + Z P ) 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 ≤ 36 L. Experimental results on a biological dataset show that our sparse dynamic programming algorithm achieves a 35-fold to 49-fold speedup over its non-sparse counterpart.

Authors

• Long-Shang Cho
• Kai-Wei Chang
• Chin Lung Lu

Keywords

• Computational biology
• Sparsification
• Dynamic programming
• Coding sequence design