Tag Archives: DNA computing

The Internet can be your pet

or  you could have a pet which embeds and run a copy of the whole Internet.

The story from this post  starts from this exploratory posting on Google plus from June 2nd, 2015, which zooms from sneakernet to sneakernet  delay-tolerant networking to  Interplanetary Internet to Nanonetworks to DNA digital data storage to molecular computers.

I’ll reproduce the final part, then I’ll pass to the Internet as you pet thing.

“At this stage things start to be interesting. There is this DNA digital data storage technique
http://en.wikipedia.org/wiki/DNA_digital_data_storage
which made the news recently by claiming that the whole content of the Net fits into a spoon of DNA (prepared so to encode it by the technique).

I have not been able to locate the exact source of that claim, but let’s believe it because it sounds reasonable (if you think at the scales involved).

It can’t be the whole content of the net, it must mean the whole passive content of the net. Data. A instant (?) picture of the data, no program execution.

But suppose you have that spoonful of DNA, how do you use it? Or what about also encoding the computers which use this data, at a molecular level.

You know, like in the post about one Turing Machine, Two Turing Machines https://plus.google.com/+MariusBuliga/posts/4T19daNatzt
if you want classical computers running on this huge DNA tape.

Or, in principle, you may be able to design a molecular google search …
molecule, which would interact with the DNA data to retrieve some piece of it.

Or you may just translate all programs running on all computers from all over the world into lambda calculus, then turn them into chemlambda molecules, maybe you get how much, a cup of molecular matter?

Which attention:
– it executes as you look at it
– you can duplicate it into two cups in a short matter of time, in the real world
– which makes the sneakernet simply huge related to the virtual net!

Which brings of course molecular computers proposal to the fore
http://chorasimilarity.github.io/chemlambda-gui/dynamic/molecular.html  ”

Let’s develop this a bit! (source)

The following are projections about the possible future of biochemical computations with really big data: the whole, global data produced and circulated by humans.

They are based on estimates of the information content in the biosphere from the article [1] and on a proposal for life like molecular computing.

Here are the facts. In [1] there are given estimates about the information content of DNA in the biosphere, which are used further.

One estimate is that there are about 5 X 10^11 tonnes of DNA, in a biomass of about 2 X 10^12 tonnes, which gives a proportion of DNA in biomass of about 1/40.

This can be interpreted as: in order to run the biochemical computations with 1g of DNA there are needed about 40g of biochemical machinery.

From the estimate that the biomass contains about 5 X 10^30 cells, it follows that 4g of DNA are contained (and thus run in the biochemical computation) in 10^13 cells.

The Internet has about 3 X 10^9 computers and the whole data stored is equivalent with about 5g of DNA [exact citation not yet identified, please provide a source].

Based on comparisons with the Tianhe-2 supercomputer (which has about 3 X 10^6 cores) it follows that the whole Internet processes in a way equivalent as a magnitude order to 10^3 such supercomputers.
From [1] (and from the rather dubious equivalence of FLOPS with NOPS)  we get that the whole biosphere has a power of 10^15 X 10^24 NOPS, which gives for 10^13 cells (the equivalent of 4g of DNA) about 10^17 NOPS. This shows that approximately the power of the biochemical computation of 4g of DNA (embedded in the biochemical machinery of about 160g) is of the same order with the power of computation of the whole internet.

Conclusion until now: the whole Internet could be run in a “pet” living organism of about 200g. (Comparable to a rat.)

This conclusion holds only if there is a way to map silicon and TM based computers into biochemical computations.

There is a huge difference between these two realms, which comes from the fact that the Internet and our computers are presently built as a hierarchy, with multiple levels of control, while in the same time the biochemical computations in a living cell do not have any external control (and there is no programming).

It is therefore hard to understand how to map the silicon and TM based computations (which run one of the many computation paradigms embedded into the way we conceive programming as a discipline of hierarchical control) into a decentralized, fully asynchronous, in a ransom environment biochemical computation.

But this is exactly the proposal made in [2], which shows that in principle this can be done.

The details are that in [2] is proposed an artificial chemistry (instead of the real world chemistry) and a model of computation which satisfies all the requirements of biochemical computations.
(See very simple examples of such computations in the chemlambda collection https://plus.google.com/u/0/collection/UjgbX )

The final conclusion, at least for me, is that provided there is a way to map this (very basic) artificial chemistry into real chemical reactions, then one day you might have the whole Internet as a copy which runs in your pet.

[1] An Estimate of the Total DNA in the Biosphere,
Hanna K. E. Landenmark,  Duncan H. Forgan,  Charles S. Cockell,
http://journals.plos.org/plosbiology/article?id=10.1371/journal.pbio.1002168

[2] Molecular computers,
Marius Buliga, 2015
http://chorasimilarity.github.io/chemlambda-gui/dynamic/molecular.html

Advertisements

Digital materialization and synthetic life

Digital materialization (DM) is not the name of a technology from Star Trek.  According to the wikipedia page

  DM can loosely be defined as two-way direct communication or conversion between matter and information that enables people to exactly describe, monitor, manipulate and create any arbitrary real object.

I linked to the Digital Materialization Group, here is a quote from their page.

DM systems possess the following attributes:

  • realistic – correct spatial mapping of matter to information
  • exact – exact language and/or methods for input from and output to matter
  • infinite – ability to operate at any scale and define infinite detail
  • symbolic – accessible to individuals for design, creation and modification

Such an approach can be applied not only to tangible objects but can include the conversion of things such as light and sound to/from information and matter. Systems to digitally materialize light and sound already largely exist now (e.g. photo editing, audio mixing, etc.) and have been quite effective – but the representation, control and creation of tangible matter is poorly supported by computational and digital systems.

My initial interest in DM came from possible interactions with the Unlimited Detail idea, see this post written some time ago.

Well, there is much more into this idea, if we think about life forms.
In the discussion section of this  article  by Craig Venter et al. we read:

This work provides a proof of principle for producing cells based on computer-designed genome sequences. DNA sequencing of a cellular genome allows storage of the genetic instructions for life as a digital file.

In  his book Life at the speed of light  Craig Venter writes (p. 6)

All living cells run on DNA software, which directs hundreds to thousands of protein robots. We have been digitizing life for decades, since we first figured out how to read the software of life by sequencing DNA. Now we can go in the other direction by starting with computerized digital code, designing a new form of life. chemically synthesizing its DNA, and then booting it up to produce the actual organism.

That is clearly a form of Digital Materialization.

Now, we have these two realms, virtual and real, and the two way bridge between them called DM.

It would be really nice if we would have the same chemistry ruled world:

  • an artificial version for the virtual one, in direct correspondence with those parts of
  • the real version (from the real world) which are relevant for the DM translation process.

This looks like a horribly complex goal to reach, because of the myriad concrete, real stumbling blocks, but hey, this is math for, right? To simplify, to abstract, to define, to understand.

[posted also here]

__________________________________________

How to use chemlambda for understanding DNA manipulations

UPDATE: Probably RNA better than DNA. The best entry point is that document. More in the references at the end of that doc. Or if you like just to see animations, there are aplenty (more than 350) in this collection.

________________

… or the converse: how to use DNA manipulations to understand chemlambda, this is a new thread starting with this post.

This is a very concrete, nice project, I already have some things written, but it is still in a very fluid form.

Everybody is invited to work with me on this. It would be very useful to collaborate with people which have knowledge about DNA and enzymes involved into the processes around DNA.

So, if you want to contribute, then you can do it in several ways:

  • by dedicating a bit of your brain power to concrete parts of this
  • by sending me links to articles which you have previously  read and understood
  • by asking questions about concrete aspects of the project
  • by proposing alternative ideas, in a clear form
  • by criticizing the ideas from here.

I am not interested just to discuss about it, I want to do it.

Therefore, if you think that there is this other project which does this and that with DNA and computation, please don’t mention it here unless you have clear explanations about the connections with this project.

Don’t use authority arguments and name dropping, please.

____________________________________

Now, if anybody is still interested to learn what is this about, after the frightening introduction, here is what I am thinking.

There is a full load of enzymes like this and that,  which cut, link, copy, etc. strings of DNA.  I want to develop a DNA-to-chemlambda dictionary which translates what happens in one world into the other.

This is rather easy to do. We need a translation of arrows and the four nodes from chemlambda into some DNA form.

Like this one, for example:

dna_1,fig

Then we need a translation of the chemlambda moves (or some version of those, see later) into processes involving DNA.

There is plenty of stuff in the DNA world to do the simple things from chemlambda. In turn, because chemlambda is universal, we get a very cheap way of defining DNA processes as computations.

Not as boolean logic computations. Forget about TRUE, FALSE and AND gates.  Think about translating DNA processes into something like lambda calculus.

I know that there is plenty of research about using DNA for computation, and there is also plenty of research about relations between lambda calculus and chemistry.

But I am not after some overarching theory which comprises everything DNA, chemistry and lambda calculus.

Instead, I am after a very concrete look at tiny parts of the whole huge field, based on a specific formalism of chemlambda.

It will of course turn out that there are many articles relevant for what will be found here and there will be a lot of overlap with research already done.

Partially, this is one of the reasons I am searching collaborations around this, in order to not invent wheels all the time, due to my ignorance.

__________________________________________

Chemical concrete machine, short list of gates and moves

Continuing from  Local FAN-IN eliminates GLOBAL FAN-OUT (II)  and   Local FAN-IN eliminates global FAN-OUT (I)  I propose the following list of gates and moves, which are taken from graphic lambda calculus, with the FAN-IN and DIST moves added. (So this could be called the “chemical concrete machine sector”, and it has Turing universality, via the fact that it contains the combinatory logic.)

_______________

Principle: each gate is a molecule, each move is an enzyme.

_______________

Dictionary:  we need four trivalent gates, which can be distinguished one from another by looking at the number of inputs/outputs and from a choice of colour between red and green. To these add the arrows, loops and the termination gate. The translation from graphic lambda calculus notation to this new coloured notation is the following.

convention_1

Each of these gates is a molecule.  [Speculations: (1) by looking at DNA backbones, could be the 5′-3′ phosphate-deoxyribose backbone be used as \rightarrow? ]

_______________

The moves, translated. Each move is made possible by an enzyme (hence move = enzyme). Here is the list, with the names taken from graphic lambda calculus, by using the dictionary for translation.

convention_2

convention_3

convention_6

convention_4

  • Elimination of loops:

convention_5

_______________

Implementation needed, but this is out of my competence.  I was thinking that could be possible by using DNA origami techniques, but it might turn out that the schema here is even more close to the structure of DNA. This is an outrageous speculation, but I can’t stop to remark that there are 4 trivalent gates, making two pairs of duality (seen in the graphic beta move and in the FAN-IN move), and this resembles to the A-T, G-C pairing (but it might be a coincidence).

Chemical concrete machine not algorithmic self-assembly of DNA, nor Turing machine

This post is partially a request for references, partially a place for possible discussions, in the comments, and partially a place for clarifications of the previous post Why build a chemical concrete machine, and how? .

I started to read Erik Winfree’s thesis Algorithmic self-assembly of DNA and, to my joy, I see that at least at the knowledge level of 1998, what I propose is different. Here is a short brief of what I got from Winfree’s thesis  (along with my excuses for not representing things correctly and for misattributions) :

  • Adleman, Lipton, propose a model of DNA computing which uses exponential space, i.e. all the candidates for a solution of a combinatorial problem, each one represented by a strand of DNA, which are then filtered by a sequence of physical, or chemical manipulations of test tubes, of one of the types: separate (a tube into two others, according to the value of the variable at “i” position), merge (two tubes into one), detect. Variants (not due to Adleman, Lipton, Karp) are to add an amplify operation (like a FAN-OUT with variables) which transform a tube into two copies of it. Or (Boneh), instead of amplify, an append operation which adds a new variable with a give value.  All these models have variables and are based on the mechanism of selection of the solution from an exponential sea of candidates.
  • Hagiya, single-strand DNA computation, using a mechanism called “whiplash PCR”, which I don’t understand yet, but which has the computational power of a GOTO program. Has variables.
  • Winfree, single-strand DNA computation, but in 2D, where he proposes a “materialization” of a block cellular automaton (BCA) which has Turing universality. Has variables, tries to make a Turing machine.

_________________

In the post   Why build a chemical concrete machine, and how?   I mentioned Turing machines, but this is obviously wrong, as can be seen by looking at the previous post A chemical concrete machine for lambda calculus. I don’t want to have a ” syringe with 10^9 nano geometrical turing machines”, no, that’s misleading, what I call a chemical concrete machine works with lambda calculus terms (among other graphs, more geometrical, from graphic lambda calculus), which are reduced by chemical reactions (using for example the graphic beta move enzyme). That’s different.

_________________

At page 29 of Winfree’s thesis, there’s a picture illustrating various reactions and results of reactions between DNA strands.  I find interesting the Holliday junction, (image taken from the wiki page)

472px-Holliday_Junctionbecause it’s relation to crossings in knot diagrams. Recall that in the \lambda-TANGLE sector of the graphic lambda calculus, the graphic beta move appears as a SPLICE move.

Compare with these images from 3D crossings in graphic lambda calculus:

3d_crossing_3

3d_crossing_2

_________________

 

As that’s an exploratory post, kind of note to self, but open to anybody, take a look at this short course

[Updates will follow here]

Why build a chemical concrete machine, and how?

Asked about this, I spent a bit thinking and I arrived at  this very brute answer:

What I have in mind can be split in two.

There is a first part concerning graphic lambda calculus seen as it’s about real molecules interacting in space. For this part I would like to construct graphs which are like a Turing machine (or other computing devices) then, the important step is to eliminate everything which is due to our human 1d writing conventions (see details in the rant from the first part of this post) and thinking and simplify such “machines”, in the same way, for example, like I saw it’s possible

A serious tool for doing this would be, for example, a program which allows to visualize and perform moves  (automatically and from the keyboard) on graphs in GRAPH.

The second part, which goes in parallel, would be to try to find in the real world (here DNA origami looks like a possible tool) ways to construct chemically, physically, such machines, which are naturally adapted to the real world because they are geometrical (an object or a property is geometrical if it can be described, or it’s invariant to an arbitrary change of parametrization, in our case, an arbitrary renaming).  For this part I want to understand first how DNA origami works, to the level of being able to absorb information and understand some of the hurdles.  This leads to applications, which are still vague in my head, but I was impressed by this video

as well as by research of Jean-Pierre Banatre and Daniel Le Metayer.

In conclusion, I can’t imagine what a syringe with 10^9 nano geometrical turing machines  graphs representing lambda terms [see UPDATE]  can’t do.

______________

UPDATE:  Corrections to this post are made in  Chemical concrete machine not algorithmic self-assembly of DNA, nor Turing machine   , where it is stressed that the “chemical concrete machine”, even if it has Turing universality property, it is not intended to be a Turing machine, (nor an automaton), as is wrongly suggested in this post.

A chemical concrete machine for lambda calculus

This post is a call for building one. More precisely, for building one for graphic lambda calculus, which satisfies all the requests  from section 5 of The chemical abstract machine by Berry and Boudol  for a calculus more general than lambda calculus.

First a short comment on “The chemical abstract machine”. This is a very interesting article, thanks are due  to Mike Stay for telling me about it, in relation to what is described in my previous post  Can graphic lambda calculus be implemented in some form of DNA computing?  The following quote describes exactly what I was looking for (p.1 from the linked file):

Intuitively, the state of a system is like a chemical solution in which floating molecules can interact with each other according to reaction rules … Solutions are finite multisets of molecules …

But from here I will not jump to identify terms in lambda calculus with solutions, like it’s done in section 5.2 on the \gamma calculus. Nor shall I use membranes and airlocks, as useful as they seem (and probably there is a possible implementation of those in graphic lambda calculus).

Finally, there is something which I don’t understand in the article, concerning variables and substitutions. I might be wrong, please tell if so, but apparently an abstract chemical machine still uses names for variables, which appear as “ions”. What I don’t get is: how are two solutions, each one corresponding to a lambda term, the same if the two lambda terms are the same by renaming the variables?

In graphic lambda calculus there is no such problem, because there are no variable names. Moreover, lambda terms (which appear as certain graphs in graphic lambda calculus) are molecules and the moves between them (like the graphic beta move) are chemical reactions.

How can this be done? Here is sketch, mind you that I propose things which I believe are possible from a chemical perspective, but I don’t have any chemistry knowledge.  If you do, and if you are interested to make a chemical concrete machine for graphic lambda calculus, then please contact me.

The graphs from GRAPH which we need for the lambda calculus sector of the graphic lambda calculus, are  made by three gates corresponding to lambda abstraction, application and fan-out (I shall ignore the termination gate). So we need three molecules.

enzyme_1

The five coloured triangles are parts of the molecules which bond one with the other. Say there is a bond strength associated with each pairing, such that the bigger is the bond strength, more easily the bond is made and more stronger it is.

Remark that the molecules from the right of the figure don’t seem to have oriented arrows inside. That is why we need several types of bonding places. The table of bond strengths is this:

enzyme_3

The strength coefficients are taken out of … my imagination, such that they satisfy a number of mental experiments I did with them.  As you see there are:

  • two bonding places — yellow and red, which correspond to input half-arrows,
  • two bonding places — blue and green, which correspond to output half-arrows,
  • one bonding place – magenta, which can be seen as well as input or output half-arrow.

The bipartite graph from the lower part of the figure shows which bonding places CAN bond (i.e. they have bonding strength not equal to 0).  In the upper part of the figure there is a table with strengths.

As you see, this solves the problem of representing decorated nodes of oriented graphs. Nice.

Now, let’s pass to the main move, the graphic beta move. This should be a chemical reaction. Imagine that we have an enzyme called “beta”, which recognizes magenta-magenta bonds. When it does recognize such a bond, it does like in the next figure:

enzyme_2

So, the beta enzyme cuts the other bonds, like in the middle part of the picture, then the bonding places bond according to the strength table. Voila!

If you want to play with, here is a “chemical” representation of the 2-zipper, try to see how it works.

enzyme_4

I hope this adds more details to my call of building a real, concrete chemical machine (or to recognize one with at least the expressivity of untyped lambda calculus). Can anybody do it?