Graph-theoretic analysis of gene expression networks

Abstract

We use graph theory to model a database of gene expression levels and provide a tool that can assist in designing biological experiments which could help to better understand the interactions between genes. The data was provided by StemBase (http://www.stembase.ca). We model a portion of this database as a graph, and study some parameters on it that may be biologically relevant. We include theoretical discussion of the parameters, and presentation of algorithms for their computation. The focus is on structural properties of the graph; thus, we investigate the graph's bipartiteness, connected components, distance between vertices, radius, diameter, center, cut-vertices and blocks, and its maximal and maximum cliques. We develop the terminology and results used for modeling the database, and implement some of the algorithms in MATLAB. We analyze the results of running the code on the database and discuss their relevance.