Shannon's Mathematical Theory of Communication Applied to DNA Sequencing

If we could have James Joyce and Robert Anton Wilson in the mix we might get close to something very really close to 'the tale of the tribe'. With a focus on RAW's book 'Coincidance' in which he defines DNA based information theory through a Joycean measure of the redundancy of information, poetry as information, political speeches as low. love, fly.

 

Shannon's Mathematical Theory of Communication Applied to DNA Sequencing

Nobody knows which sequencing technology is fastest because there has never been a fair way to compare the rate at which they extract information from DNA. Until now.

kfc 04/02/2012

• 2 Comments

One of the great unsung heroes of 20th-century science is Claude Shannon, an engineer at the famous Bell Laboratories during its heyday in the mid-20th century. Shannon's most enduring contribution to science is information theory, which underpins all digital communication.
In a famous paper dating from the late 1940s, Shannon set out the fundamental problem of communication: to reproduce, at one point in space, a message that has been created at another. The message is first encoded in some way, transmitted, and then decoded.

Shannon's showed that a message can always be reproduced at another point in space with arbitrary precision provided noise is below some threshold level. He went on to work out how much information could be sent in this way, a property known as the capacity of this information channel.

Shannon's ideas have been applied widely to all forms of information transmission with much success. One particularly interesting avenue has been the application of information theory to biology--the idea that life itself is the transmission of information from one generation to the next.

That type of thinking is ongoing, revolutionary, and still in its early stages. There's much to come.
Today, we look at an interesting corollary in the area of biological information transmission. Abolfazl Motahari and pals at the University of California, Berkeley, use Shannon's approach to examine how rapidly information can be extracted from DNA using the process of shotgun sequencing.

The problem here is to determine the sequence of nucleotides (A, G, C, and T) in a genome. That's time-consuming because genomes tend to be long--for instance, the human genome consists of some 3 billion nucleotides or base pairs. This would take forever to sequence in series.
So the shotgun approach involves cutting the genome into random pieces, consisting of between 100 and 1,000 base pairs, and sequencing them in parallel. The information is then glued back together in silico by a so-called reassembly algorithm.

Of course, there's no way of knowing how to reassemble the information from a single "read" of the genome. So in the shotgun approach, this process is repeated many times. Because each read divides up the genome in a different way, pieces inevitably overlap with segments from a previous run. These areas of overlap make it possible to reassemble the entire genome, like a jigsaw puzzle.

That smells like a classic problem of information theory, and indeed various people have thought about in this way. However, Motahari and co go a step further by restating it more or less exactly as an analogue of Shannon's famous approach.

They say the problem of genome sequencing is essentially of reproducing a message written in DNA, in a digital electronic format. In this approach, the original message is in DNA, it is encoded for transmission by the process of reading, and then it is decoded by a reassembly algorithm to produce an electronic version.

What they prove is that there is a channel capacity that defines a maximum rate of information flow during the process of sequencing. "It gives the maximum number of DNA base pairs that can be resolved per read, by any assembly algorithm, without regard to computational limitations," they say.

That is a significant result for anybody interested in sequencing genomes. An important question is how quickly any particular sequencing technology can do its job and whether it is faster or slower than other approaches.

That's not possible to work out at the moment because many of the algorithms used for assembly are designed for specific technologies and approaches to reading. Motohari and co say there are at least 20 different reassembly algorithms, for example. "This makes it difficult to compare different algorithms," they say.

Consequently, nobody really knows which is quickest or even which has the potential to be quickest.

The new work changes this. For the first time, it should be possible to work how close a given sequencing technology gets to the theoretical limit.

That could well force a clear-out-dead-wood from this area and stimulate a period of rapid innovation in sequencing technology.

Ref: arxiv.org/abs/1203.6233: Information Theory of DNA Sequencing

http://www.technologyreview.com/blog/arxiv/27689/

Bit By Bit, 'The Information' Reveals Everything

http://www.npr.org/player/v2/mediaPlayer.html?action=1&t=1&islist=false&id=134366651&m=134371366

March 8, 2011

The Information, written by James Gleick, covers nearly everything — jungle drums, language, Morse code, telegraphy, telephony, quantum mechanics, thermodynamics, genetics and more — as it relates to information, which he describes as the "fundamental core of things." Information theory can now be seen as the overarching concept for our times, describing how scientists in many disciplines see a common thread to their work.

Gleick's book spans centuries and geographic locations, but one person stays throughout the story for almost 400 pages: Claude Shannon, an engineer and mathematician who worked at Bell Labs in the mid-20th century. Shannon created what is now called information theory, Gleick tells Robert Siegel on All Things Considered:

"He was the first person to use the word 'bit' as a scientific unit of measuring this funny abstract thing that until this point in time scientists had not thought of as a measurable scientific quantity."

Bits are more commonly recognized as the 1s and 0s that enable computers to store and share information, but can also be thought of in this context as a yes/no, either/or or on/off switch. Gleick describes the bit as "the irreducible quantum of information," upon which all things are built.

Just like Isaac Newton took vague words like "force" and "mass" that had fuzzy contemporary meanings and turned them into specific mathematical definitions, "information" now can refer to a specific scientific definition similar to a bit.

"Binary yes or no choices are at the root of things," Gleick explains. The physicist John Archibald Wheeler coined an epigram to encapsulate the concept behind information theory: "It from bit." It described the idea that the smallest particle of every piece of matter is a binary question, a 1 or a 0. From these pieces of information, other things could develop — like DNA, matter and living organisms. The field of information theory, in addition to creating new meanings for words like "information," also builds upon knowledge from other scientific disciplines such as thermodynamics, even though the result may be a little tough to understand.
James Gleick also wrote Chaos: Making a New Science, which popularized the idea of the butterfly effect. His books have been finalists for the Pulitzer Prize and the National Book Award.
Phylis Rose

James Gleick also wrote Chaos: Making a New Science, which popularized the idea of the butterfly effect. His books have been finalists for the Pulitzer Prize and the National Book Award.

"When Claude Shannon first wrote his paper and made a connection between information and the thermodynamic concept of entropy, a rumor started around Bell Labs that the great atomic physicist John von Neumann had suggested to Shannon, 'Just use the word entropy — no one will know what you're talking about, and everyone will be scared to doubt you.' "

Though it may be a difficult subject to conceptualize, entropy does have a deep connection to information science, Gleick says. Entropy is associated with disorder in thermodynamic systems, and analogously so in informational systems. Though it may seem paradoxical to link information to disorder, Gleick explains that each new bit of information is a surprise — if you knew what a particular message contained, there would not be information in it.

"Information equals disorder, disorder equals entropy and a lot of physicists have been both scratching their heads and making scientific progress ever since," Gleick says.

In the everyday — not scientific — sense, an object like the moon only seems to contain information when we perceive it and develop thoughts about it, whether that's the man in the moon, the moon being made of cheese or the moon driving people to madness. But Gleick says that even without our perceiving it, the moon is more than just matter — it still has its own bits of intrinsic information.

"It sounds mystical, and I can't pretend that I fully understand it either, but it's just one of the many ways in which scientists have discovered a conception of information that helps them solve problems in a whole range of disciplines."

We can see now that information is what our world runs on: the blood and the fuel, the vital principle. It pervades the sciences from top to bottom, transforming every branch of knowledge. Information theory began as a bridge from mathematics to electrical engineering and from there to computing. What English speakers call "computer science" Europeans have long since known as informatique, informatica, and Informatik. Now even biology has become an information science, a subject of messages, instructions, and code. Genes encapsulate information and enable procedures for reading it in and writing it out. Life spreads by networking. The body itself is an information processor. Memory is stored not just in brains but in every cell. No wonder genetics bloomed along with information theory. DNA is the quintessential information molecule, the most advanced message processor at the cellular level—an alphabet and a code, 6 billion bits to form a human being. "What lies at the heart of every living thing is not a fire, not warm breath, not a 'spark of life,'" declares the evolutionary theorist Richard Dawkins. "It is information, words, instructions. . . . If you want to understand life, don't think about vibrant, throbbing gels and oozes, think about information technology." The cells of an organism are nodes in a richly interwoven communications network, transmitting and receiving, coding and decoding. Evolution itself embodies an ongoing exchange of information between organism and environment.

"The information circle becomes the unit of life," says Werner Loewenstein after thirty years spent studying intercellular communication. He reminds us that information means something deeper now: "It connotes a cosmic principle of organization and order, and it provides an exact measure of that." The gene has its cultural analog, too: the meme. In cultural evolution, a meme is a replicator and propagator—an idea, a fashion, a chain letter, or a conspiracy theory. On a bad day, a meme is a virus.