Graph Coloring And Graph TheOry Applications In Bioinformaties

As the development of biotechnologies, more and more mathematic method are used to solve biological problems。Graph Theory is to study the relations and structures of elements and it plays important role in RNA-seq data alignment, analyzing protein interaction network, disease-drug and drug-drug relations. Here, we show how to analyze genome data and provide new method for drug repositioning using diffusion map. Also, we try to find core signaling pathways of diseases and provide new tools for disease diag-nosis and drug treatment. At last, we introduce [r,s,c,t]-colorings of graphs and the [r,s,c,t]-chromatic numbers for certain graphs.In Chapter1, we introduce data types, normalization and analysis method, we present gene expression data, SNP data, RNA-seq data and DNA methy-lation data background and normalization method. We apply CONEXIC to integrate medulloblastoma gene expression data and SNP data to do sub-typing, find differentially expressed genes, core signaling network and drugs that can be used to treat it. For RNA-seq data, we collaborate with Baylor College of Medicine to do data analysis for breast cancer stem cells in order to find biomarkers, aberrant pathways and drug treat mechanisms using drug profiles. For DNA methylation data, we collaborate with Choi, Dong soon from The Methodist Hospital Research Institute, to study drug treatment on breast cancer stem cells. We look into the drug treat mechanisms from different aspects, one of which is analyzing DNA methylation profiles before and after treatment. We aim to find differentially methylated gene promoter regions around transcription start site in order to estimate the drug affected signaling pathways.In Chapter2, we show the background and method for drug reposition-ing. It will take10to17years to find a new drug, from target validating to drug approved, spending lots of time and money. Drug repositioning can reduce the time to3to12years, which is a fast method for drug discover. We introduce two methods, cMap and PREDICT, for drug repositioning. Then we propose a new method using diffusion map and apply it to medulloblas-toma in Chapter4. Diffusion map method is related with vertex connectivity in Graph Theory. The higher connectivity, the smaller diffusion distance. We use diffusion distance to find drugs treat the disease and do experiment val-idation. The results show our method is more efficient compared with cMap method.In Chapter3, we introduce protein-protein interaction network and sig-naling pathways. Proteins regulate cell functions through interactions. We present several protein interaction database.These database are good refer-ences for studying biological functions. But signaling pathways involve part of the proteins and protein-protein interaction network lack of reliability. Here we integrate pathways and PPIs from online database and give weight to the interactions. This integrated network provide background references to network based analyzing method. By inputting disease; driver genes, ap-plying diffusion map method, we can find core signaling network of diseases, which is a useful tool to study disease aberrant functions. In Chapter4, we apply drug repositioning method and optimal subnet-work finding method to medulloblastoma, which is the most common malig-nant pediatric brain tumor, to find disease core signaling network and drugs repositioned to treat it. Medulloblastoma is the most common malignant pediatric brain tumor, and consists of several heterogeneous subtypes with distinct genomic patterns. Despite the improvement of treatment combina-tions, e.g. surgical resection, radiotherapy and chemotherapy, the outcomes are poor with serious neurological and cognitive deficits due to aggressive treatment. The targeted drugs with less toxicity are promising for MB ther-apy. As MB is a rare disease, limited efforts have been devoted for novel drug discovery. Repositioning existing drugs for new applications is becom-ing an accelerated route for drug discovery considering the availability of es-tablished clinical and pharmacokinetic data and safety tests. Though some pathway inhibiting compounds have been tested in two MB subtypes with SHH and Wnt signaling dysfunctions respectively, however, it is challenging to reposition existing drugs for the rest MB patients, grouped as non-SHH, non-Wnt (NWS) subtype, as there is no predominant dysfunctional signal-ing pathway. Herein, we propose to reposition existing drugs to NWS MBs coupling the available genomic data of MB, and the pharmacological data in the’connectivity Map’database. To reduce the noise in the high dimen-sional pharmacogenomic space, we apply the manifold learning approach to prioritize existing drugs inhibiting NWS MBs, which considers the global ef-ficacy distance of drugs. To further elucidate underlying mechanisms of drug actions for NWS MBs, we again apply the manifold learning approach to identify the core signaling networks linking these effective drug targets and NWS driver genes based on an integrated interactome network. To validate our discovery, we tested the available repositioned drugs targeting the pre- dicted signaling networks on the NWS MB cell line, MED8A. Surprisingly, these top-ranked drugs show effective growth inhibition rates, and the com-parison shows the proposed approach significantly improves the repositioning approach available in cMAP. Moreover, additional effective targets are found closely linked to driver genes in the predicted core signaling network.In Chapter5, we introduce background knowledge of Graph Theory and give the definition of [r,s,c,t]-colorings of Graphs. Then we give the [r,s,c,t]-chromatic number of graph G with δ(G)=1or G is an even cycle.