Algorithms for DNA sequencing

The process of reading DNA, or determining the order of nucleotides that form a DNA molecule, is called sequencing. The sequencing of the human genome was a multi-billion dollar, decade-long effort that was officially concluded 10 years ago. Currently, the DNA of humans and other organisms is routinely sequenced within hours or days, at a cost of thousands of dollars.

I will give an informal introduction to sequencing and to the computational problems associated with sequencing. I will talk about the ubiquitous read mapping problem, and describe a random permutations based algorithm for mapping. If we have time, I will also talk about the assembly problem, homopolymer length filters and non random i.i.d. organisms.