AbstractTo-date systematic testing and comparison of the accuracy of available primer-dimer prediction software has never been conducted, due in part to a lack of tools able to measure the efficacy of Gibbs free energy (ΔG) calculations at predicting dimer formation in PCR. To address this we have developed a novel online tool called PrimerROC (www.primer-dimer.com/roc/), which uses epidemiologically-based Receiver Operating Characteristic (ROC) curves to assess dimer prediction accuracy. Moreover, by integrating PrimerROC with our PrimerDimer prediction software we can determine a ΔG-based dimer-free threshold above which dimer formation is predicted unlikely to occur. Notably, PrimerROC determines this cut-off without any additional information such as salt concentration or annealing temperature, meaning that our PrimerROC method is an assay and condition independent prediction tool. To demonstrate the broad utility of PrimerROC we assessed the performance of seven publically available primer design and dimer analysis tools using a dataset of over 300 primer pairs. We found that our PrimerROC/PrimerDimer software consistently outperforms these other tools and can achieve predictive accuracies greater than 92%. To illustrate its predictive power this method was used in multiplex PCR design to successfully generate four resequencing assays containing up to 126 primers with no observable primer-primer amplification artefacts.
In a recent paper [arXiv:1506.06649 [nlin.CG]], we presented an example of a 3-state cellular automaton which exhibits behaviour analogous to degenerate hyperbolicity often observed in finite-dimensional dynamical systems. We also calculated densities of 0, 1 and 2 after n iterations of this rule, using finite state machines to conjecture patterns present in preimage sets. Here, we re-derive the same formulae in a rigorous way, without resorting to any semi-empirical methods. This is done by analysing the behaviour of continuous clusters of symbols and by considering their interactions.
In this paper, we construct a weakly universal cellular automaton with two states only on the tiling {11,3}. The cellular automaton is rotation invariant and it is a true planar one.
Research on asynchronous cellular automata has received a great amount of attention these last years and has turned to a thriving field. We survey the recent research that has been carried out on this topic and present a wide state of the art where computing and modelling issues are both represented.
In this paper, we construct a cellular automaton on the pentagrid which is planar, weakly universal and which have five states only. This result much improves the best result which was with nine states
Cellular automata (CA) have been utilized for decades as discrete models of many physical, mathematical, chemical, biological, and computing systems. The most widely known form of CA, the elementary cellular automaton (ECA), has been studied in particular due to its simple form and versatility. However, these dynamic computation systems possess evolutionary rules dependent on a neighborhood of adjacent cells, which limits their sampling radius and the environments that they can be used in. The purpose of this study was to explore the complex nature of one-dimensional CA in configurations other than that of the standard ECA. Namely, "long-distance cellular automata" (LDCA), a construct that had been described in the past, but never studied. I experimented with a class of LDCA that used spaced sample cells unlike ECA, and were described by the notation LDCA-x-y-n, where x and y represented the amount of spacing between the cell and its left and right neighbors, and n denoted the length of the initial tape for tapes of finite size. Some basic characteristics of ECA are explored in this paper, such as seemingly universal behavior, the prevalence of complexity with varying neighborhoods, and qualitative behavior as a function of x and y spacing. Focusing mainly on purely Class 4 behavior in LDCA-1-2, I found that Rule 73 could potentially be Turing universal through the emulation of a cyclic tag system, and revealed a connection between the mathematics of binary trees and Eulerian numbers that might provide insight into unsolved problems in both fields.
A two-state, three-dimensional, deterministic, reversible cellular automaton is shown to be capable of approximately circular orbits, wavelike undulations, and particle-like configurations that decay in accordance with a half-life law.
We present what we argue is the generic generalization of Conway's "Game of Life" to a continuous domain. We describe the theoretical model and the explicit implementation on a computer.
In this paper we define products of one-dimensional Number Conserving Cellular Automata (NCCA) and show that surjective NCCA with 2 blocks (i.e radius 1/2) can always be represented as products of shifts and identites. In particular, this shows that surjective 2-block NCCA are injective.
Studying cellular automata with methods from communication complexity appears to be a promising approach. In the past, interesting connections between communication complexity and intrinsic universality in cellular automata were shown. One of the last extensions of this theory was its generalization to various "communication problems'', or "questions'' one might ask about the dynamics of cellular automata. In this article, we aim at structuring these problems, and find what makes them interesting for the study of intrinsic universality and quasi-orders induced by simulation relations.
We are interested in fixed points in Boolean networks, $\textit{i.e.}$ functions $f$ from $\{0,1\}^n$ to itself. We define the subnetworks of $f$ as the restrictions of $f$ to the hypercubes contained in $\{0,1\}^n$, and we exhibit a class $\mathcal{F}$ of Boolean networks, called even or odd self-dual networks, satisfying the following property: if a network $f$ has no subnetwork in $\mathcal{F}$, then it has a unique fixed point. We then discuss this "forbidden subnetworks theorem''. We show that it generalizes the following fixed point theorem of Shih and Dong: if, for every $x$ in $\{0,1\}^n$, there is no directed cycle in the directed graph whose the adjacency matrix is the discrete Jacobian matrix of $f$ evaluated at point $x$, then $f$ has a unique fixed point. We also show that $\mathcal{F}$ contains the class $\mathcal{F'}$ of networks whose the interaction graph is a directed cycle, but that the absence of subnetwork in $\mathcal{F'}$ does not imply the existence and the uniqueness of a fixed point.
We study iterations of the Bernoulli measure under nearest-neighbour asynchronous binary cellular automata (CA) with a single transition. For these CA, we show that a coarse-level description of the orbit of the Bernoulli measure can be obtained, that is, one can explicitly compute measures of short cylinder sets after arbitrary number of iterations of the CA. In particular, we give expressions for probabilities of ones for all three minimal single-transition rules, as well as expressions for probabilities of blocks of length 3 for some of them. These expressions can be interpreted as "response curves'', that is, curves describing the dependence of the final density of ones on the initial density of ones.
We study the projective subdynamics of two-dimensional shifts of finite type, which is the set of one-dimensional configurations that appear as columns in them. We prove that a large class of one-dimensional shifts can be obtained as such, namely the effective subshifts which contain positive-entropy sofic subshifts. The proof involves some simple notions of simulation that may be of interest for other constructions. As an example, it allows us to prove the undecidability of all non-trivial properties of projective subdynamics.
LFSR and NFSR are the basic building blocks in almost all the state of the art stream ciphers like Trivium and Grain-128. However, a number of attacks are mounted on these type of ciphers. Cellular Automata (CA) has recently been chosen as a suitable structure for crypto-primitives. In this work, a stream cipher is presented based on hybrid CA. The stream cipher takes 128 bit key and 128 bit initialization vector (IV) as input. It is designed to produce $\mathrm{2^{128}}$ random keystream bits and initialization phase is made faster 4 times than that of Grain-128. We also analyze the cryptographic strength of this cipher. Finally, the proposed cipher is shown to be resistant against known existing attacks.
Chris Kuhlman, Henning Mortveit, David Murrugarra
et al.
This paper characterizes the attractor structure of synchronous and asynchronous Boolean networks induced by bi-threshold functions. Bi-threshold functions are generalizations of standard threshold functions and have separate threshold values for the transitions $0 \rightarrow $1 (up-threshold) and $1 \rightarrow 0$ (down-threshold). We show that synchronous bi-threshold systems may, just like standard threshold systems, only have fixed points and 2-cycles as attractors. Asynchronous bi-threshold systems (fixed permutation update sequence), on the other hand, undergo a bifurcation. When the difference $\Delta$ of the down- and up-threshold is less than 2 they only have fixed points as limit sets. However, for $\Delta \geq 2$ they may have long periodic orbits. The limiting case of $\Delta = 2$ is identified using a potential function argument. Finally, we present a series of results on the dynamics of bi-threshold systems for families of graphs.
Sand Pile Models are discrete dynamical systems emphasizing the phenomenon of $\textit{Self-Organized Criticality}$. From a configuration composed of a finite number of stacked grains, we apply on every possible positions (in parallel) two grain moving transition rules. The transition rules permit one grain to fall to its right or left (symmetric) neighboring column if the difference of height between those columns is larger than 2. The model is nondeterministic and grains always fall downward. We propose a study of the set of fixed points reachable in the Parallel Symmetric Sand Pile Model (PSSPM). Using a comparison with the Symmetric Sand Pile Model (SSPM) on which rules are applied once at each iteration, we get a continuity property. This property states that within PSSPM we can't reach every fixed points of SSPM, but a continuous subset according to the lexicographic order. Moreover we define a successor relation to browse exhaustively the sets of fixed points of those models.