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

DOI10.1007/978-3-319-43681-4_17MaRDI QIDQ1708434zbMATH OpenOpenAlexFDO

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

Publication date 23 March 2018

Full work available at URL https://arxiv.org/abs/1605.02168

zbMATH Keywords

exact solvermaximum weight connected subgraph problemmixed integer programmingnetwork enrichment

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Applications of graph theory (05C90) Computational methods for problems pertaining to biology (92-08) Biochemistry, molecular biology (92C40) Systems biology, networks (92C42)

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.

Recommendations

• A relax-and-cut framework for large-scale maximum weight connected subgraph problems
• The Maximum Weight Connected Subgraph Problem
• Combining NP-hard reduction techniques and strong heuristics in an exact algorithm for the maximum-weight connected subgraph problem
• Algorithms for the maximum weight connected k-induced subgraph problem
• Exploring the constrained maximum edge-weight connected graph problem

Cited in

(7)

• A relax-and-cut framework for large-scale maximum weight connected subgraph problems
• Solving Connected Subgraph Problems in Wildlife Conservation
• Combining NP-hard reduction techniques and strong heuristics in an exact algorithm for the maximum-weight connected subgraph problem
• Method of the Joint Clustering in Network and Correlation Spaces
• Approximation hardness of the cross-species conserved active modules detection problem
• The Maximum Weight Connected Subgraph Problem
• Travelling on graphs with small highway dimension

This page was built for publication: Solving generalized maximum-weight connected subgraph problem for network enrichment analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1708434)