Integer compositions and DNA self-assembly strategies: a combinatorial and a geometric approach

It is known that some sequences of four elements, that are the nitrogenous bases A, C, G, T (namely adenine, cytosine, guanine and thymine) from which DNA is assembled, are repeated in the human genome many times. Because of the structure of DNA, different sequences that are equivalent up to cyclic rotation and reverse complementation, determine the same repeated pattern. In [G.I. Bell, R.L. Bivins, J.D. Louck, N. Metropolis and M.L. Stein, Properties of words on four letters from those on two letters with an application to DNA sequences. Advances in Applied Mathematics, 14(3):348–367, 1993], the authors were able to derive a formula for the number of equivalence classes of primitive patterns of DNA sequences of length n using the bijective correspondence between words on two letters of length 2n and words of length n on four letters. A further derivation of the formula for the classification of DNA sequences of length n is provided in [W. Y. C. Chen and J. D. Louck, Necklaces, MSS sequences, and DNA sequences. Advances in Applied Mathematics, 18(1):18–32, 1997] by using properties of cycle structures related to fixed points of the hypercube Q_n. In this thesis a cyclic binary string of length n is interpreted as a particular cyclic composition of n and the notion of the partition graph P_n of a positive integer n is introduced: the vertices of P_n are binary necklaces. Moreover, the relation between paths and cycles of P_n and Q_n is investigated. The second part of this work deals with techniques that use the Watson-Crick complementarity properties of DNA strands to self-assembly nanostructures, particularly polyhedra. For all of these methods, an essential step is designing the component molecular building blocks; thus there is an increased necessity for a mathematical approach to these design strategy problems. We provide a mathematical model that captures the geometric constraints of rigid tiles, which are the branched junction molecule building blocks for tile-based DNA self-assembly. We also describe graph theoretical formalism for the DNA origami method. Using the aforementioned techniques we provide DNA self-assembly strategies to efficiently construct Platonic and Archimedean 3-regular polyhedral skeletons.

È noto che alcune sequenze di quattro elementi, che sono le basi azotate A, C, G, T (cioè adenina, citosina, guanina e timina) da cui è formato il DNA, si ripetono nel genoma umano molte volte. A causa della struttura del DNA, differenti sequenze che sono equivalenti a meno di rotazione ciclica e complementazione inversa, determinano lo stesso schema ripetuto nella sequenza del DNA. In [G.I. Bell, R.L. Bivins, J.D. Louck, N. Metropolis and M.L. Stein, Properties of words on four letters from those on two letters with an application to DNA sequences. Advances in Applied Mathematics, 14(3):348–367, 1993], gli autori hanno determinato una formula per il numero di classi di equivalenza di schemi primitivi di sequenze di DNA di lunghezza n utilizzando la corrispondenza biunivoca tra le parole su due lettere di lunghezza 2n e le parole di lunghezza n in quattro lettere. Un'ulteriore derivazione della formula di classificazione delle sequenze di DNA di lunghezza n è presentata in [W. Y. C. Chen and J. D. Louck, Necklaces, MSS sequences, and DNA sequences. Advances in Applied Mathematics, 18(1):18–32, 1997] dove si utilizzano proprietà di strutture cicliche relative ai punti fissi dell'ipercubo Q_n. In questa tesi una stringa binaria ciclica di lunghezza n è interpretata come una particolare composizione ciclica di n e viene introdotta la nozione di grafo partizione P_n di un intero positivo n: i vertici di P_n sono collane binarie. Inoltre, viene studiato il rapporto tra cammini e cicli di P_n e Q_n. Nella seconda parte di questo lavoro vengono analizzate alcune tecniche che utilizzano le proprietà di complementarità dei filamenti di DNA per costruire nanostrutture, in particolare poliedri. Per tutti questi metodi, un passo essenziale è la descrizione accurata delle componenti molecolari che costituiranno i blocchi da utilizzare durante il processo di assemblaggio; vi è quindi una crescente necessità di approcci matematici a questi problemi di progettazione. In questa tesi forniamo un modello matematico in grado di catturare i vincoli geometrici dei tasselli rigidi ("rigid tile"), i quali rappresentano "branched junction molecules". Descriviamo anche un formalismo teorico per il metodo DNA-origami. Utilizzando queste tecniche mostriamo come costruire in modo efficiente i solidi platonici ed archimedei 3-regolari.