DNA hash pooling

The draft paper that came out of our trip to Paris has now been lodged with the arXiv e-print server.

DNA Hash Pooling and its Applications

Dennis Shasha (Courant Institute, New York University), Martyn Amos (Computing and Mathematics, Manchester Metropolitan University)

Abstract: In this paper we describe a new technique for the characterisation of populations of DNA strands. Such tools are vital to the study of ecological systems, at both the micro (e.g., individual humans) and macro (e.g., lakes) scales. Existing methods make extensive use of DNA sequencing and cloning, which can prove costly and time consuming. The overall objective is to address questions such as: (i) (Genome detection) Is a known genome sequence present at least in part in an environmental sample? (ii) (Sequence query) Is a specific fragment sequence present in a sample? (iii) (Similarity Discovery) How similar in terms of sequence content are two unsequenced samples?

We propose a method involving multiple filtering criteria that result in "pools" of DNA of high or very high purity. Because our method is similar in spirit to hashing in computer science, we call the method DNA hash pooling. To illustrate this method, we describe examples using pairs of restriction enzymes. The in silico empirical results we present reflect a sensitivity to experimental error. The method requires minimal DNA sequencing and, when sequencing is required, little or no cloning.

Available at http://www.arxiv.org/abs/0705.3597.

Spiked innovation survey

I was recently asked to contribute to the annual innovation survey from spiked. There appear to be many interpretations of the term "innovation", but notable entries (from my own perspective) include those by Scott Aaronson, Paul Rothemund and Jeffrey Shallit.

Here's the blurb from the spiked website:

"The internet, the alphabet, the discovery of nuclear fusion, x-rays, the brick, rockets, the eraser: all of these have been identified as the greatest innovations in history in a new survey.

Over 100 key thinkers and experts from the fields of science, technology and medicine - including six Nobel laureates - participated in the brand new spiked/Pfizer survey 'What's the Greatest Innovation?', which goes live on spiked today.

In his introduction to the survey, spiked's editor-at-large Mick Hume says: 'Some choose "sexy" looking innovations, others apologise for the apparent dullness of their arcane choices. But whatever the appearances, almost all of our respondents exude a sense of certainty about the improvement that innovations in their field are making to our world, and the potential for more of the same."