| There are several aspects of research in DNA analysis. This thesis is an exploration of four different areas of DNA analysis that use Combinatorics and its applications. First, Levenshtein introduced the idea of Levenshtein Distance. For two strings, Levenshtein Distance is the number of operations (insertions, deletions and substitutions) required to transform one string into the other. An application of Levenshtein Distance includes creation of large sets of synthetic tissue identification that provided error detection and correction. The second area of DNA analysis using Combinatorics is the application of Graph Theory. Two methods of sequencing technique, fragmentation (overlap) method and sequencing by hybridization, both of which use Graph Theory, are studied. The third area of DNA analysis that we study is sequence comparison. Dynamic programming is used to effectively pair up two sequences. A heuristic method of searching sequence alignment such as FASTA is discussed. The final area of DNA analysis studied is the efficient selection of unique oligonucleotide (oligo) from a database containing large DNA or protein sequences. With the large size of database, an effective approach to find unique oligos is required. In this thesis, the Brute-Force method and the filtration methods for the selection of unique oligos, and parallelization of these methods to save some time in searching for unique oligos, are studied. The Brute-Force and filtration methods give us accurate results but they may take a long time. We attempt a new approach, which gives us less accurate results over much improved searching time. |
