Skip to main content

Storing Information in DNA (efficiently)

A recent article in the Economist summarizes work done in Cambridge by Dr. Goldman, Dr. Birney and their teams.  They came up with a mapping for data into base pairs for storage in DNA; while today DNA storage is quite expensive, it is quickly decreasing in cost...and DNA has the advantage that information does not decay anywhere near as fast as other current storage mediums; 10's of thousands of years vs a handful.  The DNA format is also unlikely to change, so it may remain a more consistent technology than others.  
The team in Cambridge came up with a way to ensure that base pairs do not repeat, as sequencing errors are much higher when there are strings of the same base.  The encoding table is shown above.  First the digital data is converted to base 3, and then a differential coding is used to write so that no base pair ever repeats.  For example, if the last base was A, and we are looking to encode a 2, then we would write a T.

It struck me immediately that this was not a very efficient coding. Two digits in base 3 have 3^2 = 9 permutations, but the encoding table above has 12 possible transitions.  So, there is 25% wasted space in this encoding mechanism.  

The obvious way to optimize this is to use a (digital) base of  sqrt(12) = 2*sqrt(3).  With sqrt(3) being irrational, this might be a challenge :-)  However, it is easy to take a fixed estimate slightly smaller than sqrt(12), say 3.4641, and use this as the digital base; then we are only wasting a tiny fraction of the 12 transitions. [It would be even easier to use 3.45; the "Digits to be encoded", in the table above, would then be 0, 1.15, and 2.30, as shown below]

Previous 0.00   1.15 2.30 
A C G T
C G T A
G T A C
T A C G

This also points to the fact that although the DNA "format" may be static for many years, the encoding mechanism is most likely going to change over time.  Perhaps we need a standard header using a very simple A and C are 0, G and T are 1, in order to specify the encoding format for the rest of the string.


Popular posts from this blog

Pwned by CarShark

Here is your guide to "sharking" a car. With Carshark, and a little creativity, you to can make your drive to work more interesting.  In the paper they show you how to hook things up so that you can control a car through WiFi. You are sitting at a red light, and want to have a little fun.  How about sending 07 AE 15 A2; this controls the horn frequency?  Drive-by ringtones.  Could be a $1B business.

The Fourth R.

Reading, wRiting, aRithmetic, and algoRithms.  My wife and I were just brainstorming about this: how coding should be the next "basic" skill.  Of course, someone was ahead of us and posted this .  It is awesome to see Mozilla Hackasaurus referenced in this article.  It is a small world. In the early days of the printing press, scholars wrote the books; the press was simply used for production (see this article ).  As time went on, "average" people became familiar with the medium, and used it for their own messages.  We are at just that point with the Web.  Software Engineers write the code, and the Web distributes it.   Software Engineers are the algoRithm scholars of today.  They won't be for long.  Soon algoRithms will be taught starting in elementary school, along with the other three R's.

The Trouble with Physics

I enjoy reading layman physics books.  And, I enjoy the Science vs Religion debates, especially those that cast Science as a Religion. Superstring theory has always both intrigued and bothered me. Intrigued as, on the surface, it has a nice visual "ah ha" about it; the universe is comprised of tiny (zero dimension) vibrating strings, which can form chords and harmonies that result in manifestations that are available to the human senses. Bothered as, below the surface, it is a huge mess of mumbo-jumbo that has no intuitive sense to it.  Relative to relativity (sic), this is a fairly easy statement to make; even a layman can get a grasp of relativity through Einstein's own writings.  But, relative to quantum theory, can Superstring theory really have "no intuitive sense".  What I really mean is that superstring theory has no science behind it - no way to test anything.  Quantum theory, on the other hand, has been tested over and over again. [...