School of Computer and Electronics and Information, Guangxi Key Laboratory of Multimedia Communications Network Technology, Guangxi University, Nanning, 530004, China.
School of Computer and Electronics and Information, Guangxi Key Laboratory of Multimedia Communications Network Technology, Guangxi University, Nanning, 530004, China.
Comput Biol Med. 2019 Apr;107:1-9. doi: 10.1016/j.compbiomed.2019.01.025. Epub 2019 Feb 2.
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.
在这项工作中，我们研究了列表着色图模式问题，该问题旨在检测生物网络中的功能模式。给定一个多色集 M 作为查询模式和一个列表着色图 G，其中 G 的每个顶点都与一组颜色相关联，该问题的目的是找到 G 的一个子图，其顶点集的颜色恰好与 motif M 完全相同。为了解决这个问题，我们提出了一种启发式方法，使用分支定界策略在生物网络中有效地、准确地检测列表着色图模式。我们将列表着色图模式的检测转换为在列表着色图中搜索连通诱导子图，其中子图中的顶点被分配给查询模式的独特颜色。这种转换使我们的方法能够在不枚举和验证所有子图的情况下准确地发现查询模式的出现。此外，还提出了一种基于顶点颜色的新的初始顶点选择策略，以准确地确定模式的搜索范围。在代谢网络和蛋白质相互作用网络上进行的实验表明，与其他现有方法相比，我们的方法在准确性和效率方面具有更好的性能。
