Various Algorithms for High Throughput Sequencing

The growing volume of generated DNA sequencing data makes the problem of its long-term storage increasingly important. In the first chapter we present ReCoil - an I/O efficient external memory algorithm designed for compression of very large datasets of short readsDNA data. Typically each position of DNA sequence is covered by multiple reads of a short read dataset and our algorithm makes use of resulting redundancy to achieve high compression rate. While compression based on encoding mismatches between the dataset and a similar reference can yield high compression rate, good quality reference sequence may be unavailable. Instead, ReCoil's compression is based on encoding the differences between similar or overlapping reads. As such reads may appear at large distances from each other in the dataset and since random access memory is a limited resource, ReCoil is designed to work efficiently in external memory, leveraging high bandwidth of modern hard disk drives.The next problem we address is the problem of mapping sequencing data to the reference genome. We revisit the basic problem of mapping a dataset of reads to the reference, developing a fast, memory-efficient algorithm for mapping of the new generation of long high error rate reads. We introduce a novel approach to hash based indexing which is both succinct and can be constructed very efficiently, avoiding the need to build the index in advance. Using our new index, we design a cache oblivious algorithm that makes an efficient use of the modern hardware to quickly cluster the reads in the dataset according to their position on the reference.Next, we show an algorithm for aligning two-pass Single Molecule Sequencing reads. Single Molecule Sequencing technologies such as the Heliscope simplify the preparation of DNA for sequencing, while sampling millions of reads in a day. The technology suffers from a high error rate, ameliorated by the ability to sample multiple reads from the same location. We develop novel rapid alignment algorithms for two-pass Single Molecule Sequencing methods. We combinethe Weighted Sequence Graph representation of all optimal and near optimal alignments between the two reads sampled from a piece of DNA with k-mer filtering methods and spaced seeds to quickly generate candidate locations for the reads on the reference genome. Our method combines these approaches with fast implementation of the Smith-Waterman algorithm in order to build an algorithm that is both fast andaccurate, since it is able to take complete advantage of both of the reads sampled during two pass sequencing.While genetic sequencing is growing in popularity as the tool to answer various kinds of questions about the genome, technical as well as practical considerations, such as high cost, impose limitations on its use. Microarrays are a commonly used alternative to sequencing for the task of microsatellite genotyping. We discuss the problem of optimal coloring of dotted interval graphs that arises naturally in the context of microsatelite genotyping using microarrays.Ph.D