DNA sequencing by hybridization

Sheppard, Bradley (2014) DNA sequencing by hybridization. Masters thesis, Memorial University of Newfoundland.

[English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (931kB)

Abstract

DNA Sequencing by Hybridization (SBH) is a method for reconstructing a DNA sequence based on its k-length subsequences. In this thesis we investigate several issues related to SBH. The set of all k-mers of a sequence is known as the k-spectrum. Using graph theory it is possible to reconstruct the unknown DNA sequence using only the information available in the k-spectrum, but unique reconstruction of the DNA sequence is not always possible. In this thesis we examine probabilistic models which determine the likelihood of a random DNA sequence of length N being uniquely reconstructable based on its k-spectrum. We will also discuss extensions of SBH using both additional information on the k-spectrum and restriction enzymes. The use of restriction enzymes in SBH is a next generation sequencing technique whereby the DNA sequence is split into fragments using restriction enzymes and sequencing is performed on the individual fragments rather than the sequence as a whole. We develop algorithms which use a library of restriction enzymes to cut the sequence and perform sequencing. The width of DNA graphs is also important in the sense of computational complexity and we investigate the DAG-width of the graphs obtained from SBH. We show that the DAG-width of the these graphs is usually small, enabling polynomial time solvability of the Hamiltonian path problem, which is at the core of sequence reconstruction when the problem is modeled using graphs. In the final section, we discuss a next generation variant on SBH.

Actions (login required)

View Item