User login
Navigation
Recent blog posts
Random image
Who's online
Search
Relationships between recursive sequences and other topics
"It is remarkable that the deepest ideas of number theory reveal a far-reaching resemblance to the ideas of modern theoretical physics. ... One would like to hope that this resemblance is no accident, and that we are already hearing new words about the World in which we live, but we do not yet understand their meaning."
Yuri I. Manin, pg. 99 in "Mathematics and Physics" (translation of "Matematika i fizika", Birkhauser, Boston 1981)"As knowledge increases, the attitude of science toward the things of the invisible world is undergoing considerable modification. Its attention is no longer directed solely to the earth with all its variety of objects, or to the physical worlds around it; but it finds itself compelled to glance further afield, and to construct hypotheses as to the nature of the matter and force which lie in the regions beyond the ken of its instruments."
Annie Wood Besant in "Thought Forms", 1905
The simplicity of recursive sequences guarantees that they will be related to many topics. Some of these topics are mathematical, some physical, and some are in relation to modeling physical phenomena. In addition to a short discussion of how recursive sequences show their stripes in various fields of study, the various equivalent formal expressions and descriptive language is briefly described. There are different ways of skinning a cat, but the result is always a skinned cat.
Math, geometry
Group Theory
A symmetry group of a Thue - Morse quasicrystal
Jean-Pierre Gazeau, Jacek Miekisz
J. Phys. A: Math. Gen 31 No 23 (12 June 1998) L435-L440
We present a method of coding general self-similar structures. In particular, we construct a symmetry group of a one-dimensional Thue - Morse quasicrystal, i.e. of a nonperiodic ground state of a certain translation-invariant, exponentially decaying interaction.
A symmetry group of a three-dimensional crystal consists of lattice translations, rotations, and reflections. Starting from any point of a crystal, we can reach any other point, successively applying different elements of the symmetry group of the crystal. It was recently shown [1,2] that certain one-dimensional quasicrystals can be built by successive applications, on one of its points, of elements of certain discrete affine semigroups. Here we describe a general method, based on ideas contained in [3,4], of representing self-similar structures by one-sided sequences of two symbols. In particular, we construct a symmetry group of a Thue - Morse quasicrystal, i.e. of a nonperiodic ground state of a certain one-dimensional classical lattice-gas model.
Recursive sequences and number theory
With respect to discrete similarity tilings and knots, see Robert W. Fathauer's Fractal Knots Created by Iterative Substitution. From the abstract:
"A widely-applicable method for iterating knots is described. This method relies on substitution of portions of a knot with smaller copies of the entire knot. A starting knot is first arranged as a patch of tiles that contains individual tiles similar in shape to the overall patch. Iterative substitution leads to the creation of complex knots that are often esthetically pleasing, particularly for knots possessing a high degree of symmetry. The iteration process is designed to allow repetition ad infinitum; i.e., an infinite number of iterations leads to a unicursal fractal that is, therefore, a (wild) knot."
[To Do: Recursive sequences and numeral systems]
[To Do: Analysis, infinite series]
[ To Do: Infinite sums examples, and relation to infinte sequences. These systems are just such infinite sequences, so can be viewed as sinfinite sums. 0101... and 1010... example. Aperiodic deterministic sequences are irrational numbers (and at least some are trancendental numbers ).]
[To Do: Finite geometry combinatorics, group theory. e.g. Steven H. Cullinane's geometry of the square and cube , and "Diamond Theory "]
In mathematics, symbolic dynamics is the practice of modelling a topological or smooth dynamical system by a discrete space consisting of infinite sequences of abstract symbols, each of which corresponds to a state of the system, with the dynamics (evolution) given by the shift operator.
[To Do: Dynamical systems.]
Sandpile dynamics, an example of self-organised criticality in a simple CA type system. Dynamical systems are also used to model movements in the Earth's crust, stock market fluctuations, the formation of traffic jams, and many other physical systems.
Recursive sequences and physics
Recursive sequences, human language and formal grammars
[To Do: Computational topics, finite state automaton, context free grammars. ]
DNA-based computation and algorithmic assembly
Aperiodic tilings (Wang tiles) can be shown to emulate the operation of a Turing machine.
L-systems are a small class of a formal grammar (a set of rules and symbols), in particular a Type-3 grammar without a terminating symbol, which Chompsky (1956, and others) characterized with respect to more complex grammars.
A Type-3 grammar generates the regular languages. Such a grammar restricts its rules to a single nonterminal on the left-hand side and a right-hand side consisting of a single terminal, possibly followed (or preceded, but not both in the same grammar) by a single nonterminal. The ruleis also allowed here if S does not appear on the right side of any rule. These languages are exactly all languages that can be decided by a finite state automaton.
Cellular automata CA can be modeled by a restricted class of these L-systems. The state change of a single cell is represented by a set of rules that maps every possible 3x3 cell sub-array to a single cell state, where the system is understood to act on every overlapping 3x3 cell array. This results in a one-to-one mapping between generations. [Show example system.]
Finite automata and arithmetic , J.-P. Allouche
The notion of sequence generated by a finite automaton, (or more precisely a finite automaton with output function, i. e. a "uniform tag system") has been introduced and studied by Cobham in 1972. In 1980, Christol, Kamae, Mendes France and Rauzy, proved that a sequence with values in a finite field is automatic if and only if the related formal power series is algebraic over the rational functions with coeffcients in this field: this was the starting point of numerous results linking automata theory, combinatorics and number theory.
Several problems in graph and network theory can be described in terms of chaos theory and emergent self-similarity. For example:
Understanding the Long-Term Self-Similarity of Internet Traffic (2001)
Steve Uhlig, Olivier Bonaventure, Lecture Notes in Computer Science
From the Alan Kay Wikipedia entry:
"On 31 August 2006, Kay's proposal to the United States National Science Foundation, NSF, was granted, thus funding Viewpoints Research Institute for several years. The proposal title is: Steps Toward the Reinvention of Programming: A compact and Practical Model of Personal Computing as a Self-exploratorium [4]. A sense of what Kay is trying to do comes from this quote, from the abstract of a seminar on this given at Intel Research Labs, Berkeley: "The conglomeration of commercial and most open source software consumes in the neighborhood of several hundreds of millions of lines of code these days. We wonder: how small could be an understandable practical "Model T" design that covers this functionality? 1M lines of code? 200K LOC? 100K LOC? 20K LOC?" [5]
The system being developed makes extensive use of parsing via a bottom up rewrite grammar [6], [7], [8]."
[To Do: Feedback systems]
[To Do: Information theory]
The Thue-Morse and Period doubling sequence are closely related to Hamming codes and Gray codes, due to the boundaries of anti-symmetries across indices that are powers of two. These codes are used for error detection and correction. The Gray code, also known as the reflected binary code, forms a Hamiltonian cycle on a hypercube, where each bit is seen as one dimension. Also see Gray code Thue-Morse binary fractal and algorithm.
From Hadamard transform (accessed 2008-12-19):
The Hadamard transform (also known as the Walsh-Hadamard transform, Hadamard-Rademacher-Walsh transform, Walsh transform, or Walsh-Fourier transform) is an example of a generalized class of Fourier transforms. It is named for the French mathematician Jacques Solomon Hadamard, the German-American mathematician Hans Adolph Rademacher, and the American mathematician Joseph Leonard Walsh. It performs an orthogonal, symmetric, involutary, linear operation on 2m real numbers (or complex numbers, although the Hadamard matrices themselves are purely real).
The Hadamard transform can be regarded as being built out of size-2 discrete Fourier transforms (DFTs), and is in fact equivalent to a multidimensional DFT of size
. It decomposes an arbitrary input vector into a superposition of Walsh functions.
One of the simplest 2-D recursive systems generates Hadamard matrices, which are also related to Walsh codes. The Hadamard code, based on these matrices, is also a system used for signal error detection and correction:
Note that the right column and bottom row are Thue-Morse sequences.
Also see:
Hadamard Matrices and Weaving'Seeing' The Quantum World: How A Quantum Computer Would Work
“The goal of our animated movie about the quantum computer is to convey to a non-expert audience the nature of quantum computation: its power, how it would work, what it would look like,” says Sanders, who also has an article published in the December issue of Physics World on the making of his four-minute animation.
“The animation incorporates state-of-the-art techniques to show the science and the technology in the most accurate and exciting way possible while being true to the underlying principles of quantum computing,” says Sanders.
Visualizing a silicon quantum computer
2008 New J. Phys. 10 125005 (20pp)Quantum computer operation visualizations (including the Hadamard operation)
Redundancy
The patterns generated by all systems considered are near a maximum of redundancy. This is related to their short description and high algorithmic complexity.[To Do: Fill out and illustrate.]The descriptions of recursive systems are short (low algorithmic complexity), but the system's evolve long strings. These strings are necessarily redundant. One consequence is the rules are maximally sensitive to errors, but the resulting strings are robust: infrequent errors in the evolving strings have small effects on the statistics (distribution of symbols) of the fixed point strings. Given a portion of a string, some aspects of the rules can be inferred, even if there are errors
[
To Do: Self-replicating systems
Recursive systems result in redundant structure (patterns). Recursive block replacement systems -- the rules, transformations, and resulting patterns -- can be viewed as highly simplified self-replicating automata. They have a characteristic peculiar to all self replicating systems; in some sense the rules are encoded in the patterns, and the patterns are encoded in the rules. From an instance of one part of the system, the other parts can be reconstructed.
Recent research [1] has begun to categorize replicators, often based on the amount of support they require.
- Natural replicators have all or most of their design from nonhuman sources. Such systems include natural life forms.
- Autotrophic replicators can reproduce themselves "in the wild". They mine their own materials. It is conjectured that non-biological autotrophic replicators could be designed by humans, and could easily accept specifications for human products.
- Self-reproductive systems are conjectured systems which would produce copies of themselves from industrial feedstocks such as metal bar and wire.
- Self-assembling systems assemble copies of themselves from finished, delivered parts. Simple examples of such systems have been demonstrated at the macro scale.
The design space for machine replicators is very broad. A comprehensive study[2] to date by Robert Freitas and Ralph Merkle has identified 137 design dimensions grouped into a dozen separate categories, including: (1) Replication Control, (2) Replication Information, (3) Replication Substrate, (4) Replicator Structure, (5) Passive Parts, (6) Active Subunits, (7) Replicator Energetics, (8) Replicator Kinematics, (9) Replication Process, (10) Replicator Performance, (11) Product Structure, and (12) Evolvability.
A self-replicating machine is an artificial construct that is theoretically capable of autonomously manufacturing a copy of itself using raw materials taken from its environment.
The concept of self-replicating machines has been advanced and examined by Homer Jacobsen, Edward F. Moore, Freeman Dyson, John von Neumann and in more recent times by K. Eric Drexler in his book on nanotechnology, Engines of Creation and by Robert Freitas and Ralph Merkle in their review Kinematic Self-Replicating Machines[1].
From Asimov's Three Laws of Robotics unsafe?
AI is a recursively self-improving pattern.
"Just as evolution creates order and structure enormously faster than accidental emergence, we may find that recursive self-improvement creates order enormously faster than evolution. If so, we may have only one chance to get this right."
Asimov's laws are not sufficient, said Michael Anissimov, writing in an article on the 3 Laws Unsafe site. "It's not so straightforward to convert a set of statements into a mind that follows or believes in those statements. Two, semantic ambiguity means that without personally understanding the reasons for the laws and the original intent, a robot might misinterpret their meaning, leading to problems. Third, Asimov's Laws ignore the possibility that a robot will acquire the ability to reprogram itself -- an inevitable eventuality if intelligent robots are created."
To Do: Graph of types of self-replicating systems, their environmental types, error correction an homeostasis, and the information phase space they occupy.
To Do: What's the signifiance of two uber-geeks (Adrian Bowyer and Vik Olliver) grinning next to two rapid prototyping (RepRap) machines [First replication]?
Von Neumann Universal Constructor
John von Neumann's Universal Constructor is a self-replicating machine in a cellular automata environment. It was designed in the 1940s, without the use of a computer. The fundamental details of the machine were published in von Neumann's book Theory of Self-Reproducing Automata, completed in 1966 by Arthur W. Burks after von Neumann's death.[2]
Von Neumann's specification defined the machine as using 29 states, these states constituting means of signal carriage and logical operation, and acting upon signals represented as bit streams. A 'tape' of cells encodes the sequence of actions to be performed by the machine. Using a writing head (termed a construction arm) the machine can print out (construct) a new pattern of cells, allowing it to make a complete copy of itself, and the tape.
[Author] in "Information and Nature" argues that living systems can be distinguished from non-living system by whether their dynamics are driven by purely physical forces, or are partly determined by environmental patterns. He uses a prototypical example of a moth's photoxaxis, the pattern of light driving a flight path, with physical forces not providing a full description. Physical forces are used for flight, but the environmental pattern of forces don't determine the moth's path.
What about man-made devices that respond based on pattern? Computers-keyboard systems, a robotic moth with directional or intensity based light detection? I've made a Lego Mindstorms based robot that moves preferentially in the direction of a light field maximum, using two intensity sensitive point photodetectors and a wheel or tread mediated motorized translocation system. What about a thermostat that maintains a temperature homeostasis? [To Do: Diagram(s)]
[Author] discounts these information processing mechanical system as, at best, extensions of other living systems -- ourselves. They are not living systems because their behavior was planned by an entity that was alive, an animal that knows how to respond to pattern such that physice is overridden. It seems that intent, purpose of mind, comes into this arguement. This is a simplification of his argument. He gives a sophisticated analysis of the simplest physical systems -- elementary particle interactions -- that are the building blocks of all non-living systems. But are they not the buliding blocks of a moth and those mechanical systems designer?
I don't buy into this arguement, but over time I haven't come up with an arguement that convinces me it is not true. So now it's a point of that I can't believe, but can discount.
What I do believe is that thinking machines are living systems, only different in that their systems are comprehensible. They can be understood because we designed them, but they may become so comple that we no longer do. We won't be able to think of a way that they could be designed.
But if my point of view is true, there should be an intermediate case, a clear physical system that responds to pattern but was not designed by another living system.
- Glaciers and shaded slopes
- Shaded slopes get cut deeper lead to more shaded slopes.
- Can a pattern that involves small physical forces result in large differences in a separate (largely independent, but for this interaction) system?
- Does a transistor respond to pattern? [To Do: Diagram.]
- BZ reaction
- Where the human observer places reagents toggles the system
- A vision system that performs the same spatial arrangement task is a human extension, not an autonomous life-form.
A virion tail protien structure serves an information processing and physical reaction necessary for reproduction. See, for example, P22 bacteriophage tail machin:
Upon encountering a host bacterium, the tail section of the virion binds to receptors on the cell surface, and delivers the DNA into the cell by use of an injectisome like mechanism (an injectisome is a nanomachine that evolved for the delivery of proteins, by type III secretion). The tail section of the virus punches a hole through the bacterial cell wall and plasma membrane, and the genome passes down the tail into the cell.
Is this a function of the virion that clearly indicates it is living? The structure recognizes (without intention or purpose, presumeably) a cellular surface protien, changes configuration, adheres to the cell surface by interacting with the recognized surface protien causing a configuration change, and the injectosome is activated allowing the virion template and construction instructions (RNA or DNA) to enter a suitable environment for reproduction (the the cell).
The virus depends on other living systems for reproduction, and so is perhaps "just" a machine, an extension of living systems. [To Do: Virus ecology.]
Arthur C. Clarke's Third Law, of his laws of prediction:
"Any sufficiently advanced technology is indistinguishable from magic."
Just after I wrote this, I saw the reports of a study in Science that appears to have created self-propogating and limited evolutionary selection of a chemical system:
Self-Sustained Replication of an RNA Enzyme
Tracey A. Lincoln and Gerald F. Joyce
An RNA enzyme that catalyzes the RNA-templated joining of RNA was converted to a format whereby two enzymes catalyze each other’s synthesis from a total of four oligonucleotide substrates. These cross replicating RNA enzymes undergo self-sustained exponential amplification in the absence of proteins or other biological materials. Amplification occurs with a doubling time of about one hour, and can be continued indefinitely. Populations of various cross-replicating enzymes were constructed and allowed to compete for a common pool of substrates, during which recombinant replicators arose and grew to dominate the population. These replicating RNA enzymes can serve as an experimental model of a genetic system. Many such model systems could be constructed, allowing different selective outcomes to be related to the underlying properties of the genetic system.
Erik A. Schultes and David P. Bartel Science 21 July 2000:
Vol. 289. no. 5478, pp. 448 - 452
We describe a single RNA sequence that can assume either of two ribozyme folds and catalyze the two respective reactions. The two ribozyme folds share no evolutionary history and are completely different, with no base pairs (and probably no hydrogen bonds) in common. Minor variants of this sequence are highly active for one or the other reaction, and can be accessed from prototype ribozymes through a series of neutral mutations. Thus, in the course of evolution, new RNA folds could arise from preexisting folds, without the need to carry inactive intermediate sequences. This raises the possibility that biological RNAs having no structural or functional similarity might share a common ancestry. Furthermore, functional and structural divergence might, in some cases, precede rather than follow gene duplication.
RNA STRUCTURE: Ribozyme Evolution at the Crossroads
Gerald F. Joyce
Science 21 July 2000:
Vol. 289. no. 5478, Perspectives, pp. 401 - 402
It is a fundamental tenet of biology that the amino acid sequence of a protein determines its structure, which in turn determines its function. If two proteins have a similar sequence, then their structures and functions are likely to be similar. The same may be said of RNA molecules that behave as enzymes (called ribozymes). Sequence similarity between two such RNA molecules implies that they have the same structure and function. Or does it? On page 448 of this issue, Schultes and Bartel (1) present an example of one RNA sequence that can adopt two completely different structures, each having a distinct catalytic activity. Furthermore, they demonstrate that a continuum of mutations in this common RNA sequence leads in a stepwise manner to sequences that are optimized exclusively for one catalytic activity or the other. This shows that smooth evolutionary pathways exist between distinct ribozymes, facilitating the rapid evolution of RNA-based catalytic activities.
The two catalytic activities selected by the investigators have no evolutionary relationship. One activity is the cleavage of RNA catalyzed by the hepatitis delta virus (HDV) ribozyme, which assists in the replication of HDV viral RNA (2). The other is RNA ligation catalyzed by the class III ligase ribozyme, an activity obtained in the laboratory through "test-tube" evolution (3). The two catalyzed reactions have distinct mechanisms (see the figure). RNA is cleaved by the HDV ribozyme through attack by an internal 2' hydroxyl on the adjacent phosphate, forming a 2',3'-cyclic phosphate and releasing an oligonucleotide 5'-hydroxyl. RNA ligation by the class III ligase occurs through attack by the terminal 2'-hydroxyl group of an oligonucleotide substrate on the a-phosphate of an oligonucleotide 5'-triphosphate, forming a 2',5'-phosphodiester linkage and releasing inorganic pyrophosphate. The two ribozymes have approximately 25% sequence similarity (no more than would be expected by chance) and adopt completely different secondary and tertiary structures.
A switch-hitting enzyme. A single RNA molecule has been engineered to adopt two different structures: that of the class III ligase ribozyme (left) or that of the HDV ribozyme (right). Each base-paired region in the ligase ribozyme is indicated by a different color (left). These regions are completely rearranged in the HDV ribozyme (right). The reaction catalyzed by each ribozyme is different, resulting in the formation of a 2',5'-phosphodiester (left) or the cleavage of a 3',5'-phosphodiester (right).
After careful examination of the HDV and class III ligase ribozymes, Schultes and Bartel constructed an "intersection sequence" that simultaneously satisfied the requirements for both catalytic activities. This is no small feat. Imagine generating a string of text that, without changing the order of a single letter, could be grouped into different words so as to provide two paragraphs that have entirely different meanings. This would be a near-impossible task with an alphabet of 26 letters (or 20 amino acids), especially if the paragraphs (or proteins) had a complex structure. The task is less difficult with RNA molecules because they contain only four "letters"--A, U, G, and C. Furthermore, the letters are interchangeable in a pairwise fashion (maintaining Watson and Crick pairing) within stem structures or individually within single-stranded regions of RNA. Another advantage of RNA is wobble pairing, which allows G to pair with either C or U, and U to pair with either A or G.
The HDV and class III ligase ribozymes studied by Schultes and Bartel contain 85 and 84 nucleotides, respectively. The secondary structure of these RNAs is well known, and a crystal structure of the HDV ribozyme has been reported (4). In converting the HDV ribozyme to the intersection sequence, the authors changed the nucleotide composition of 11 base pairs, altered 16 unpaired residues, converted one base pair to unpaired nucleotides, and replaced three Watson-Crick pairs by wobble pairs. In converting the class III ligase ribozyme to the intersection sequence, they changed the composition of 13 base pairs, altered 11 unpaired residues, converted one base pair to unpaired nucleotides, and replaced one Watson-Crick pair by a wobble pair. The resulting intersection sequence is both fish and fowl. Most of the time it folds into the shape of the class III ligase ribozyme and has a ligation rate that is about 750-fold greater than that of the uncatalyzed reaction. But some of the time it folds into the shape of the HDV ribozyme and has an RNA cleavage rate that is 70-fold greater than that of the uncatalyzed reaction.
Schultes and Bartel then devised a series of RNA sequence mutants that represented all of the steps in the pathways from the intersection sequence to the standard form of either the HDV or class III ligase ribozyme. Each pathway contained 25 steps, with one or two mutations introduced per step and with either cleavage or ligation activity maintained throughout. The first few steps from the intersection sequence had the most impact. A single mutation resulted in an improvement in RNA-cleavage activity by a factor of 120 and a reduction in ligation activity by half. A second mutation provided another factor of 10 improvement in RNA-cleavage activity and reduced ligation activity to undetectable levels. A single mutation in the opposite direction improved ligation activity by a factor of 120 and reduced RNA-cleavage activity to undetectable levels; a second mutation in that direction resulted in another factor of 5 improvement in ligation activity.
It is not unusual for an RNA or protein molecule to exist in more than one conformation. Alternative conformations are a frequent source of interest (and aggravation) for enzymologists and structural biologists. Different conformations of a macromolecule may be associated with different biochemical properties, a notorious example being the soluble and insoluble forms of the prion protein (5). The intersection sequence of Schultes and Bartel, however, is the first example of a molecule that can adopt two different conformations, each associated with a distinct catalytic activity.
New enzymes can arise after a gene duplication event, with one gene copy retaining the original activity and the other diverging to adopt a new function. The new function is likely to be similar to the old one, perhaps involving a different substrate or a related reaction mechanism (6). In some cases the new activity is thought to derive from the "catalytic promiscuity" of the original enzyme, which has the ability to catalyze a reaction other than the one for which it evolved, albeit at a very low level (7). Combining the notion of catalytic promiscuity with that of alternative conformations, one can regard different conformations as providing an evolutionary opportunity similar to that afforded by duplicated genes. The dominant conformation retains the original function of the enzyme, whereas another conformation is free to evolve a new function. In this way, diversification might precede gene duplication, although a duplication event would eventually be needed to allow independent optimization of the two functions. An example of conformational opportunism in enzyme evolution is seen in the maturation of a catalytic antibody: The mature antibody takes on one of the several conformations in which the corresponding germ line antibody can exist (8).
More so than proteins, RNA molecules are amenable to the exploration of alternative conformations. The reason for this is that RNA has four subunits that are highly interchangeable. In addition, distinct conformations of an RNA molecule often are separated by only a few mutations. A computational analysis of the "neighborhood" of a typical RNA secondary structure demonstrated that these neighborhoods often overlap (9). Thus, a succession of modest sequence changes can give rise to a succession of structural and associated functional changes. An extreme example of this behavior is seen in the Schultes and Bartel study, which demonstrates that even without a sequence change, dramatic alterations in structure and function do occur.
Compared to proteins, RNA molecules are sorely lacking when it comes to the chemical diversity of their subunits. Ribozymes cannot match their protein counterparts in catalytic sophistication or the ability to sustain a complex biochemistry. No wonder that the "RNA world" (the presumed ancestral era during which life was based on RNA genes and RNA catalysts) was replaced by a genetic system based on DNA and protein. On the other hand, RNA appears to be built for speed in the arena of Darwinian evolution. Nearly every RNA sequence is soluble in aqueous solution. The secondary structural components of RNA are simple, modular, and highly tolerant of sequence variation. Moreover, evolutionary pathways exist that allow easy traversal between distinct structural and functional motifs. The time during which RNA-based evolution dominated life on Earth may have been brief, but it is likely to have been a fast ride.
References
- E. A. Schultes and D. P. Bartel, Science 289, 448 (2000).
- M. Y.-P. Kuo, L. Sharmeen, G. Dinter-Gottlieb, J. Taylor, J. Virol. 62, 4439 (1988) [Medline].
- E. Ekland, J. Szostak, D. Bartel, Science 269, 364 (1995) [Medline].
- A. R. Ferré-D'Amaré, K. Zhou, J. A. Doudna, Nature 395, 567 (1998) [Medline].
- K. Pan et al., Proc. Natl. Acad. Sci. U.S.A. 90, 10962 (1993) [Medline].
- R. A. Jensen, Annu. Rev. Microbiol. 30, 409 (1976) [Medline].
- P. J. O'Brien and D. Herschlag, Chem. Biol. 6, R91 (1999) [Medline].
- G. J. Wedemayer, L. Wang, P. A. Patten, P. G. Schultz, R. C. Stevens, Science 276, 1665 (1997).
- W. Fontana and P. Schuster, Science 280, 1451 (1998).
From http://blog.wired.com/wiredscience/2009/01/replicatingrna.html
Life makes more of itself.
And now so can a set of custom-designed chemicals. Chemists have shown that a group of synthetic enzymes replicated, competed and evolved much like a natural ecosystem, but without life or cells.
"So long as you provide the building blocks and the starter seed, it goes forever," said Gerald Joyce, a chemist at the Scripps Research Institute and co-author of the paper published Thursday in Science. "It is immortalized molecular information."
Joyce's chemicals are technically hacked RNA enzymes, much like the ones we have in our bodies, but they don't behave anything like those in living creatures. But, these synthetic RNA replicators do provide a model for evolution — and shed light on one step in the development of early living systems from on a lifeless globe.
Scientists believe that early life on Earth was much more primitive than what we see around us today. It probably didn't use DNA like our cells do. This theory of the origin of life is called the RNA World hypothesis, and it posits that life began using RNA both to store information, like DNA does now, and as a catalyst allowing the molecules to reproduce. To try to understand what this life might have looked like, researchers are trying to build models for early life forms and in the process, they are discovering entirely new lifelike behavior that nonetheless isn't life, at least as we know it.
As Joyce put it, "This is more of a Life 2.0 thing."
The researchers began with pairs of enzymes they've been tweaking and designing for the past eight years. Each member of the pairs can only reproduce with the help of the other member.
"We have two enzymes, a plus and a minus," Joyce explains. "The plus assembles the pieces to make the minus enzyme, and the minus enzyme assembles the pieces to draw the plus. It's kind of like biology, where there is a DNA strand with plus and minus strands."
From there, Joyce and his graduate student Tracey Lincoln, added the enzymes into a soup of building blocks, strings of nucleic bases that can be assembled into RNA, DNA or larger strings, and tweaked them to find pairs of enzymes that would reproduce. One day, some of the enzymes "went critical" and produced more RNA enzymes than the researchers had put in.
It was an important day, but Joyce and Lincoln wanted more. They wanted to create an entire population of enzymes that could replicate, compete and evolve, which is exactly what they did.
"To put it in info speak, we have a channel of 30 bit capacity for transferring information," Joyce said. "We can configure those bits in different ways and make a variety of different replicators. And then have them compete with each other."
But it wasn't just a bunch of scientist-designed enzymes competing, like a miniature molecular BattleBots sequence. As soon as the replicators got into the broth, they began to change.
"Most of the time they breed true, but sometimes there is a bit flip — a mutation — and it's a different replicator," explained Joyce.
Most of these mutations went away quickly, but — sound familiar? — some of the changes ended up being advantageous to the chemicals in replicating better. After 77 doublings of the chemicals, astounding changes had occurred in the molecular broth.
"All the original replicators went extinct and it was the new recombinants that took over," said Joyce. "There wasn't one winner. There was a whole cloud of winners, but there were three mutants that arose that pretty much dominated the population."
It turned out that while the scientist-designed enzymes were great at reproducing without competition, when you put them in the big soup mix, a new set of mutants emerged that were better at replicating within the system. It almost worked like an ecosystem, but with just straight chemistry.
"This is indeed interesting work," said Jeffrey Bada, a chemist at the Scripps Institution of Oceanography, who was not involved with the work. It shows that RNA molecules "could have carried out their replication in the total absence" of the more sophisticated biological machinery that life now possesses.
"This is a nice example of the robustness of the RNA world hypothesis," he said. However, "it still leaves the problem of how RNA first came about. Some type of self-replicating molecule likely proceeded RNA and what this was is the big unknown at this point."
[[ Jared Diamond, in "Guns, Germs and Steel: the fates of Human Societies" 1997, Ch. 13, 258-270, has a short oberview of the autocatalysis of technology. Can technology be considered a system itself, within the context of societies, that maintain homeostasis and promote the development of new technologies? Vonnegut's "Player Piano". Wiener's Cybernetics: "The organism is the message"]]
]
From Wikipedia's Redundancy (information theory) (accessed 2008-09-27)
Redundancy in information theory is the number of bits used to transmit a message minus the number of bits of actual information in the message. Informally, it is the amount of wasted "space" used to transmit certain data. Data compression is a way to reduce or eliminate unwanted redundancy, while checksums are a way of adding desired redundancy for purposes of error detection when communicating over a noisy channel of limited capacity.
Biological systems and bioinformatics (and other natural processes)
Why aren't these systems commonly used to describe natural processes? Are they rare, or difficult to recognize? Certainly many complex biological processes use processes that are related to recursive replacement systems, for example trees branch and the branches branch, but mechanistic descriptions are hard to come by.
Przemyslaw Prusinkiewicz advanced the idea that instances of the Fibonacci numbers/sequence in nature can be in part understood as the expression of certain algebraic constraints on free groups, specifically as certain Lindenmayer grammars (Prusinkiewicz, Przemyslaw; James Hanan (1989). Lindenmayer Systems, Fractals, and Plants (Lecture Notes in Biomathematics). Springer-Verlag. ISBN 0-387-97092-4).
Erwin Schrödinger's comparison of genes to aperiodic crystals, in his essay "What is Life?".
Also, from his Wikipedia page:
"In 1944, he wrote What is Life?, which contains a discussion of Negentropy and the concept of a complex molecule with the genetic code for living organisms. According to James D. Watson 's memoir, DNA, The Secret of Life, Schrödinger's book gave Watson the inspiration to research the gene, which led to the discovery of the DNA double helix structure. Similarly, Francis Crick , in his autobiographical book What Mad Pursuit, described how he was influenced by Schrödinger's speculations about how genetic information might be stored in molecules."Epigenetics, the effect on gene expression that is not a direct consequence of the genetic code
(from Tackling A Hard-to-treat Childhood Cancer By Targeting Epigenetic Changes )
Giving chromosomes their structure and shape, strands of DNA, shown in gray, are coiled around histones, depicted as spheres. In MLL-rearranged ALL, a form of acute lymphoblastic leukemia affecting infants, an enzyme call DOT1L modifies the histones by methylating them in an abnormal way (as indicated in orange), leading to inappropriate activation of cancer-promoting genes. Drugs inhibiting this enzyme could prevent a variety of cancerous changes in cells. (Credit: Eric Smith, Dana-Farber Cancer Institute)
From One Genome, Many Types of Cells. But How?
NICHOLAS WADE
New York Times, February 23, 2009
(Good description of the range of epigenetic mechanisms and effects)
"One of the enduring mysteries of biology is that a variety of specialized cells collaborate in building a body, yet all have an identical genome. Somehow each of the 200 different kinds of cells in the human body — in the brain, liver, bone, heart and many other structures — must be reading off a different set of the hereditary instructions written into the DNA.
...
The epigenome consists of many million chemical modifications, or marks as they are called, that are made along the length of the chromatin, the material of the chromosomes. The chromatin includes the double-stranded ribbon of DNA and the protein spools around which it is wound. Some of the marks that constitute the epigenome are made directly on the DNA, but most are attached to the short tails that stick out from the protein spools. Marks of a certain kind generally extend through a large region or domain of the DNA that covers one or more genes. They are recognized by chromatin regulator proteins that perform the tasks indicated by each kind of mark.
In some marked domains, the regulators cause the DNA to be wound up so tightly that the genes are permanently inaccessible. The center and tips of the chromosomes are sites of such repressive domains. So is one of the two X chromosomes in every woman’s cells, a step that ensures both male and female cells have the same level of activity of the X-based genes.
In other domains, the marks are more permissive, allowing the gene regulators called transcription factors to find their target sites on the DNA. The transcription factors then recruit other members of the complex transcription machinery that begins the process of copying the genes and making the proteins the cell needs. A third kind of domain must be established ahead of the transcription machinery to let it roll along the DNA and transcribe the message in the underlying gene."
Evolving L-Systems to Capture Protein Structure Native Conformations, a book chapter of Genetic Programming by Gabi Escuela, Gabriela Ochoa and Natalio Krasnogor
"A protein is a linear chain of amino acids that folds into a unique functional structure, called its native state. In this state, proteins show repeated substructures like alpha helices and beta sheets. This suggests that native structures may be captured by the formalism known as Lindenmayer systems (L-systems). In this paper an evolutionary approach is used as the inference procedure for folded structures on simple lattice models. The algorithm searches the space of L-systems which are then executed to obtain the phenotype, thus our approach is close to Grammatical Evolution. The problem is to find a set of rewriting rules that represents a target native structure on the lattice model. The proposed approach has produced promising results for short sequences. Thus the foundations are set for a novel encoding based on L-systems for evolutionary approaches to both the Protein Structure Prediction and Inverse Folding Problems."
Language oriented bioinformatics, a list of references and a short summary.
Also see:
Information theory: a short introduction to its application in genetics, particularly redundancy.
Pattern formation, orderly outcomes of self-organisation and the common principles behind similar patterns.
In developmental biology, pattern formation refers to the generation of complex organizations of cell fates in space and time. Pattern formation is controlled by genes. The role of genes in pattern formation is best understood in the anterior-posterior patterning of embryos from the model organism Drosophila melanogaster (fruit fly).
Language of Life by David Pescovitz
What does the work of famed theoretical linguist Noam Chomsky have to do with bioengineering? DNA is just another language that can be translated, says Ian Holmes, a UC Berkeley computational biologist. Holmes is applying Chomsky's theories about grammar and syntax to the piles of genetic data that's emerging from DNA sequencing efforts around the world.
...
The trick is aligning the sequenced genomes from various species so that they can be combed for similarities and differences. Bioinformatics tools already exist to do this, Holmes explains, but the datasets now available only contain hundreds of genes. What kinds of tools are necessary when thousands, millions, or even billions of genes are available for comparison?
Holmes and his colleagues are developing new tools built to scale up to these massive data sets. They draw freely from such seemingly disparate fields as statistical physics, machine learning, probability theory, and, yes, linguistics.
In the 1950s, Chomsky developed a method to mathematically analyze and describe the grammar of languages. The authors of computer programming languages found inspiration in Chomsky's approach and it's also commonly used in natural language computer interfaces and translation tools. For example, a simple translation system for dialects of English would automatically substitute the American word "diaper" for the British term "nappie" or replace "or" in "color" with "our." A more complex system that can parse syntax would use a "tree tranducer" to make even more advanced substitutions such as "I have already eaten" to "I already ate."
Engineering and design
Omnidirectional reflection of electromagnetic waves on Thue-Morse dielectric multilayers
F. Qiu - R. W. Peng - X. Q. Huang - X. F. Hu - Mu Wang - A. Hu - S. S. Jiang - D. Feng
National Laboratory of Solid State Microstructures and Department of Physics, Nanjing University - Nanjing 210093, PRC
Europhys. Lett., 68 (5), p. 658 (2004), published online 3 November 2004We report here the reflection of electromagnetic waves in self-similar Thue-Morse dielectric multilayers, which presents the features of multiple omnidirectional photonic bandgaps (PBGs). The number and the width of omnidirectional PBG depend on the ratio of the refraction indexes and the thicknesses of the dielectric materials. The theoretical result is partly verified by optical observation in Thue-Morse
multilayers with visible and near-infrared light. Our investigations provide a new approach to achieve the omnidirectional reflection in multiple frequency ranges. With this progress, the application of dielectric reflection mirrors can be further widened.
Assembling Materials with DNA as the Guide
Faisal A. Aldaye, Alison L. Palmer, Hanadi F. Sleiman Science 26 September 2008:
Vol. 321. no. 5897, pp. 1795 - 1799In this approach, DNA tiles are typically made using strands with different sequences to prevent the formation of undesired structures. In practice, however, this requires synthesizing a large number of components and mixing these in exact stoichiometric ratios for successful assembly. By incorporating identical sequences (sequence symmetry) in DNA strands, Mao found that a stable four-way junction can be constructed from three strands instead of nine and that it assembles into the desired square grid array with an increased long-range order (2). Yan used sequence symmetry to tackle the problem of constructing finite arrays, rather than extended 2D assemblies, from a small number of DNA tiles (2). Thus, judicious incorporation of sequence symmetry in DNA strands merely used as architectural elements, such as struts and junctions, can simplify tile-based assembly. Winfree proposed the concept of "algorithmic DNA self-assembly" to increase complexity in DNA assembly. This was achieved by designing a set of DNA building blocks that represent "Wang tiles." Conceptually, Wang tiles contain a single color on each of their four sides and assemble so that the adjacent sides of each square are of the same color. This requirement necessarily means that each tile can fit in a specific manner within the assembly. Winfree adapted this methodology to construct rectangular-shaped DNA tiles, with four addressable sticky ends at each side as Wang tiles, and demonstrated the feasibility of assembling these according to a set of algorithmic rules initiated by a nucleating strand. Impressively complex fractal patterns can be generated using this approach, from a minimal set of DNA tiles (3).
Using fractal structures for antenna design.
L-System Tool for Generating Fractal Antenna Structures with Ability to Export into EM Simulators
Directory of Open Access Journals (DOAJ ), 2006
Pavel HAZDRA, Miloš MAZÁNEK
Department of Electromagnetic Field, Czech Technical University, Technická 2, 166 27 Praha, Czech RepublicAn L-System (Lindenmayer system) is a scheme primarily developed in the area of the computer science for simulating the development of biological structures. It has also been found very useful for generating the geometry of various fractal antennas. A Matlab environment has been used for both implementing an in-plane L-systems algorithm and for creating appropriate files for widely used EM simulators like the IE3D and the CST Microwave Studio. Finally, the performance of the developed script is demonstrated on two fractal microstrip patch antennas.
(Thesis Abstract of Geraldine Sarmiento
Interactive Telecommunications Program
New York University, Spring 2006.)A beautiful exposition with nice quotes and general development.
"The fascination for the underlying structure of forms and patterns in the natural and artificial world has been with me since childhood. Self-similar and fractal-like forms inspired my imagination in the perception and confusion of scale. I would imagine worlds within worlds in all scales. Why are there similarities in the forms of nature in various scales? Why does repetition and variation of form create harmony in poetry? in wallpaper? in music? in architecture? Why do we seek patterns in everything? These are just some of the questions I’ve asked myself in my curiosity for the wonderful mysteries and the great variety of forms in all things. Through the focus on transitions in growth and form, I hope to discover the process by which complexity and beauty emerge through the use of L-systems.
[To Do: Cybernetics.]
"The Principia Cybernetica Project (PCP) is a collaborative, computer-supported attempt to develop a complete cybernetic and evolutionary philosophy. Such a philosophical system should arise from a transdisciplinary unification and foundation of the domain of Systems Theory and Cybernetics. Similar to the metamathematical character of Whitehead and Russell's "Principia Mathematica", PCP is metacybernetical: cybernetic tools and methods are used to analyze and develop cybernetic theory (see our methodology) "
"The Project aims to develop a complete philosophy or "world-view", based on the principles of evolutionary cybernetics, and supported by collaborative computer technologies."
"We hold that in our time, the age of information, it is systems science and cybernetics, as the general sciences of organization and communication, that can provide the basis for contemporary philosophy. Therefore, this philosophical system is derived from, and further develops, the basic principles of cybernetics."
[To Do: Tilings, as a separate topic under Simple Recursive Systems. ]
[To Do: Simple aperiodic square tilings. Motif replacement. Weaves. Fractal tilings and fractal prototiles.]
[To Do: 1 and 2-D periodic patterns -- the frieze and wallpaper groups.]
2008-08-21 Ted Bell writes:
"I've made a chart showing how four types of transformation can be applied to 4 basic shapes generating 16 different possibilities. This set of 16 is degenerate in a couple of ways that leads back to the 7 friezes.
The four basic shapes are assymmetrical vertical symmetry only horizontal symmetry only chiral symmetry about the center four transformations are:glide (or simple translation)
glide reflect (like a barrel roll, twisting like a screw along the axis of movement)
rolling glide (like a forward roll)
spinning roll (moving along the axis but doing a 180 turn)
These are of course very similar to conways descriptions of the 7 frieze movements, but I believe they reveal something that is obscured in the set of 7, namely how the larger set is degenerate.
I believe that I can do the same thing with the wall paper groups, with the addition of a couple of basic shapes (triangle, hex), and multiplying the transformations in both directions. It's a larger table, but large portions of it are degenerate. However some of the degeneracies are interesting, in that they aren't simple duplications, but rather large complexes which have the same symmetry properties as the smaller basic shapes."2008-08-24 Ted Bell writes:
This isn't the frieze chart, but it is a set of tilings generated by applying one of four types of transforms along on direction and another four along a second.
It's only the set generated by one assymmetrical unit. There are two versions, in the second version there is a one unit glide/offset.
- Login to post comments
Recent comments
18 weeks 4 days ago
19 weeks 3 days ago
19 weeks 3 days ago
21 weeks 8 hours ago
21 weeks 1 day ago
24 weeks 2 days ago
30 weeks 3 days ago
30 weeks 3 days ago
31 weeks 3 days ago
35 weeks 6 days ago