hide
Free keywords:
-
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.