Select Page

Celebration of Scholarship and Creative Activity 2021

“New and improved bounds on the tile complexity of uniquely self-assembling thin rectangles at temperature-1 in 3D”

Logan Withers

Senior, Computer Science

Abstract

In this project, we study the problem of determining the minimum number of unique tile types required for the self-assembly of thin rectangles in the abstract Tile Assembly Model (aTAM). The aTAM is the simplest, yet most popular, discrete mathematical model of nano-scale DNA tile self-assembly. In this field, we try to minimize the number of unique tile types because it is expensive, time-consuming, and difficult to experimentally build many different types of molecules (tile types), but it is trivial to experimentally copy an existing tile type. Our objective to give an improved upper bound on the tile complexity of “just-barely” 3D thin rectangles at temperature-1, where tiles are allowed to be placed at most one step into the third dimension. Our self-assembling computer algorithm, which produces a unique terminal assembly, implements a just-barely 3D, zig-zag counter, whose base depends on the dimensions of the target rectangle, and whose digits are encoded geometrically, vertically oriented and in binary.

Project Background

We pursued this work because it is directly built off of Dr. Summers’ previous work published in 2018, which we thought we could improve (at least for some of the results). The process essentially started with us brainstorming and generating lots of very detailed images depicting our algorithm, allowing us to test out different ways for a counter to geometrically encode information, and then reason about its correctness. After that, we spent time decomposing our algorithm into smaller modules, aiding in the process of producing the formal proof of correctness. The final step of this process was actually writing the formal proof of correctness of our algorithm in LaTeX and completing the paper; this involved generating even more of images, as well as careful verification of technical details and writing the textual explanations. All throughout this process, we also had regular virtual meetings, allowing us to collaborate effectively.

 

 

What Do You Think? 

We encourage you to leave a respectful note, thought or comment with the presenter(s) below as a means of engaging with them. Your responses are appreciated and the presenter(s) will be participating in the conversation. 

0 Comments

Submit a Comment

Your email address will not be published.

Thank you for visiting Celebration of Scholarship and Creative Activity!
We hope you are inspired by the excellence and hard work of UW Oshkosh Titans.