DNA Encoding Optimisation Based on Thermodynamics

Abstract

Due to their exceptional programmability, DNA molecules are widely employed in the design of molecular circuits for appli-cations such as DNA computing, DNA storage and cancer diagnosis and treatment. The quality of DNA sequences directly determines the reliability of these molecular circuits. However, existing DNA encoding algorithms suffer from limitations such as reliance on Hamming distance and confiicts among multiple objectives, resulting in insufficient stability of the generated sequences. To address these issues, this paper proposes a thermodynamics-based multi-objective evolutionary optimisation algorithm (TEMOA). The core innovations of the proposed algorithm are as follows: First, a thermodynamics-based DNA encoding modelling strategy (TDEMS) is introduced, which simplifies the encoding process and significantly improves the sequence quality by incorporating thermodynamic stability constraints. Second, two diversity optimisation strategies—the di-versity assessment strategy (DAS) and the front equalisation nondominated sorting (FENS) strategy—are designed to enhance the algorithm's global search capability. Finally, a fiexible fitness function design is incorporated to accommodate diverse user requirements. Experimental results demonstrate that TEMOA is more effective than state-of-the-art methods on challenging multi-objective optimisation problems, whereas the DNA sequences generated by TEMOA exhibit greater reliability compared to those produced by traditional DNA encoding algorithms.

Keywords

biology computing / genetic algorithms / minimisation

References

[1] J. D. Watson and F. H. Crick, “Molecular Structure of Nucleic Acids: A Structure for Deoxyribose Nucleic Acid,” Nature 171, no. 4356 (1953): 737-738, https://doi.org/10.1038/171737a0.

[2] C. Zhang, X. Ma, X. Zheng, et al., “Programmable Allosteric DNA Regulations for Molecular Networks and Nanomachines,” Science Ad-vances 8, no. 5 (2022): eabl4589, https://doi.org/10.1126/sciadv.abl4589.

[3] H. Lv, N. Xie, M. Li, et al., “DNA-Based Programmable Gate Arrays for General-Purpose DNA Computing,” Nature 622, no. 7982 (2023):292-300, https://doi.org/10.1038/s41586-023-06484-9.

[4] E. Winfree, F. Liu, L. A. Wenzler, and N. C. Seeman, “Design and Self-Assembly of Two-Dimensional DNA Crystals,” Nature 394, no. 6693 (1998): 539-544, https://doi.org/10.1038/28998.

[5] A. J. Bogdanove and D. F. Voytas, “TAL Effectors: Customizable Proteins for DNA Targeting,” Science. 333, no. 6051 (2011): 1843-1846, https://doi.org/10.1126/science.1204094.

[6] Q. Liu, L. Wang, A. G. Frutos, A. E. Condon, R. M. Corn, and L. M. Smith, “DNA Computing on Surfaces ” Nature 403, no. 6766 (2000): 175-179, https://doi.org/10.1038/35003155.

[7] M. Ogihara and A. Ray, “DNA Computing on a Chip,” Nature 403, no. 6766 (2000): 143-144, https://doi.org/10.1038/35003071.

[8] G. M. Church,Y. Gao, and S. Kosuri, “Next-Generation Digital In-formation Storage in DNA,” Science. 337, no. 6102 (2012): 1628, https://doi.org/10.1126/science.1226355.

[9] N. Goldman, P. Bertone, S. Chen, et al., “Towards Practical, High-Capacity, Low-Maintenance Information Storage in Synthesized DNA,” Nature 494, no. 7435 (2013): 77-80, https://doi.org/10.1038/nature11875.

[10] L. H. Hurley, “DNA and Its Associated Processes as Targets for Cancer Therapy,” Nature Reviews Cancer 2, no. 3 (2002): 188-200, https://doi.org/10.1038/nrc749.

[11] T. Helleday, E. Petermann, C. Lundin, B. Hodgson, and R. A. Sharma, “DNA Repair Pathways as Targets for Cancer Therapy,” Nature Reviews Cancer 8, no. 3 (2008): 193-204, https://doi.org/10.1038/nrc2342.

[12] V. Luncasu and M. Raschip, “A Graph-Based Approach for the DNA Word Design Problem,” IEEE/ACM Transactions on Computational Biology and Bioinformatics 18, no. 6 (2020): 2747-2752, https://doi.org/10.1109/tcbb.2020.3008346.

[13] F. Piva and G. Principato, “RANDNA: A Random DNA Sequence Generator,” In Silico Biology 6, no. 3 (2006): 253-258, https://doi.org/10.3233/isb-00239.

[14] M. Arita, A. Nishikawa, M. Hagiya, K. Komiya, H. Gouzu and K. Sakamoto, “Improving Sequence Design for DNA Computing,” in Pro-ceedings of the 2nd Annual Conference on Genetic and Evolutionary Computation (Morgan Kaufmann, 2000), 875-882, https://dl.acm.org/doi/abs/10.5555/2933718.2933883.

[15] E. B. Baum, “DNA Sequences Useful for Computation,” in DIMACS Series in Discrete Mathematics and Theoretical Computer Science (1996), 235-241, https://doi.org/10.1090/dimacs/044/18.

[16] J. Xu, W. Liu, K. Zhang and E. Zhu, “DNA Coding Theory and Algorithms,” Artificial Intelligence Review 58, no. 6 (2025): 178, https://doi.org/10.1007/s10462-025-11132-x.

[17] M. Gong, S. Wang, W. Liu, J. Yan, and L. Jiao, “Evolutionary Computation in China: A Literature Survey,” CAAI Transactions on Intelligence Technology 1, no. 4 (2016): 334-354, https://doi.org/10.1016/j.trit.2016.11.002.

[18] Q. Fan, M. Jiang, W. Huang, and Q. Jiang, “Considering Spatio-temporal Evolutionary Information in Dynamic Multi-Objective Opti-misation,” CAAI Transactions on Intelligence Technology (2023): cit2.12249, https://doi.org/10.1049/cit2.12249.

[19] N. Mashru, G. G. Tejani, P. Patel, and M. Khishe, “Optimal Truss Design With MOHO: A Multi-Objective Optimization Perspective,” PLoS One 19, no. 8 (2024): e0308474, https://doi.org/10.1371/journal.pone.0308474.

[20] S. Kumar, G. G. Tejani, P. Mehta, S. M. Sait, A. R. Yildiz, and S. Mirjalili, “Optimization of Truss Structures Using Multi-Objective Cheetah Optimizer,” Mechanics Based Design of Structures and Ma-chines 53, no. 2 (2025): 1494-1515, https://doi.org/10.1080/15397734.2024.2389109.

[21] P. Mehta,S. Kumar, and G. G. Tejani, “MOBBO: A Multiobjective Brown Bear Optimization Algorithm for Solving Constrained Structural Optimization Problems,” Journal of Optimization 2024, no. 1 (2024):5546940, https://doi.org/10.1155/2024/5546940.

[22] S. Kumar, N. Panagant, G. G. Tejani, et al., “A Two-Archive Multi-Objective Multi-Verse Optimizer for Truss Design,” Knowledge-Based Systems 270 (2023): 110529, https://doi.org/10.1016/j.knosys.2023.11.0529

[23] S. Kumar, G. G. Tejani, N. Pholdee, and S. Bureerat, “Multiobjecitve Structural Optimization Using Improved Heat Transfer Search,” Knowledge-Based Systems 219 (2021): 106811, https://doi.org/10.1016/j.knosys.2021.106811.

[24] S. Kumar, P. Jangir, G. G. Tejani, and M. Premkumar, “A Decom-position Based Multi-Objective Heat Transfer Search Algorithm for Structure Optimization,” Knowledge-Based Systems 253 (2022): 109591, https://doi.org/10.1016/j.knosys.2022.109591.

[25] S. Kumar, G. G. Tejani, N. Pholdee, S. Bureerat, and P. Mehta, “Hybrid Heat Transfer Search and Passing Vehicle Search Optimizer for Multi-Objective Structural Optimization,” Knowledge-Based Systems 212 (2021): 106556, https://doi.org/10.1016/j.knosys.2020.106556.

[26] S. Y. Shin, I. H. Lee, D. Kim, and B. T. Zhang, “Multiobjective Evolutionary Optimization of DNA Sequences for Reliable DNA Computing,” IEEE Transactions on Evolutionary Computation 9, no. 2 (2005): 143-158, https://doi.org/10.1109/tevc.2005.844166.

[27] J. M. Chaves-González and M. A. Vega-Rodríguez, “A Multi-objective Approach Based on the Behavior of Firefiies to Generate Reliable DNA Sequences for Molecular Computing,” Applied Mathe-matics and Computation 227 (2014): 291-308, https://doi.org/10.1016/j.amc.2013.11.032.

[28] G. Yang, B. Wang, X. Zheng, C. Zhou, and Q. Zhang, “IWO Algo-rithm Based on Niche Crowding for DNA Sequence Design,” Interdis-ciplinary Sciences: Computational Life Sciences 9, no. 3 (2017): 341-349, https://doi.org/10.1007/s12539-016-0160-0.

[29] J. M. Chaves-González and J. Martínez-Gil, “An Efficient Design for a Multi-Objective Evolutionary Algorithm to Generate DNA Libraries Suitable for Computation,” Interdisciplinary Sciences: Computational Life Sciences 11, no. 3 (2019): 542-558, https://doi.org/10.1007/s12539-018-0303-6.

[30] L. Xie, S. Wang, D. Zhu, G. Hu, and C. Zhou, “DNA Sequence Optimization Design of Arithmetic Optimization Algorithm Based on Billiard Hitting Strategy,” Interdisciplinary Sciences: Computational Life Sciences 15, no. 2 (2023): 231-248, https://doi.org/10.1007/s12539-023-00559-x.

[31] X. Yang, D. Zhu, C. Yang, and C. Zhou, “H-ACO With Consecutive Bases Pairing Constraint for Designing DNA Sequences,” Interdisci-plinary Sciences: Computational Life Sciences 16, no. 3 (2024): 1-15, https://doi.org/10.1007/s12539-024-00614-1.

[32] X. Ji, M. Li, Z. Yue, H. Zhang, and Y. Wang, “Renewable Energy Consumption Strategies for Electric Vehicle Aggregators Based on a Two-Layer Game,” Energies 18, no. 1 (2024): 80, https://doi.org/10.3390/en18010080.

[33] M. E. C. Bento, “Design of a Wide-Area Power System Stabilizer to Tolerate Multiple Permanent Communication Failures,” Electricity 4, no. 2 (2023): 154-170, https://doi.org/10.3390/electricity4020010.

[34] M. H. Sulaiman, Z. Mustaffa, and M. I. M. Rashid, “An Application of Teaching-Learning-Based Optimization for Solving the Optimal Po-wer Flow Problem With Stochastic Wind and Solar Power Generators,” Results in Control and Optimization 10 (2023): 100187, https://doi.org/10.1016/j.rico.2022.100187.

[35] X. Li, Z. Zhang, Y. Jiang, et al., “Multi-Objective Operation Opti-mization of Park Microgrid Based on Green Power Trading Price Pre-diction in China,” Energies 18, no. 1 (2025): 46, https://doi.org/10.3390/en18010046.

[36] A. J. Hartemink, D. K. Gifford, and J. Khodor, “Automated Constraint-Based Nucleotide Sequence Selection for DNA Computa-tion,” Biosystems 52, no. 1 (1999): 227-235, https://doi.org/10.1016/s0303-2647(99)00050-7.

[37] R. Penchovsky and J. Ackermann, “DNA Library Design for Mo-lecular Computation,” Journal of Computational Biology 10, no. 2 (2003): 215-229, https://doi.org/10.1089/106652703321825973.

[38] A. Marathe, A. E. Condon, and R. M. Corn, “On Combinatorial DNA Word Design,” Journal of Computational Biology 8, no. 3 (2001): 201-219, https://doi.org/10.1089/10665270152530818.

[39] M. Arita and S. Kobayashi, “DNA Sequence Design Using Tem-plates,” New Generation Computing 20, no. 3 (2002): 263-277, https://doi.org/10.1007/bf03037360.

[40] U. Feldkamp, S. Saghafi, W. Banzhaf, and H. Rauhe, “DNASe-quenceGenerator: A Program for the Construction of DNA Sequences,” in International Workshop on DNA-Based Computers (Springer, 2002), 23-32, https://doi.org/10.1007/3-540-48017-X_3.

[41] F. Tanaka, M. Nakatsugawa, M. Yamamoto, T. Shiba, and A. Ohuchi1, “Developing Support System for Sequence Design in DNA Computing,” in International Workshop on DNA-Based Computers (Springer, 2002), 129-137, https://doi.org/10.1007/3-540-48017-X_12.

[42] J. Xiao, Y. Jiang, J. He, and Z. Cheng, “A Dynamic Membrane Evolutionary Algorithm for Solving DNA Sequences Design With Minimum Free Energy,” MATCH Communications in Mathematical and in Computer Chemistry 70, no. 3 (2013): 971-986, https://dl.acm.org/doi/abs/10.5555/2933718.2933883.

[43] R. M. Dirks, J. S. Bois, J. M. Schaeffer, E. Winfree, and N. A. Pierce, “Thermodynamic Analysis of Interacting Nucleic Acid Strands,” SIAM Review 49, no. 1 (2007): 65-88, https://doi.org/10.1137/060651100.

[44] M. E. Fornace, N. J. Porubsky, and N. A. Pierce, “A Unified Dy-namic Programming Framework for the Analysis of Interacting Nucleic Acid Strands: Enhanced Models, Scalability, and Speed,” ACS Synthetic Biology 9, no. 10 (2020): 2665-2678, https://doi.org/10.1021/acssynbio.9b00523.

[45] J. SantaLucia, H. T. Allawi, and P. A. Seneviratne, “Improved Nearest-Neighbor Parameters for Predicting DNA Duplex Stability,” Biochemistry 35, no. 11 (1996): 3555-3562, https://doi.org/10.1021/bi951907q.

[46] J. G. Wetmur, “DNA Probes: Applications of the Principles of Nucleic Acid Hybridization,” Critical Reviews in Biochemistry and Mo-lecular Biology 26, no. 3-4 (1991): 227-259, https://doi.org/10.3109/10409239109114069.

[47] Y. Tian, R. Cheng, X. Zhang, and Y. Jin, “PlatEMO: A MATLAB Platform for Evolutionary Multi-Objective Optimization [Educational Forum],” IEEE Computational Intelligence Magazine 12, no. 4 (2017):73-87, https://doi.org/10.1109/mci.2017.2742868.

[48] D. Zhu, Z. Huang, S. Liao, C. Zhou, S. Yan, and G. Chen, “Improved Bare Bones Particle Swarm Optimization for DNA Sequence Design,” IEEE Transactions on NanoBioscience 22, no. 3 (2022): 603-613, https://doi.org/10.1109/tnb.2022.3220795.

[49] J. N. Zadeh, C. D. Steenberg, J. S. Bois, et al., “NUPACK: Analysis and Design of Nucleic Acid Systems,” Journal of Computational Chemistry 32, no. 1 (2011): 170-173, https://doi.org/10.1002/jcc.21596.

[50] E. Zitzler, K. Deb, and L. Thiele, “Comparison of Multiobjective Evolutionary Algorithms: Empirical Results,” Evolutionary Computation 8, no. 2 (2000): 173-195, https://doi.org/10.1162/106365600568202.

[51] S. Huband, P. Hingston, L. Barone, and L. While, “A Review of Multiobjective Test Problems and a Scalable Test Problem Toolkit,” IEEE Transactions on Evolutionary Computation 10, no. 5 (2006): 477-506, https://doi.org/10.1109/tevc.2005.861417.

[52] K. Li, A. Fialho, S. Kwong, and Q. Zhang, “Adaptive Operator Se-lection With Bandits for a Multiobjective Evolutionary Algorithm Based on Decomposition,” IEEE Transactions on Evolutionary Computation 18, no. 1 (2013): 114-130, https://doi.org/10.1109/tevc.2013.2239648.

[53] R. Cheng, Y. Jin, K. Narukawa, and B. Sendhoff, “A Multiobjective Evolutionary Algorithm Using Gaussian Process-Based Inverse Modeling,” IEEE Transactions on Evolutionary Computation 19, no. 6 (2015): 838-856, https://doi.org/10.1109/tevc.2015.2395073.

[54] H. Zhang, A. Zhou, S. Song, Q. Zhang, X. Z. Gao, and J. Zhang, “A Self-Organizing Multiobjective Evolutionary Algorithm,” IEEE Trans-actions on Evolutionary Computation 20, no. 5 (2016): 792-806, https://doi.org/10.1109/tevc.2016.2521868.

[55] L. Sun and K. Li, “Adaptive Operator Selection Based on Dynamic Thompson Sampling for MOEA/D,” in International Conference on Parallel Problem Solving from Nature (Springer, 2020), 271-284, https://doi.org/10.1007/978-3-030-58115-2_19.

[56] Y. Tian, X. Li, H. Ma, X. Zhang, K. C. Tan, and Y. Jin, “Deep Reinforcement Learning Based Adaptive Operator Selection for Evolu-tionary Multi-Objective Optimization,” IEEE Transactions on Emerging Topics in Computational Intelligence 7, no. 4 (2022): 1051-1064, https://doi.org/10.1109/tetci.2022.3146882.

Funding

National Major Scientific Instrument and Equipment Development Project of National Natural Science Foundation of China(62427811)

National Major Scientific Instrument and Equipment Development Project of National Natural Science Foundation of China(62272115)