RANGI: a fast list-colored graph motif finding algorithm.
Given a multiset of colors as the query and a list-colored graph, i.e., an undirected graph with a set of colors assigned to each of its vertices, in the NP-hard list-colored graph motif problem the goal is to find the largest connected subgraph such that one can select a color from the set of colors assigned to each of its vertices to obtain a subset of the query. This problem was introduced to find functional motifs in biological networks. We present a branch-and-bound algorithm named RANGI for finding and enumerating list-colored graph motifs. As our experimental results show, RANGI's pruning methods and heuristics make it quite fast in practice compared to the algorithms presented in the literature. We also present a parallel version of RANGI that achieves acceptable scalability.
Faculty of Electrical and Computer Engineering, Tarbiat Modares University, Tehran, Iran, PO Box 14115-194, Tehran, Iran. gholamirudi@modares.ac.ir
Ali Gholami
AG
Rudi
Saeed
S
Shahrivari
Saeed
S
Jalili
Zahra Razaghi
ZR
Moghadam Kashani
D000465:Algorithms; D000818:Animals; D002417:Cattle; D003116:Color; D019295:Computational Biology / Q000379:methods*; D006801:Humans; D007091:Image Processing, Computer-Assisted / Q000379:methods*; D051379:Mice; D060066:Protein Interaction Maps; D051381:Rats; D015203:Reproducibility of Results; D012984:Software