CeFunMO: A centrality based method for discovering functional motifs with application in biological networks

Area of Science:

• Systems Biology
• Graph Theory
• Computational Biology

Background:

• Detecting functional motifs in biological networks is a key challenge in systems biology.
• This problem involves finding connected subgraphs that match a given multiset of colors in a list-colored graph.

Purpose of the Study:

• To address the NP-complete problem of functional motif detection in list-colored graphs.
• To develop an efficient algorithm for identifying functional motifs.

Main Methods:

• A novel color-based centrality measure for list-colored graphs was defined.
• A greedy strategy was employed to develop a polynomial time algorithm named CeFunMO.
• The algorithm's performance was compared against existing methods like RANGI and GraMoFoNe.

Main Results:

• CeFunMO demonstrates superior running time compared to other algorithms.
• The algorithm provides acceptable accuracy in discovering functional motifs.
• The proposed centrality measure effectively guides the motif discovery process.

Conclusions:

• The developed CeFunMO algorithm offers an efficient solution for functional motif detection in biological networks.
• The new color-based centrality measure is a valuable tool for analyzing list-colored graphs.
• This work contributes to advancing computational approaches in systems biology.