When synthesizing a gene with a long DNA sequence, it is usually necessary to divide it into several fragments. Based on these fragments, a set of oligonucleotides for gene assembly is produced. Each oligonucleotide is synthesized separately by the chemical reaction, and then the obtained oligonucleotides are assembled into the full gene sequence, in a specific environment, by polymerase chain reaction (PCR) or ligase chain reaction (LCR). In this paper, an effective and efficient algorithm to divide long genes into oligonucleotide sets is presented. First, according to the length of the overlapping oligonucleotide region, the long DNA sequence to be synthesized is divided into fragments of approximately equal length. Second, the length of these fragments is iterated to dynamically optimize the length of the overlapping regions to reduce melting temperature fluctuations. Then, the improved depth-first search algorithm is used according to the design principle of pruning optimization to obtain a uniform set of oligonucleotides with very close melting temperatures. This will decrease the errors in gene assembly with PCR or LCR. Lastly, the oligonucleotides that have homologous melting temperatures needed for PCR-based synthesis and two-step assembly of the target gene are deduced and outputted. Based on these fragments, a set of oligonucleotides for gene assembly is produced. Each oligonucleotide is synthesized separately by the chemical reaction, and then the obtained oligonucleotides are assembled into the full gene sequence, in a specific environment, by polymerase chain reaction (PCR) or ligase chain reaction (LCR). In this paper, an effective and efficient algorithm to divide long genes into oligonucleotide sets is presented. First, according to the length of the overlapping oligonucleotide region, the long DNA sequence to be synthesized is divided into fragments of approximately equal length. Second, the length of these fragments is iterated to dynamically optimize the length of the overlapping regions to reduce melting temperature fluctuations. Then, the improved depth-first search algorithm is used according to the design principle of pruning optimization to obtain a uniform set of oligonucleotides with very close melting temperatures. This will decrease the errors in gene assembly with PCR or LCR. Lastly, the oligonucleotides that have homologous melting temperatures needed for PCR-based synthesis and two-step assembly of the target gene are deduced and outputted. gene assembly depth-first search algorithm oligonucleotide design melting temperature pmc-status-qastatus 0 pmc-status-live yes pmc-status-embargo no pmc-status-released yes pmc-prop-open-access yes pmc-prop-olf no pmc-prop-manuscript no pmc-prop-legally-suppressed no pmc-prop-has-pdf yes pmc-prop-has-supplement yes pmc-prop-pdf-only no pmc-prop-suppress-copyright no pmc-prop-is-real-version no pmc-prop-is-scanned-article no pmc-prop-preprint no pmc-prop-in-epmc yes pmc-license-ref CC BY Introduction Gene synthesis now mainly utilizes overlapping oligonucleotides to assemble large genes (>1000 bp) by polymerase chain reaction (PCR) or ligase chain reaction (LCR) ( Stemmer et al., 1995 ; Au et al., 1998 ). To optimize the PCR or LCR process and minimize errors in assembly, gene synthesis computer programs have been developed to aid in designing the oligonucleotides. The program’s algorithm automates and streamlines the oligonucleotide design process, so that errors in assembly are minimized and large genes can be synthesized effectively. In gapless PCR assembly, some web-based applications, for example, TmPrime and DNAWorks which use an iterative algorithm, have been developed ( David and DNAWorks, 2002 ; Marcus et al., 2009 ). The best result is a deviation in melting temperature of less than 1°C in the overlapped region, which is attained with the use of a dynamic programming algorithm ( Fang and Liang, 2022 ). However, its time complexity is too high to be used as a web-based application. When assembling oligonucleotides using gapped PCR, the DNA fragments are contiguous with few base deletions. Compared with gapless PCR or LCR, gapped PCR assembly can lead to more assembly errors, but these errors are insignificant and can be ignored ( Xiong et al., 2000 ). Gapped PCR assembly is more flexible and economical ( Xiong et al., 2000 ). In this work, an algorithm that makes use of overlapping regions with homologous melting temperatures to output oligonucleotides for gapped PCR assembly is proposed. Methods According to the simple observation depicted in Figure 1 , the proposed algorithm with an iteration step is introduced. A nearest neighbor model is used to calculate melting temperatures along with Santa Lucia’s thermodynamic parameters ( Santa Lucia and Hicks, 2004 ), the salt and oligonucleotide concentrations, and the totality of phosphates in the duplex ( Owczarzy et al., 2008 ). The equations and procedures used to calculate DNA melting temperature are described in detail in the Supplementary Material . After processing with the iteration algorithm, the oligonucleotide set can be deduced from the segmentation results. These oligonucleotides can be used for LCR or gapless PCR assembly; however, this step may not provide the best solution to the problem. Although DFS for this application is an approximation algorithm, it is open-source. It was not only developed for web-based application, but also for people in related fields to modify and develop related algorithms, and it is easy to carry out on an ordinary desktop computer. Oligo design is very important in gene synthesis. The web-based applications, TmPrime, DNAWorks, Gene2Oligo, Assembly PCR Oligo Maker etc., are no longer available and their source code is not always open-source. The DFS algorithm has been developed for oligo design and is open-source for all users. This project has been written into the computer program to facilitate gene synthesis.

The use, distribution or reproduction in other forums is permitted, provided the original author(s) and the copyright owner(s) are credited and that the original publication in this journal is cited, in accordance with accepted academic practice. No use, distribution or reproduction is permitted which does not comply with these terms. The design and construction of large synthetic genes can be a slow, difficult, and confusing process, especially in the key step of oligodeoxynucleotide design. Herein we present an integrated algorithm to design oligonucleotide sets for gene synthesis by both ligase chain reaction and polymerase chain reaction. It offers much flexibility with no constraints on the gene to be synthesized. Firstly, it divides the long-input DNA sequence by a greedy algorithm based on the length of the oligodeoxynucleotide overlap region. Secondly, it tunes the length of the overlap region iteratively in an attempt to minimize the melting temperature variance of overlap. Thirdly, dynamic programming algorithm is used to achieve the uniform melting temperature of the oligodeoxynucleotide overlaps. Finally, the oligodeoxynucleotides with homologous melting temperature necessary for ligase chain reaction-based or two-step assembly PCR-based synthesis of the desired gene are outputted. This modern gene synthesis technique can synthesize a whole eukaryotic genome, and current gene synthesis methods rely on the use of overlapped oligonucleotides to construct large genes by ligase chain reaction (LCR) ( Au et al., 1998 ) and polymerase chain reaction (PCR) ( Stemmer et al., 1995 ). Algorithms and computer programs have been developed for gene synthesis to automatically design oligonucleotides to minimize the error of assembly and to optimize the LCR or PCR process. Programs such as TmPrime and DNAWorks, based on iteration algorithm, have been developed for gapless PCR assembly ( David and Jacek, 2002 ; Marcus et al., 2009 ). Other programs, such as Gene2Oligo, Assembly PCR Oligo Maker, GeneDesign, and GeMS, also mainly based on iteration algorithm, have been developed for gap PCR assembly ( Jean-Marie et al., 2004 ; Roman et al., 2005 ; Sebastian et al., 2005 ; Sarah et al., 2006 ). In the key step of oligodeoxynucleotide design, all the algorithms carried out in the programs will divide the input gene sequences into oligonucleotides with a homologous melting temperature, and the corresponding overlaps of these oligonucleotides possess uniform melting temperatures. The best result of these programs, which is attained by TmPrime, is less than 3°C in deviation of melting temperature ( Marcus et al., 2009 ), but in optimization theory, it is not always the best solution to this sort of problem ( Cormen et al., 2001 ). In order to prove this and minimize the error of assembly in gene synthesis, herein we present an integrated algorithm to solve this problem and attain a better result. In the key step of oligodeoxynucleotide design in gene synthesis for gapless PCR or LCR assembly, all oligonucleotides are designed to be exactly adjacent, with no gap between two consecutive oligonucleotides. The given sequence can be seen as the serial connection of all overlapping regions of oligonucleotides. With this simple observation, the problem of designing oligonucleotides with a uniform melting temperature in overlaps will be equivalent to dividing the given sequence into segments with a homologous melting temperature, with each segment representing an overlapping region ( Marcus et al., 2009 ) ( Figure 1 ). FIGURE 1 Scheme of gapless PCR or ligase chain reaction assembly. The input sequence is regarded as the serial connection of the overlap regions of oligonucleotides. TABLE 2 The iteration algorithm. After the iteration algorithm, a better result will be given. The result can be used to produce oligodeoxynucleotides for LCR or gapless PCR assembly. In previous study, the PKB2 gene is selected for synthesis based on the reported difficulty of assembly via PCR ( Gao et al., 2003 ). Compared to the oligodeoxynucleotide set that TmPrime produces for Escherichia coli codon-optimized PKB2 gene, the integrated algorithm presented in this paper can produce oligodeoxynucleotide sets for gapless PCR assembly with more uniform melting temperatures. This guarantees the imbricated structure of oligodeoxynucleotides as shown in diagrams in Figures 1 , 2 . The added tail can be eliminated in a PCR reaction by using particular primers. Results When designing oligodeoxynucleotides for gene synthesis, the uniformity of oligo melting temperature especially in an overlap region is the key factor that should be considered. The oligodeoxynucleotide sets designed by the integrated algorithm possess the least SD in overlap melting temperature and can be used for gapless and gapped assembly ( Table 4 ). The SD in melting temperature of the designed oligodeoxynucleotides is also less than what another program produces ( Table 4 ).