Solving generalized maximum-weight connected subgraph problem for network enrichment analysis

Alexander A. Loboda, Maxim N. Artyomov, Alexey A. Sergushichev

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

8 Scopus citations

Abstract

Network enrichment analysis methods allow to identify active modules without being biased towards a priori defined pathways. One of mathematical formulations of such analysis is a reduction to a maximum-weight connected subgraph problem. In particular, in analysis of metabolic networks a generalized maximum-weight connected subgraph (GMWCS) problem, where both nodes and edges are scored, naturally arises. Here we present the first to our knowledge practical exact GMWCS solver. We have tested it on real-world instances and compared to similar solvers. First, the results show that on node-weighted instances GMWCS solver has a similar performance to the best solver for that problem. Second, GMWCS solver is faster compared to the closest analogue when run on GMWCS instances with edge weights.

Original languageEnglish
Title of host publicationAlgorithms in Bioinformatics - 16th International Workshop, WABI 2016, Proceedings
EditorsMartin Frith, Christian Nørgaard Storm Pedersen
PublisherSpringer Verlag
Pages210-221
Number of pages12
ISBN (Print)9783319436807
DOIs
StatePublished - Jan 1 2016
Event16th International Workshop on Algorithms in Bioinformatics, WABI 2016 - Aarhus, Denmark
Duration: Aug 22 2016Aug 24 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9838 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Workshop on Algorithms in Bioinformatics, WABI 2016
CountryDenmark
CityAarhus
Period08/22/1608/24/16

Keywords

  • Exact solver
  • Maximum weight connected subgraph problem
  • Mixed integer programming
  • Network enrichment

Fingerprint Dive into the research topics of 'Solving generalized maximum-weight connected subgraph problem for network enrichment analysis'. Together they form a unique fingerprint.

Cite this