Branched molecules of deoxyribonucleic acid (DNA) can self-assemble into
nanostructures through complementary cohesive strand base pairing. The production
of DNA nanostructures is valuable in targeted drug delivery and biomolecular
computing. With theoretical efficiency of laboratory processes in mind, we use a
flexible tile model for DNA assembly. We aim to minimize the number of different
types of branched junction molecules necessary to assemble certain target structures.
We represent target structures as discrete graphs and branched DNA molecules as
vertices with half-edges. We present the minimum numbers of required branched
molecule and cohesive-end types under three levels of restrictive conditions for the
tadpole and lollipop graph families. These families represent cycle and complete
graphs with a path appended via a single cut-vertex. We include three general
lemmas regarding such vertex-induced path subgraphs. Through proofs and
examples, we demonstrate the challenges that can arise in determining optimal
construction strategies.
Keywords
graph theory, discrete graph, lollipop graphs, tadpole
graphs, DNA self-assembly, nanostructures, flexible tile
model
