title: Directed random walks and constraint programming reveal active pathways in hepatocyte growth factor signaling.
abstract: An effective means to analyze mRNA expression data is to take advantage of established knowledge from pathway databases, using methods such as pathway-enrichment analyses. However, pathway databases are not case-specific and expression data could be used to infer gene-regulation patterns in the context of specific pathways. In addition, canonical pathways may not always describe the signaling mechanisms properly, because interactions can frequently occur between genes in different pathways. Relatively few methods have been proposed to date for generating and analyzing such networks, preserving the causality between gene interactions and reasoning over the qualitative logic of regulatory effects. We present an algorithm (MCWalk) integrated with a logic programming approach, to discover subgraphs in large-scale signaling networks by random walks in a fully automated pipeline. As an exemplary application, we uncover the signal transduction mechanisms in a gene interaction network describing hepatocyte growth factor-stimulated cell migration and proliferation from gene-expression measured with microarray and RT-qPCR using in-house perturbation experiments in a keratinocyte-fibroblast co-culture. The resulting subgraphs illustrate possible associations of hepatocyte growth factor receptor c-Met nodes, differentially expressed genes and cellular states. Using perturbation experiments and Answer Set programming, we are able to select those which are more consistent with the experimental data. We discover key regulator nodes by measuring the frequency with which they are traversed when connecting signaling between receptors and significantly regulated genes and predict their expression-shift consistently with the measured data. The Java implementation of MCWalk is publicly available under the MIT license at: https://bitbucket.org/akittas/biosubg.
authors.affiliation: Centre for Process Systems Engineering, Department of Chemical Engineering, University College London, UK.
authors.forename: Aristotelis
authors.initials: A
authors.lastname: Kittas
authors.affiliation: École Centrale de Nantes, IRCCyN UMR CNRS 6597, France.
authors.forename: Aurélien
authors.initials: A
authors.lastname: Delobelle
authors.affiliation: Institute of Pathology, University Hospital Heidelberg, Germany.
authors.forename: Sabrina
authors.initials: S
authors.lastname: Schmitt
authors.affiliation: Institute of Pathology, University Hospital Heidelberg, Germany.
authors.forename: Kai
authors.initials: K
authors.lastname: Breuhahn
authors.affiliation: École Centrale de Nantes, IRCCyN UMR CNRS 6597, France.
authors.forename: Carito
authors.initials: C
authors.lastname: Guziolowski
authors.affiliation: Department of Medical Oncology, NCT, University Hospital Heidelberg, Germany.
authors.forename: Niels
authors.initials: N
authors.lastname: Grabe
mesh_terms: D000465:Algorithms; D016208:Databases, Factual; D005786:Gene Expression Regulation; D053263:Gene Regulatory Networks; D017228:Hepatocyte Growth Factor / Q000235:genetics* / Q000378:metabolism; D006801:Humans; D015603:Keratinocytes / Q000378:metabolism; D009010:Monte Carlo Method; D020411:Oligonucleotide Array Sequence Analysis; D011897:Random Allocation; D015398:Signal Transduction
chemical_list: C066855:HGF protein, human; D017228:Hepatocyte Growth Factor
keywords: HGF signaling; answer set programming; biological networks; logic programming; logical modelling; random walks; subgraph extraction