Ask a Librarian

Threre are lots of ways to contact a librarian. Choose what works best for you.

HOURS TODAY

3:00 pm - 7:00 pm

Reference Desk

CONTACT US BY PHONE

(802) 656-2022

Voice

(802) 503-1703

Text

MAKE AN APPOINTMENT OR EMAIL A QUESTION

Schedule an Appointment

Meet with a librarian or subject specialist for in-depth help.

Email a Librarian

Submit a question for reply by e-mail.

WANT TO TALK TO SOMEONE RIGHT AWAY?

Library Hours for Sunday, October 21st

All of the hours for today can be found below. We look forward to seeing you in the library.
HOURS TODAY
10:00 am - 12:00 am
MAIN LIBRARY

SEE ALL LIBRARY HOURS
WITHIN BAILEY/HOWE

MapsClosed

Media Services1:00 pm - 9:00 pm

Reference Desk3:00 pm - 7:00 pm

Cyber Cafe (All Night Study)12:00 am - 8:00 am

OTHER DEPARTMENTS

Special Collections1:00 pm - 5:00 pm

Dana Medical Library9:00 am - 11:00 pm

Classroom Technology ServicesClosed

 

CATQuest

Search the UVM Libraries' collections

UVM Theses and Dissertations

Browse by Department
Format:
Online
Author:
Morse, Ada Nicole
Dept./Program:
College of Engineering and Mathematical Sciences
Year:
2018
Degree:
PhD
Abstract:
Designing self-assembling DNA nanostructures often requires the identification of a route for a scaffolding strand of DNA through the target structure. When the target structure is modeled as a graph, these scaffolding routes correspond to Eulerian circuits subject to turning restrictions imposed by physical constraints on the strands of DNA. Existence of such Eulerian circuits is an NP-hard problem, which can be approached by adapting solutions to a version of the Traveling Salesperson Problem. However, the author and collaborators have demonstrated that even Eulerian circuits obeying these turning restrictions are not necessarily feasible as scaffolding routes by giving examples of nontrivially knotted circuits which cannot be traced by the unknotted scaffolding strand. Often, targets of DNA nanostructure self-assembly are modeled as graphs embedded on surfaces in space. In this case, Eulerian circuits obeying the turning restrictions correspond to A-trails, circuits which turn immediately left or right at each vertex. In any graph embedded on the sphere, all A-trails are unknotted regardless of the embedding of the sphere in space. We show that this does not hold in general for graphs on the torus. However, we show this property does hold for checkerboard-colorable graphs on the torus, that is, those graphs whose faces can be properly 2-colored, and provide a partial converse to this result. As a consequence, we characterize (with one exceptional family) regular triangulations of the torus containing unknotted A-trails. By developing a theory of sums of A-trails, we lift constructions from the torus to arbitrary n-tori, and by generalizing our work on A-trails to smooth circuit decompositions, we construct all torus links and certain sums of torus links from circuit decompositions of rectangular torus grids. Graphs embedded on surfaces are equivalent to ribbon graphs, which are particularly well-suited to modeling DNA nanostructures, as their boundary components correspond to strands of DNA and their twisted ribbons correspond to double-helices. Every ribbon graph has a corresponding delta-matroid, a combinatorial object encoding the structure of the ribbon-graph's spanning quasi-trees (substructures having exactly one boundary component). We show that interlacement with respect to quasi-trees can be generalized to delta-matroids, and use the resulting structure on delta-matroids to provide feasible-set expansions for a family of delta-matroid polynomials, both recovering well-known expansions of this type (such as the spanning-tree expansion of the Tutte polynnomial) as well as providing several previously unknown expansions. Among these are expansions for the transition polynomial, a version of which has been used to study DNA nanostructure self-assembly, and the interlace polynomial, which solves a problem in DNA recombination.