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 structures used to model pairwise relations between objects from a certain collection. Many real-world problems can be modeled as problems on graphs. It is of great importance to develop efficient graph algorithms for different graph problems. 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, we have developed and implemented a new relational approach. Compared with the current known approaches, this relational approach is very computationally efficient. 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 designed an algorithm for Maximum Common Subgraph problem and applied it to protein structure-structure alignment. Compared with current available structure comparison and alignment software, our approach shows improvement in structure alignment efficiency and will be very useful for structure comparisons of proteins with large sizes. We have also worked on the Gene Markers and develop a general framework to build genome-wide unique gene markers. This framework includes a novel graph theoretical model for extracting robust gene markers and 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
