TY - GEN
T1 - Efficient algorithms for extracting biological key pathways with global constraints
AU - Baumbach, Jan
AU - Friedrich, Tobias
AU - Kötzing, Timo
AU - Krohmer, Anton
AU - Müller, Joachim
AU - Pauling, Josch
PY - 2012
Y1 - 2012
N2 - The integrated analysis of data of different types and with various interdependencies is one of the major challenges in computational biology. Recently, we developed KeyPathwayMiner, a method that combines biological networks modeled as graphs with disease-specific genetic expression data gained from a set of cases (patients, cell lines, tissues, etc.). We aimed for finding all maximal connected sub-graphs where all nodes but K are expressed in all cases but at most L, i.e. key pathways. Thereby, we combined biological networks with OMICS data, instead of analyzing these data sets in isolation. Here we present an alternative approach that avoids a certain bias towards hub nodes: We now aim for extracting all maximal connected sub-networks where all but at most K nodes are expressed in all cases but in total (!) at most L, i.e. accumulated over all cases and all nodes in a solution. We call this strategy GLONE (global node exceptions); the previous problem we call INES (individual node exceptions). Since finding GLONE-components is computationally hard, we developed an Ant Colony Optimization algorithm and implemented it with the KeyPathwayMiner Cytoscape framework as an alternative to the INES algorithms. KeyPathwayMiner 3.0 now offers both the INES and the GLONE algorithms. It is available as plugin from Cytoscape and online at http://keypathwayminer.mpi-inf. mpg.de.
AB - The integrated analysis of data of different types and with various interdependencies is one of the major challenges in computational biology. Recently, we developed KeyPathwayMiner, a method that combines biological networks modeled as graphs with disease-specific genetic expression data gained from a set of cases (patients, cell lines, tissues, etc.). We aimed for finding all maximal connected sub-graphs where all nodes but K are expressed in all cases but at most L, i.e. key pathways. Thereby, we combined biological networks with OMICS data, instead of analyzing these data sets in isolation. Here we present an alternative approach that avoids a certain bias towards hub nodes: We now aim for extracting all maximal connected sub-networks where all but at most K nodes are expressed in all cases but in total (!) at most L, i.e. accumulated over all cases and all nodes in a solution. We call this strategy GLONE (global node exceptions); the previous problem we call INES (individual node exceptions). Since finding GLONE-components is computationally hard, we developed an Ant Colony Optimization algorithm and implemented it with the KeyPathwayMiner Cytoscape framework as an alternative to the INES algorithms. KeyPathwayMiner 3.0 now offers both the INES and the GLONE algorithms. It is available as plugin from Cytoscape and online at http://keypathwayminer.mpi-inf. mpg.de.
KW - ant colony optimization
KW - epigenetics
KW - gene expression
KW - systems biology
UR - http://www.scopus.com/inward/record.url?scp=84864714156&partnerID=8YFLogxK
U2 - 10.1145/2330163.2330188
DO - 10.1145/2330163.2330188
M3 - Conference contribution
AN - SCOPUS:84864714156
SN - 9781450311779
T3 - GECCO'12 - Proceedings of the 14th International Conference on Genetic and Evolutionary Computation
SP - 169
EP - 175
BT - GECCO'12 - Proceedings of the 14th International Conference on Genetic and Evolutionary Computation
T2 - 14th International Conference on Genetic and Evolutionary Computation, GECCO'12
Y2 - 7 July 2012 through 11 July 2012
ER -