A Cubic-Vertex Kernel for Flip Consensus Tree
A Cubic-Vertex Kernel for Flip Consensus Tree
复制标题
翻转共识树的立方顶点核
DOI：
10.1007/s00453-012-9663-1
复制
发表时间：
2012
期刊：
影响因子：
1.1
通讯作者：
J. Uhlmann
中科院分区：
文献类型：
--
作者：
C. Komusiewicz;J. Uhlmann
给定一个二分图G=(Vc,Vt,E)和一个非负整数k，NP-completeMinimum-Flip共识树问题询问G是否可以使用最多的边插入和删除，转换成一个不包含其第一个顶点在Vt中的诱导P5的图（所谓的M图或Σ图）。这个问题在计算系统发育学中起着重要作用，代表性状，代表类群。陈等人。 （IEEE/ACM Trans.Comput.Biol.Bioinform.3:165–173, 2006）。表明最小翻转共识树是 NP 完全的，并提出了一种运行时间为 O(6k⋅|Vt|⋅|Vc|) 的参数化算法。随后，Böcker 等人。 (ACM Trans. Algorithms 8:7:1–7:17, 2012) 提出了一种改进的搜索树算法，运行时间为O(4.42k(|Vt|+|Vc|)+|Vt|⋅|Vc|)。我们继续研究k参数化的最小翻转共识树。我们的主要贡献是多项式时间可执行数据缩减规则，产生具有 O(k3) 个顶点的问题内核。此外，我们提出了一种改进的搜索树算法，运行时间为 O(3.68k⋅|Vc|2|Vt|)。
Given a bipartite graphG=(Vc,Vt,E) and a nonnegative integerk, the NP-completeMinimum-Flip Consensus Treeproblem asks whetherGcan be transformed, using up tokedge insertions and deletions, into a graph that does not contain an inducedP5with its first vertex inVt(a so-calledM-graph orΣ-graph). This problem plays an important role in computational phylogenetics,Vcstanding for the characters andVtstanding for taxa. Chen et al. (IEEE/ACM Trans. Comput. Biol. Bioinform. 3:165–173, 2006). showed thatMinimum-Flip Consensus Treeis NP-complete and presented a parameterized algorithm with running timeO(6k⋅|Vt|⋅|Vc|). Subsequently, Böcker et al. (ACM Trans. Algorithms 8:7:1–7:17, 2012) presented a refined search tree algorithm with running timeO(4.42k(|Vt|+|Vc|)+|Vt|⋅|Vc|). We continue the study ofMinimum-Flip Consensus Treeparameterized byk. Our main contribution are polynomial-time executable data reduction rules yielding a problem kernel withO(k3) vertices. In addition, we present an improved search tree algorithm with running timeO(3.68k⋅|Vc|2|Vt|).
登录
查看更多内容
DOI：
10.1093/comjnl/bxm040
发表时间：
2007
期刊：
Comput. J.
影响因子：
--
作者：
Falk Hüffner;R. Niedermeier;S. Wernicke
通讯作者：
S. Wernicke
不完全定向完美系统发育
DOI：
10.1007/3-540-45123-4_14
发表时间：
2000
期刊：
SIAM J. Comput.
影响因子：
--
作者：
I. Pe’er;R. Shamir;R. Sharan
通讯作者：
R. Sharan
一种改进的最小翻转共识树固定参数算法
DOI：
10.1007/978-3-540-79723-4_6
发表时间：
2008
期刊：
IEEE/ACM Transactions on Computational Biology and Bioinformatics
影响因子：
--
作者：
Sebastian Böcker;Quang Bao Anh Bui;A. Truß
通讯作者：
A. Truß
派系覆盖的数据缩减、精确和启发式算法
影响因子：
0.5
作者：
J. Gramm;Jiong Guo;Falk Hüffner;R. Niedermeier
通讯作者：
R. Niedermeier
DOI：
10.1007/3-540-54945-5_49
发表时间：
1991-12
期刊：
--
影响因子：
--
作者：
W. Hsu;T. Ma
通讯作者：
W. Hsu;T. Ma