Practical and Efficient Algorithms for Degenerate and Weighted Sequences Derived from High Throughput Sequencing Technologies

High throughput, (or next generation) sequencing technologies have opened new and exciting opportunities in the use of DNA sequences. The new emerging technologies mark the beginning of a new era of high throughput short read sequencing: they have the potential to assemble a bacterial genome during a single experiment and at a moderate cost. In this paper, we address the problem of efficiently mapping millions of degenerate and weighted sequences to a reference genome with respect to whether they occur exactly once in the genome or not, and by taking probability scores into consideration. In particular, we define and solve the Massive Exact and Approximate Unique Pattern Matching problem for degenerate and weighted sequences derived from high throughput sequencing technologies.