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

Area of Science:

• Computational Biology
• Bioinformatics
• Synthetic Biology

Background:

• Existing dynamic programming algorithms like CDSfold focus on minimizing minimum free energy (MFE) for coding sequence (CDS) design.
• Modifying these algorithms to jointly optimize secondary structure stability and codon adaptation index (CAI) has been challenging.

Purpose of the Study:

• To modify the CDSfold dynamic programming algorithm for the joint optimization of CDS secondary structure stability and CAI.
• To develop an efficient computational tool for high-quality CDS design.

Main Methods:

• Modified a dynamic programming algorithm to exactly solve the joint CDS design problem in O(L^3) time and O(L^2) space.
• Accelerated the algorithm using beam search for approximate CDS design in O(L) time, implemented as LinearCDSfold.
• Compared LinearCDSfold's performance against state-of-the-art tools LinearDesign and DERNA.

Main Results:

• LinearCDSfold achieves comparable accuracy to LinearDesign and DERNA in terms of MFE and CAI when using exact search.
• LinearCDSfold demonstrates significantly faster runtime than DERNA, despite similar theoretical complexity.
• Beam search in LinearCDSfold enables rapid design of high-quality approximate CDS with excellent MFE and CAI.

Conclusions:

• The modified DP algorithm successfully addresses the challenge of jointly optimizing CDS secondary structure stability and CAI.
• LinearCDSfold provides an accurate and efficient tool for CDS design, with a fast approximate design option.
• This work advances computational methods for synthetic biology and genetic engineering.