Item

Abstract

Advances in the field of systems biology have provided the biological community with massive amounts of pathway data that describe the interplay of genes and their products. The resulting biological networks usually consist of thousands of entities and interactions that can be modeled mathematically as graphs. Since these networks only provide a static picture of the accumulated knowledge, pathways that are affected during development of complex diseases cannot be extracted easily. This gap can be lled by means of OMICS technologies such as DNA microarrays, which measure the activity of genes and proteins under different conditions. Integration of both interaction and expression datasets can increase the quality and accuracy of analysis when compared to independant inspection of each. However, sophisticated computational methods are needed to deal with the size of the datasets while also accounting for the presence of biological and technological noise inherent in the data generating process. In this dissertation the KeyPathwayMiner is presented, a method that enables the extraction and visualization of affected pathways given the results of a series of gene expression studies. Specically, given network and gene expression data, KeyPathwayMiner identies those maximal subgraphs where all but k nodes of the subnetwork are differentially expressed in all but at most l cases in the gene expression data. This new formulation allows users to control the number of outliers with two parameters that provide good interpretability of the solutions. Since identifying these subgraphs is computationally intensive, an heuristic algorithm based on Ant Colony Optimization was designed and adapted to this problem, where solutions are reported in the order of seconds on a standard personal computer. The Key-PathwayMiner was tested on real Huntingtons Disease and Breast Cancer datasets, where it is able to extract pathways containing a large percentage of known relevant genes when compared to other similar approaches. KeyPathwayMiner has been implemented as a plugin for Cytoscape, one of the most widely used open source biological network analysis and visualization platforms. The Key-PathwayMiner is available online at http://keypathwayminer.mpi-inf.mpg.de or through the plugin manager of Cytoscape.