Finding and Counting Vertex-Colored Subtrees
Finding and Counting Vertex-Colored Subtrees
复制标题
查找并计算顶点颜色子树
DOI：
10.1007/s00453-011-9600-8
复制
发表时间：
2013
期刊：
影响因子：
1.1
通讯作者：
Florian Sikora
中科院分区：
文献类型：
--
作者：
Sylvain Guillemot;Florian Sikora
本文研究的问题源于Lacroix等人（IEEE/ACM Trans.）提出的graph Motifproblem。第一版。医学杂志。生物信息学报。3(4):360-368,2006)问题是确定一个顶点颜色的图是否有一个连通的子图，其颜色等于给定的多集colorsM。它是图形模式匹配问题的变体，其中模式出现的结构不重要，唯一的要求是连通性。利用Koutis（第35届自动机、语言和程序设计国际学术研讨会论文集，计算机科学讲义，第5125卷，第575-586页，2008年）和Koutis和Williams（第36届自动机、语言和程序设计国际学术研讨会论文集，计算机科学讲义，第5555卷，第653-664页，2009年）最近介绍的代数框架，我们获得了新的图形Motifand变体的FPT算法，具有改进的运行时间。我们也得到了这个问题的计数版本的结果，证明了计数问题是FPT的，但变成了#W[1]-hard的，如果它是一个有两种颜色的多集。最后，我们在真实数据集上对该方法进行了实验评估，表明其性能优于现有软件。
The problems studied in this article originate from theGraph Motifproblem introduced by Lacroix et al. (IEEE/ACM Trans. Comput. Biol. Bioinform. 3(4):360–368, 2006) in the context of biological networks. The problem is to decide if a vertex-colored graph has a connected subgraph whose colors equal a given multiset of colorsM. It is a graph pattern-matching problem variant, where the structure of the occurrence of the pattern is not of interest but the only requirement is the connectedness. Using an algebraic framework recently introduced by Koutis (Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 5125, pp. 575–586, 2008) and Koutis and Williams (Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 5555, pp. 653–664, 2009), we obtain new FPT algorithms forGraph Motifand variants, with improved running times. We also obtain results on the counting versions of this problem, proving that the counting problem is FPT ifMis a set, but becomes #W[1]-hard ifMis a multiset with two colors. Finally, we present an experimental evaluation of this approach on real datasets, showing that its performance compares favorably with existing software.
登录
查看更多内容
使用莫比乌斯反演的快速多项式空间算法：斯坦纳树及相关问题的改进
DOI：
10.1007/978-3-642-02927-1_59
发表时间：
2009
期刊：
Food Science
影响因子：
--
作者：
Jesper Nederlof
通讯作者：
Jesper Nederlof
一些图基序问题的参数化算法和硬度结果
DOI：
10.1007/978-3-540-69068-9_6
发表时间：
2008
期刊：
Journal of computational biology : a journal of computational molecular cell biology
影响因子：
--
作者：
Nadja Betzler;M. Fellows;Christian Komusiewicz;R. Niedermeier
通讯作者：
R. Niedermeier
DOI：
10.1016/0167-6377(82)90044-x
发表时间：
1982-04
期刊：
Oper. Res. Lett.
影响因子：
--
作者：
R. Karp
通讯作者：
R. Karp
彩色图中的弱模式匹配：最小化连接组件的数量
DOI：
10.1142/9789812770998_0007
发表时间：
2007
期刊：
Journal of computational biology : a journal of computational molecular cell biology
影响因子：
--
作者：
R. Dondi;G. Fertin;Stéphane Vialette
通讯作者：
Stéphane Vialette
用于在顶点彩色图中查找连接图案的清晰易处理边界线
DOI：
10.1007/978-3-540-73420-8_31
发表时间：
2007
期刊：
Food Science
影响因子：
--
作者：
M. Fellows;G. Fertin;D. Hermelin;Stéphane Vialette
通讯作者：
Stéphane Vialette