COStar: A D-star Lite-based dynamic search algorithm for codon optimization

• Introduce a new codon optimization software COStar.
• Dynamic search algorithm to inhibit global repetitive sequences.
• Convert the codon optimization problem into a directed acyclic graph.
• Formulate and optimize five widely used DNA sequence properties.
• Performance of COStar is more competitive than the existing optimization tools.

Codon optimized genes have two major advantages: they simplify de novo gene synthesis and increase the expression level in target hosts. Often they achieve this by altering codon usage in a given gene. Codon optimization is complex because it usually needs to achieve multiple opposing goals. In practice, finding an optimal sequence from the massive number of possible combinations of synonymous codons that can code for the same amino acid sequence is a challenging task. In this article, we introduce COStar, a D-star Lite-based dynamic search algorithm for codon optimization. The algorithm first maps the codon optimization problem into a weighted directed acyclic graph using a sliding window approach. Then, the D-star Lite algorithm is used to compute the shortest path from the start site to the target site in the resulting graph. Optimizing a gene is thus converted to a search in real-time for a shortest path in a generated graph. Using in silico experiments, the performance of the algorithm was shown by optimizing the different genes including the human genome. The results suggest that COStar is a promising codon optimization tool for de novo gene synthesis and heterologous gene expression.