Date of Award
9-12-2011
Document Type
Thesis
Degree Name
Computer Science, MS
First Advisor
Xiuzhen Huang
Committee Members
E.T. Hammerand; Hai Jiang; Hung-Chi Su; Jeff Jenness
Call Number
LD251 .A566t 2011 W3
Abstract
Graph theory is the study of graphs in theoretical computer science. Graphs are mathematical models used to describe pairwise relations between objects from a certain collection. Many practical problems can be modeled as graphs problems, so it is of great importance to develop efficient graph algorithms for different graph problems based on high-throughput data. In this work, we study several important bioinformatics problems which are modeled as problems on weighted graphs, bounded local tree-width graphs, bounded-degree graphs, or mixed graphs etc. We design very efficient algorithms based on the color-coding method for these graph problems. We also apply the idea of dynamic programming in the algorithm development. Our algorithms achieve nice results on both the theoretical side and the application side especially for problems on very large graphs. For pathway analysis of protein-protein interaction networks problem, we have developed a new set of approaches based on color-coding method which is very computationally efficient compared to the current known approaches. We have applied the methods to solve the Subgraph Isomorphism problem of protein-protein interaction networks which work well for large protein-protein interaction networks. We have modeled protein structure-structure alignment problem as Maximum Common Subgraph problem based on graphs build by amino acid, and also designed an algorithm for that problem. Compared with current available structure comparison and alignment methods, our approach got great improvement in structure alignment efficiency and especially in structure comparisons of proteins with large sizes. In addition, we have also worked on the Gene Markers project, in which we develop a general framework to build genome-wide unique gene markers which are very useful for accelerating the process of aligning new gene sequence to the known genome. Besides a novel graph theoretical model for extracting gene markers, we also designed effective methods for evaluating the sets of gene markers.
Rights Management
This work is licensed under a Creative Commons Attribution 4.0 International License.
Recommended Citation
Wang, Kun, "Efficient Graph Algorithms Based on Color Coding Method" (2011). Student Theses and Dissertations. 888.
https://arch.astate.edu/all-etd/888
