Skip to content
2000
image of An Optimization Scheme Based on the Simulated Annealing Algorithm for In situ DNA Microarray Synthesis

Abstract

Introduction

DNA microarray synthesis enables the large-scale and precise generation of DNA sequences for genomic research, data storage, and synthetic biology. However, the order of nucleotide addition significantly affects synthesis efficiency and accuracy. This study aims to model DNA microarray synthesis as a traveling salesman problem (TSP) and to develop an optimized synthesis strategy.

Methods

A mathematical model for microarray synthesis was established, and both greedy algorithms and a simulated annealing algorithm were applied to optimize the nucleotide addition order. The performance of these approaches was evaluated by comparing the number of synthesis cycles required at different sequence scales, ranging from 10 × 10 nt to 10000 × 120 nt arrays.

Results

The optimized synthesis schemes effectively reduced the total number of synthesis cycles. At the 10 × 10 nt scale, simulated annealing reduced cycles by 40.65% compared to the traditional scheme and by 8.52% compared to the greedy algorithm. At larger scales (100 × 100 nt to 10000 × 120 nt), cycle reductions ranged from 33.80% to 37.26%, with simulated annealing outperforming the greedy algorithm by 2.68% to 3.42%. These reductions translated into significant savings in synthesis time, reagent consumption, and overall cost.

Discussion

The simulated annealing–based optimization strategy demonstrates clear advantages in improving DNA microarray synthesis efficiency while reducing material usage and waste, thereby enhancing cost-effectiveness. Such improvements offer practical benefits for applications, including gene editing, drug development, and DNA data storage.

© 2026 Bentham Science Publishers
Loading

Article metrics loading...

/content/journals/cchts/10.2174/0113862073402626251112103715
2026-01-21
2026-01-30

  • From This Site

    /content/journals/cchts/10.2174/0113862073402626251112103715
    dcterms_title,dcterms_subject,pub_keyword
    -contentType:Contributor -contentType:Concept -contentType:Institution
    10
    5
Loading full text...

Full text loading...

References

  1. Rydning D-R-J-G-J. Reinsel J. Gantz J. The digitization of the world from edge to core. Framingham International Data Corporation 2018 16
    [Google Scholar]
  2. Kim S.J. Jung W.B. Jung H.S. Lee M.H. Heo J. Horgan A. Godron X. Ham D. The bottom of the memory hierarchy: Semiconductor and DNA data storage. MRS Bull. 2023 48 5 547 559 10.1557/s43577‑023‑00510‑x
    [Google Scholar]
  3. Church G.M. Gao Y. Kosuri S. Next-generation digital information storage in DNA. Science 2012 337 6102 1628 10.1126/science.1226355 22903519
    [Google Scholar]
  4. Ceze L. Nivala J. Strauss K. Molecular digital data storage using DNA. Nat. Rev. Genet. 2019 20 8 456 466 10.1038/s41576‑019‑0125‑3 31068682
    [Google Scholar]
  5. Yu M. Tang X. Li Z. Wang W. Wang S. Li M. Yu Q. Xie S. Zuo X. Chen C. High-throughput DNA synthesis for data storage. Chem. Soc. Rev. 2024 53 9 4463 4489 10.1039/D3CS00469D 38498347
    [Google Scholar]
  6. Kosuri S. Church G.M. Large-scale de novo DNA synthesis: Technologies and applications. Nat. Methods 2014 11 5 499 507 10.1038/nmeth.2918 24781323
    [Google Scholar]
  7. Organick L. Ang S.D. Chen Y.J. Lopez R. Yekhanin S. Makarychev K. Racz M.Z. Kamath G. Gopalan P. Nguyen B. Takahashi C.N. Newman S. Parker H.Y. Rashtchian C. Stewart K. Gupta G. Carlson R. Mulligan J. Carmean D. Seelig G. Ceze L. Strauss K. Random access in large-scale DNA data storage. Nat. Biotechnol. 2018 36 3 242 248 10.1038/nbt.4079 29457795
    [Google Scholar]
  8. Lee H.H. Kalhor R. Goela N. Bolot J. Church G.M. Terminator-free template-independent enzymatic DNA synthesis for digital information storage. Nat. Commun. 2019 10 1 2383 10.1038/s41467‑019‑10258‑1 31160595
    [Google Scholar]
  9. Tomek K.J. Volkel K. Simpson A. Hass A.G. Indermaur E.W. Tuck J.M. Keung A.J. Driving the scalability of DNA-based information storage systems. ACS Synth. Biol. 2019 8 6 1241 1248 10.1021/acssynbio.9b00100 31117362
    [Google Scholar]
  10. Palluk S. Arlow D.H. de Rond T. Barthel S. Kang J.S. Bector R. Baghdassarian H.M. Truong A.N. Kim P.W. Singh A.K. Hillson N.J. Keasling J.D. De novo DNA synthesis using polymerase-nucleotide conjugates. Nat. Biotechnol. 2018 36 7 645 650 10.1038/nbt.4173 29912208
    [Google Scholar]
  11. Cheng C. Gu X. Fei Z. Xiao P. An algorithm-optimized scheme for in situ synthesis of DNA microarrays. Comb. Chem. High Throughput Screen. 2023 26 8 1609 1617 10.2174/1386207326666230118114032 36654466
    [Google Scholar]
  12. Deng X. Li H. Song Y. Inkjet printing-based high-throughput DNA synthesis. Giant 2024 17 100222 10.1016/j.giant.2023.100222
    [Google Scholar]
  13. Pawloski A.R. McGall G. Kuimelis R.G. Barone D. Cuppoletti A. Ciccolella P. Spence E. Afroz F. Bury P. Chen C. Chen C. Pao D. Le M. McGee B. Harkins E. Savage M. Narasimhan S. Goldberg M. Rava R. Fodor S.P.A. Photolithographic synthesis of high-density DNA probe arrays: Challenges and opportunities. J. Vac. Sci. Technol. B Microelectron. Nanometer Struct. Process. Meas. Phenom. 2007 25 6 2537 2546 10.1116/1.2794325
    [Google Scholar]
  14. Nguyen B.H. Takahashi C.N. Gupta G. Smith J.A. Rouse R. Berndt P. Yekhanin S. Ward D.P. Ang S.D. Garvan P. Parker H.Y. Carlson R. Carmean D. Ceze L. Strauss K. Scaling DNA data storage with nanoscale electrode wells. Sci. Adv. 2021 7 48 eabi6714 10.1126/sciadv.abi6714 34818035
    [Google Scholar]
  15. Ghadami O. Lu H. Chan M. Tan M. Chung S. Lee S.H. Holden M.T. Ridder R.d. Merriman B. Hall D.A. Helix: An electrochemical CMOS DNA synthesizer. 2022 IEEE Symposium on VLSI Technology and Circuits Honolulu, HI, USA, 12-17 June 2022 66 67 10.1109/VLSITechnologyandCir46769.2022.9830446
    [Google Scholar]
  16. Chee M. Yang R. Hubbell E. Berno A. Huang X.C. Stern D. Winkler J. Lockhart D.J. Morris M.S. Fodor S.P.A. Accessing genetic information with high-density DNA arrays. Science 1996 274 5287 610 614 10.1126/science.274.5287.610 8849452
    [Google Scholar]
  17. Tolonen A.C. Albeanu D.F. Corbett J.F. Handley H. Henson C. Malik P. Optimized in situ construction of oligomers on an array surface. Nucleic Acids Res. 2002 30 20 107e 107 10.1093/nar/gnf106 12384609
    [Google Scholar]
  18. Rahmann S. Fast large scale oligonucleotide selection using the longest common factor approach. J. Bioinform. Comput. Biol. 2003 1 2 343 361 10.1142/S0219720003000125 15290776
    [Google Scholar]
  19. Kasif S. Weng Z. Derti A. Beigel R. DeLisi C. A computational framework for optimal masking in the synthesis of oligonucleotide microarrays. Nucleic Acids Res. 2002 30 20 106e 106 10.1093/nar/gnf105 12384608
    [Google Scholar]
  20. Ning K. Choi K.P. Leong H.W. Zhang L. A post-processing method for optimizing synthesis strategy for oligonucleotide microarrays. Nucleic Acids Res. 2005 33 17 144 10.1093/nar/gni147 16192568
    [Google Scholar]
  21. Yang F-P. Wu Y-Q. Lin S. Zhang S-J. Huang Y-J. Zhou X-M. Liu Z-C. Application of reversal operation in optimizing synthesis strategy for DNA microarrays. 2011 5th International Conference on Bioinformatics and Biomedical Engineering Wuhan, China 10-12 May 2011 1 3 10.1109/icbbe.2011.5780004
    [Google Scholar]
  22. Pop P.C. Cosma O. Sabo C. Sitar C.P. A comprehensive survey on the generalized traveling salesman problem. Eur. J. Oper. Res. 2024 314 3 819 835 10.1016/j.ejor.2023.07.022
    [Google Scholar]
  23. Baidoo E. Opoku Oppong S. Solving the TSP using traditional computing approach. Int. J. Comput. Appl. 2016 152 8 13 19 10.5120/ijca2016911906
    [Google Scholar]
  24. Wang S. Liu M. Chu F. Approximate and exact algorithms for an energy minimization traveling salesman problem. J. Clean. Prod. 2020 249 119433 10.1016/j.jclepro.2019.119433
    [Google Scholar]
  25. Gavish B. Srikanth K. An optimal solution method for large-scale multiple traveling salesmen problems. Oper. Res. 1986 34 5 698 717 10.1287/opre.34.5.698
    [Google Scholar]
  26. Yu H. Zhang K. Optimizing the greedy algorithm used in the TSP abstract problems. Appl. Mech. Mater. 2014 651-653 2352 2355 10.4028/www.scientific.net/AMM.651‑653.2352
    [Google Scholar]
  27. Huang Y.Y. Pan Q.K. Huang J.P. Suganthan P.N. Gao L. An improved iterated greedy algorithm for the distributed assembly permutation flowshop scheduling problem. Comput. Ind. Eng. 2021 152 107021 10.1016/j.cie.2020.107021
    [Google Scholar]
  28. Lu C. Zheng J. Yin L. Wang R. An improved iterated greedy algorithm for the distributed hybrid flowshop scheduling problem. Eng. Optim. 2024 56 5 792 810 10.1080/0305215X.2023.2198768
    [Google Scholar]
  29. Mafarja M.M. Mirjalili S. Hybrid Whale Optimization Algorithm with simulated annealing for feature selection. Neurocomputing 2017 260 302 312 10.1016/j.neucom.2017.04.053
    [Google Scholar]
  30. Zhang W. Maleki A. Rosen M.A. Liu J. Optimization with a simulated annealing algorithm of a hybrid system for renewable energy including battery and hydrogen storage. Energy 2018 163 191 207 10.1016/j.energy.2018.08.112
    [Google Scholar]
  31. Liu Y. Heidari A.A. Cai Z. Liang G. Chen H. Pan Z. Alsufyani A. Bourouis S. Simulated annealing-based dynamic step shuffled frog leaping algorithm: Optimal performance design and feature selection. Neurocomputing 2022 503 325 362 10.1016/j.neucom.2022.06.075
    [Google Scholar]
  32. Fontes D.B.M.M. Homayouni S.M. Gonçalves J.F. A hybrid particle swarm optimization and simulated annealing algorithm for the job shop scheduling problem with transport resources. Eur. J. Oper. Res. 2023 306 3 1140 1157 10.1016/j.ejor.2022.09.006
    [Google Scholar]
  33. Groba C. Sartal A. Vázquez X.H. Solving the dynamic traveling salesman problem using a genetic algorithm with trajectory prediction: An application to fish aggregating devices. Comput. Oper. Res. 2015 56 22 32 10.1016/j.cor.2014.10.012
    [Google Scholar]
  34. Toaza B. Esztergár-Kiss D. A review of metaheuristic algorithms for solving TSP-based scheduling optimization problems. Appl. Soft Comput. 2023 148 110908 10.1016/j.asoc.2023.110908
    [Google Scholar]
  35. Gan R. Guo Q. Chang H. Yi Y. Improved ant colony optimization algorithm for the traveling salesman problems. J. Syst. Eng. Electron. 2010 21 2 329 333 10.3969/j.issn.1004‑4132.2010.02.025
    [Google Scholar]
  36. Zhang Y. Wang S. Ji G. A comprehensive survey on particle swarm optimization algorithm and its applications. Math. Probl. Eng. 2015 2015 1 38 10.1155/2015/931256
    [Google Scholar]
  37. Xu J. Chun H. Wang L. Mei H. Chen S. Huang X. DNA microarray chips: Fabrication and cutting-edge applications. Chem. Eng. J. 2024 499 155937 10.1016/j.cej.2024.155937
    [Google Scholar]
  38. Wang W. Tian W. Xu D. Zang H. Arctic puffin optimization: A bio-inspired metaheuristic algorithm for solving engineering design optimization. Adv. Eng. Softw. 2024 195 103694 10.1016/j.advengsoft.2024.103694
    [Google Scholar]
  39. Wang J. Wang W.C. Hu X.X. Qiu L. Zang H.F. Black-winged kite algorithm: A nature-inspired meta-heuristic for solving benchmark functions and engineering problems. Artif. Intell. Rev. 2024 57 1 28 10.1007/s10462‑023‑10620‑2
    [Google Scholar]
  40. Zhou Y. Bi K. Xu Q. Liu Q. Zhao X. Ge Q. Lu Z. Ultrafast and accurate DNA storage and reading integrated system via microfluidic magnetic beads polymerase chain reaction. ACS Nano 2025 19 7 7306 7316 10.1021/acsnano.4c17817 39946680
    [Google Scholar]
  41. Efcavitch J.W. Heiner C. Depurination as a yield decreasing mechanism in oligodeoxynucleotide synthesis. Nucleosides Nucleotides 1985 4 1-2 267 10.1080/07328318508077883
    [Google Scholar]
  42. LeProust E.M. Peck B.J. Spirin K. McCuen H.B. Moore B. Namsaraev E. Caruthers M.H. Synthesis of high-quality libraries of long (150mer) oligonucleotides by a novel depurination controlled process. Nucleic Acids Res. 2010 38 8 2522 2540 10.1093/nar/gkq163 20308161
    [Google Scholar]
  43. Hoose A. Vellacott R. Storch M. Freemont P.S. Ryadnov M.G. DNA synthesis technologies to close the gene writing gap. Nat. Rev. Chem. 2023 7 3 144 161 10.1038/s41570‑022‑00456‑9 36714378
    [Google Scholar]
  44. Anavy L. Vaknin I. Atar O. Amit R. Yakhini Z. Data storage in DNA with fewer synthesis cycles using composite DNA letters. Nat. Biotechnol. 2019 37 10 1229 1236 10.1038/s41587‑019‑0240‑x 31501560
    [Google Scholar]
/content/journals/cchts/10.2174/0113862073402626251112103715
Loading
An Optimization Scheme Based on the Simulated Annealing Algorithm for In situ DNA Microarray Synthesis
Bentham Science Publishers ; https://doi.org/10.2174/0113862073402626251112103715
/content/journals/cchts/10.2174/0113862073402626251112103715
/content/journals/cchts/10.2174/0113862073402626251112103715
Loading

Data & Media loading...

Supplements

Supplementary material is available on the publisher’s website along with the published article.

file format download Download

  • Article Type:     Research Article
Keywords: traveling salesman problem (TSP) ; DNA microarray synthesis ; greedy algorithm ; simulated annealing algorithm ; optimization algorithm ; synthesis cycles

Most Cited Most Cited RSS feed

This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error
Please enter a valid_number test