Reverse engineering DNA origami nanostructure designs from raw scaffold and staple sequence lists

Abstract

Designs for scaffolded DNA origami nanostructures are commonly and minimally published as the list of DNA staple and scaffold sequences required. In nearly all cases, high-level editable design files (e.g. caDNAno) which generated the low-level sequences are not made available. This de facto 'raw sequence' exchange format allows published origami designs to be re-attempted in the laboratory by other groups, but effectively stops designs from being significantly modified or re-purposed for new future applications. To make the raw sequence exchange format more accessible to further design and engineering, in this work we propose the first algorithmic solution to the inverse problem of converting staple/scaffold sequences back to a 'guide schematic' resembling the original origami schematic. The guide schematic can be used to aid the manual re-input of an origami into a CAD tool like caDNAno, hence recovering a high-level editable design file. Creation of a guide schematic can also be used to double check that a list of staple strand sequences does not have errors and indeed does assemble into a desired origami nanostructure prior to costly laboratory experimentation. We tested our reverse algorithm on 36 diverse origami designs from the literature and found that 29 origamis (81 %) had a good quality guide schematic recovered from raw sequences. Our software is made available at https://revnano.readthedocs.io.

Keywords: Constraint programming; Contact map; DNA nanotechnology; DNA origami; Reverse engineering; Spring embedder.

Reverse engineering unstructured scaffold and staple sequences back into a DNA origami schematic.

Fig. 1

Forward Design and Reverse Engineering of DNA Origami Nanostructures.(a) In the traditional forward design process, a DNA origami schematic has a scaffold sequence assigned from which the Watson-Crick complementary staple strands are derived. The geometric origami schematic implicitly embeds a topological contact map detailing how the staple and scaffold bases are pairwise hybridised. The process of going from schematic to raw sequences involves two stages of information loss, I₁ and I₂. (b) The inverse problem addressed in this work, i.e. going from raw sequences back to a geometric origami schematic, involves the (partial) recovery of I₂ and then I₁. The REVNANO constraint programming solver first reconstructs an approximate contact map of scaffold-staple base pair connectivity r; the latter is converted into an equivalent graph representation of the origami domain-level connectivity $\mathbb{D}$; finally a spring-embedder algorithm converts the graph into an approximate non-crossing geometric representation in 2D or 3D using spring energy minimisation.

Fig. 2

REVNANO Constraint Programming Solver: Principles Illustrated with Rothemund Smiley Origami. (a) Stage 0: Staple routing trees (SRTs) are constructed for all staples. Tree node (1236: 8) signifies a staple section that begins at scaffold base 1236 and runs for 8 bases in total toward scaffold 5′. Staple 176 has 5 viable routes across the scaffold; Staple 25 has 1 single viable route and casts a larger ‘footprint’ (inset boxes, red starred bases). (b) Definite 1-route staples are identified and placed on the origami as initial hard constraints. (c) Stage 1: SRTs are pruned by the footprints of other SRTs in an iterative process. Over successive iterations more staples (green) collapse to a single defined route. The initial hard constraint staples placed at Stage 0 are shown in black. (d) Stage 2: ‘Problem’ staples remaining with > 1 route are placed by forcing the staple with the clearest shortest path through the current origami mesh to its shortest path route, and repeating over and over. Orange = staple forced to single route on iteration; Green = ‘ripple effect’ staples collapsing to a single defined route because of the latter action; Purple = total problem multi-route staples placed up to the current iteration. (e) Stage 3: Staple-staple overlaps (at locations shown by red dots) are fixed. (f) A few minor defects remain (see Results for discussion). For the REVNANO parameters used in this example (${\mu }_{\min }$ = 6 bp, σ = 5 bp, β = 0.5), 240 staples are placed approximately correctly, 1 staple is placed incorrectly and 2 staples are omitted. Note that in all diagrams, staples are superimposed on top of a pre-existing smiley scaffold routing to clearly show how staples have been placed: however, REVNANO does not know this scaffold routing a priori.

Fig. 3

REVNANO Solver Parameter Sensitivity. Heatmap shows regions of the REVNANO parameter space $({\mu }_{\min }=6\mathrm{bp},\sigma ,\beta )$ where reverse engineering of the Rothemund Smiley contact map is most effective in terms of total number of staples placed. REVNANO running in deterministic staple placement mode. Smiley faces 1 and 2 (right) show how staple placement differs at (σ = 10 bp, β = 0.05) and (σ = 0 bp, β = 0.6) parameter points, respectively. White space at the top of the heatmap represents parameter points terminating in a REVNANO error condition: E2 = Not enough staples placed to perform reliable shortest-path calculations; E4 = Unresolvable 3-staple overlap exists. See Supplementary Note 7 for $({\mu }_{\min }=5\mathrm{bp},\sigma ,\beta )$ case, and REVNANO run times for each parameter combination.

Fig. 4

Example Origami Guide Schematics Reverse Engineered from Raw Scaffold and Staple Sequence Lists. (a) Original origami schematics. Raw sequences derived from these schematics were passed through the reverse engineering pipeline (Fig. 1b) using REVNANO with optimal parameter settings, to produce the following reconstructed guide schematics: (b) 3D Ball in staples view, 100 % staples placed; (c) 3D Dodecahedron in scaffold routing view, 96.6 % staples placed (purple arrows highlight regions where staples omitted); (d) 2D Lotus Mesh in staples view, 97.8 % staples placed; (e) 2D Rothemund Star in staples view, 99.6 % staples placed; (f) 2D Hexagonal Tile in staples view, 98 % staples placed; (g) 2D Pentagon in staples view, 100 % staples placed; (h) 2D Annulus Mesh 2 in staples view, 100 % staples placed; (i) 2D Fivewell Plate, 100 % staples placed and shown in sequence-ambiguous junctions view computed by the AMBIG algorithm. Immoveable junctions in green, moveable junctions in red. When using the Fivewell Plate guide schematic to re-enter the design into an origami CAD tool, symmetry can be used to guess the correct positions of the ambiguous red crossovers by looking at the positions of the unambiguous green crossovers. Guide schematics for all other origamis in the test set of Table 1 are given in Supplementary Note 8.