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

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

doi:10.1007/978-3-319-43681-4_17

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 proceeding › Conference contribution › peer-review

12 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 language	English
Title of host publication	Algorithms in Bioinformatics - 16th International Workshop, WABI 2016, Proceedings
Editors	Martin Frith, Christian Nørgaard Storm Pedersen
Publisher	Springer Verlag
Pages	210-221
Number of pages	12
ISBN (Print)	9783319436807
DOIs	https://doi.org/10.1007/978-3-319-43681-4_17
State	Published - Jan 1 2016
Event	16th International Workshop on Algorithms in Bioinformatics, WABI 2016 - Aarhus, Denmark Duration: Aug 22 2016 → Aug 24 2016

Publication series

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

Conference

Conference	16th International Workshop on Algorithms in Bioinformatics, WABI 2016
Country/Territory	Denmark
City	Aarhus
Period	08/22/16 → 08/24/16

Keywords

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

Access to Document

10.1007/978-3-319-43681-4_17

Cite this

Loboda, A. A., Artyomov, M. N., & Sergushichev, A. A. (2016). Solving generalized maximum-weight connected subgraph problem for network enrichment analysis. In M. Frith, & C. N. S. Pedersen (Eds.), Algorithms in Bioinformatics - 16th International Workshop, WABI 2016, Proceedings (pp. 210-221). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9838 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-43681-4_17

Loboda, Alexander A. ; Artyomov, Maxim N. ; Sergushichev, Alexey A. / Solving generalized maximum-weight connected subgraph problem for network enrichment analysis. Algorithms in Bioinformatics - 16th International Workshop, WABI 2016, Proceedings. editor / Martin Frith ; Christian Nørgaard Storm Pedersen. Springer Verlag, 2016. pp. 210-221 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6e106d4d54d04e868955550c544ea000,

title = "Solving generalized maximum-weight connected subgraph problem for network enrichment analysis",

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.",

keywords = "Exact solver, Maximum weight connected subgraph problem, Mixed integer programming, Network enrichment",

author = "Loboda, {Alexander A.} and Artyomov, {Maxim N.} and Sergushichev, {Alexey A.}",

year = "2016",

month = jan,

day = "1",

doi = "10.1007/978-3-319-43681-4_17",

language = "English",

isbn = "9783319436807",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "210--221",

editor = "Martin Frith and Pedersen, {Christian N{\o}rgaard Storm}",

booktitle = "Algorithms in Bioinformatics - 16th International Workshop, WABI 2016, Proceedings",

note = "16th International Workshop on Algorithms in Bioinformatics, WABI 2016 ; Conference date: 22-08-2016 Through 24-08-2016",

}

Loboda, AA, Artyomov, MN & Sergushichev, AA 2016, Solving generalized maximum-weight connected subgraph problem for network enrichment analysis. in M Frith & CNS Pedersen (eds), Algorithms in Bioinformatics - 16th International Workshop, WABI 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9838 LNCS, Springer Verlag, pp. 210-221, 16th International Workshop on Algorithms in Bioinformatics, WABI 2016, Aarhus, Denmark, 08/22/16. https://doi.org/10.1007/978-3-319-43681-4_17

Solving generalized maximum-weight connected subgraph problem for network enrichment analysis. / Loboda, Alexander A.; Artyomov, Maxim N.; Sergushichev, Alexey A.
Algorithms in Bioinformatics - 16th International Workshop, WABI 2016, Proceedings. ed. / Martin Frith; Christian Nørgaard Storm Pedersen. Springer Verlag, 2016. p. 210-221 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9838 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

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

AU - Loboda, Alexander A.

AU - Artyomov, Maxim N.

AU - Sergushichev, Alexey A.

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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.

AB - 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.

KW - Exact solver

KW - Maximum weight connected subgraph problem

KW - Mixed integer programming

KW - Network enrichment

UR - http://www.scopus.com/inward/record.url?scp=84984999394&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-43681-4_17

DO - 10.1007/978-3-319-43681-4_17

M3 - Conference contribution

AN - SCOPUS:84984999394

SN - 9783319436807

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 210

EP - 221

BT - Algorithms in Bioinformatics - 16th International Workshop, WABI 2016, Proceedings

A2 - Frith, Martin

A2 - Pedersen, Christian Nørgaard Storm

PB - Springer Verlag

T2 - 16th International Workshop on Algorithms in Bioinformatics, WABI 2016

Y2 - 22 August 2016 through 24 August 2016

ER -

Loboda AA, Artyomov MN , Sergushichev AA. Solving generalized maximum-weight connected subgraph problem for network enrichment analysis. In Frith M, Pedersen CNS, editors, Algorithms in Bioinformatics - 16th International Workshop, WABI 2016, Proceedings. Springer Verlag. 2016. p. 210-221. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-43681-4_17

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this