Efficient Algorithms for Extracting Biological Key Pathways with Global Constraints

被引:10
作者
Baumbach, Jan [1 ]
Friedrich, Tobias [1 ]
Koetzing, Timo [1 ]
Krohmer, Anton
Mueller, Joachim [1 ]
Pauling, Josch [1 ]
机构
[1] Max Planck Inst Informat, Saarbrucken, Germany
来源
PROCEEDINGS OF THE FOURTEENTH INTERNATIONAL CONFERENCE ON GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE | 2012年
关键词
Ant Colony Optimization; Systems Biology; Gene Expression; Epigenetics; INTEGRATED ANALYSIS; RECONSTRUCTION; EXPRESSION;
D O I
10.1145/2330163.2330188
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
The integrated analysis of data of different types and with various interdependencies is one of the major challenges in computational biology. Recently, we developed Key-PathwayMiner, 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.
引用
收藏
页码:169 / 175
页数:7
相关论文
共 26 条
  • [1] Alcaraz N., 2012, INTEGR BIOL IN PRESS
  • [2] KeyPathwayMiner: Detecting Case-Specific Biological Pathways Using Expression Data
    Alcaraz, Nicolas
    Kuecuek, Hande
    Weile, Jochen
    Wipat, Anil
    Baumbach, Jan
    [J]. INTERNET MATHEMATICS, 2011, 7 (04) : 299 - 313
  • [3] PSICQUIC and PSISCORE: accessing and scoring molecular interactions
    Aranda, Bruno
    Blankenburg, Hagen
    Kerrien, Samuel
    Brinkman, Fiona S. L.
    Ceol, Arnaud
    Chautard, Emilie
    Dana, Jose M.
    De Las Rivas, Javier
    Dumousseau, Marine
    Galeota, Eugenia
    Gaulton, Anna
    Goll, Johannes
    Hancock, Robert E. W.
    Isserlin, Ruth
    Jimenez, Rafael C.
    Kerssemakers, Jules
    Khadake, Jyoti
    Lynn, David J.
    Michaut, Magali
    O'Kelly, Gavin
    Ono, Keiichiro
    Orchard, Sandra
    Prieto, Carlos
    Razick, Sabry
    Rigina, Olga
    Salwinski, Lukasz
    Simonovic, Milan
    Velankar, Sameer
    Winter, Andrew
    Wu, Guanming
    Bader, Gary D.
    Cesareni, Gianni
    Donaldson, Ian M.
    Eisenberg, David
    Kleywegt, Gerard J.
    Overington, John
    Ricard-Blum, Sylvie
    Tyers, Mike
    Albrecht, Mario
    Hermjakob, Henning
    [J]. NATURE METHODS, 2011, 8 (07) : 528 - 529
  • [4] Computing topological parameters of biological networks
    Assenov, Yassen
    Ramirez, Fidel
    Schelhorn, Sven-Eric
    Lengauer, Thomas
    Albrecht, Mario
    [J]. BIOINFORMATICS, 2008, 24 (02) : 282 - 284
  • [5] Uncovering a hidden distributed architecture behind scale-free transcriptional regulatory networks
    Balaji, S.
    Iyer, Lakshminarayan M.
    Aravind, L.
    Babu, M. Madan
    [J]. JOURNAL OF MOLECULAR BIOLOGY, 2006, 360 (01) : 204 - 212
  • [6] NCBI GEO: archive for functional genomics data sets-10 years on
    Barrett, Tanya
    Troup, Dennis B.
    Wilhite, Stephen E.
    Ledoux, Pierre
    Evangelista, Carlos
    Kim, Irene F.
    Tomashevsky, Maxim
    Marshall, Kimberly A.
    Phillippy, Katherine H.
    Sherman, Patti M.
    Muertter, Rolf N.
    Holko, Michelle
    Ayanbule, Oluwabukunmi
    Yefanov, Andrey
    Soboleva, Alexandra
    [J]. NUCLEIC ACIDS RESEARCH, 2011, 39 : D1005 - D1010
  • [7] BAUMBACH J, 2006, J INTEGRATIVE BIOINF, V3, P24
  • [8] Baumbach J., 2010, NUCL ACIDS RES
  • [9] Integrated analysis and reconstruction of microbial transcriptional gene regulatory networks using CoryneRegNet
    Baumbach, Jan
    Wittkop, Tobias
    Kleindt, Christiane Katja
    Tauch, Andreas
    [J]. NATURE PROTOCOLS, 2009, 4 (06) : 992 - 1005
  • [10] Towards the integrated analysis, visualization and reconstruction of microbial gene regulatory networks
    Baumbach, Jan
    Tauch, Andreas
    Rahmann, Sven
    [J]. BRIEFINGS IN BIOINFORMATICS, 2009, 10 (01) : 75 - 83