An Improved Fixed-Parameter Algorithm for Minimum-Flip Consensus Trees
An Improved Fixed-Parameter Algorithm for Minimum-Flip Consensus Trees
复制标题
一种改进的最小翻转共识树固定参数算法
DOI：
10.1007/978-3-540-79723-4_6
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
A. Truß
中科院分区：
文献类型：
--
作者：
Sebastian Böcker;Quang Bao Anh Bui;A. Truß
在计算系统发育学中，经常解决针对给定的一组输入树的构造共识树的问题。在本文中，我们研究了最小翼型问题：输入被转化为二进制矩阵，我们希望找到一种完美的晶状体发育层以实现完美的基因发育。此矩阵使用最小数量的翻转，即对矩阵中的单个条目进行校正。为了找到一组最小的边缘修改，以使其图形没有四个边缘的诱导路径，该路径启动了VT。
我们为n个分类单元，m字符和k个flips提供了一种固定参数算法（4.83k（m+n）+mn）系统发育数据的结果。
In computational phylogenetics, the problem of constructinga consensus tree for a given set of input trees has frequently been addressed.In this paper we study the Minimum-Flip Problem: the inputtrees are transformed into a binary matrix, and we want to find a perfectphylogeny for this matrix using a minimum number of flips, that is,corrections of single entries in the matrix. In its graph-theoretical formulation,the problem is as follows: Given a bipartite graph G = (Vt∪Vc, E),the problem is to find a minimum set of edge modifications such that theresulting graph has no induced path with four edges which starts andends in Vt.
We present a fixed-parameter algorithm for the Minimum-Flip Problemwith running time O(4.83k (m+n)+mn) for n taxa, m characters,and k flips. Additionally, we discuss several heuristic improvements. Wealso report computational results on phylogenetic data.