A depth-first search algorithm for oligonucleotide design in gene assembly

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.