EGNAS: an exhaustive DNA sequence design algorithm

BMC Bioinformatics

Michael Mertig²  Martin Bönsch¹  Alfred Kick² 

[1]Professur für Physikalische Chemie, Mess- und Sensortechnik, Technische Universität Dresden, Dresden 01062, Germany

[2]Kurt-Schwabe-Institut für Mess- und Sensortechnik e.V. Meinsberg, Kurt-Schwabe-Straße 4, Ziegra-Knobelsdorf 04720, Germany

关键词: DNA origami;    DNA computing;    Polymerase chain reaction (PCR);    Single-base extension (SBE);    Single nucleotide polymorphism (SNP);    stem-and-loop structure;    Hairpin;    DNA sequence design algorithm;   

Others  :  1088232
DOI  :  10.1186/1471-2105-13-138

 received in 2012-02-03, accepted in 2012-06-07,  发布年份 2012

【 摘 要 】

Background

The molecular recognition based on the complementary base pairing of deoxyribonucleic acid (DNA) is the fundamental principle in the fields of genetics, DNA nanotechnology and DNA computing. We present an exhaustive DNA sequence design algorithm that allows to generate sets containing a maximum number of sequences with defined properties. EGNAS (Exhaustive Generation of Nucleic Acid Sequences) offers the possibility of controlling both interstrand and intrastrand properties. The guanine-cytosine content can be adjusted. Sequences can be forced to start and end with guanine or cytosine. This option reduces the risk of “fraying” of DNA strands. It is possible to limit cross hybridizations of a defined length, and to adjust the uniqueness of sequences. Self-complementarity and hairpin structures of certain length can be avoided. Sequences and subsequences can optionally be forbidden. Furthermore, sequences can be designed to have minimum interactions with predefined strands and neighboring sequences.

Results

The algorithm is realized in a C++ program. TAG sequences can be generated and combined with primers for single-base extension reactions, which were described for multiplexed genotyping of single nucleotide polymorphisms. Thereby, possible foldback through intrastrand interaction of TAG-primer pairs can be limited. The design of sequences for specific attachment of molecular constructs to DNA origami is presented.

Conclusions

We developed a new software tool called EGNAS for the design of unique nucleic acid sequences. The presented exhaustive algorithm allows to generate greater sets of sequences than with previous software and equal constraints. EGNAS is freely available for noncommercial use athttp://www.chm.tu-dresden.de/pc6/EGNAS webcite.

【 授权许可】

   
2012 Kick et al.; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

Figure 7.

Figure 8.

【 参考文献 】

• [1]Watson JD, Crick FH: Molecular structure of nucleic acids: A structure for deoxyribose nucleic acid. Nature 1953, 171(4356):737-738.
• [2]Seeman NC: Nucleic acid junctions and lattices. J Theor Biol 1982, 99(2):237-247.
• [3]Seeman NC, Kallenbach NR: Design of immobile nucleic acid junctions. Biophys J 1983, 44(2):201-209.
• [4]Seeman NC: De novo design of sequences for nucleic acid structural engineering. J Biomol Struct Dyn 1990, 8(3):573-581.
• [5]Adleman LM: Molecular computation of solutions to combinatorial problems. Science 1994, 266(5187):1021-1024.
• [6]Rothemund PWK: Folding DNA to create nanoscale shapes and patterns. Nature 2006, 440(7082):297-302.
• [7]Hirschhorn JN, Sklar P, Lindblad-Toh K, Lim YM, Ruiz-Gutierrez M, Bolk S, Langhorst B, Schaffner S, Winchester E, Lander ES: SBE-TAGS: An array-based method for efficient single-nucleotide polymorphism genotyping. Proc Natl Acad Sci USA 2000, 97(22):12164-12169.
• [8]Fan JB, Chen X, Halushka MK, Berno A, Huang X, Ryder T, Lipshutz RJ, Lockhart DJ, Chakravarti A: Parallel Genotyping of human SNPs using generic high-density oligonucleotide tag arrays. Genome Res 2000, 10(6):853-860.
• [9]Kick A, Bönsch M, Katzschner B, Voigt J, Herr A, Brabetz W, Jung M, Sonntag F, Klotzbach U, Danz N, Howitz S, Mertig M: DNA microarrays for hybridization detection by surface plasmon resonance spectroscopy. Biosens Bioelectron 2010, 26(4):1543-1547.
• [10]Seiffert J: Ein Sequenzdesign-Algorithmus für verzweigte DNA-Strukturen. PhD thesis. Technischen Universität Dresden, Fakultät Informatik 2008
• [11]Seiffert J, Huhle A: A full-automatic sequence design algorithm for branched DNA structures. J Biomol Struct Dyn 2008, 25(5):453-466.
• [12]Deaton R, Garzon M, Murphy RC, Rose JA, Franceschetti DR, Stevens JrSE: Genetic search of reliable encodings for DNA-based computation. In Late Breaking Papers at the Genetic Programming 1996 Conference Stanford University July 28-31, 1996. Edited by Koza JR. Stanford University, CA, USA: Stanford Bookstore; 1996:9-15.
• [13]Arita M, Nishikawa A, Hagiya M, Komiya K, Gouzu H, Sakamoto K: Improving sequence design for DNA computing. In Proceedings of Genetic and Evolutionary Computation Conference 2000 (GECCO ’00) July 8-12, 2000. Edited by Whitley LD, Goldberg DE, Cantú-Paz E, Spector L, Parmee IC, Vegas BeyerH-G. Las. Nevada, USA: Morgan Kaufmann; 2000:875-882.
• [14]Faulhammer D, Cukras AR, Lipton RJ, Landweber LF: Molecular computation: RNA solutions to chess problems. Proc Natl Acad Sci USA 2000, 97(4):1385-1389.
• [15]Feldkamp U, Saghafi S, Banzhaf W, Rauhe H: DNA Sequence Generator: A program for the construction of DNA sequences DNA computing. In DNA Computing Volume 2340 of Lecture Notes in Computer Science. Edited by Jonoska N, Seeman N. Berlin, Heidelberg: Springer Berlin / Heidelberg; 2002:23-32.
• [16]Shin SY, Kim DM, Lee IH, Zhang BT: Evolutionary sequence generation for reliable DNA computing. In Proceedings of the 2002 Congress on Evolutionary Computation (CEC ’02) May 12-17 2002, Volume 1. Hilton, Hawaiian Village Hotel, Honolulu, Hawaii, USA; 2002:79-84.
• [17]Tanaka F, Nakatsugawa M, Yamamoto M, Shiba T, Ohuchi A: Towards a general-purpose sequence design system in DNA computing, Volume 1. In Proceedings of the 2002 Congress on Evolutionary Computation (CEC ’02) May 12-17, 2002. Hilton, Hawaiian Village Hotel, Honolulu, Hawaii, USA; 2002:73-78.
• [18]Tanaka F, Nakatsugawa M, Yamamoto M, Shiba T, Ohuchi1 A: Developing support system for sequence design in DNA computing. In DNA Computing Volume 2340 of Lecture Notes in Computer Science. Edited by Jonoska N, Seeman N. Berlin, Heidelberg: Springer Berlin / Heidelberg; 2002:129-137.
• [19]Kaderali L, Deshpande A, Nolan JP, White PS: Primer-design for multiplexed genotyping. Nucleic Acids Res 2003, 31(6):1796-1802.
• [20]Feldkamp U, Rauhe H, Banzhaf W: Software tools for DNA sequence design. Genet Programming Evolvable Machines 2003, 4(2):153-171.
• [21]Yin P, Guo B, Belmore C, Palmeri W, Winfree E, LaBean TH, Reif JH: TileSoft: Sequence optimization software for designing DNA secondary structures. 2004. (February 1, 2012). [ http://www.cs.duke. edu/reif/paper/peng/TileSoft/TileSoft.pdf webcite]
• [22]Feldkamp U: Computer aided DNA sequence design. PhD thesis. Universität Dortmund, Fachbereich Informatik 2005
• [23]Feldkamp U, Niemeyer CM: Rational design of DNA nanoarchitectures. Angew Chem Int Ed 2006, 45(12):1856-1876.
• [24]Zhu J, Wei B, Yuan Y, Mi Y: UNIQUIMER 3D, a software system for structural DNA nanotechnology design, analysis and evaluation. Nucleic Acids Res 2009, 37(7):2164-2175.
• [25]Feldkamp U: CANADA: Designing nucleic acid sequences for nanobiotechnology applications. J Comput Chem 2010, 31(3):660-663.
• [26]Brenneman A, Condon A: Strand design for biomolecular computation. Theor Comput Sci 2002, 287:39-58.
• [27]Breslauer KJ, Frank R, Blöcker H, Marky LA: Predicting DNA duplex stability from the base sequence. Proc Nat Acad Sci 1986, 83(11):3746-3750.
• [28]SantaLucia JJr, Allawi HT, Seneviratne PA: Improved nearest-neighbor parameters for predicting DNA duplex stability. Biochemistry 1996, 35(11):3555-3562.
• [29]Marky LA, Canuel L, Jones RA, Breslauer KJ: Calorimetric and spectroscopic investigation of the helix-to-coil transition of the self-complementary deoxyribonucleotide ATGCAT. Biophys Chem 1981, 13(2):141-149.
• [30]Sen D, Gilbert W: Formation of parallel four-stranded complexes by guanine-rich motifs in DNA and its implications for meiosis. Nature 1988, 334(6180):364-366.
• [31]Sundquist WI, Klug A: Telomeric DNA dimerizes by formation of guanine tetrads between hairpin loops. Nature 1989, 342(6251):825-829.
• [32]Kunkel TA: Misalignment-mediated DNA synthesis errors. Biochemistry 1990, 29(35):8003-8011.
• [33]Markham NR, Zuker M: DINAMelt web server for nucleic acid melting prediction. Nucleic Acids Res 2005, 33(Web Server issue):W577—W581.
• [34]Feldkamp U, Wacker R, Schroeder H, Banzhaf W, Niemeyer CM: Microarray-based in vitro evaluation of DNA oligomer libraries designed in silico. ChemPhysChem 2004, 5(3):367-372.
• [35]Penchovsky R, Ackermann J: DNA library design for molecular computation. J Comput Biol 2003, 10(2):215-229.
• [36]Dunbar SA: Applications of LuminexⓇ xMAPTM technology for rapid, high-throughput multiplexed nucleic acid detection. Clin Chim Acta 2006, 363:71-82.
• [37]Tørring T, Voigt NV, Nangreave J, Yan H, Gothelf KV: DNA origami: a quantum leap for self-assembly of complex structures. Chem Soc Rev 2011, 40(12):5636-5646.
• [38]Douglas SM, Marblestone AH, Teerapittayanon S, Vazquez A, Church GM, Shih WM: Rapid prototyping of 3D DNA-origami shapes with caDNAno. Nucleic Acids Res 2009, 37(15):5001-5006.
• [39]Yanisch-Perron C, Vieira J, Messing J: Improved M13 phage cloning vectors and host strains: nucleotide sequences of the M13mp18 and pUC19 vectors. Gene 1985, 33:103-119.
• [40]Ding B, Deng Z, Yan H, Cabrini S, Zuckermann RN, Bokor J: Gold nanoparticle self-similar chain structure organized by DNA origami. J Am Chem Soc 2010, 132(10):3248-3249.
• [41]Stearns LA, Chhabra R, Sharma J, Liu Y, Petuskey WT, Yan H, Chaput JC: Template-directed nucleation and growth of inorganic nanoparticles on DNA scaffolds. Angew Chem, Int Ed 2009, 48(45):8494-8496.