DNA Polyhedra Compiler

Dennis Shasha

Omniheurist Course

Computer Science


 

Description

DNA has a directionality (from what is called the 5' to 3' end). When two strands (or two parts of strands) of DNA pair, they pair in opposite directions. Further, each nucleotide pairs with its complement (i.e., A with T, C with G etc.). Thus the pairing is to a reverse complement. For example AACCCGG in the 5' to 3' direction will pair to CCGGGTT in the 5' to 3' direction. (The two Cs will pair to the last two Gs and so on).

If two strands pair only partly, then they will separate where they stop pairing. Further if a strand s of length n can pair with a strand s1 of length k1 or a strand s2 of length k2 but not both and k1 is less than k2, then s will pair with s2. (Pairing results in a lower energy state.) Finally, we'd like our strands to be of minimal length, because they won't break that way and the whole structure can be smaller.

Ned Seeman of the NYU chemistry department has taken advantage of the properties of DNA to create structures that are more than one dimensional. The simplest is a little crossroads like structure. In that structure, four ``two-lane'' roads leave an intersection. Conceptually, one produces this by creating strands of this form AB, B'C, C'D, D'A', where the letters represent sequences of nucleotides and the prime represents the reverse complement.

An example set of strands might be: A = AACC
B = TGTG
B' = CACA
C = CCGG
C' = CCGG
D = ACAC
D' = GTGT
A' = TTGG

Your Task

You will be given the task of designing a polyhedral structure with a certain number of faces. You are to try to determine the strands that would result in such a structure. Tyler Neylon will provide a verifier to ensure that your design falls only into the shape that is desired.