| Title: | Skein Theoretic Approach to Yang-Baxter Homology |
|---|---|
| Authors: | Mohamed Elhamdadi, Masahico Saito, Emanuele Zappala |
| Abstract: | We introduce skein theoretic techniques to compute the Yang-Baxter (YB) homology and cohomology groups of the \(R\)-matrix corresponding to the Jones polynomial. More specifically, we show that the YB operator \(R\) for Jones, normalized for homology, admits a skein decomposition \(R = I + \beta\alpha\), where \(\alpha : V^{\otimes 2} \to k \) is a "cup" pairing map and \(\beta: k\to V^{\otimes 2}\) is a "cap" copairing map, and differentials in the chain complex associated to \(R\) can be decomposed into horizontal tensor concatenations of cups and caps. We apply our skein theoretic approach to determine the second and third YB homology groups, confirming a conjecture of Przytycki and Wang. Further, we compute the cohomology groups of \(R\), and provide computations in higher dimensions that yield some annihilations of submodules. |
| Citation: | M. Elhamdadi, M. Saito, E. Zappala. Skein Theoretic Approach to Yang-Baxter Homology. Topology and its Applications 302 (2021) 107836. |
| DOI: | 10.1016/j.topol.2021.107836 |
| Title: | Higher Arity Self-distributive Operations in Cascades and Their Cohomology |
|---|---|
| Authors: | Mohamed Elhamdadi, Masahico Saito, Emanuele Zappala |
| Abstract: | We investigate constructions of higher arity self-distributive operations, and give relations between cohomology groups corresponding to operations of different arities. For this purpose we introduce the notion of mutually distributive n-ary operations generalizing those for the binary case, and define a cohomology theory labeled by these operations. A geometric interpretation in terms of framed links is described, with the scope of providing algebraic background of constructing 2-cocycles for framed link invariants. This theory is also studied in the context of symmetric monoidal categories. Examples from Lie algebras, coalgebras and Hopf algebras are given. |
| Citation: | M. Elhamdadi, M. Saito, E. Zappala. Higher Arity Self-distributive Operations in Cascades and Their Cohomology. Journal of Algebra and Its Applications 20:07 (2021) 2150116. |
| DOI: | 10.1142/S0219498821501164 |
| Title: | Heap and Ternary Self-distributive Cohomology |
|---|---|
| Authors: | Mohamed Elhamdadi, Masahico Saito, Emanuele Zappala |
| Abstract: | Heaps are algebraic structures endowed with para-associative ternary operations, bijectively exemplified by groups via the operation \((x,y,z)\mapsto xy^{-1}z\). They are also ternary self-distributive and have a diagrammatic interpretation in terms of framed links. Motivated by these properties, we define para-associative and heap cohomology theories and also a ternary self-distributive cohomology theory with abelian heap coefficients. We show that one of the heap cohomologies is related to group cohomology via a long exact sequence. Moreover, we construct maps between second cohomology groups of normalized group cohomology and heap cohomology, and show that the latter injects into the ternary self-distributive second cohomology group. We proceed to study heap objects in symmetric monoidal categories providing a characterization of pointed heaps as involutory Hopf monoids in the given category. Finally, we prove that heap objects are also "categorically" self-distributive in an appropriate sense. |
| Citation: | M. Elhamdadi, M. Saito, E. Zappala. Heap and Ternary Self-distributive Cohomology. Communications in Algebra 49:6 (2021) pp. 2378-2401. |
| DOI: | 10.1080/00927872.2020.1871484 |
| Title: | DNA Origami Words, Graphical Structures and Their Rewriting Systems |
|---|---|
| Authors: | James Garrett, Nataša Jonoska, Hwee Kim, Masahico Saito |
| Abstract: | We classify rectangular DNA origami structures according to their scaffold and staples organization by associating a graphical representation to each scaffold folding. Inspired by well studied Temperley-Lieb algebra, we identify basic modules that form the structures. The graphical description is obtained by 'gluing' basic modules one on top of the other. To each module we associate a symbol such that gluing of modules corresponds to concatenating the associated symbols. Every word corresponds to a graphical representation of a DNA origami structure. A set of rewriting rules defines equivalent words that correspond to the same graphical structure. We propose two different types of basic module structures and corresponding rewriting rules. For each type, we provide the number of all possible structures through the number of equivalence classes of words. We also give a polynomial time algorithm that computes the shortest word for each equivalence class. |
| Citation: | J. Garrett, N. Jonoska, H. Kim, M. Saito. DNA Origami Words, Graphical Structures and Their Rewriting Systems. Natural Computing 20 (2021) pp. 217-231. |
| DOI: | 10.1007/s11047-020-09825-z |
| Title: | SDRAP for Annotating Scrambled or Rearranged Genomes |
|---|---|
| Authors: | Jasper Braun, Rafik Neme, Yi Feng, Laura F. Landweber, Nataša Jonoska |
| Abstract: | DNA rearrangements are of importance in various contexts, such as in vertebrate immunity, and cancer genome instability. The single-celled eukaryote Oxytricha trifallax undergoes massive and reproducible genome rearrangement during post-zygotic development, making it a compelling model organism to study DNA rearrangements. To date, computational tools for the extraction and analysis of rearrangement annotations lack transparency and rely on assumptions that may not hold for all analyzed data, leading to irreproducibility of results and loss of information through data filtering or misrepresentation. This work introduces a theoretical framework and concrete procedure to systematically extract and analyze annotations from assemblies of rearrangement precursor and product data. The software makes no assumptions about the structure of the rearrangements, and permits the user to select parameters to suit the data. An implementation of the procedure as a web application is discussed and tested. The resulting annotations provide an improvement over previous annotations in the following manner. (a) SDRAP achieves more complete precursor-product mapping then previous software (b) the software allows for full transparency of all parameters used during the annotation and therefore facilitates reproducible results, and (c) this parameter transparency makes SDRAP suitable for comparison of genomic data from different sources, including cancer genomes. |
| Title: | Secondary Structure Ensemble Analysis via Community Detection |
|---|---|
| Authors: | Huijing Du, Margherita Maria Ferrari, Christine Heitsch, Forrest Hurley, Christine V. Mennicke, Blair D. Sullivan, Bin Xu |
| Abstract: | We explored the extent to which graph algorithms for community detection can improve the mining of structural information from the predicted Boltzmann/Gibbs ensemble for the biological objects known as RNA secondary structures. As described, a new computational pipeline was developed, implemented, and tested against the prior method RNAStructProfiling. Since the new approach was judged to provide more structural information in 75% of the test cases, this proof-of-principle analysis supports efforts to improve the data mining of RNA secondary structure ensembles. |
| Citation: | H. Du, M. M. Ferrari, C. Heitsch, F. Hurley, C. V. Mennicke, B. D. Sullivan, B. Xu. Secondary Structure Ensemble Analysis via Community Detection. Using Mathematics to Understand Biological Complexity (R. Segal, B. Shtylla, S. Sindi, Eds.) Springer, Association for Women in Mathematics Series, (2021) pp. 55-81. |
| DOI: | 10.1007/978-3-030-57129-0_4 |
| Title: | Modeling RNA:DNA Hybrids with Formal Grammars |
|---|---|
| Authors: | Nataša Jonoska, Nida Obatake, Svetlana Poznanović, Candice Price, Manda Riehl, Mariel Vazquez |
| Abstract: | R-loops are nucleic acid structures consisting of a DNA:RNA hybrid and a DNA single strand. They form naturally during transcription when the nascent RNA hybridizes to the template DNA, forcing the coding DNA strand to wrap around the RNA:DNA duplex. Although formation of R-loops can have deleterious effects on genome integrity, there is evidence of their role as potential regulators of gene expression and DNA repair. Here we initiate an abstract model based on formal grammars to describe RNA:DNA interactions and the formation of R-loops. Separately we use a sliding window approach that accounts for properties of the DNA nucleotide sequence, such as C-richness and CG-skew, to identify segments favoring R-loops. We evaluate these properties on two DNA plasmids that are known to form R-loops and compare results with a recent energetics model from the Chédin Lab. Our abstract approach for R-loops is an initial step toward a more sophisticated framework which can take into account the effect of DNA topology on R-loop formation. |
| Citation: | N. Jonoska, N. Obatake, S. Poznanovic, C. Price, M. Reihl, M. Vazquez. Modeling RNA:DNA Hybrids with Formal Grammars. Using Mathematics to Understand Biological Complexity (R. Segal, B. Shtylla, S. Sindi, Eds.) Springer, Association for Women in Mathematics Series, (2021) pp. 35-54. |
| DOI: | 10.1007/978-3-030-57129-0_3 |
| Title: | Recognizable and Regular Subsets of Monoids |
|---|---|
| Authors: | Nataša Jonoska |
| Abstract: | This note is a short review of regular and recognizable subsets of monoids. We introduce a new question about characterizing classes of monoids and show that idempotent monoids can be characterized by the properties of the languages they recognize. |
| Citation: | N. Jonoska. Recognizable and Regular Subsets of Monoids. Section of Natural, Mathematical and Biotechnical Sciences, MASA 41:2 (2020) pp. 141-146. |
| Preprint: | View |
| Title: | The Topology of Scaffold Routings on Non-Spherical Mesh Wireframes |
|---|---|
| Authors: | Abdulmelik Mohammed, Nataša Jonoska, Masahico Saito |
| Abstract: | The routing of a DNA-origami scaffold strand is often modelled as an Eulerian circuit of an Eulerian graph in combinatorial models of DNA origami design. The knot type of the scaffold strand dictates the feasibility of an Eulerian circuit to be used as the scaffold route in the design. Motivated by the topology of scaffold routings in 3D DNA origami, we investigate the knottedness of Eulerian circuits on surface-embedded graphs. We show that certain graph embeddings, checkerboard colorable, always admit unknotted Eulerian circuits. On the other hand, we prove that if a graph admits an embedding in a torus that is not checkerboard colorable, then it can be re-embedded so that all its non-intersecting Eulerian circuits are knotted. For surfaces of genus greater than one, we present an infinite family of checkerboard-colorable graph embeddings where there exist knotted Eulerian circuits. |
| Citation: | A. Mohammed, N. Jonoska, M. Saito. The Topology of Scaffold Routings on Non-Spherical Mesh Wireframes. DNA Computing and Molecular Programming LIPIcs 174 (2020) pp. 1-17. |
| DOI: | 10.4230/LIPIcs.DNA.2020.1 |
| Title: | Companions and an Essential Motion of a Reaction System |
|---|---|
| Authors: | Daniela Genova, Hendrik Jan Hoogeboom, Nataša Jonoska |
| Abstract: | For a family of sets we consider elements that belong to the same sets within the family as companions. The global dynamics of a reactions system (as introduced by Ehrenfeucht and Rozenberg) can be represented by a directed graph, called a transition graph, which is uniquely determined by a one-out subgraph, called the 0-context graph. We consider the companion classes of the outsets of a transition graph and introduce a directed multigraph, called an essential motion, whose vertices are such companion classes. We show that all one-out graphs obtained from an essential motion represent 0-context graphs of reactions systems with isomorphic transition graphs. All such 0-context graphs are obtained from one another by swapping the outgoing edges of companion vertices. |
| Citation: | D. Genova, H. J. Hoogeboom, N. Jonoska. Companions and an Essential Motion of a Reaction System. Fundamenta Informaticae 175:1-4 (2020) pp. 187-199. |
| DOI: | 10.3233/FI-2020-1953 |
| Title: | Symbol Separations and Double Occurrence Words |
|---|---|
| Authors: | Nataša Jonoska, Masahico Saito, Hwee Kim, Brad Mostowski |
| Abstract: | A double occurrence word (DOW) is a word in which every symbol appears exactly twice. We define the symbol separation of a DOW \(w\) to be the number of letters between the two copies of a symbol, and the separation of \(w\) to be the sum of separations over all symbols in \(w\). We then analyze relationship among size, reducibility and separation of DOWs. Specifically, we provide tight bounds of separations of DOWs with a given size and characterize the words that attain those bounds. We show that all separation numbers within the bounds can be realized. We present recursive formulas for counting the numbers of DOWs with a given separation under various restrictions, such as the number of irreducible factors. These formulas can be obtained by inductive construction of all DOWs with the given separation. |
| Citation: | N. Jonoska, H. Kim, B. Mostowski, M. Saito. Symbol Separations and Double Occurrence Words. Int. J. of Foundations of Computer Science 31:7 (2020) pp. 915-928. |
| Title: | Some Combinatorial Properties of the Generalized Derangement Numbers |
|---|---|
| Authors: | Margherita Maria Ferrari, Emanuele Munarini, Norma Zagaglia Salvi |
| Abstract: | In this paper, we give a simple description of the \(m\)-widened permutations (generalized \(m\)-permutations) and the \(m\)-widened derangements (generalized \(m\)-derangements) in terms of ordinary permutations and derangements with a suitable constraint. This approach allows us to give a natural combinatorial interpretation of the generalized derangement numbers and the generalized rencontres polynomials in terms of species of structures. Finally, we obtain some formulas relating the generalized derangement numbers with the \(r\)-Bell numbers. In particular, we give an extension of the Clarke-Sved identity. |
| Citation: | M.M. Ferrari, E. Munarini, N. Zagaglia Salvi, Some Combinatorial Properties of the Generalized Derangement Numbers, Rivista di Matematica della Università di Parma 11 (2020) pp. 217-249. |
| Title: | On the Minimum Number of Bond-Edge Types and Tile Types: an Approach by Edge-Colorings of Graphs |
|---|---|
| Authors: | Simona Bonvicini, Margherita Maria Ferrari |
| Abstract: | The purpose of this paper is twofold. On one hand, we want to describe from a new graph theory perspective the self-assembly of DNA structures with branched junction molecules having flexible arms. On the other hand, we employ edge-colorings and graph decompositions to study the well-known problem of determining the minimum number of bond-edge types and tile types, which are graph invariants appearing in this context. We provide a strategy that can be applied to arbitrary graphs for obtaining upper bounds for these graph invariants. |
| Citation: | S. Bonvicini, M. M. Ferrari. On the Minimum Number of Bond-Edge Types and Tile Types: an Approach by Edge-Colorings of Graphs. Discrete Applied Mathematics 277 (2020) pp. 1-13. |
| DOI: | 10.1016/j.dam.2019.09.004 |
| Title: | Graph Based Analysis for Gene Segment Interactions In a Scrambled Genome |
|---|---|
| Authors: | Mustafa Hajij, Nataša Jonoska, Denys Kukushkin, Masahico Saito |
| Abstract: | DNA recombinant processes can involve gene segments that overlap or interleave with gene segments of another gene. Such gene segment appearances relative to each other are called here gene segment organization. We use graphs to represent the gene segment organization in a chromosome locus. Vertices of the graph represent contigs resulting after the recombination and the edges represent the gene segment organization prior to rearrangement. To each graph we associate a vector whose entries correspond to graph properties, and consider this vector as a point in a higher dimensional Euclidean space such that cluster formations and analysis can be performed with a hierarchical clustering method. The analysis is applied to a recently sequenced model organism Oxytricha trifallax, a species of ciliate with highly scrambled genome that undergoes massive rearrangement process after conjugation. The analysis shows some emerging star-like graph structures indicating that segments of a single gene can interleave, or even contain all of the segments from fifteen or more other genes in between its segments. We also observe that as many as six genes can have their segments mutually interleaving or overlapping. |
| Citation: | M. Hajij, N. Jonoska, D. Kukushkin, M. Saito. Graph Based Analysis for Gene Segment Interactions In a Scrambled Genome. Journal of Theoretical Biology 494 (2020) 110215. |
| DOI: | 10.1016/j.jtbi.2020.110215 |
| Title: | Insertions Yielding Equivalent Double Occurrence Words |
|---|---|
| Authors: | Daniel A. Cruz, Margherita Maria Ferrari, Nataša Jonoska, Lukas Nabergall, Masahico Saito |
| Abstract: | A double occurrence word (DOW) is a word in which every symbol appears exactly twice; two DOWs are equivalent if one is a symbol-to-symbol image of the other. We consider the so called repeat pattern \((\alpha\alpha)\) and the return pattern \((\alpha\alpha^R)\), with gaps allowed between the \(\alpha\)'s. These patterns generalize square and palindromic factors of DOWs, respectively. We introduce a notion of inserting repeat/return words into DOWs and study how two distinct insertions into the same word can produce equivalent DOWs. Given a DOW \(w\), we characterize the structure of \(w\) which allows two distinct insertions to yield equivalent DOWs. This characterization depends on the locations of the insertions and on the length of the inserted repeat/return words and implies that when one inserted word is a repeat word and the other is a return word, then both words must be trivial (i.e., have only one symbol). The characterization also introduces a method to generate families of words recursively. |
| Citation: | D. A. Cruz, M. M. Ferrari, N. Jonoska, L. Nabergall, M. Saito. Insertions Yielding Equivalent Double Occurrence Words. Fundamenta Informaticae 171:1-4 (2020) pp. 113-132. |
| DOI: | 10.3233/FI-2020-1875 |
| Title: | Algebraic and Computational Aspects of Quandle 2-Cocycle Invariants |
|---|---|
| Authors: | W. Edwin Clark, Masahico Saito |
| Abstract: | Quandle homology theories have been developed and cocycles have been used to construct invariants in state-sum form for knots using colorings of knot diagrams by quandles. Quandle 2-cocycles can be also used to define extensions as in the case of groups. There are relations among algebraic properties of quandles, their homology theories, and cocycle invariants; certain algebraic properties of quandles affect the values of the cocycle invariants, and identities satisfied by quandles induce subcomplexes of homology theory. Recent developments in these matters, as well as computational aspects of the invariant, are reviewed. Problems and conjectures pertinent to the subject are also listed. |
| Citation: | W. E. Clark, M. Saito. Algebraic and Computational Aspects of Quandle 2-Cocycle Invariant. Knots, Low-Dimensional Topology and Applications, Springer Proceedings in Mathematics and Statistics 284 (2019) pp. 147-162. |
| DOI: | 10.1007/978-3-030-16031-9_6 |
| Title: | Continuous Cohomology of Topological Quandles |
|---|---|
| Authors: | Mohamed Elhamdadi, Masahico Saito, Emanuele Zappala |
| Abstract: | A continuous cohomology theory for topological quandles is introduced, and compared to the algebraic theories. Extensions of topological quandles are studied with respect to continuous 2-cocycles, and used to show the differences in second cohomology groups for specific topological quandles. A method of computing the cohomology groups of the inverse limit is applied to quandles. |
| Citation: | M. Elhamdadi, M. Saito, E. Zappala. Continuous Cohomology of Topological Quandles. Journal of Knot Theory and Its Ramifications 28:06 (2019) 1950036. |
| DOI: | 10.1142/S0218216519500366 |
| Title: | Ruleset Optimization on Isomorphic Oritatami Systems |
|---|---|
| Authors: | Yo-Sub Han, Hwee Kim |
| Abstract: | We study an optimization problem of a computational folding model, proving its hardness and proposing heuristic algorithms. RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized out of a gene. An oritatami model (OM) is a computational model of this phenomenon that lets its sequence of beads (abstract molecules) fold cotranscriptionally by the interactions between beads, according to its ruleset. We study the problem of reducing the ruleset size, while keeping the terminal conformations geometrically the same. We first prove the hardness of finding the smallest ruleset, and then suggest two approaches that reduce the ruleset size efficiently. |
| Citation: | YS. Han, H. Kim. Ruleset Optimization on Isomorphic Oritatami Systems. Theoretical Computer Science 785 (2019) pp. 128-139. |
| DOI: | 10.1016/j.tcs.2019.03.020 |
| Title: | DNA Origami Words and Rewriting Systems |
|---|---|
| Authors: | James Garrett, Nataša Jonoska, Hwee Kim, Masahico Saito |
| Abstract: | We classify rectangular DNA origami structures according to their scaffold and staples organization by associating a graphical representation to each scaffold folding. Inspired by well studied Temperley-Lieb algebra, we identify basic modules that form the structures. The graphical description is obtained by 'gluing' basic modules one on top of the other. To each module we associate a symbol such that gluing of molecules corresponds to concatenating the associated symbols. Every word corresponds to a graphical representation of a DNA origami structure. A set of rewriting rules defines equivalent words that correspond to the same graphical structure. We propose two different types of basic module structures and corresponding rewriting rules. For each type, we provide the number of all possible structures through the number of equivalence classes of words. We also give a polynomial time algorithm that computes the shortest word for each equivalence class. |
| Citation: | J. Garrett, N. Jonoska, H. Kim, M. Saito. DNA Origami Words and Rewriting Systems. Unconventional Computation and Natural Computation LNCS 11493 (2019) pp. 94-107. |
| DOI: | 10.1007/978-3-030-19311-9_9 |
| Title: | Changes in Genus Ranges of 4-Regular Graphs by Insertions of Certain Subgraphs |
|---|---|
| Authors: | Nataša Jonoska, Hayden Hunter, Masahico Saito |
| Abstract: | A rigid vertex is a vertex with a prescribed cyclic order of its incident edges. An embedding of a rigid vertex graph preserves such a cyclic order in the surface at every vertex. A cellular embedding of a graph has the complementary regions homeomorphic to open disks. The genus range of a \(4\)-regular rigid vertex graph \(\Gamma\) is the set of genera of closed surfaces that \(\Gamma\) can be cellularly embedded into. Inspired by models of DNA rearrangements, we study the change in the genus range of a graph \(\Gamma\) after the insertion of subgraph structures that correspond to intertwining two edges. We show that such insertions can increase the genus at most by \(2\), and decrease by at most by \(1\), regardless of the number of new vertices inserted. |
| Citation: | N. Jonoska, H. Hunter, M. Saito. Changes in Genus Ranges of 4-Regular Graphs by Insertions of Certain Subgraphs. Congressus Numerantium 232 (2019) pp.165-188. |
| Title: | A General Architecture of Oritatami Systems for Simulating Arbitrary Finite Automata |
|---|---|
| Authors: | Yo-Sub Han, Hwee Kim, Yusei Masuda, Shinnosuke Seki |
| Abstract: | In this paper, we propose an architecture of oritatami systems with which one can simulate an arbitrary nondeterministic finite automaton (NFA) in a unified manner. The oritatami system is known to be Turing-universal but the simulation available so far requires 542 bead types and \(O(t^4\log^2t)\) steps in order to simulate \(t\) steps of a Turing machine. The architecture we propose employs only 329 bead types and requires just \(O(t|Q|^4|\Sigma|^2)\) steps to simulate an NFA with a state set \(Q\) working on a word of length \(t\) over an alphabet \(\Sigma\). |
| Citation: | YS. Han, H. Kim, Y. Masuda, S. Seki. A General Architecture of Oritatami Systems for Simulating Arbitrary Finite Automata. Implementation and Application of Automata LNCS 11601 (2019) pp. 146-157. |
| DOI: | 10.1007/978-3-030-23679-3_12 |
| Title: | Paranemic Crossover DNA: There and Back Again |
|---|---|
| Authors: | Xing Wang, Arun Richard Chandrasekaran, Zhiyong Shen, Yoel P. Ohayon, Tong Wang, Megan E. Kizer, Ruojie Sha, Chengde Mao, Hao Yan, Xiaoping Zhang, Shiping Liao, Baoquan Ding, Banani Chakraborty, Nataša Jonoska, Dong Niu, Hongzhou Gu, Jie Chao, Xiang Gao, Yuhang Li, Tanashaya Ciengshin, Nadrian C. Seeman |
| Abstract: | Over the past 35 years, DNA has been used to produce various nanometer-scale constructs, nanomechanical devices, and walkers. Construction of complex DNA nanostructures relies on the creation of rigid DNA motifs. Paranemic crossover (PX) DNA is one such motif that has played many roles in DNA nanotechnology. Specifically, PX cohesion has been used to connect topologically closed molecules, to assemble a three-dimensional object, and to create two-dimensional DNA crystals. Additionally, a sequence-dependent nanodevice based on conformational change between PX and its topoisomer, JX2, has been used in robust nanoscale assembly lines, as a key component in a DNA transducer, and to dictate polymer assembly. Furthermore, the PX motif has recently found a new role directly in basic biology, by possibly serving as the molecular structure for double-stranded DNA homology recognition, a prominent feature of molecular biology and essential for many crucial biological processes. This review discusses the many attributes and usages of PX-DNA-its design, characteristics, applications, and potential biological relevance-and aims to accelerate the understanding of PX-DNA motif in its many roles and manifestations. |
| Citation: | X. Wang, A. R. Chandrasekaran, Z. Shen, Y. P. Ohayon, T. Wang, M. E. Kizer, R. Sha, C. Mao, H. Yan, X. Zhang, S. Liao, B. Ding, B. Chakraborty, N. Jonoska, D. Niu, H. Gu, J. Chao, X. Gao, Y. Li, T. Ciengshin, N. C. Seeman. Paranemic Crossover DNA: There and Back Again. Chemical Reviews, 119:10 (2019) pp. 6273-6289. |
| DOI: | 10.1021/acs.chemrev.8b00207 |
| Title: | Deterministic 2-Dimensional Temperature-1 Tile Assembly Systems Cannot Compute |
|---|---|
| Authors: | Jérôme Durand-Lose, Hendrik Jan Hoogeboom, Nataša Jonoska |
| Abstract: | We consider non cooperative binding in so called 'temperature 1', in deterministic (here called confluent) tile self-assembly systems (1-TAS) and prove the standing conjecture that such systems do not have universal computational power. We call a TAS whose maximal assemblies contain at least one ultimately periodic assembly path para-periodic. We observe that a confluent 1-TAS has at most one maximal producible assembly, \(\alpha_{max}\), that can be considered a union of path assemblies, and we show that such a system is always para-periodic. This result is obtained through a superposition and a combination of two paths that produce a new path with desired properties, a technique that we call co-grow of two paths. Moreover we provide a characterization of an \(\alpha_{max}\) of a confluent 1-TAS as one of two possible cases, so called, a grid or a disjoint union of combs. To a given \(\alpha_{max}\) we can associate a finite labeled graph, called quipu, such that the union of all labels of paths in the quipu equals \(\alpha_{max}\), therefore giving a finite description for \(\alpha_{max}\). This finite description implies that \(\alpha_{max}\) is a union of semi-affine subsets of \(\mathbb{Z}^2\) and since such a finite description can be algorithmicly generated from any 1-TAS, 1-TAS cannot have universal computational power. |
| Preprint: | View |
| Title: | Tile-Based DNA Nanostructures: Mathematical Design and Problem Encoding |
|---|---|
| Authors: | Joanna Ellis-Monaghan, Nataša Jonoska, Greta Pangborn |
| Abstract: | The chemical and physical properties of DNA that enable biological functions such as self-replication and encoding of genetic information also allow DNA to be used as a nanoscale building material. This emergent field of self-assembling DNA nanostructures has driven new areas of mathematical and computational investigation. This chapter surveys some self-assembly methods and mathematical tools that can be used to develop early-stage optimal design strategies for creating the target molecules. We review DNA assembly of three-dimensional structures using tile or block assembly (flexible and rigid). The mathematical tools come largely from the field of combinatorics, particularly graph theory, and we also discuss some algorithmic approaches. Further, we give a theoretical description of how self-assembly processes may be used to solve mathematical and computational problems. |
| Citation: | J. Ellis-Monaghan, N. Jonoska, G. Pangborn. Tile-based DNA Nanostructures: Mathematical Design and Problem Encoding. Algebraic and Combinatorial Computational Biology, Academic Press (2019) pp. 35-60. |
| DOI: | 10.1016/B978-0-12-814066-6.00002-7 |
| Title: | Graphs Associated With DNA Rearrangements and Their Polynomials |
|---|---|
| Authors: | Robert Brijder, Hendrik Jan Hoogeboom, Nataša Jonoska, Masahico Saito |
| Abstract: | DNA rearrangement is a process often found in biology on both developmental and evolutionary scale. While many models have considered abstract operations involved in the rearrangement, the process itself can be directly modeled through four-regular graphs, as presented here. We describe ways to explain DNA rearrangements through four-regular graphs and double occurrence words. These models are illustrated through the rearrangement processes in a well-studied ciliate species where DNA recombination is observed on a massive scale. The number of resulting molecules and the intermediate molecules throughout this process can be counted as terms in graph polynomials, closely related to the well-known Tutte polynomial. We present two such polynomials in the last section. |
| Citation: | R. Brijder, H. J. Hoogeboom, N. Jonoska, M. Saito. Graphs Associated with DNA Rearrangements and Their Polynomials. Algebraic and Combinatorial Computational Biology, Academic Press (2019) pp. 61-87. |
| DOI: | 10.1016/B978-0-12-814066-6.00003-9 |
| Title: | Algebraic Systems Motivated by DNA Origami |
|---|---|
| Authors: | James Garrett, Nataša Jonoska, Hwee Kim, Masahico Saito |
| Abstract: | We initiate an algebraic approach to study DNA origami structures. We identify two types of basic building blocks and describe a DNA origami structure by their composition. These building blocks are taken as generators of a monoid, called the origami monoid, and motivated by the well studied Temperley-Lieb algebras, we identify a set of relations that characterize the origami monoid. We present several observations about Green's relations for the origami monoid and study the relations to a direct product of Jones monoids, which is a morphic image of an origami monoid. |
| Citation: | J. Garrett, N. Jonoska, H. Kim, M. Saito. Algebraic Systems Motivated by DNA Origami. Algebraic Informatics LNCS 11545 (2019) pp. 164-176. |
| DOI: | 10.1007/978-3-030-21363-3_14 |
| Title: | Decomposition of some Hankel Matrices Generated by the Generalized Rencontres Polynomials |
|---|---|
| Authors: | Margherita Maria Ferrari, Emanuele Munarini |
| Abstract: | Using the algebraic techniques of formal series, we obtain a combinatorial decomposition of some matrices generated by the generalized rencontres polynomials. Specifically, for the complete matrix and the Hankel matrix we obtain an LDU-decomposition , where \(D \) is a diagonal matrix and \(R\) and \(S\) are two Sheffer matrices. Then, for the shifted matrices we obtain an LTU-decomposition , where \(T\) is a tridiagonal matrix and \(R\) and \(S\) are two Sheffer matrices. Furthermore, we give an algebraic characterization of the generalized rencontres numbers and polynomials in terms of Hankel determinants. Finally, we determine a relation between the complete matrices and the Hankel matrices. |
| Citation: | M. M. Ferrari, E. Munarini. Decomposition of some Hankel Matrices Generated by the Generalized Rencontres Polynomials. Linear Algebra and its Applications 567 (2019) pp. 180-201. |
| DOI: | 10.1016/j.laa.2018.12.029 |
| Title: | Transcript Design Problem of Oritatami Systems |
|---|---|
| Authors: | Yo-Sub Han, Hwee Kim, Shinnosuke Seki |
| Abstract: | RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized out of a gene. Oritatami model is a computation model of this phenomenon, which lets its sequence (transcript) of beads (abstract molecules) fold cotranscriptionally by the interactions between beads according to its ruleset. We study the problem of designing a transcript that folds into the given conformation using the given ruleset, which is called the transcript design problem. We prove that the problem is computationally difficult to solve (NP-hard). Then we design efficient poly-time algorithms with additional restrictions on the oritatami system. |
| Citation: | YS. Han, H. Kim, S. Seki. Transcript Design Problem of Oritatami Systems. DNA Computing and Molecular Programming LNCS 11145 (2018) pp. 139-154. |
| DOI: | 10.1007/978-3-030-00030-1_9 |
| Title: | Construction of Geometric Structure by Oritatami System |
|---|---|
| Authors: | Yo-Sub Han, Hwee Kim |
| Abstract: | Self-assembly is the process where smaller components autonomously assemble to form a larger and more complex structure. One of the application areas of self-assembly is engineering and production of complicated nanostructures. Recently, researchers proposed a new folding model called the oritatami model (OM) that simulates the cotranscriptional self-assembly, based on the kinetics on the final shape of folded molecules. Nanostructures in oritatami system (OS) are represented by a sequence of beads and interactions on the lattice. We propose a method to design a general OS, which we call GEOS, that constructs a given geometric structure. The main idea is to design small modular OSs, which we call hinges, for every possible pair of adjacent points in the target structure. Once a shape filling curve for the target structure is ready, we construct an appropriate primary structure that follows the curve by a sequence of hinges. We establish generalized guidelines on designing a GEOS, and propose two GEOSs. |
| Citation: | YS. Han, H. Kim. Construction of Geometric Structure by Oritatami System. DNA Computing and Molecular Programming LNCS 11145 (2018) pp. 173-188. |
| DOI: | 10.1007/978-3-030-00030-1_11 |
| Title: | Site-Directed Deletion |
|---|---|
| Authors: | Da-Jung Cho, Yo-Sub Han, Hwee Kim, Kai Salomaa |
| Abstract: | We introduce a new bio-inspired operation called a site-directed deletion motivated from site-directed mutagenesis performed by enzymatic activity of DNA polymerase: Given two strings \(x\) and \(y\), a site-directed deletion partially deletes a substring of \(x\) guided by the string \(y\) that specifies which part of a substring can be deleted. We study a few decision problems with respect to the new operation and examine the closure properties of the (iterated) site-directed deletion operations. We, then, define a site-directed deletion-closed (and -free) language \(L\) and investigate its decidability properties when \(L\) is regular or context-free. |
| Citation: | DJ. Cho, YS. Han, H. Kim, K. Salomaa. Site-Directed Deletion. Developments in Language Theory LNCS 11088 (2018) pp. 219-230. |
| DOI: | 10.1007/978-3-319-98654-8_18 |
| Title: | Longitudinal Mapping Knot Invariant for SU(2) |
|---|---|
| Authors: | W. Edwin Clark, Masahico Saito |
| Abstract: | The knot coloring polynomial defined by Eisermann for a finite pointed group is generalized to an infinite pointed group as the longitudinal mapping invariant of a knot. In turn, this can be thought of as a generalization of the quandle 2-cocycle invariant for finite quandles. If the group is a topological group, then this invariant can be thought of as a topological generalization of the 2-cocycle invariant. The longitudinal mapping invariant is based on a meridian-longitude pair in the knot group. We also give an interpretation of the invariant in terms of quandle colorings of a 1-tangle for generalized Alexander quandles without use of a meridian-longitude pair in the knot group. The invariant values are concretely evaluated for the torus knots \(T(2,n)\), their mirror images, and the figure eight knot for the group SU(2). |
| Citation: | W. E. Clark, M. Saito. Longitudinal Mapping Knot Invariant for SU(2). Journal of Knot Theory and its Ramifications 27:11 (2018) 1843014. |
| DOI: | 10.1142/S0218216518430149 |
| Title: | Twist Regions and Coefficients Stability of the Colored Jones Polynomial |
|---|---|
| Authors: | Mohamed Elhamdadi, Mustafa Hajij, Masahico Saito |
| Abstract: | We prove that the coefficients of the colored Jones polynomial of alternating links stabilize under increasing the number of twists in the twist regions of the link diagram. This gives us an infinite family of \(q\)-power series derived from the colored Jones polynomial parametrized by the color and the twist regions of the alternating link diagram. |
| Citation: | M. Elhamdadi, M. Hajij, M. Saito. Twist Regions and Coefficients Stability of the Colored Jones Polynomial. Transactions of the American Mathematical Society 370 (2018) pp. 5155-5177. |
| DOI: | 10.1090/tran/7128 |
| Title: | Cyclic Compositions and Cycles of the Hypercube |
|---|---|
| Authors: | Margherita Maria Ferrari, Norma Zagaglia Salvi |
| Abstract: | The partition graph of a positive integer \(n\), \(P_n\), is the graph whose vertices are the cyclic compositions of \(n\) and two vertices are adjacent if one composition is obtained from the other one by replacing two cyclically consecutive parts by their sum. In this paper we introduce and investigate the notions of singular cyclic composition and singular edge of \(P_n\). We associate with every singular edge and every cycle of \(P_n\), whose vertices are aperiodic cyclic compositions of \(n\), a cycle or a set of disjoint cycles of equal length of the hypercube \(Q_n\). |
| Citation: | M. M. Ferrari, N. Zagaglia Salvi. Cyclic Compositions and Cycles of the Hypercube. Aequationes Mathematicae 92:4 (2018) pp. 671-682. |
| DOI: | 10.1007/s00010-018-0554-7 |
| Title: | A Generalization of the "Problème des Rencontres" |
|---|---|
| Authors: | Stefano Capparelli, Margherita Maria Ferrari, Emanuele Munarini, Norma Zagaglia Salvi |
| Abstract: | In this paper, we study a generalization of the classical problème des rencontres (problem of coincidences), where you are asked to enumerate all permutations \( \pi \in \mathbb{S}_n \) with \(k\) fixed points, and, in particular, to enumerate all permutations \( \pi \in \mathbb{S}_n \) with no fixed points (derangements). Specifically, here we study this problem for the permutations of the \(n+m\) symbols \(1\), \(2\), \(\ldots\), \(n\), \(v_1\), \(v_2\), \(\ldots\), \(v_m\), where \( v_i \not\in\{1,2,\ldots,n\} \) for every \(i=1,2,\ldots,m\). In this way, we obtain a generalization of the derangement numbers, the rencontres numbers and the rencontres polynomials. For these numbers and polynomials, we obtain the exponential generating series, some recurrences and representations, and several combinatorial identities. Moreover, we obtain the expectation and the variance of the number of fixed points in a random permutation of the considered kind. Finally, we obtain some asymptotic formulas for the generalized rencontres numbers and the generalized derangement numbers. |
| Citation: | S. Capparelli, M. M. Ferrari, E. Munarini, N. Zagaglia Salvi. A Generalization of the "Problème des Rencontres". Journal of Integer Sequences 21 (2018) 18.2.8. |
| Preprint: | View |
| Title: | Russian Doll Genes and Complex Chromosome Rearrangements in Oytricha trifallax |
|---|---|
| Authors: | Jasper Braun, Lukas Nabergall, Rafik Neme, Laura F. Landweber, Masahico Saito, Nataša Jonoska |
| Abstract: | 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. |
| Citation: | J. Braun, L. Nabergall, R. Neme, L. Landweber, M. Saito, N. Jonoska. Russian Doll Genes and Complex Chromosome Rearrangements in Oytricha trifallax. G3: Genes, Genomes, Genetics 8:5 (2018) pp. 1669-1674. |
| DOI: | 10.1534/g3.118.200176 |
| Title: | Unknotted Strand Routings of Triangulated Meshes |
|---|---|
| Authors: | Abdulmelik Mohammed, Mustafa Hajij |
| Abstract: | In molecular self-assembly such as DNA origami, a circular strand's topological routing determines the feasibility of a design to assemble to a target. In this regard, the Chinese-postman DNA scaffold routings of Benson et al. (2015) only ensure the unknottedness of the scaffold strand for triangulated topological spheres. In this paper, we present a cubic-time \(\frac{5}{3}\)-approximation algorithm to compute unknotted Chinese-postman scaffold routings on triangulated orientable surfaces of higher genus. Our algorithm guarantees every edge is routed at most twice, hence permitting low-packed designs suitable for physiological conditions. |
| Citation: | A. Mohammed, M. Hajij. Unknotted Strand Routings of Triangulated Meshes. DNA Computing and Molecular Programming LNCS 10467 (2017) pp. 46-63. |
| DOI: | 10.1007/978-3-319-66799-7_4 |
| Title: | The Palette Numbers of 2-bridge Knots |
|---|---|
| Authors: | Takuji Nakamura, Yasutaka Nakanishi, Masahico Saito, Shin Satoh |
| Abstract: | 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\). |
| Citation: | 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) 1750047. |
| DOI: | 10.1142/S021821651750047X |
| Title: | The 6- and 8-palette Numbers of Links |
|---|---|
| Authors: | Takuji Nakamura, Yasutaka Nakanishi, Masahico Saito, Shin Satoh |
| Abstract: | 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\). |
| Citation: | 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. |
| DOI: | 10.1016/j.topol.2017.02.080 |
| Title: | Patterns and Distances in Words Related to DNA Rearrangement |
|---|---|
| Authors: | Nataša Jonoska, Lukas Nabergall, Masahico Saito |
| Abstract: | 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. |
| Citation: | N. Jonoska, L. Nabergall, M. Saito. Patterns and Distances in Words Related to DNA Rearrangement. Fundamenta Informaticae 154: 1-4 (2017) pp 225-238. |
| DOI: | 10.3233/FI-2017-1563 |
| Title: | Platform Color Designs for Interactive Molecular Arrangements |
|---|---|
| Authors: | Jasper Braun, Daniel A. Cruz, Nataša Jonoska |
| Abstract: | 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. |
| Citation: | J. Braun, D. Cruz, N. Jonoska. Platform Color Designs for Interactive Molecular Arrangements. Unconventional Computation and Natural Computation LNCS 10240 (2017) pp 69-81. |
| DOI: | 10.1007/978-3-319-58187-3_6 |
| Title: | Computation of Quandle 2-Cocycle Knot Invariants Without Explicit 2-Cocycles |
|---|---|
| Authors: | W. Edwin Clark, Larry A Dunning, Masahico Saito |
| Abstract: | 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. |
| Citation: | 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). |
| DOI: | 10.1142/S0218216517500353 |
| Title: | A Graph Isomorphism Condition and Equivalence of Reaction Systems |
|---|---|
| Authors: | Daniela Genova, Hendrik Jan Hoogeboom, Nataša Jonoska |
| Abstract: | 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. |
| Citation: | D. Genova, H.J. Hoogeboom, N. Jonoska. A Graph Isomorphism Condition and Equivalence of Reaction Systems. Theoretical Computer Science 701 (2017) pp 109-119. |
| DOI: | 10.1016/j.tcs.2017.05.019 |
| Title: | Quandle Identities and Homology |
|---|---|
| Authors: | W. Edwin Clark, Masahico Saito |
| Abstract: | 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. |
| Citation: | W.E. Clark, M. Saito. Quandle Identities and Homology. Contemporary Mathematics 689 (2017) pp 23-35. |
| DOI: | 10.1090/conm/689/13857 |
| Title: | Homology for Quandles with Partial Group Operations |
|---|---|
| Authors: | J. Scott Carter, Atsushi Ishii, Masahico Saito, Kokoro Tanaka |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.2140/pjm.2017.287.19 |
| Title: | Counter Machines and Crystallographic Structures |
|---|---|
| Authors: | Nataša Jonoska, Milé Krajčevski, Gregory McColm |
| Abstract: | 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≅Δ. |
| Citation: | N. Jonoska, M. Krajčevski, G. McColm. Counter Machines and Crystallographic Structures. Natural Computing 15:1 (2016) pp. 97-113. |
| DOI: | 10.1007/s11047-015-9527-0 |
| Title: | Traversal Languages Capturing Isomorphism Classes of Sierpinski Gaskets |
|---|---|
| Authors: | Nataša Jonoska, Milé Krajčevski, Gregory McColm |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1007/978-3-319-41312-9_13 |
| Title: | Recurring Patterns Among Scrambled Genes in the Encrypted Genome of the Ciliate Oxytricha trifallax |
|---|---|
| Authors: | Jonathan Burns, Denys Kukushkin, Xiao Chen, Laura F. Landweber, Masahico Saito, Nataša Jonoska |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1016/j.jtbi.2016.08.038 |
| Preprint: | View |
| Title: | Algebraic Properties of Quandle Extensions and Values of Cocycle Knot Invariants |
|---|---|
| Authors: | W. Edwin Clark, Masahico Saito |
| Abstract: | 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. |
| Citation: | 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). |
| DOI: | 10.1142/S0218216516500802 |
| Title: | Quandle coloring and cocycle invariants of composite knots and abelian extensions |
|---|---|
| Authors: | W. Edwin Clark, Masahico Saito, Leandro Vendramin |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1142/S0218216516500243 |
| Title: | <mds_ies_db>: A Database of Ciliate Genome Rearrangements |
|---|---|
| Authors: | Jonathan Burns, Denys Kukushkin, Kelsi Lindblad, Xiao Chen, Nataša Jonoska, Laura F. Landweber |
| Abstract: | 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 |
| Citation: | J. Burns, D. Kukushkin, K. Lindblad, X. Chen, N. Jonoska, L. Landweber. <mds_ies_db>: A Database of Ciliate Genome Rearrangements. Nucleic Acids Res. 44:D1 (2015) pp. D703-D709. |
| DOI: | 10.1093/nar/gkv1190 |
| Title: | Molecular ping-pong Game of Life on a two-dimensional DNA origami array |
|---|---|
| Authors: | Nataša Jonoska, Nadrian C. Seeman |
| Abstract: | 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. |
| Citation: | 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). |
| DOI: | 10.1098/rsta.2014.0215 |
| Title: | Combinatorial DNA Rearrangement Facilitates the Origin of New Genes in Ciliates |
|---|---|
| Authors: | Xiao Chen, Seolkyoung Jung, Leslie Y Beh, Sean R Eddy, Laura F. Landweber |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1093/gbe/evv172 |
| Title: | Dynamic Simulation of 1D Cellular Automata in the Active aTAM |
|---|---|
| Authors: | Nataša Jonoska, Daria Karpenko, Shinnosuke Seki |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1007/s00354-015-0302-7 |
| Title: | A Signal-Passing DNA-Strand-Exchange Mechanism for Active Self-Assembly of DNA Nanostructures. |
|---|---|
| Authors: | Jennifer E Padilla, Ruojie Sha, Martin Kristiansen, Martin Kristiansen, Nataša Jonoska, Nadrian C. Seeman |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1002/anie.201500252 |
| Title: | Existence of constants in regular splicing languages |
|---|---|
| Authors: | Paola Bonizzoni, Nataša Jonoska |
| Abstract: | 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. |
| Citation: | P. Bonizzoni, N. Jonoska, Existence of constants in regular splicing languages, Information and Computation 242 (2015) pp.340-353. |
| DOI: | 10.1016/j.ic.2015.04.001 |
| Title: | Genus Ranges of Chord Diagrams |
|---|---|
| Authors: | Jonathan Burns, Nataša Jonoska, Masahico Saito |
| Abstract: | 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. |
| Citation: | Jonathan Burns, Nataša Jonoska, and Masahico Saito, Genus Ranges of Chord Diagrams. Journal of Knot Theory and its Ramifications. 24 (2015) 1550022. |
| DOI: | 10.1142/S0218216515500224 |
| Title: | Genus Ranges of 4-Regular Rigid Vertex Graphs |
|---|---|
| Authors: | Dorothy Buck, Egor Dolzhenko, Nataša Jonoska, Masahico Saito, Karen Valencia |
| Abstract: | 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. |
| Citation: | 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. |
| Preprint: | View |
| Title: | Languages Associated with Crystallographic Symmetry |
|---|---|
| Authors: | Nataša Jonoska, Gregory McColm, Milé Krajčevski |
| Abstract: | 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. |
| Citation: | 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). |
| DOI: | 10.1007/978-3-319-08123-6_18 |
| Title: | A Stronger Square Conjecture on Binary Words |
|---|---|
| Authors: | Nataša Jonoska, Florin Manea, Shinnosuke Seki |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1007/978-3-319-04298-5_30 |
| Title: | The Architecture of a Scrambled Genome Reveals Massive Levels of Genomic Rearrangement during Development |
|---|---|
| Authors: | 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 |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1016/j.cell.2014.07.034 |
| Title: | Quandle colorings of knots and applications |
|---|---|
| Authors: | W. Edwin Clark, Mohamed Elhamdadi, Masahico Saito, Timothy Yeatman |
| Abstract: | 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. |
| Citation: | 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). |
| DOI: | 10.1142/S0218216514500357 |
| Title: | Active Tile Self-Assembly, Part 2: Self-Similar Structures and Structural Recursion |
|---|---|
| Authors: | Nataša Jonoska, Daria Karpenko |
| Abstract: | 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. |
| Citation: | Nataša Jonoska and Daria Karpenko, Int. J. Found. Comput. Sci. 25, 165 (2014). |
| DOI: | 10.1142/S0129054114500099 |
| Title: | Active Tile Self-Assembly, Part 1: Universality at Temperature 1 |
|---|---|
| Authors: | Nataša Jonoska, Daria Karpenko |
| Abstract: | 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. |
| Citation: | Nataša Jonoska and Daria Karpenko, Int. J. Found. Comput. Sci. 25, 141 (2014). |
| DOI: | 10.1142/S0129054114500087 |
| Title: | Reductions on Double Occurrence Words |
|---|---|
| Authors: | Ryan Arredondo |
| Abstract: | 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. |
| Citation: | 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. |
| Preprint: | View |
| Title: | Discrete and Topological Models in Molecular Biology |
|---|---|
| Authors: | Nataša Jonoska, Masahico Saito |
| Abstract: | 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. |
| Citation: | Jonoska, Natasha; Saito, Masahico (Eds.) Discrete and Topological Models in Molecular Biology. Natural Computing Series. Springer (2013) ISBN 978-3-642-40192-3 |
| DOI: | 10.1007/978-3-642-40193-0 |
| Title: | Biologically Relevant Molecular Transducer with Increased Computing Power and Iterative Abilities |
|---|---|
| Authors: | Tamar Ratner, Ron Piran, Nataša Jonoska, Ehud Keinan |
| Abstract: | 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. |
| Citation: | 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 |
| DOI: | 10.1016/j.chembiol.2013.02.016 |
| Title: | Connected Quandles Associated with Pointed Abelian Groups |
|---|---|
| Authors: | W. Edwin Clark, Mohamed Elhamdadi, Xiang-Dong Hou, Masahico Saito, Timothy Yeatman |
| Abstract: | 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. |
| Citation: | W. Edwin Clark, Mohamed Elhamdadi, Xiang-dong Hou, Masahico Saito and Timothy Yeatman, Pacific Journal of Mathematics, Vol. 264, No. 1 (2013) 31-60 |
| DOI: | 10.2140/pjm.2013.264.31 |
| Title: | Four-regular Graphs with Rigid Vertices Associated to DNA Recombination |
|---|---|
| Authors: | Jonathan Burns, Egor Dolzhenko, Nataša Jonoska, Tilahun Muche, Masahico Saito |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1016/j.dam.2013.01.003 |
| Title: | Two-dimensional Languages and Cellular Automata |
|---|---|
| Authors: | Egor Dolzhenko, Nataša Jonoska |
| Abstract: | 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. |
| Citation: | E. Dolzhenko, N. Jonoska, Two-dimensional Languages and Cellular Automata, International Journal of Foundations of Computer Science 23:1 (2012) pp. 185-206. |
| DOI: | 10.1142/S0129054112500037 |
| Title: | A Programmable Transducer Self-Assembled from DNA |
|---|---|
| Authors: | Banani Chakraborty, Nataša Jonoska, Nadrian C. Seeman |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1039/c1sc00523e |
| Title: | Forbidding and enforcing conditions on Graphs |
|---|---|
| Authors: | Daniela Genova, Nataša Jonoska |
| Abstract: | 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. |
| Citation: | D. Genova, N. Jonoska, Forbidding and enforcing conditions on Graphs, Theoretical Computer Science 429 (2012) pp. 108-117. |
| DOI: | 10.1016/j.tcs.2011.12.029 |
| Title: | The Computational Nature of Gene Assembly in Ciliates |
|---|---|
| Authors: | Robert Brijder, Mark Daley, Tero Harju, Nataša Jonoska, Ion Petre, Grzegorz Rozenberg |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1007/978-3-540-92910-9_37 |
| Title: | Computing by molecular self-assembly |
|---|---|
| Authors: | Nataša Jonoska, Nadrian C. Seeman |
| Abstract: | 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. |
| Citation: | N. Jonoska, N.C. Seeman, Computing by molecular self-assembly, Interface Focus 2 (2012) 504-511 |
| DOI: | 10.1098/rsfs.2011.0117 |
| Title: | Rewriting rule chains modeling DNA rearrangement pathways |
|---|---|
| Authors: | Angela Angeleska, Nataša Jonoska, Masahico Saito |
| Abstract: | 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. |
| Citation: | Angeleska, A., Jonoska, N., Saito, M., Rewriting rule chains modeling DNA rearrangement pathways, Theoretical Computer Science (2012), ISSN 0304-3975 |
| DOI: | 10.1016/j.tcs.2012.04.041 |
| Title: | On Stoichometry for the Asssembly of Flexible-Tile DNA Complexes |
|---|---|
| Authors: | Nataša Jonoska, Gregory McColm, Ana Staninska |
| Abstract: | 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. |
| Citation: | N. Jonoska, G. McColm, A. Staninska, On Stoichometry for the Asssembly of Flexible-Tile DNA Complexes, Natural Computing 10 (2011) pp. 1121-1141. |
| DOI: | 10.1007/s11047-009-9169-1 |
| Title: | Regular splicing languages must have a constant |
|---|---|
| Authors: | Paola Bonizzoni, Nataša Jonoska |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1007/978-3-642-22321-1_8 |
| Title: | Counting Irreducible Double Occurrence Words |
|---|---|
| Authors: | Jonathan Burns, Tilahun Muche |
| Abstract: | 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. |
| Citation: | 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. |
| Preprint: | View |
| Title: | DNA rearrangements through spatial graphs |
|---|---|
| Authors: | Nataša Jonoska, Masahico Saito |
| Abstract: | 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. |
| Citation: | N. Jonoska, M. Saito, DNA rearrangements through spatial graphs, in Computability in Europe (F. Ferreira et al. eds.) LNCS 6158 (2010) pp. 211-218. |
| DOI: | 10.1007/978-3-642-13962-8_24 |
| Title: | Transducer Generated Arrays of Robotic Nanoarms |
|---|---|
| Authors: | Egor Dolzhenko, Nataša Jonoska, Nadrian C. Seeman |
| Abstract: | 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. |
| Citation: | Dolzhenko, E., Jonoska, N., Seeman, N. C., Natural Computing. 9:2 (2010), pp.437-455. |
| DOI: | 10.1007/s11047-009-9157-5 |
| Title: | DNA cages with icosahedral symmetry in bionanotechnology |
|---|---|
| Authors: | Nataša Jonoska, Anne Taormina, Reidun Twarock |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1007/978-3-540-88869-7_9 |
| Title: | Complexity classes for self-assembling flexible tiles |
|---|---|
| Authors: | Nataša Jonoska, Gregory McColm |
| Abstract: | 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. |
| Citation: | N. Jonoska, G. L. McColm, Complexity classes for self-assembling flexible tiles, Theoretical Computer Science 410 4-5 (2009) pp. 332-346. |
| DOI: | 10.1016/j.tcs.2008.09.054 |
| Title: | Framed versus Unframed Two Dimensional Languages |
|---|---|
| Authors: | Marcella Anselmo, Nataša Jonoska, Marina Madonia |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1007/978-3-540-95891-8_11 |
| Title: | Finite state automata representing two-dimensional subshifts |
|---|---|
| Authors: | Joni B. Pirnot, Nataša Jonoska |
| Abstract: | 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. |
| Citation: | N. Jonoska, J. Pirnot, Finite state automata representing two-dimensional subshifts, Theoretical Computer Science 410:37 (2009) pp. 3504-3512. |
| DOI: | 10.1016/j.tcs.2009.03.015 |
| Title: | DNA Splicing: Computing by Observing |
|---|---|
| Authors: | Matteo Cavaliere, Nataša Jonoska, Peter Leupold |
| Abstract: | 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. |
| Citation: | M. Cavaliere, N. Jonoska, P. Leupold, DNA Splicing: Computing by Observing, Natural Computing 8:1 (2009) pp. 157-170. |
| DOI: | 10.1007/s11047-007-9062-8 |
| Title: | Strategies for RNA-Guided DNA Recombination |
|---|---|
| Authors: | Angela Angeleska, Nataša Jonoska, Masahico Saito, Laura F. Landweber |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1007/978-3-540-88869-7_6 |
| Title: | On existence of reporter strands in DNA-based graph structures |
|---|---|
| Authors: | Nataša Jonoska, Gang Wu, Nadrian C. Seeman |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1016/j.tcs.2008.12.004 |
| Title: | DNA Rearrangement through assembly graphs |
|---|---|
| Authors: | Angela Angeleska, Nataša Jonoska, Masahico Saito |
| Abstract: | 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. |
| Citation: | A. Angeleska, N. Jonoska. M. Saito, DNA Rearrangement through assembly graphs. Discrete and Applied Math, 157 (2009) pp. 3020-3037. |
| DOI: | 10.1016/j.dam.2009.06.011 |
| Title: | Reciprocal DNA Nanomechanical Devices Controlled by the Same Set Strands |
|---|---|
| Authors: | Chunhua Liu, Nataša Jonoska, Nadrian C. Seeman |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1021/nl901008k |
| Title: | Construction of a DNA Nano-Object Directly Demonstrates Computation |
|---|---|
| Authors: | Gang Wu, Nataša Jonoska, Nadrian C. Seeman |
| Abstract: | 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. |
| Citation: | G. Wu, N. Jonoska, N.C. Seeman, Construction of a DNA Nano-Object Directly Demonstrates Computation, BioSystems 98 (2009) pp. 80-84. |
| DOI: | 10.1016/j.biosystems.2009.07.004 |
| Title: | Describing Self-assembly of Nanostructures |
|---|---|
| Authors: | Nataša Jonoska, Gregory McColm |
| Abstract: | 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. |
| Citation: | N. Jonoska, G. McColm, Describing Self-assembly of Nanostructures, SOFSEM (V. Geffert et al eds.) Springer LNCS 4910 (2008) pp. 66-73. |
| DOI: | 10.1007/978-3-540-77566-9_6 |
| Title: | Blueprints for dodecahedral DNA cages |
|---|---|
| Authors: | Nataša Jonoska, Reidun Twarock |
| Abstract: | 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. |
| Citation: | N. Jonoska, R. Twarock, Blueprints for dodecahedral DNA cages, J. of Physics A: Mathematical and Theoretical 41 (2008) 304043 (14pp). |
| DOI: | 10.1088/1751-8113/41/30/304043 |
| Title: | Involution join and solid codes |
|---|---|
| Authors: | Nataša Jonoska, Lila Kari, Kalpana Mahalingam |
| Abstract: | 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. |
| Citation: | N. Jonoska, L. Kari, K. Mahalingam, Involution join and solid codes, Fundamenta Informaticae 86 1-2 (2008) pp. 127-142. |
| DOI: | 10.1007/11779148_18 |
| Title: | Biomolecular Automata |
|---|---|
| Authors: | Nataša Jonoska |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1007/978-1-59745-218-2_11 |
| Title: | On complexity of two dimensional languages generated by transducers |
|---|---|
| Authors: | Egor Dolzhenko, Nataša Jonoska |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1007/978-3-540-70844-5_19 |
| Title: | Defining Structures through Forbidding and Enforcing Constraints |
|---|---|
| Authors: | Daniela Genova, Nataša Jonoska |
| Abstract: | 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. |
| Citation: | D. Genova, N. Jonoska, Defining Structures through Forbidding and Enforcing Constraints, Physica B: Physics of Condensed Matter 394:2 (2007) pp. 306-310. |
| DOI: | 10.1016/j.physb.2006.12.069 |
| Title: | Automata Representing Two-dimensional Subshifts |
|---|---|
| Authors: | Nataša Jonoska, Joni B. Pirnot |
| Abstract: | 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. |
| Citation: | 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. |
| DOI: | 10.1007/978-3-540-76336-9_26 |
| Title: | RNA-Guided DNA Assembly |
|---|---|
| Authors: | Angela Angeleska, Nataša Jonoska, Masahico Saito, Laura F. Landweber |
| Abstract: | 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. |
| Citation: | A. Angeleska, N. Jonoska, M. Saito, L. Landweber, RNA-Guided DNA Assembly, Journal of Theoretical Biology 248:4 (2007) pp. 706-720. |
| DOI: | 10.1016/j.jtbi.2007.06.007 |