Reconstructing a DNA Sequence from Erroneous Copies

We show how to efficiently reconstruct an original DNA sequence of length n with high probability from log ffi n erroneous copies (for some ffi ! 2), assuming the sequence itself is random and errors are random with constant error rate 1=C. Key words: DNA, sequencing, alignment, errors, Kolmogorov complexity. 1 Introduction DNA sequencing is a key step and a major bottleneck in the Human Genome Project. It is relatively slow and expensive (~$1 per base with current techniques). Since the human genome comprises no less than 3 billion bases, the development of faster and cheaper sequencing methods is crucial to the project. Certain technologies promise the ability to obtain long DNA sequences fast but with lots of errors. In single-molecule DNA sequencing, the DNA strand is passed by a cutter, that cuts off a single base at a time, which then flows down a microscopic tube at high speed past an optical device. This excites the individual molecule and reads off which type of base it is. ..