Narrow Results

This stage of our journey through the universe of one-dimensional binary Cellular Automata is devoted to period-1 rules, constituting the first of the six groups in which we systematized the 88 globally-independent CA rules.

The first part of this article is mainly dedicated to reviewing the terminology and the empirical results found in the previous papers of our quest. We also introduce the concept of the ω-limit orbit with the purpose of linking our work to the classical theory of nonlinear dynamical systems. Moreover, we present the basin tree diagrams of all period-1 rules — except for rule , which is trivial — along with their Boolean cubes and time-1 characteristic functions.

In the second part, we prove a theorem demonstrating that all rules belonging to group 1 have robust period-1 rules for any finite, and infinite, bit-string length L. This is the first time we give analytical results on the behavior of CA local rules for large values of L and, consequently, for bi-infinite bit strings.

The theoretical treatment is complemented by two remarkable practical results: an explicit formula for generating isomorphic basin trees, and an algorithm for creating new periodic orbits by concatenation. We also provide several examples of both of them, showing how they help to avoid tedious simulations.

The 11th part of our tour through one-dimensional binary Cellular Automata concerns period-2 rules, which form the second group in our classification of the 88 globally-independent CA rules according to the properties of their periodic orbits. In this article, we display the basin tree diagrams of all period-2 rules along with their time-2 characteristic functions, and then we prove that all rules belonging to group 2 have robust period-2 ω-limit orbits for any finite, and infinite, bit string length. This rigorous result, which pairs with the one about period-1 rules given in the tenth installment of our chronicle, confirms what we stated about period-2 rules on the basis of empirical evidence. In the second part of this tutorial, we introduce the notion of quasi global-equivalence and prove that there are only 82 quasi globally-independent CA rules. For the first time, we show that the space-time patterns of globally-independent local rules can depend on each other, and we present an example of quasi-global transformation. We also define the super string 𝄞, and its unique decimal representation x_𝄞, dubbed the super decimal, which provides a completely transparent yet rigorous proof that rule is chaotic when L → ∞. Moreover, we present the basin tree generation formulas, which uncover the analytical relationships between basin trees of globally-equivalent rules. Last but not least, for pedagogical and epistemological reasons, we conclude this paper with the selection of rule, instead of rule , as the prototypic universal Turing machine for our future discourse.

The problem of resolving genotypes into haplotypes, under the perfect phylogeny model, has been under intensive study recently. All studies so far handled missing data entries in a heuristic manner. We prove that the perfect phylogeny haplotype problem is NP-complete when some of the data entries are missing, even when the phylogeny is rooted. We define a biologically motivated probabilistic model for genotype generation and for the way missing data occur. Under this model, we provide an algorithm, which takes an expected polynomial time. In tests on simulated data, our algorithm quickly resolves the genotypes under high rates of missing entries.

The individual haplotyping problem is a computing problem of reconstructing two haplotypes for an individual based on several optimal criteria from one's fragments sequencing data. This paper is based on the fact that the length of a fragment and the number of the fragments covering a SNP (single nucleotide polymorphism) site are both very small compared with the length of a sequenced region and the total number of the fragments and introduces the parameterized haplotyping problems. With m fragments whose maximum length is k₁, n SNP sites and the number of the fragments covering a SNP site no more than k₂, our algorithms can solve the gapless MSR (Minimum SNP Removal) and MFR (Minimum Fragment Removal) problems in the time complexity O(nk₁k₂ + m log m + nk₂ + mk₁) and respectively. Since, the value of k₁ and k₂ are both small (about 10) in practice, our algorithms are more efficient and applicable compared with the algorithms of V. Bafna et al. of time complexity O(mn²) and O(m²n + m³), respectively.

We re-examine the evolutionary dynamics of RNA secondary structures under directional selection towards an optimum RNA structure. We find that the punctuated equilibria lead to a very slow approach to the optimum, following on average an inverse power of the evolutionary time. In addition, our study of the trajectories shows that the out-of-equilibrium effects due to the evolutionary process are very weak. In particular, the distribution of genotypes is close to that arising during equilibrium stabilizing selection. As a consequence, the evolutionary dynamics leave almost no measurable out-of-equilibrium trace, only the transition genotypes (close to the border between different periods of stasis) have atypical mutational properties.

Mendel, the father of genetics took the first steps in defining "contrasting characters, genotypes in F₁ and F₂… and setting different laws". The genotypes of F₂ is dependent on the type of its parents genotype and it follows certain roles. Purpose of this paper is to analyze the second generation genotypes of monohybrid and a dihybrid with a mathematical structure.

We use the concept of H_v-semigroup structure in the F₂-genotypes with cross operation and prove that this is an H_v-semigroup. We determine the kinds of number of the H_v-subsemigroups of F₂-genotypes.

Researchers hope that establishing a notion of proximity using topology will help to clarify the biological processes underlying the evolution of living organisms. The simple model presented here, using RNA shapes, can carry over to more general and complex genotype–phenotype systems. Proximity is an important component of continuity, in both real-world and topological terms. Consequently, phenotype spaces provide an appropriate setting for modeling and investigating continuous and discontinuous evolutionary change.

In this paper, we consider an application of hyperstructure theory in biological inheritance in which we deal with $n$-ary hyperstructures associated to the genotypes of the second generation $F_2$ for $n=2,3,4$. First, we define a hyperoperation × (mating) on $F_2$ and prove that it is a cyclic $H_v$-semigroup under the defined hyperoperation. Then we define a ternary hyperstructure $f$ associated to the genotypes of $F_2$ and prove that $(F_2,f)$ is a ternary $H_v$-semigroup. Finally, we define a $4$-ary hyperstructure $g$ associated to the genotypes of $F_2$ and prove that $(F_2,g)$ is a $4$-ary $H_v$-semigroup.

We study the problem of merging genetic maps, when the individual genetic maps are given as directed acyclic graphs. The problem is to build a consensus map, which includes and is consistent with all (or, the vast majority of) the markers in the individual maps. When markers in the input maps have ordering conflicts, the resulting consensus map will contain cycles. We formulate the problem of resolving cycles in a combinatorial optimization framework, which in turn is expressed as an integer linear program. A faster approximation algorithm is proposed, and an additional speed-up heuristic is developed. According to an extensive set of experimental results, our tool is consistently better than JOINMAP, both in terms of accuracy and running time.

As the diversity of genomic variation data increases with our growing understanding of the role of variation in health and disease, it is critical to develop standards for precise inter-system exchange of these data for research and clinical applications. The Global Alliance for Genomics and Health (GA4GH) Variation Representation Specification (VRS) meets this need through a technical terminology and information model for disambiguating and concisely representing variation concepts. Here we discuss the recent Genotype model in VRS, which may be used to represent the allelic composition of a genetic locus. We demonstrate the use of the Genotype model and the constituent Haplotype model for the precise and interoperable representation of pharmacogenomic diplotypes, HGVS variants, and VCF records using VRS and discuss how this can be leveraged to enable interoperable exchange and search operations between assayed variation and genomic knowledgebases.

This stage of our journey through the universe of one-dimensional binary Cellular Automata is devoted to period-1 rules, constituting the first of the six groups in which we systematized the 88 globally-independent CA rules.

The first part of this article is mainly dedicated to reviewing the terminology and the empirical results found in the previous papers of our quest. We also introduce the concept of the ω-limit orbit with the purpose of linking our work to the classical theory of nonlinear dynamical systems. Moreover, we present the basin tree diagrams of all period-1 rules — except for rule , which is trivial — along with their Boolean cubes and time-1 characteristic functions.

In the second part, we prove a theorem demonstrating that all rules belonging to group 1 have robust period-1 rules for any finite, and infinite, bit-string length L. This is the first time we give analytical results on the behavior of CA local rules for large values of L and, consequently, for bi-infinite bit strings.

The theoretical treatment is complemented by two remarkable practical results: an explicit formula for generating isomorphic basin trees, and an algorithm for creating new periodic orbits by concatenation. We also provide several examples of both of them, showing how they help to avoid tedious simulations.

The 11th part of our tour through one-dimensional binary Cellular Automata concerns period-2 rules, which form the second group in our classification of the 88 globally-independent CA rules according to the properties of their periodic orbits. In this article, we display the basin tree diagrams of all period-2 rules along with their time-2 characteristic functions, and then we prove that all rules belonging to group 2 have robust period-2 ω-limit orbits for any finite, and infinite, bit string length. This rigorous result, which pairs with the one about period-1 rules given in the tenth installment of our chronicle, confirms what we stated about period-2 rules on the basis of empirical evidence. In the second part of this tutorial, we introduce the notion of quasi global-equivalence and prove that there are only 82 quasi globally-independent CA rules. For the first time, we show that the space-time patterns of globally-independent local rules can depend on each other, and we present an example of quasi-global transformation. We also define the super string, and its unique decimal representation , dubbed the super decimal, which provides a completely transparent yet rigorous proof that rule 170 is chaotic when L → ∞. Moreover, we present the basin tree generation formulas, which uncover the analytical relationships between basin trees of globally-equivalent rules. Last but not least, for pedagogical and epistemological reasons, we conclude this paper with the selection of rule137, instead of rule 110, as the prototypic universal Turing machine for our future discourse.