Home Background Activities Data Software Multimedia Links Publications Members

# Publications

## Papers on DNA assembly

Title: Russian Doll Genes and Complex Chromosome Rearrangements in Oytricha trifallax Jasper Braun, Lukas Nabergall, Rafik Neme, Laura F. Landweber, Masahico Saito, Nataša Jonoska Ciliates have two different types of nuclei per cell, with one acting as a somatic, transcriptionally active nucleus (macronucleus; abbr. MAC) and another serving as a germline nucleus (micronucleus; abbr. MIC). Furthermore, Oxytricha trifallax undergoes extensive genome rearrangements during sexual conjugation and post-zygotic development of daughter cells. These rearrangements are necessary because the precursor MIC loci are often both fragmented and scrambled, with respect to the corresponding MAC loci. Such genome architectures are remarkably tolerant of encrypted MIC loci, because RNA-guided processes during MAC development reorganize the gene fragments in the correct order to resemble the parental MAC sequence. Here, we describe the germline organization of several nested and highly scrambled genes in Oxytricha trifallax. These include cases with multiple layers of nesting, plus highly interleaved or tangled precursor loci that appear to deviate from previously described patterns. We present mathematical methods to measure the degree of nesting between precursor MIC loci, and revisit a method for a mathematical description of scrambling. After applying these methods to the chromosome rearrangement maps of O. trifallax we describe cases of nested arrangements with up to five layers of embedded genes, as well as the most scrambled loci in O. trifallax. 10.1534/g3.118.200176

Title: Patterns and Distances in Words Related to DNA Rearrangement Nataša Jonoska, Lukas Nabergall, Masahico Saito We initiate studies of patterns in words that appear as subwords (not necessarily factors) of words. A pattern is a string of variables, and we say that a pattern appears in a word if each variable can be morphically mapped to a factor in the word. We define pattern indices and distances between two words relative to a given set of patterns. The distance is defined as the minimal number of ''pattern reductions'' that transfer one word into another. Motivated by patterns detected in certain scrambled ciliate genomes, we focus on double occurrence words (words where every symbol appears twice) and patterns in those words. Specifically, we show that in double occurrence words the distance relative to patterns $$\alpha\alpha$$ (repeat words) and $$\alpha\alpha^R$$ (return words) is computable. We also compare some pattern indices of highly scrambled genes in O. trifallax relative to random sequences. N. Jonoska, L. Nabergall, M. Saito. Patterns and Distances in Words Related to DNA Rearrangement. Fundamenta Informaticae 154: 1-4 (2017) pp 225-238. 10.3233/FI-2017-1563

Title: Recurring Patterns Among Scrambled Genes in the Encrypted Genome of the Ciliate Oxytricha trifallax Jonathan Burns, Denys Kukushkin, Xiao Chen, Laura F. Landweber, Masahico Saito, Nataša Jonoska Some genera of ciliates, such as Oxytricha and Stylonychia, undergo massive genome reorganization during development and provide model organisms to study DNA rearrangement. A common feature of these ciliates is the presence of two types of nuclei: a germline micronucleus and a transcriptionally-active somatic macronucleus containing over 16,000 gene sized "nano-chromosomes". During conjugation the old parental macronucleus disintegrates and a new macronucleus forms from a copy of the zygotic micronucleus. During this process, macronuclear chromosomes assemble through DNA processing events that delete 90-98% of the DNA content of the micronucleus. This includes the deletion of noncoding DNA segments that interrupt precursor DNA regions in the micronucleus, as well as transposons and other germline-limited DNA. Each macronuclear locus may be present in the micronucleus as several nonconsecutive, permuted, and/or inverted DNA segments. Here we investigate the genome-wide range of scrambled gene architectures that describe all precursor-product relationships in Oxytricha trifallax, the first completely sequenced scrambled genome. We find that five general, recurrent patterns in the sets of scrambled micronuclear precursor pieces can describe over 80% of Oxytricha's scrambled genes. These include instances of translocations and inversions, and other specific patterns characterized by alternating stretches of consecutive odd and even DNA segments. Moreover, we find that iterating patterns of alternating odd-even segments up to four times can describe over 96% of the scrambled precursor loci. Recurrence of these highly structured genetic architectures within scrambled genes presumably reflects recurrent evolutionary events that gave rise to over 3000 of scrambled loci in the germline genome. J. Burns, D. Kukushkin, X. Chen, L. Landweber, M. Saito, N. Jonoska. Recurring Patterns Among Scrambled Genes in the Encrypted Genome of the Ciliate Oxytricha trifallax. Journal of Theoretical Biology 410 (2016) pp. 171-180. 10.1016/j.jtbi.2016.08.038

Title: : A Database of Ciliate Genome Rearrangements Jonathan Burns, Denys Kukushkin, Kelsi Lindblad, Xiao Chen, Nataša Jonoska, Laura F. Landweber Ciliated protists exhibit nuclear dimorphism through the presence of somatic macronuclei (MAC) and germline micronuclei (MIC). In some ciliates, DNA from precursor segments in the MIC genome rearranges to form transcriptionally active genes in the mature MAC genome, making these ciliates model organisms to study the process of somatic genome rearrangement. Similar broad scale, somatic rearrangement events occur in many eukaryotic cells and tumors. The (http://oxytricha.princeton.edu/mds_ies_db) is a database of genome recombination and rearrangement annotations, and it provides tools for visualization and comparative analysis of precursor and product genomes. The database currently contains annotations for two completely sequenced ciliate genomes: Oxytricha trifallax and Tetrahymena thermophila. J. Burns, D. Kukushkin, K. Lindblad, X. Chen, N. Jonoska, L. Landweber. : A Database of Ciliate Genome Rearrangements. Nucleic Acids Res. 44:D1 (2015) pp. D703-D709. 10.1093/nar/gkv1190

Title: Combinatorial DNA Rearrangement Facilitates the Origin of New Genes in Ciliates Xiao Chen, Seolkyoung Jung, Leslie Y Beh, Sean R Eddy, Laura F. Landweber Programmed genome rearrangements in the unicellular eukaryote Oxytricha trifallax produce a transcriptionally active somatic nucleus from a copy of its germline nucleus during development. This process eliminates noncoding sequences that interrupt coding regions in the germline genome, and joins over 225,000 remaining DNA segments, some of which require inversion or complex permutation to build functional genes. This dynamic genomic organization permits some single DNA segments in the germline to contribute to multiple, distinct somatic genes via alternative processing. Like alternative mRNA splicing, the combinatorial assembly of DNA segments contributes to genetic variation and facilitates the evolution of new genes. In this study, we use comparative genomic analysis to demonstrate that the emergence of alternative DNA splicing is associated with the origin of new genes. Short duplications give rise to alternative gene segments that are spliced to the shared gene segments. Alternative gene segments evolve faster than shared, constitutive segments. Genes with shared segments frequently have different expression profiles, permitting functional divergence. This study reports alternative DNA splicing as a mechanism of new gene origination, illustrating how the process of programmed genome rearrangement gives rise to evolutionary innovation. X. Chen, S. Jung, L.Y. Beh, S.R. Eddy, L.F. Landweber. Combinatorial DNA Rearrangement Facilitates the Origin of New Genes in Ciliates. Genome Biology and Evolution 7:10 (2015) pp. 2859-70. 10.1093/gbe/evv172

Title: Existence of constants in regular splicing languages Paola Bonizzoni, Nataša Jonoska In spite of wide investigations of finite splicing systems in formal language theory, basic questions, such as their characterization, remain unsolved. It has been conjectured that a necessary condition for a regular language L to be a splicing language is that L must have a constant in the Schützenberger sense. We prove this longstanding conjecture to be true. The result is based on properties of strongly connected components of the minimal deterministic finite state automaton for a regular splicing language. Using constants of the corresponding languages, we also provide properties of transitive automata and path-automata. P. Bonizzoni, N. Jonoska, Existence of constants in regular splicing languages, Information and Computation 242 (2015) pp.340-353. 10.1016/j.ic.2015.04.001

Title: Genus Ranges of 4-Regular Rigid Vertex Graphs Dorothy Buck, Egor Dolzhenko, Nataša Jonoska, Masahico Saito, Karen Valencia A rigid vertex of a graph is one that has a prescribed cyclic order of its incident edges. We study orientable genus ranges of 4-regular rigid vertex graphs. The (orientable) genus range is a set of genera values over all orientable surfaces into which a graph is embedded cellularly, and the embeddings of rigid vertex graphs are required to preserve the prescribed cyclic order of incident edges at every vertex. The genus ranges of 4-regular rigid vertex graphs are sets of consecutive integers, and we address two questions: which intervals of integers appear as genus ranges of such graphs, and what types of graphs realize a given genus range. For graphs with $$2n$$ vertices $$(n > 1)$$, we prove that all intervals $$[a, b]$$ for all $$a < b \le n$$, and singletons $$[h, h]$$ for some $$h \le n$$, are realized as genus ranges. For graphs with $$2n - 1$$ vertices $$(n \ge 1)$$, we prove that all intervals $$[a, b]$$ for all $$a < b \le n$$ except $$[0, n]$$, and $$[h, h]$$ for some $$h \le n$$, are realized as genus ranges. We also provide constructions of graphs that realize these ranges. D. Buck, E. Dolzhenko, N. Jonoska, M. Saito, K. Valencia. Genus Ranges of 4-Regular Rigid Vertex. Electronic Journal of Combinatorics 22:3 (2015) #P3.43.

Title: Genus Ranges of Chord Diagrams Jonathan Burns, Nataša Jonoska, Masahico Saito A chord diagram consists of a circle, called the backbone, with line segments, called chords, whose endpoints are attached to distinct points on the circle. The genus of a chord diagram is the genus of the orientable surface obtained by thickening the backbone to an annulus and attaching bands to the inner boundary circle at the ends of each chord. Variations of this construction are considered here, where bands are possibly attached to the outer boundary circle of the annulus. The genus range of a chord diagram is the genus values over all such variations of surfaces thus obtained from a given chord diagram. Genus ranges of chord diagrams for a fixed number of chords are studied. Integer intervals that can, and cannot, be realized as genus ranges are investigated. Computer calculations are presented, and play a key role in discovering and proving the properties of genus ranges. Jonathan Burns, Nataša Jonoska, and Masahico Saito, Genus Ranges of Chord Diagrams. Journal of Knot Theory and its Ramifications. 24 (2015) 1550022. 10.1142/S0218216515500224

Title: The Architecture of a Scrambled Genome Reveals Massive Levels of Genomic Rearrangement during Development Egor Dolzhenko, Laura F. Landweber, Xiao Chen, John R. Bracht, Aaron David Goldman, Derek M. Clay, Estienne C. Swart, David H. Perlman, Thomas G. Doak, Andrew Stuart, Chris T. Amemiya, Robert P. Sebra Programmed DNA rearrangements in the single-celled eukaryote Oxytricha trifallax completely rewire its germline into a somatic nucleus during development. This elaborate, RNA-mediated pathway eliminates noncoding DNA sequences that interrupt gene loci and reorganizes the remaining fragments by inversions and permutations to produce functional genes. Here, we report the Oxytricha germline genome and compare it to the somatic genome to present a global view of its massive scale of genome rearrangements. The remarkably encrypted genome architecture contains >3,500 scrambled genes, as well as >800 predicted germline-limited genes expressed, and some posttranslationally modified, during genome rearrangements. Gene segments for different somatic loci often interweave with each other. Single gene segments can contribute to multiple, distinct somatic loci. Terminal precursor segments from neighboring somatic loci map extremely close to each other, often overlapping. This genome assembly provides a draft of a scrambled genome and a powerful model for studies of genome rearrangement. Xiao Chen, John R. Bracht, Aaron David Goldman, Egor Dolzhenko, Derek M. Clay, Estienne C. Swart, David H. Perlman, Thomas G. Doak, Andrew Stuart, Chris T. Amemiya, Robert P. Sebra, Laura F. Landweber. The Architecture of a Scrambled Genome Reveals Massive Levels of Genomic Rearrangement during Development. Cell, 158:5 (2014) 1187-1198. 10.1016/j.cell.2014.07.034

Title: Reductions on Double Occurrence Words Ryan Arredondo In the present paper we consider biologically motivated reduction operations on double occurrence words. Then we define the nesting index of a double occurrence word to be the least number of reduction operations it takes for a word to be reduced to the empty word. We use chord diagrams and circle graphs as tools to study the nesting index of double occurrence words. Arredondo, R., Reductions On Double Occurrence Words. Proceedings of the Forty-fourth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congr. Numer. 218 (2013), pp. 43-56. View

Title: Discrete and Topological Models in Molecular Biology Nataša Jonoska, Masahico Saito Theoretical tools and insights from discrete mathematics, theoretical computer science, and topology now play essential roles in our understanding of vital biomolecular processes. The related methods are now employed in various fields of mathematical biology as instruments to "zoom in" on processes at a molecular level. This book contains expository chapters on how contemporary models from discrete mathematics - in domains such as algebra, combinatorics, and graph and knot theories - can provide perspective on biomolecular problems ranging from data analysis, molecular and gene arrangements and structures, and knotted DNA embeddings via spatial graph models to the dynamics and kinetics of molecular interactions. The contributing authors are among the leading scientists in this field and the book is a reference for researchers in mathematics and theoretical computer science who are engaged with modeling molecular and biological phenomena using discrete methods. It may also serve as a guide and supplement for graduate courses in mathematical biology or bioinformatics, introducing nontraditional aspects of mathematical biology. Jonoska, Natasha; Saito, Masahico (Eds.) Discrete and Topological Models in Molecular Biology. Natural Computing Series. Springer (2013) ISBN 978-3-642-40192-3 10.1007/978-3-642-40193-0

Title: Four-regular Graphs with Rigid Vertices Associated to DNA Recombination Jonathan Burns, Egor Dolzhenko, Nataša Jonoska, Tilahun Muche, Masahico Saito Genome rearrangement and homological recombination processes have been modeled by 4-regular spacial graphs with rigid vertices, called assembly graphs. These graphs can also be represented by double occurrence words called assembly words. The rearranged DNA segments are modeled by certain types of paths in the assembly graphs called polygonal paths. The minimum number of polygonal paths visiting all vertices in a graph is called an assembly number for the graph. In this paper, we give formulas for counting certain types of assembly graphs and assembly words. Some of these formulas produce sequences not previously reported at the Online Encyclopedia of Integer Sequences. We provide a sharp upper bound for the number of polygonal paths in Hamiltonian sets of polygonal paths, and present a family of graphs that achieves this bound. We investigate changes in the assembly numbers as a result of graph compositions. Finally, we introduce a polynomial invariant for assembly graphs and show properties of this invariant. These studies provide possible DNA structures during recombination processes. J. Burns, E. Dolzhenko, N. Jonoska, T. Muche, M. Saito. Four-regular graphs with rigid vertices associated to DNA recombination. Discrete Applied Mathematics, 161:10-11 (2013) pp 1378-1394. 10.1016/j.dam.2013.01.003

Title: The Computational Nature of Gene Assembly in Ciliates Robert Brijder, Mark Daley, Tero Harju, Nataša Jonoska, Ion Petre, Grzegorz Rozenberg In this chapter we review several approaches and results in the computational study of gene assembly. We introduce the basic biological details of the gene assembly process as currently understood and experimentally observed. After mathematical preliminaries, we introduce two of the mostly studied molecular models for gene assembly (intermolecular and intramolecular) which are based on string rewriting techniques. We also discuss several mathematical approaches used in studying these models as well as some properties of the gene assembly process, called invariants, that hold independently of the molecular model and assembly strategy. Possible molecular implementation of the gene assembly process are presented through models for template-based DNA recombination. R. Brijder, M. Daley, T. Harju, N. Jonoska, I. Petre, and Gr. Rozenberg. The Computational Nature of Gene Assembly in Ciliates. Chapter in Handbook of Natural Computing (2012) pp. 1233-1280. 10.1007/978-3-540-92910-9_37

Title: Rewriting rule chains modeling DNA rearrangement pathways Angela Angeleska, Nataša Jonoska, Masahico Saito We introduce a model that describes rearrangement pathways of DNA recombination events. The recombination processes may happen in a succession, possibly with some recombination events performed simultaneously, but others in a prescribed order. These events are modeled by three rewriting rules applied on a set of formal linear and circular words. We define a partial order on these sets in such a way that two sets are related by this order when molecules represented by one are produced by recombination events from the other. We apply our model to experimental data obtained for DNA rearrangement of the actin I gene in O. trifallax ciliates, and we predict possible pathways of gene rearrangement compatible with the data. Angeleska, A., Jonoska, N., Saito, M., Rewriting rule chains modeling DNA rearrangement pathways, Theoretical Computer Science (2012), ISSN 0304-3975 10.1016/j.tcs.2012.04.041

Title: Regular splicing languages must have a constant Paola Bonizzoni, Nataša Jonoska In spite of wide investigations of finite splicing systems in formal language theory, basic questions, such as their characterization, remain unsolved. In search for understanding the class of finite splicing systems, it has been conjectured that a necessary condition for a regular language $$L$$ to be a splicing language is that $$L$$ must have a constant in the Schützenberger's sense. We prove this longstanding conjecture to be true. The result is based on properties of strongly connected components of the minimal deterministic finite state automaton for a regular splicing language. P. Bonizzoni, N. Jonoska, Regular splicing languages must have a constant, Developments in Language Theory (G. Mauri and A. Leporati, Eds.) DLT 2011, LNCS 6795 (2011) pp. 82-92. 10.1007/978-3-642-22321-1_8

Title: Counting Irreducible Double Occurrence Words Jonathan Burns, Tilahun Muche A double occurrence word w over a finite alphabet Σ is a word in which each alphabet letter appears exactly twice. Such words arise naturally in the study of topology, graph theory, and combinatorics. Recently, double occurrence words have been used for studying DNA recombination events. We develop formulas for counting and enumerating several elementary classes of double occurrence words such as palindromic, irreducible, and strongly-irreducible words. Burns, J., Muche, T., Counting irreducible double occurrence words. Proceedings of the Forty-second Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congr. Numer. 207 (2011), pp. 181-196. View

Title: DNA rearrangements through spatial graphs Nataša Jonoska, Masahico Saito The paper is a short overview of a recent model of homologous DNA recombination events guided by RNA templates that have been observed in certain species of ciliates. This model uses spatial graphs to describe DNA rearrangements and show how gene recombination can be modeled as topological braiding of the DNA. We show that a graph structure, which we refer to as an assembly graph, containing only 1- and 4-valent rigid vertices can provide a physical representation of the DNA at the time of recombination. With this representation, 4-valent vertices correspond to the alignment of the recombination sites, and we model the actual recombination event as smoothing of these vertices. N. Jonoska, M. Saito, DNA rearrangements through spatial graphs, in Computability in Europe (F. Ferreira et al. eds.) LNCS 6158 (2010) pp. 211-218. 10.1007/978-3-642-13962-8_24

Title: DNA Splicing: Computing by Observing Matteo Cavaliere, Nataša Jonoska, Peter Leupold Motivated by several techniques for observing molecular processes in real-time we introduce a computing device that stresses the role of the observer in biological computations and that is based on the observed behavior of a splicing system. The basic idea is to introduce a marked DNA strand into a test tube with other DNA strands and restriction enzymes. Under the action of these enzymes the DNA starts to splice. An external observer monitors and registers the evolution of the marked DNA strand. The input marked DNA strand is then accepted if its observed evolution follows a certain expected pattern. We prove that using simple observers (finite automata), applied on finite splicing systems (finite set of rules and finite set of axioms), the class of recursively enumerable languages can be recognized. M. Cavaliere, N. Jonoska, P. Leupold, DNA Splicing: Computing by Observing, Natural Computing 8:1 (2009) pp. 157-170. 10.1007/s11047-007-9062-8

Title: Strategies for RNA-Guided DNA Recombination Angela Angeleska, Nataša Jonoska, Masahico Saito, Laura F. Landweber We present a model for homologous DNA recombination events guided by double-stranded RNA (dsRNA) templates, and apply this model to DNA rearrangements in some groups of ciliates, such as Stylonychia or Oxytricha. In these organisms, differentiation of a somatic macronucleus from a germline micronucleus involves extensive gene rearrangement, which can be modeled as topological braiding of the DNA, with the template-guided alignment proceeding through DNA branch migration.We show that a graph structure, which we refer to as an assembly graph, containing only 1- and 4-valent vertices can provide a physical representation of the DNA at the time of recombination.With this representation, 4-valent vertices correspond to the alignment of the recombination sites, and we model the actual recombination event as smoothing of these vertices. A. Angeleska, N. Jonoska, M. Saito, L. Landweber, Strategies for RNA-Guided DNA Recombination, in Algorithmic Bioprocesses (Condon, A.; Harel, D.; Kok, J.N.; Salomaa, A.; Winfree, E. , eds.) (2009) pp. 83-98. 10.1007/978-3-540-88869-7_6

Title: On existence of reporter strands in DNA-based graph structures Nataša Jonoska, Gang Wu, Nadrian C. Seeman We consider a generalization of an Eulerian path in (multi)graphs. Define a pseudo Eulerian (multi)graph to be a (multi)graph which contains a path that visits each edge once or twice, if an edge is visited twice, then this is done in opposite directions. We show that every multigraph is pseudo-Eulerian. This shows that every multigraph can be assembled by DNA such that there is a single strand that traces each edge in the graph at least once. N. Jonoska, G. Wu, N.C. Seeman, Existence of single-stranded reporters in DNA-based graph structures, Theoretical Computer Science 410:15 (2009) pp. 1448-1460. 10.1016/j.tcs.2008.12.004

Title: DNA Rearrangement through assembly graphs Angela Angeleska, Nataša Jonoska, Masahico Saito Motivated by DNA rearrangements and DNA homologous recombination modeled, we investigate smoothings on graphs that consist of only 4-valent and 1-valent rigid vertices, called assembly graphs. An assembly graph can be seen as a DNA representation of during certain recombination processes in which 4-valent vertices correspond to the alignment of the recombination sites. A single gene is modeled by a polygonal path in an assembly graph. A polygonal path makes a “right-angle” turn at every vertex, defining smoothings at the 4-valent vertices and therefore modeling the recombination process. We investigate minimal number of polygonal paths visiting all vertices of a given graph exactly once, and show that for every positive integer $$n$$ there are graphs that require at least $$n$$ such polygonal paths. We show that there is an embedding in three dimensional space of each assembly graph such that smoothings of vertices according to a given set of polygonal paths results in an unlinked graph. As some recombination processes may happen simultaneously, we characterize the subsets of vertices whose simultaneous smoothings keep a given gene in tact and give a characterization of all sequences of sets of vertices defining successive simultaneous smoothings that can realize complete gene rearrangement. A. Angeleska, N. Jonoska. M. Saito, DNA Rearrangement through assembly graphs. Discrete and Applied Math, 157 (2009) pp. 3020-3037. 10.1016/j.dam.2009.06.011

Title: RNA-Guided DNA Assembly Angela Angeleska, Nataša Jonoska, Masahico Saito, Laura F. Landweber We propose molecular models for homologous DNA recombination events that are guided by either double-stranded RNA (dsRNA) or single-stranded RNA (ssRNA) templates. The models are applied to explain DNA rearrangements in some groups of ciliates, such as Stylonychia or Oxytricha, where extensive gene rearrangement occurs during differentiation of a somatic macronucleus from a germline micronucleus. We describe a model for RNA-template guided DNA recombination, such that the template serves as a catalyst that remains unchanged after DNA recombination. This recombination can be seen as topological braiding of the DNA, with the template-guided alignment proceeding through DNA branch migration. We show that a virtual knot diagram can provide a physical representation of the DNA at the time of recombination. Schematically, the braiding process can be represented as a crossing in the virtual knot diagram. The homologous recombination corresponds to removal of the crossings in the knot diagram (called smoothing). We show that if all recombinations are performed in parallel (i.e., parallel smoothings of the crossings) then one of the resulting DNA molecules will always contain all of the gene segments in their correct, linear order, which produces the mature DNA sequence. A. Angeleska, N. Jonoska, M. Saito, L. Landweber, RNA-Guided DNA Assembly, Journal of Theoretical Biology 248:4 (2007) pp. 706-720. 10.1016/j.jtbi.2007.06.007

## Other papers related to the project

Title: The Palette Numbers of 2-bridge Knots Takuji Nakamura, Yasutaka Nakanishi, Masahico Saito, Shin Satoh We prove that for any odd $$n \geq 3$$, the $$n$$-palette number of any effectively $$n$$-colorable $$2$$-bridge knot is equal to $$2 + \lfloor \log_2 n\rfloor$$. Namely, there is an effectively $$n$$-colored diagram of the $$2$$-bridge knot such that the number of distinct colors that appeared in the diagram is exactly equal to $$2 + \lfloor \log_2 n\rfloor$$. T. Nakamura, Y. Nakanishi, M. Saito, S. Satoh. The Palette Numbers of 2-bridge Knots. Journal of Knot Theory and its Ramifications 26:8 (2017). 10.1142/S021821651750047X

Title: The 6- and 8-palette Numbers of Links Takuji Nakamura, Yasutaka Nakanishi, Masahico Saito, Shin Satoh For an effectively $$n$$-colorable link $$L$$, $$C_n^\ast(L)$$ stands for the minimum number of distinct colors used over all effective $$n$$-colorings of $$L$$. It is known that $$C_n^\ast(L)\geq 1 + \log_2 n$$ for any effectively $$n$$-colorable link $$L$$ with non-zero determinant. The aim of this paper is to prove that $$C_6^\ast(L) = 4$$ and $$C_8^\ast(L) = 5$$ for any effectively 6- and 8-colorable link $$L$$, respectively. For ribbon 2-links, we prove the same equalities for $$n = 6$$ and $$8$$, and $$C_{13}^\ast(L) = 5$$ for $$n = 13$$. T. Nakamura, Y. Nakanishi, M. Saito, S. Satoh. The 6- and 8-palette Numbers of Links. Topology and its Applications 222 (2017) pp 200-216. 10.1016/j.topol.2017.02.080

Title: Platform Color Designs for Interactive Molecular Arrangements Jasper Braun, Daniel A. Cruz, Nataša Jonoska It has been shown that alternating attachments of two types (species) of floating molecular (DNA based) tiles on a predesigned array that consists of communicating neighboring DNA tiles complementary to the floating tiles can dynamically simulate some types of cellular automata (CA). We show that the model can simulate any elementary one dimensional CA confirming the universal computational power of the model. We address the question of which design of the platform array provides communication across the whole plane. We show that for square tiles only the checkerboard arrangement of the two species can provide communication between any two tiles of the plane. On the other hand, there are an uncountable number of arrangements of two colors of hexagonal tiles on the plane which provide communication between any two tiles. J. Braun, D. Cruz, N. Jonoska. Platform Color Designs for Interactive Molecular Arrangements. Unconventional Computation and Natural Computation LNCS 10240 pp 69-81. 10.1007/978-3-319-58187-3_6

Title: Computation of Quandle 2-Cocycle Knot Invariants Without Explicit 2-Cocycles Edwin Clark, Larry A Dunning, Masahico Saito We explore a knot invariant derived from colorings of corresponding 11-tangles with arbitrary connected quandles. When the quandle is an abelian extension of a certain type the invariant is equivalent to the quandle 2-cocycle invariant. We construct many such abelian extensions using generalized Alexander quandles without explicitly finding 2-cocycles. This permits the construction of many 2-cocycle invariants without exhibiting explicit 2-cocycles. We show that for connected generalized Alexander quandles the invariant is equivalent to Eisermann's knot coloring polynomial. Computations using this technique show that the 2-cocycle invariant distinguishes all of the oriented prime knots up to 11 crossings and most oriented prime knots with 12 crossings including classification by symmetry: mirror images, reversals, and reversed mirrors. W.E. Clark, L.A. Dunning, M. Saito. Computation of Quandle 2-Cocycle Knot Invariants Without Explicit 2-Cocycles. Journal of Knot Theory and Its Ramifications 26: 7 (2017). 10.1142/S0218216517500353

Title: A Graph Isomorphism Condition and Equivalence of Reaction Systems Daniela Genova, Hendrik Jan Hoogeboom, Nataša Jonoska We consider global dynamics of reaction systems as introduced by Ehrenfeucht and Rozenberg. The dynamics is represented by a directed graph, the so-called transition graph, and two reaction systems are considered equivalent if their corresponding transition graphs are isomorphic. We introduce the notion of a skeleton (a one-out graph) that uniquely determines a directed graph. We provide the necessary and sufficient conditions for two skeletons to define isomorphic graphs. This provides a necessary and sufficient condition for two reactions systems to be equivalent, as well as a characterization of the directed graphs that correspond to the global dynamics of reaction systems. D. Genova, H.J. Hoogeboom, N. Jonoska. A Graph Isomorphism Condition and Equivalence of Reaction Systems. Theoretical Computer Science 701 (2017) pp 109-119. 10.1016/j.tcs.2017.05.019

Title: Counter Machines and Crystallographic Structures Nataša Jonoska, Milé Krajčevski, Gregory McColm One way to depict a crystallographic structure is by a periodic (di)graph, i.e., a graph whose group of automorphisms has a translational subgroup of finite index acting freely on the structure. We establish a relationship between periodic graphs representing crystallographic structures and an infinite hierarchy of intersection languages DCLd, d=0,1,2,..., within the intersection classes of deterministic context-free languages. We introduce a class of counter machines that accept these languages, where the machines with d counters recognize the class DCLd. An intersection of d languages in DCLi defines DCLd. We prove that there is a one-to-one correspondence between sets of walks starting and ending in the same unit of a d-dimensional periodic (di)graph and the class of languages in DCLd. The proof uses the following result: given a digraph Δ and a group G, there is a unique digraph Γ such that G≤AutΓ, G acts freely on the structure, and Γ/G≅Δ. N. Jonoska, M. Krajčevski, G. McColm. Counter Machines and Crystallographic Structures. Natural Computing 15:1 (2016) pp. 97-113. 10.1007/s11047-015-9527-0

Title: Traversal Languages Capturing Isomorphism Classes of Sierpinski Gaskets Nataša Jonoska, Milé Krajčevski, Gregory McColm We consider recursive structural assembly using regular d-dimensional simplexes such that a structure at every level is obtained by joining d+1 structures from a previous level. The resulting structures are similar to the Sierpinski gasket. We use intersection graphs and index sequences to describe these structures. We observe that for each d>:1 there are uncountably many isomorphism classes of these structures. Traversal languages that consist of labels of walks that start at a given vertex can be associated with these structures, and we find that these traversal languages capture the isomorphism classes of the structures. N. Jonoska, M. Krajčevski, G. McColm. Traversal Languages Capturing Isomorphism Classes of Sierpinski Gaskets. Unconventional Computation and Natural Computation LNCS 9726 (2016) pp. 155-167. 10.1007/978-3-319-41312-9_13

Title: Algebraic Properties of Quandle Extensions and Values of Cocycle Knot Invariants Edwin Clark, Masahico Saito Quandle 2-cocycles define invariants of classical and virtual knots, and extensions of quandles. We show that the quandle 2-cocycle invariant with respect to a non-trivial 2-cocycle is constant, or takes some other restricted form, for classical knots when the corresponding extensions satisfy certain algebraic conditions. In particular, if an abelian extension is a conjugation quandle, then the corresponding cocycle invariant is constant. Specific examples are presented from the list of connected quandles of order less than 48. Relations among various quandle epimorphisms involved are also examined. W.E. Clark, M. Saito. Algebraic properties of quandle extensions and values of cocycle knot invariants. Journal of Knot Theory and Its Ramifications, 25:14 (2016). 10.1142/S0218216516500802

Title: Quandle Identities and Homology Edwin Clark, Masahico Saito Quandle homology was defined from rack homology as the quotient by a subcomplex corresponding to idempotency, for invariance under the type I Reidemeister move. Similar subcomplexes have been considered for various identities of racks and moves on diagrams. We observe common aspects of these identities and subcomplexes; a quandle identity gives rise to a 2-cycle, the abelian extension with a 2-cocycle that vanishes on the 2-cycle inherits the identity, and a subcomplex is constructed from the identity. Specific identities are examined among small connected quandles. W.E. Clark, M. Saito. Quandle Identities and Homology. Contemporary Mathematics 689 (2017) pp 23-35. 10.1090/conm/689/13857

Title: Homology for Quandles with Partial Group Operations J. Scott Carter, Atsushi Ishii, Masahico Saito, Kokoro Tanaka A quandle is a set that has a binary operation satisfying three conditions corresponding to the Reidemeister moves. Homology theories of quandles have been developed in a way similar to group homology, and have been applied to knots and knotted surfaces. In this paper, a homology theory is defined that unifies group and quandle homology theories. A quandle that is a union of groups with the operation restricting to conjugation on each group component is called a multiple conjugation quandle (MCQ, defined rigorously within). In this definition, compatibilities between the group and quandle operations are imposed which are motivated by considerations on colorings of handlebody-links. A homology theory defined here for MCQs take into consideration both group and quandle operations, as well as their compatibility. The first homology group is characterized, and the notion of extensions by 2-cocycles is provided. Degenerate subcomplexes are defined in relation to simplicial decompositions of prismatic (products of simplices) complexes and group inverses. Cocycle invariants are also defined for handlebody-links. S. Carter, A. Ishii, M. Saito, K. Tanaka. Homology for Quandles with Partial Group Operations. Pacific Journal of Mathematics 287:1 (2017) pp 19-48. 10.2140/pjm.2017.287.19

Title: Molecular ping-pong Game of Life on a two-dimensional DNA origami array Nataša Jonoska, Nadrian C. Seeman We propose a design for programmed molecular interactions that continuously change molecular arrangements in a predesigned manner. We introduce a model where environmental control through laser illumination allows platform attachment/detachment oscillations between two floating molecular species. The platform is a two-dimensional DNA origami array of tiles decorated with strands that provide both, the floating molecular tiles to attach and to pass communicating signals to neighbouring array tiles. In particular, we show how algorithmic molecular interactions can control cyclic molecular arrangements by exhibiting a system that can simulate the dynamics similar to two-dimensional cellular automata on a DNA origami array platform. N. Jonoska, N.C. Seeman. Molecular ping-pong Game of Life on a two-dimensional DNA origami array. Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 373:2046 (2015). 10.1098/rsta.2014.0215

Title: Dynamic Simulation of 1D Cellular Automata in the Active aTAM Nataša Jonoska, Daria Karpenko, Shinnosuke Seki The Active aTAM is a tile based model for self-assembly where tiles are able to transfer signals and change identities according to the signals received. We extend Active aTAM to include deactivation signals and thereby allow detachment of tiles. We show that the model allows a dynamic simulation of cellular automata with assemblies that do not record the entire computational history but only the current updates of the states, and thus provide a way for (a) algorithmic dynamical structural changes in the assembly and (b) reusable space in self-assembly. The simulation is such that at a given location the sequence of tiles that attach and detach corresponds precisely to the sequence of states the synchronous cellular automaton generates at that location. N. Jonoska, D. Karpenko, S. Seki. Dynamic Simulation of 1D Cellular Automata in the Active aTAM. New Generation Computing, 33:3 (2015) pp 271-295. 10.1007/s00354-015-0302-7

Title: A Signal-Passing DNA-Strand-Exchange Mechanism for Active Self-Assembly of DNA Nanostructures. Jennifer E Padilla, Ruojie Sha, Martin Kristiansen, Martin Kristiansen, Nataša Jonoska, Nadrian C. Seeman DNA nanostructured tiles play an active role in their own self-assembly in the system described herein whereby they initiate a binding event that produces a cascading assembly process. We present DNA tiles that have a simple but powerful property: they respond to a binding event at one end of the tile by passing a signal across the tile to activate a binding site at the other end. This action allows sequential, virtually irreversible self-assembly of tiles and enables local communication during the self-assembly process. This localized signal-passing mechanism provides a new element of control for autonomous self-assembly of DNA nanostructures. J. E. Padilla, R. Sha, M. Kristiansen, J. Chen, N. Jonoska, N.C. Seeman. A Signal-Passing DNA-Strand-Exchange Mechanism for Active Self-Assembly of DNA Nanostructures. Angewandte Chemie Int Ed Engl, 54:20 (2015) pp.5939-42. 10.1002/anie.201500252

Title: Quandle coloring and cocycle invariants of composite knots and abelian extensions Edwin Clark, Masahico Saito, Leandro Vendramin Quandle colorings and cocycle invariants are studied for composite knots, and applied to chirality and abelian extensions. The square and granny knots, for example, can be distinguished by quandle colorings, so that a trefoil and its mirror can be distinguished by quandle invariants of composite knots. We investigate this and related phenomena. Quandle cocycle invariants are studied in relation to the connected sum, and formulas are given for computing the cocycle invariant from the number of colorings of composite knots. Relations to corresponding abelian extensions of quandles are studied, and extensions are examined for the table of small connected quandles, called Rig quandles. Computer calculations are presented, and summaries of outputs are discussed. W. Edwin Clark, Masahico Saito, Leandro Vendramin, Quandle Coloring and Cocycle Invariants of Composite Knots and Abelian Extensions. Journal of Knot Theory and Its Ramifications 25:5 (2016) 34 pp. 10.1142/S0218216516500243

Title: Languages Associated with Crystallographic Symmetry Nataša Jonoska, Gregory McColm, Milé Krajčevski We establish a relationship between periodic graphs representing crystallographic structures and an infinite hierarchy of intersection languages DCLd, d=0,1,2,..., within the intersection classes of deterministic context-free languages. We introduce a class of counter machines that accept these languages, where the machines with d counters recognize the class DCLd. Each language in DCLd is an intersection of d languages in DCL1. We prove that there is a one-to-one correspondence between sets of walks starting and ending in the same unit of a d-dimensional periodic (di)graph and the class of languages in DCLd. N. Jonoska, M. Krajčevski, G. McColm, Languages Associated with Crystallographic Symmetry Unconventional Computing and Natural Computing (O. Ibarra et al. eds) LNCS 8553 (2014) 216--228 (best paper award). 10.1007/978-3-319-08123-6_18

Title: A Stronger Square Conjecture on Binary Words Nataša Jonoska, Florin Manea, Shinnosuke Seki We propose a stronger conjecture regarding the number of distinct squares in a binary word. Fraenkel and Simpson conjectured in 1998 that the number of distinct squares in a word is upper bounded by the length of the word. Here, we conjecture that in the case of a word of length n over the alphabet $$\{a,b\}$$, the number of distinct squares is upper bounded by $$n\frac{2k-1}{2k+2}$$, where $$k$$ is the least of the number of $$a$$'s and the number of $$b$$'s. We support the conjecture by showing its validity for several classes of binary words. We also prove that the bound is tight. N. Jonoska, F. Manea, S. Seki A Stronger Square Conjecture on Binary Words in SOFSEM 2014 (V. Geffert, B. Preneel, B. Rovan, J. Stuller and A M. Tjoa eds) LNCS 8327 (2014) 339--351. 10.1007/978-3-319-04298-5_30

Title: Quandle colorings of knots and applications Edwin Clark, Mohamed Elhamdadi, Masahico Saito, Timothy Yeatman We present a set of 26 finite quandles that distinguish (up to reversal and mirror image) by number of colorings, all of the 2977 prime oriented knots with up to 12 crossings. We also show that 1058 of these knots can be distinguished from their mirror images by the number of colorings by quandles from a certain set of 23 finite quandles. We study the colorings of these 2977 knots by all of the 431 connected quandles of order at most 35 found by L. Vendramin. Among other things, we collect information about quandles that have the same number of colorings for all of the 2977 knots. For example, we prove that if $$Q$$ is a simple quandle of prime power order then $$Q$$ and the dual quandle $$Q^*$$ of $$Q$$ have the same number of colorings for all knots and conjecture that this holds for all Alexander quandles $$Q$$. We study a knot invariant based on a quandle homomorphism $$f:Q_1 \rightarrow Q_0$$. We also apply the quandle colorings we have computed to obtain some new results for the bridge index, the Nakanishi index, the tunnel number, and the unknotting number. In an appendix we discuss various properties of the quandles in Vendramin's list. Links to the data computed and various programs in C, GAP and Maple are provided. W. Edwin Clark, Mohamed Elhamdadi, Masahico Saito, Timothy Yeatman, Quandle colorings of knots and applications, Journal of Knot Theory and Its Ramifications, 23 (2014) 1450035 (29 pp). 10.1142/S0218216514500357

Title: Active Tile Self-Assembly, Part 2: Self-Similar Structures and Structural Recursion Nataša Jonoska, Daria Karpenko We introduce a mathematical framework to describe self-similarity and structural recursion within the active tile self-assembly model introduced in [6], thereby providing a connection between substitution tiling and algorithmic self-assembly. We show that one such structurally recursive assembly system can simulate the dynamics of the self-similar substitution tiling known as the L-shape tiling. Nataša Jonoska and Daria Karpenko, Int. J. Found. Comput. Sci. 25, 165 (2014). 10.1142/S0129054114500099

Title: Active Tile Self-Assembly, Part 1: Universality at Temperature 1 Nataša Jonoska, Daria Karpenko We present an active tile assembly model which extends Winfree‘s abstract tile assembly model [35] to tiles that are capable of transmitting and receiving binding site activation signals. We also prove that this model has universal computational power in 2D at temperature 1 by showing an active tile assembly construction that simulates one-dimensional cellular automata in 2D at temperature 1. Nataša Jonoska and Daria Karpenko, Int. J. Found. Comput. Sci. 25, 141 (2014). 10.1142/S0129054114500087

Title: Biologically Relevant Molecular Transducer with Increased Computing Power and Iterative Abilities Tamar Ratner, Ron Piran, Nataša Jonoska, Ehud Keinan As computing devices, which process data and interconvert information, transducers can encode new information and use their output for subsequent computing, offering high computational power that may be equivalent to a universal Turing machine. We report on an experimental DNA-based molecular transducer that computes iteratively and produces biologically relevant outputs. As a proof of concept, the transducer accomplished division of numbers by 3. The iterative power was demonstrated by a recursive application on an obtained output. This device reads plasmids as input and processes the information according to a predetermined algorithm, which is represented by molecular software. The device writes new information on the plasmid using hardware that comprises DNA-manipulating enzymes. The computation produces dual output: a quotient, represented by newly encoded DNA, and a remainder, represented by E. coli phenotypes. This device algorithmically manipulates genetic codes. Tamar Ratner, Ron Piran, Natasha Jonoska, Ehud Keinan, Biologically Relevant Molecular Transducer with Increased Computing Power and Iterative Abilities, Chemistry & Biology, Volume 20, Issue 5, 23 May 2013, Pages 726-733, ISSN 1074-5521 10.1016/j.chembiol.2013.02.016

Title: Two-dimensional Languages and Cellular Automata Egor Dolzhenko, Nataša Jonoska We initiate a study of one-dimensional cellular automata through two-dimensional languages. The time evolution of a bi-infinite configuration of a one-dimensional cellular automaton can be visualized as a half-plane array of symbols. The set of rectangular blocks extracted from such arrays forms a two-dimensional (picture) language. If this picture language is factorial-local, we call the cellular automaton factorial-local. We show that CA are factorial-local if and only if for sufficiently large $$k$$ all their $$k$$-traces are shifts of finite type, and therefore are properly included in the class of regular cellular automata. We show that it is decidable whether a given set of blocks defines a factorial-local CA with a given radius, but the general membership problem for this class of cellular automata is undecidable. E. Dolzhenko, N. Jonoska, Two-dimensional Languages and Cellular Automata, International Journal of Foundations of Computer Science 23:1 (2012) pp. 185-206. 10.1142/S0129054112500037

Title: A Programmable Transducer Self-Assembled from DNA Banani Chakraborty, Nataša Jonoska, Nadrian C. Seeman A transducer consists of an input/output alphabet, a finite set of states, and a transition function. From an input symbol applied to a given state, the transition function determines the next state, and an output symbol. Using DNA, we have constructed a transducer that divides a number by 3. The input consists of a series of individually addressable 2-state DNA nanomechanical devices that control the orientations of a group of flat 6-helix DNA motifs; these motifs have edge domains tailed in sticky ends corresponding to the numbers 0 and 1. Three-domain DNA molecules (TX tiles) act as computational tiles that correspond to the transitions that the transducer can undergo. The output domain of these TX tiles contains sticky ends that also correspond to 0 or 1. Two different DNA tiles can chelate these output domains: A 5 nm gold nanoparticle is attached to the chelating tile that binds to 0-domains and a 10 nm gold nanoparticle is attached to the chelating tile that binds to 1-domains. The answer to the division is represented by the series of gold nanoparticles, which can be interpreted as a binary number. The answers of the computation are read out by examination of the transducer complexes under a transmission electron microscope. The start or end points of the output sequence can be indicated by the presence of a 15 nm gold nanoparticle. This work demonstrates two previously unreported features integrated in a single framework: [1] a system that combines DNA algorithmic self-assembly with DNA nanomechanical devices that control that input, and [2] the arrangement of non-DNA species, here metallic nano-particles, through DNA algorithmic self-assembly. The nanomechanical devices are controlled by single-stranded DNA strands, allowing multiple input sequences to be applied to the rest of the system, thus guiding the algorithmic self-assembly to a variety of outputs. B. Chakraborty, N. Jonoska, N. C. Seeman, A Programmable Transducer Self-Assembled from DNA, Chemical Science, The Royal Society of Chemistry 3 (2012) pp. 168-176. 10.1039/c1sc00523e

Title: Forbidding and enforcing conditions on Graphs Daniela Genova, Nataša Jonoska This paper introduces a way to define classes of graphs based on forbidding and enforcing boundary conditions. Forbidding conditions prevent a graph to have certain combinations of subgraphs and enforcing conditions impose certain subgraph structures. We say that a class of graphs is an fe-class if the class can be defined through forbidding and enforcing conditions. We investigate properties of fe-systems and characterize familiar classes of graphs such as paths and cycles, trees, bi-partite, complete, Eulerian, and $$k$$-regular graphs as fe-classes. D. Genova, N. Jonoska, Forbidding and enforcing conditions on Graphs, Theoretical Computer Science 429 (2012) pp. 108-117. 10.1016/j.tcs.2011.12.029

Title: Computing by molecular self-assembly Nataša Jonoska, Nadrian C. Seeman The paper reviews two computing models by DNA self-assembly whose proof of principal have recently been experimentally confirmed. The first model incorporates DNA nano-devices and triple cross-over DNA molecules to algorithmically arrange non DNA species. This is achieved by simulating a finite state automaton with output where golden nanoparticles are assembled to read-out the result. In the second model, a complex DNA molecule representing a graph emerges as a solution of a computational problem. This supports the idea that in molecular self-assembly computing it may be necessary to develop the notion of shape processing besides the classical approach through symbol processing. N. Jonoska, N.C. Seeman, Computing by molecular self-assembly, Interface Focus 2 (2012) 504-511 10.1098/rsfs.2011.0117

Title: Connected Quandles Associated with Pointed Abelian Groups Edwin Clark, Mohamed Elhamdadi, Xiang-Dong Hou, Masahico Saito, Timothy Yeatman A quandle is a self-distributive algebraic structure that appears in quasi-group and knot theories. For each abelian group $$A$$ and $$c \in A$$ we define a quandle $$G(A,c)$$ on $$\mathbb{Z}_{3} \times A$$. These quandles are generalizations of a class of non-medial Latin quandles defined by V. M. Galkin so we call them Galkin quandles. Each $$G(A,c)$$ is connected but not Latin unless $$A$$ has odd order. $$G(A,c)$$ is non-medial unless $$3A = 0$$. We classify their isomorphism classes in terms of pointed abelian groups, and study their various properties. A family of symmetric connected quandles is constructed from Galkin quandles, and some aspects of knot colorings by Galkin quandles are also discussed. W. Edwin Clark, Mohamed Elhamdadi, Xiang-dong Hou, Masahico Saito and Timothy Yeatman, Pacific Journal of Mathematics, Vol. 264, No. 1 (2013) 31-60 10.2140/pjm.2013.264.31

Title: On Stoichometry for the Asssembly of Flexible-Tile DNA Complexes Nataša Jonoska, Gregory McColm, Ana Staninska Given a set of flexible branched junction DNA molecules with sticky-ends (building blocks), called here “tiles”, we consider the problem of determining the proper stoichiometry such that all sticky-ends could end up connected. In general, the stoichiometry is not uniform, and the goal is to determine the proper proportion (spectrum) of each type of molecule within a test tube to allow for complete assembly. According to possible components that assemble in complete complexes we partition multisets of tiles, called here “pots”, into classes: unsatisfiable, weakly satisfiable, satisfiable and strongly satisfiable. This classification is characterized through the spectrum of the pot, and it can be computed in PTIME using the standard Gauss-Jordan elimination method. We also give a geometric description of the spectrum as a convex hull within the unit cube. N. Jonoska, G. McColm, A. Staninska, On Stoichometry for the Asssembly of Flexible-Tile DNA Complexes, Natural Computing 10 (2011) pp. 1121-1141. 10.1007/s11047-009-9169-1

Title: Transducer Generated Arrays of Robotic Nanoarms Egor Dolzhenko, Nataša Jonoska, Nadrian C. Seeman We consider sets of two-dimensional arrays, called here transducer generated languages, obtained by iterative applications of transducers (finite state automata with output). Each transducer generates a set of blocks of symbols such that the bottom row of a block is an input string accepted by the transducer and, by iterative application of the transducer, each row of the block is an output of the transducer on the preceding row. We show how these arrays can be implemented through molecular assembly of triple crossover DNA molecules. Such assembly could serve as a scaffold for arranging molecular robotic arms capable of simultaneous movements. We observe that transducer generated languages define a class of languages which is a proper subclass of recognizable picture languages, but it contains the class of all factorial local two-dimensional languages. By taking the average growth rate of the number of blocks in the language as a measure of its complexity, we further observe that arrays with high complexity patterns can be generated in this way. Dolzhenko, E., Jonoska, N., Seeman, N. C., Natural Computing. 9:2 (2010), pp.437-455. 10.1007/s11047-009-9157-5

Title: DNA cages with icosahedral symmetry in bionanotechnology Nataša Jonoska, Anne Taormina, Reidun Twarock Blueprints for polyhedral cages with icosahedral symmetry made of circular DNA molecules are provided. The basic rule is that every edge of the cage is met twice in opposite directions by the DNA strand(s), and vertex junctions are realized by a set of admissible junction types. As nanocontainers for cargo storage and delivery, the icosidodecahedral cages are of special interest because they have the largest volume per surface ratio of all cages discussed here. N. Jonoska, A. Taormina, R. Twarock, DNA cages with icosahedral symmetry in bionanotechnology, Algorithmic Bioprocesses (Condon, A.; Harel, D.; Kok, J.N.; Salomaa, A.; Winfree, E. , eds.) (2009) pp. 141-158. 10.1007/978-3-540-88869-7_9

Title: Complexity classes for self-assembling flexible tiles Nataša Jonoska, Gregory McColm We present a theoretical model for self-assembling DNA tiles with flexible branches. We encode an instance of a “problem” as a pot of such tiles for which a “solution” is an assembled complete complex without any free sticky ends. Using the number of tiles in an assembled complex as a measure of complexity we show how NTIME classes (such as NP and NEXP) can be represented with corresponding classes of the model. N. Jonoska, G. L. McColm, Complexity classes for self-assembling flexible tiles, Theoretical Computer Science 410 4-5 (2009) pp. 332-346. 10.1016/j.tcs.2008.09.054

Title: Framed versus Unframed Two Dimensional Languages Marcella Anselmo, Nataša Jonoska, Marina Madonia Two-dimensional languages are nowadays a topic of interest for a lot of researchers in different frameworks. Actually the research follows two main directions. There are people interested in the tiling of the infinite plane and other ones more involved in the formal investigation of sets of finite two-dimensional blocks (or pictures), as a generalization of one-dimensional string languages. This paper has the ambition to bridge these two points of view, showing some similarities and differences. Differences arise since boundaries provide some information. Boundaries can limit or force the size and the content of pictures in a language. Furthermore, constraints fixed on a local language can considerably affect the ambiguity (i.e. number of pre-images) of its projection. M. Anselmo, N. Jonoska, M. Madonia, Framed versus Unframed Two Dimensional Languages, SOFSEM 09 (M. Nielsen et al. eds) LNCS 5404 (2009) pp. 79-92. 10.1007/978-3-540-95891-8_11

Title: Finite state automata representing two-dimensional subshifts Joni B. Pirnot, Nataša Jonoska A new type of two-dimensional automaton has been defined to recognize a class of two-dimensional shifts of finite type having the property that every admissable block found within the related local picture language can be extended to a point of the subshift. Here it is shown that this automaton accurately represents the image of the represented two-dimensional shift of finite type under a block code. It is then shown that these automata can be used to check for a certain type of two-dimensional transitivity in the factor language of the corresponding shift space and how this relates to periodicity in the two-dimensional case. The paper closes with a notion of “follower sets” that are used to reduce the size of the automata representing two-dimensional sofic shifts. N. Jonoska, J. Pirnot, Finite state automata representing two-dimensional subshifts, Theoretical Computer Science 410:37 (2009) pp. 3504-3512. 10.1016/j.tcs.2009.03.015

Title: Reciprocal DNA Nanomechanical Devices Controlled by the Same Set Strands Chunhua Liu, Nataša Jonoska, Nadrian C. Seeman Reciprocating devices are a key features in macroscopic machines. We have adapted the DNA PX-JX2 device to a reciprocal format. The PX-JX2 device is a robust sequence-dependent nanomachine, whose state of is established by a pair of control strands that set it to be either in the PX state or in the JX2 state. The two states differ by a half-turn rotation between their ends. Here we report the construction of a pair of reciprocal PX-JX2 devices, wherein the control strands leading to the PX state in one device lead to the JX2 state in the other device, and vice versa. The formation, transformation and reciprocal motions of these two device systems are confirmed using gel electrophoresis, and atomic force microscopy. This system is likely to be of use for molecular robotic applications where reciprocal motions are of value, in addition its inherent contribution to molecular choreography and molecular aesthetics. C. Liu, N. Jonoska, N. C. Seeman, Reciprocal DNA Nanomechanical Devices Controlled by the Same Set Strands, Nano Letters 9:7 (2009) pp. 2641-2647. 10.1021/nl901008k

Title: Construction of a DNA Nano-Object Directly Demonstrates Computation Gang Wu, Nataša Jonoska, Nadrian C. Seeman We demonstrate a computing method in which a DNA nano-object representing the solution of a problem emerges as a result of self-assembly. We report an experiment in which three-vertex colorability for a 6-vertex graph with 9 edges is solved by constructing a DNA molecule representing the colored graph itself. Our findings show that computation based on “shape processing” is a viable alternative to symbol processing when computing by molecular self-assembly. G. Wu, N. Jonoska, N.C. Seeman, Construction of a DNA Nano-Object Directly Demonstrates Computation, BioSystems 98 (2009) pp. 80-84. 10.1016/j.biosystems.2009.07.004

Title: Describing Self-assembly of Nanostructures Nataša Jonoska, Gregory McColm We outline an algebraic model for describing complex structures obtained through self-assembly of molecular building blocks and show that, with this model, the assembled structure can be associated to a language and it can be determined up to congruence. N. Jonoska, G. McColm, Describing Self-assembly of Nanostructures, SOFSEM (V. Geffert et al eds.) Springer LNCS 4910 (2008) pp. 66-73. 10.1007/978-3-540-77566-9_6

Title: Blueprints for dodecahedral DNA cages Nataša Jonoska, Reidun Twarock Cage structures engineered from nucleic acids are of interest in nanotechnology, for example as a means of drug delivery (Destito et al 2007). Until now, most experimentally realized DNA cages have crystallographic symmetry, such as the shape of a cube (Chen and Seeman 1991 Nature 350 631-3), a tetrahedron (Goodman et al 2005 Science 310 1661-5), an octahedron (Shih et al 2004 Nature 427 618-21) or a truncated octahedron (Zhang and Seeman 1994 J. Am. Chem. Soc. 116 1661-9). Two examples of cages with non-crystallographic symmetry, a dodecahedron and a buckyball, have been realized recently (He et al 2008 Nature 452 198-201). A characteristic feature of these realizations is the fact that the cages are built from a number of identical building blocks called tiles: 20 for the case of the dodecahedron, and 60 for the case of the buckyball. We derive here a blueprint for the organization of nucleic acid in a dodecahedral cage such that the final product has a minimal number of strands. In particular, we show that a dodecahedral cage can be realized in terms of only two circular DNA molecules. We focus on the dodecahedral cage, because the volume to surface ratio of such a cage is larger than that of its crystallographic counterparts given the same fixed radial distance of the polyhedral vertices from the centre of the structure, whilst still requiring a smaller complexity than the truncated icosahedron (buckyball). We therefore expect that the dodecahedral DNA cages discussed here may be of interest in further applications in nanotechnology. N. Jonoska, R. Twarock, Blueprints for dodecahedral DNA cages, J. of Physics A: Mathematical and Theoretical 41 (2008) 304043 (14pp). 10.1088/1751-8113/41/30/304043

Title: Involution join and solid codes Nataša Jonoska, Lila Kari, Kalpana Mahalingam In this paper we study a generalization of the classical notions of solid codes and comma-free codes motivated by DNA based computing. This research extends the study of coding properties of DNA languages suitable for computations, i.e., properties that ensure that no unintended Watson-Crick bonds are formed between the strings of the language. The mathematical formalization of the Watson-Crick binding between two DNA single strands is captured by the notion of an involution function: a function $$\theta$$ such that $$\theta^2$$ equals the identity. An involution code refers to any of the generalizations of the classical notions of codes in which the identity function is replaced by an involution function. In this paper we study two such involution codes: $$\theta$$-solid codes and $$\theta$$-join codes. We investigate closure properties of these codes, as well as necessary conditions for $$\theta$$-solid codes to be maximal. We also discuss the properties of codes that are themselves not $$\theta$$-comma free but can be split into a union of subcodes that are $$\theta$$-comma free. N. Jonoska, L. Kari, K. Mahalingam, Involution join and solid codes, Fundamenta Informaticae 86 1-2 (2008) pp. 127-142. 10.1007/11779148_18

Title: Biomolecular Automata Nataša Jonoska As an emerging new research area, DNA nano engineering and computation, extends into other fields such as nanotechnology and material design, and is developing into a new sub-discipline of science and engineering. This chapter provides a brief overview of the design and development of computational devices by DNA. In particular two approaches for biomolecular models of automata are described. The first model is based on using action of restriction endonucleases and the second is based on DNA self-assembly and DNA nanomolecular devices. N. Jonoska, Biomolecular Automata in NanoBioTechnology, Bioinspired Devices and Materials of the Future, Chapter 11, (S. Oded, I. Levi eds.) Humana Press (2008) pp. 267-299. 10.1007/978-1-59745-218-2_11

Title: On complexity of two dimensional languages generated by transducers Egor Dolzhenko, Nataša Jonoska We consider two-dimensional languages, called here 2d transducer languages, generated by iterative applications of transducers (finite state automata with output). To each transducer a two-dimensional language consisting of blocks of symbols is associated: the bottom row of a block is an input string accepted by the transducer and, by iterative application of the transducer, each row of the block is an output of the transducer on the preceding row. We observe that this class of languages is a proper subclass of recognizable picture languages containing the class of all factorial local 2d languages. By taking the average growth rate of the number of blocks in the language as a measure of its complexity, also known as the entropy of the language, we show that every entropy value of a one-dimensional regular language can be obtained as an entropy value of a 2d transducer language. E. Dolzhenko, N. Jonoska, On complexity of two dimensional languages generated by transducers in Implementation and Application of Automata (O. Ibaraa et al eds.) Springer LNCS 5148 (2008) pp. 181-190. 10.1007/978-3-540-70844-5_19

Title: Defining Structures through Forbidding and Enforcing Constraints Daniela Genova, Nataša Jonoska This paper introduces a new way of modeling classes of physical and biochemical processes and structures based on boundary conditions that are called “forbidden” and “enforced”. The model of forbidding-enforcing systems (fe-systems) is presented in a general categorical sense and we use three specific examples of categories to illustrate three different phenomena. The hydrogen and covalent bonds of DNA, as well as, splicing DNA by enzymes, and recombination is illustrated with fe-systems on the category of languages (1-dimensional structures). Fe-systems over the simple category on sets can define the solutions to a computational problem, the $$k$$-colorability problem (information processing). By using the category of graphs fe-systems model graphs as an abstraction of 3-D structures such that a characterization of familiar classes of graphs, such as trees, bi-partite graphs, and complete graphs are obtained. D. Genova, N. Jonoska, Defining Structures through Forbidding and Enforcing Constraints, Physica B: Physics of Condensed Matter 394:2 (2007) pp. 306-310. 10.1016/j.physb.2006.12.069

Title: Automata Representing Two-dimensional Subshifts Nataša Jonoska, Joni B. Pirnot We employ a two-dimensional automaton to recognize a class of two-dimensional shifts of finite type having the property that every admissable block found within the related local picture language can be extended to a point of the subshift. Here, we show that the automaton accurately represents the image of the represented two-dimensional shift of finite type under a block code. We further show that such automata can be used to check for a certain type of two-dimensional transitivity in the factor language of the corresponding shift space and how this relates to periodicity in the two-dimensional case. The paper closes with a notion of “follower sets” used to reduce the size of the automata representing two-dimensional sofic shifts. N. Jonoska, J. Pirnot, Finite State Automata Representing Two-dimensional Subshifts, CIAA 2007 (J. Holub, J. Žd’árek eds.) Springer LNCS 4783 (2007) pp. 277-289. 10.1007/978-3-540-76336-9_26

Home Background Activities Data Software Multimedia Links Publications Members