TY - GEN
T1 - Ranking vertices for active module recovery problem
AU - Isomurodov, Javlon E.
AU - Loboda, Alexander A.
AU - Sergushichev, Alexey A.
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - Selecting a connected subnetwork enriched in individually important vertices is an approach commonly used in many areas of bioinformatics, including analysis of gene expression data, mutations, metabolomic profiles and others. It can be formulated as a recovery of an active module from which an experimental signal is generated. Commonly, methods for solving this problem result in a single subnetwork that is considered to be a good candidate. However, it is usually useful to consider not one but multiple candidate modules at different significance threshold levels. Therefore, in this paper we suggest to consider a problem of finding a vertex ranking instead of finding a single module. We also propose two algorithms for solving this problem: one that we consider to be optimal but computationally expensive for real-world networks and one that works close to the optimal in practice and is also able to work with big networks.
AB - Selecting a connected subnetwork enriched in individually important vertices is an approach commonly used in many areas of bioinformatics, including analysis of gene expression data, mutations, metabolomic profiles and others. It can be formulated as a recovery of an active module from which an experimental signal is generated. Commonly, methods for solving this problem result in a single subnetwork that is considered to be a good candidate. However, it is usually useful to consider not one but multiple candidate modules at different significance threshold levels. Therefore, in this paper we suggest to consider a problem of finding a vertex ranking instead of finding a single module. We also propose two algorithms for solving this problem: one that we consider to be optimal but computationally expensive for real-world networks and one that works close to the optimal in practice and is also able to work with big networks.
KW - Active module
KW - Connected subgraphs
KW - Dynamic programming
KW - Integer linear programming
KW - Interaction networks
KW - Vertex ranking
UR - http://www.scopus.com/inward/record.url?scp=85020421959&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-58163-7_5
DO - 10.1007/978-3-319-58163-7_5
M3 - Conference contribution
AN - SCOPUS:85020421959
SN - 9783319581620
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 75
EP - 84
BT - Algorithms for Computational Biology - 4th International Conference, AlCoB 2017, Proceedings
A2 - Vega-Rodriguez, Miguel A.
A2 - Figueiredo, Daniel
A2 - Pratas, Diogo
A2 - Martin-Vide, Carlos
PB - Springer Verlag
T2 - 4th International Conference on Algorithms for Computational Biology, AlCoB 2017
Y2 - 5 June 2017 through 6 June 2017
ER -