CDSfold: an algorithm for designing a protein-coding sequence with the most stable secondary structure
Abstract
Motivation: An important problem in synthetic biology is to design a nucleotide sequence of an mRNA that confers a desirable expression level of a target protein. The secondary structure of protein-coding sequences (CDSs) is one potential factor that could have both positive and negative effects on protein production. To elucidate the role of secondary structure in CDSs, algorithms for manipulating secondary structure should be developed. Results: We developed an algorithm for designing a CDS with the most stable secondary structure among all possible ones translated into the same protein, and implemented it as the program CDSfold. The algorithm runs the Zuker algorithm under the constraint of a given amino acid sequence. The time and space complexity is O(L3) and O(L2), respectively, where L is the length of the CDS to be designed. Although our algorithm is slower than the original Zuker algorithm, it could design a relatively long (2.7-kb) CDS in approximately 1 h. Availability and implementation: The CDSfold program is freely available for non-commercial users as stand-alone and web-based software from http://cdsfold.trahed.jp/cdsfold/. Contacts: terai-goro@aist.go.jp or asai@k.u-tokyo.ac.jp Supplementary information: Supplementary data are available at Bioinformatics online.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Cohen et al. and CDSfold do not have any graph-theoretic or formal representation of the design space.
“By contrast, Cohen et al. and CDSfold extend the standard Zuker algorithm with the consideration of amino acid constraints, and they do not have any graph-theoretic or formal representation of the design space.”
From Algorithm for optimized mRNA design improves stability and immunogenicity (2023) · cites this paper as [23]
CDSfold uses simulated annealing to improve CAI by fine-tuning from the MFE solution, but this is a heuristic with no guarantees.
“CDSfold uses simulated annealing to improve CAI by fine-tuning from the MFE solution, but this is a heuristic with no guarantees.”
From Algorithm for optimized mRNA design improves stability and immunogenicity (2023) · cites this paper as [23]
The stability-only version of this work reduced the mRNA design problem to lattice parsing, resulting in a simpler and more efficient algorithm than previous specifically-designed algorithms.
“By contrast, the stability-only version of our work reduced the mRNA design problem to the classical computational linguistics problem of lattice parsing, resulting in a much simpler and more efficient algorithm that is vastly different from the specifically-designed algorithms such as the one described in Cohen et al.22 and CDSfold23.”
From Algorithm for optimized mRNA design improves stability and immunogenicity (2023) · cites this paper as [23]
Two previous studies also tackled optimal-stability mRNA design via dynamic programming, but their algorithms are complicated, not generalizable and less efficient.
“Two previous studies22,23 also tackled the problem of optimal-stability mRNA design (that is, our objective 1) via dynamic programming, but their algorithms are complicated, not generalizable and less efficient.”
From Algorithm for optimized mRNA design improves stability and immunogenicity (2023) · cites this paper as [23]
Cites
UniProt: a hub for protein information
The UniProt Consortium (2015) · Nucleic Acids Research · doi:10.1093/nar/gku989 · Cited by 5,106 · see citing works
Lorenz, R., Bernhart, S. H., Höner zu Siederdissen, C., Tafer, H., Flamm, C., Stadler, P. F., & Hofacker, I. L. (2011) · Algorithms for Molecular Biology · doi:10.1186/1748-7188-6-26 · Cited by 5,098 · see citing works
Sharp, P. M., & Li, W.-H. (1987) · Nucleic Acids Research · doi:10.1093/nar/15.3.1281 · Cited by 3,992 · see citing works
Mathews, D. H., Sabina, J., Zuker, M., & Turner, D. H. (1999) · Journal of Molecular Biology · doi:10.1006/jmbi.1999.2700 · Cited by 3,795 · see citing works
Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information
Zuker, M., & Stiegler, P. (1981) · Nucleic Acids Research · doi:10.1093/nar/9.1.133 · Cited by 3,604 · see citing works
Biological sequence analysis probabilistic models of proteins and nucleic acids
Durbin, R. M., Eddy, S. R., Krogh, A., & Mitchison, G. (1998) · Cited by 3,565 · see citing works
Durbin, R. M., Eddy, S. R., Krogh, A., & Mitchison, G. (1998) · Cambridge University Press eBooks · doi:10.1017/cbo9780511790492 · Cited by 3,255 · see citing works
Automated design of synthetic ribosome binding sites to control protein expression
Salis, H. M., Mirsky, E. A., & Voigt, C. A. (2009) · Nature Biotechnology · doi:10.1038/nbt.1568 · Cited by 1,844 · see citing works
Synonymous but not the same: the causes and consequences of codon bias
Plotkin, J. B., & Kudla, G. (2010) · Nature Reviews Genetics · doi:10.1038/nrg2899 · Cited by 1,677 · see citing works
Dissecting the regulatory circuitry of a eukaryotic genome
Holstege, F. C. P., Jennings, E. G., Wyrick, J. J., Lee, T. I., Hengartner, C. J., Green, M. R., Golub, T. R., Lander, E. S., & Young, R. A. (1998) · Cell · doi:10.1016/s0092-8674(00)81641-4 · Cited by 1,670 · see citing works
Coding-Sequence Determinants of Gene Expression in <i>Escherichia coli</i>
Kudla, G., Murray, A. W., Tollervey, D., & Plotkin, J. B. (2009) · Science · doi:10.1126/science.1170160 · Cited by 1,458 · see citing works
Untranslated regions of mRNAs.
(2002) · Genome biology · doi:10.1186/gb-2002-3-3-reviews0004 · Cited by 987 · see citing works
Genome-wide measurement of RNA secondary structure in yeast
Kertesz, M., Wan, Y., Mazor, E., Rinn, J. L., Nutter, R. C., Chang, H. Y., & Segal, E. (2010) · Nature · doi:10.1038/nature09322 · Cited by 765 · see citing works
Effects of rare codon clusters on high-level expression of heterologous proteins in Escherichia coli
Kane, J. F. (1995) · Current Opinion in Biotechnology · doi:10.1016/0958-1669(95)80082-4 · Cited by 759 · see citing works
Nussinov, R., Pieczenik, G., Griggs, J. R., & Kleitman, D. J. (1978) · SIAM Journal on Applied Mathematics · doi:10.1137/0135006 · Cited by 587 · see citing works
Landscape and variation of RNA secondary structure across the human transcriptome
Wan, Y., Qu, K., Zhang, Q. C., Flynn, R. A., Manor, O., Ouyang, Z., Zhang, J., Spitale, R. C., Snyder, M. P., Segal, E., et al. (2014) · Nature · doi:10.1038/nature12946 · Cited by 555 · see citing works
Kozak, M. (1984) · Nature · doi:10.1038/308241a0 · Cited by 538 · see citing works
Krämer, G., Boehringer, D., Ban, N., & Bukau, B. (2009) · Nature Structural & Molecular Biology · doi:10.1038/nsmb.1614 · Cited by 478 · see citing works
Gu, W., Zhou, T., & Wilke, C. O. (2010) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1000664 · Cited by 313 · see citing works
Deciphering the rules by which 5′-UTR sequences affect protein expression in yeast
Dvir, S., Velten, L., Sharon, E., Zeevi, D., Carey, L. B., Weinberger, A., & Segal, E. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1222534110 · Cited by 246 · see citing works
Raab, D., Graf, M., Notka, F., Schödl, T., & Wagner, R. (2010) · Systems and Synthetic Biology · doi:10.1007/s11693-010-9062-3 · Cited by 215 · see citing works
Chin, J. X., Chung, B. K.-S., & Lee, D. (2014) · Bioinformatics · doi:10.1093/bioinformatics/btu192 · Cited by 142 · see citing works
Laso, M. R. V., Zhu, D., Sagliocco, F. A., et al. (1993) · Journal of Biological Chemistry · doi:10.1016/s0021-9258(18)53273-7 · Cited by 134 · see citing works
Park, C., Chen, X., Yang, J., & Zhang, J. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1218066110 · Cited by 113 · see citing works
Strong association between mRNA folding strength and protein abundance in S. cerevisiae
Zur, H., & Tuller, T. (2012) · EMBO Reports · doi:10.1038/embor.2011.262 · Cited by 95 · see citing works
Computational codon optimization of synthetic gene for protein expression
Chung, B. K.-S., & Lee, D. (2012) · BMC Systems Biology · doi:10.1186/1752-0509-6-134 · Cited by 93 · see citing works
mRNA secondary structure optimization using a correlated stem–loop prediction
Gaspar, P., Moura, G., Santos, M. A. S., & Oliveira, J. L. (2013) · Nucleic Acids Research · doi:10.1093/nar/gks1473 · Cited by 89 · see citing works
EuGene: maximizing synthetic gene design for heterologous expression
Gaspar, P., Oliveira, J. L., Frommlet, J. C., Santos, M. A. S., & Moura, G. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts465 · Cited by 72 · see citing works
The mRNA landscape at yeast translation initiation sites
Robbins-Pianka, A., Rice, M. D., & Weir, M. P. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq509 · Cited by 39 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Algorithm for optimized mRNA design improves stability and immunogenicity
Zhang, H., Zhang, L., Lin, A., Xu, C., Li, Z., Liu, K., Liu, B., Ma, X., Zhao, F., Jiang, H., et al. (2023) · Nature · doi:10.1038/s41586-023-06127-z · Cited by 498 · see citing works
Combinatorial optimization of mRNA structure, stability, and translation for RNA-based therapeutics
Leppek, K., Byeon, G. W., Kladwang, W., Wayment-Steele, H. K., Kerr, C. H., Xu, A. F., Kim, D. S., Topkar, V. V., Choe, C., Rothschild, D., et al. (2022) · Nature Communications · doi:10.1038/s41467-022-28776-w · Cited by 399 · see citing works
Combinatorial optimization of mRNA structure, stability, and translation for RNA-based therapeutics
Leppek, K., Byeon, G. W., Kladwang, W., Wayment-Steele, H. K., Kerr, C. H., Xu, A. F., Kim, D. S., Topkar, V. V., Choe, C., Rothschild, D., et al. (2021) · doi:10.1101/2021.03.29.437587 · Cited by 399 · see citing works
Theoretical basis for stabilizing messenger RNA through secondary structure design
Wayment-Steele, H. K., Kim, D. S., Choe, C. A., Nicol, J. J., Wellington-Oguri, R., Watkins, A. M., Parra Sperberg, R. A., Huang, P.-S., Participants, E., & Das, R. (2021) · Nucleic Acids Research · doi:10.1093/nar/gkab764 · Cited by 197 · see citing works
- Authors
- Terai, G., Kamegai, S., & Asai, K.
- Affiliations
- Intec Inc. (Japan) (JP)
- National Institute of Advanced Industrial Science and Technology (JP)
- Corresponding author
- Terai, Goro
- Asai, Kiyoshi
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2015-11-20
- Volume
- 32
- Issue
- 6
- Pages
- 828-834
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2179601024
- Cited by
- 36
- References
- 29
- Citations by year
- 2026: 11 · 2025: 10 · 2024: 6 · 2023: 2 · 2022: 2 · 2021: 2 · 2020: 1 · 2019: 1 · 2016: 1
- FWCI
- 0.14
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Bioinformatics (publishedVersion)
- PubMed (publishedVersion)
- HighWire Press Open Archive (submittedVersion)
- Funders
- National Institute of Advanced Industrial Science and Technology
- Vedecká Grantová Agentúra MŠVVaŠ SR a SAV
- Topics
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › RNA and protein synthesis mechanisms
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Protein Structure and Dynamics
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › RNA Research and Splicing
- Keywords
- mRNA secondary structure, protein expression, synthetic biology, web application
- MeSH terms
- Algorithms, Amino Acid Sequence, Base Sequence, Software, Open Reading Frames, Sequence Alignment, Protein Structure, Secondary
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
