| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 504774 | Computers in Biology and Medicine | 2016 | 6 Pages |
•CeFunMO algorithm is developed to discover functional motifs in list-colored graphs.•A new color-based centrality measure is proposed to solve this NP-complete problem.•CeFunMO adopts a greedy strategy to discover functional motifs in polynomial time.•CeFunMO has superior running time compared to other well-known algorithms.•The accuracy of CeFunMO is shown by comparing its results with optimal solutions.
Detecting functional motifs in biological networks is one of the challenging problems in systems biology. Given a multiset of colors as query and a list-colored graph (an undirected graph with a set of colors assigned to each of its vertices), the problem is reduced to finding connected subgraphs, which best cover the multiset of query. To solve this NP-complete problem, we propose a new color-based centrality measure for list-colored graphs. Based on this newly-defined measure of centrality, a novel polynomial time algorithm is developed to discover functional motifs in list-colored graphs, using a greedy strategy. This algorithm, called CeFunMO, has superior running time and acceptable accuracy in comparison with other well-known algorithms, such as RANGI and GraMoFoNe.
