These tools will no longer be maintained as of December 31, 2024. Archived website can be found here. PubMed4Hh GitHub repository can be found here. Contact NLM Customer Service if you have questions.


Pubmed for Handhelds

PUBMED FOR HANDHELDS

Search MEDLINE/PubMed

  • Title: Detecting list-colored graph motifs in biological networks using branch-and-bound strategy.
    Author: Huang Y, Zhong C.
    Journal: Comput Biol Med; 2019 Apr; 107():1-9. PubMed ID: 30738296.
    Abstract:
    In this work, we study the list-colored graph motif problem, which was introduced to detect functional motifs in biological networks. Given a multi-set M of colors as the query motif and a list-colored graph G where each vertex in G is associated with a set of colors, the aim of this problem is to find a sub-graph of G whose vertex set is colored exactly as motif M. To solve this problem, we present a heuristic method to efficiently and accurately detect list-colored graph motifs in biological networks using branch-and-bound strategy. We transform the detection of list-colored graph motif to the search of connected induced sub-graphs in list-colored graph, where the vertices in the sub-graph are assigned to distinctive colors of query motif. This transformation enables our method to accurately discover the occurrences of query motif without enumerating and verifying all sub-graphs. Furthermore, a new initial vertex selection strategy based on the colors of vertices is proposed to accurately determine the search scope of motifs. Experiments conducted on metabolic networks and protein-interaction networks demonstrate that our method can achieve better performance in accuracy and efficiency in comparison to other existing methods.
    [Abstract] [Full Text] [Related] [New Search]