FIXED-PARAMETER ALGORITHMS FOR MAXIMUM AGREEMENT FORESTS

被引：59
|
作者：
Whidden, Chris [1 ]
Beiko, Robert G. [1 ]
Zeh, Norbert [1 ]
机构：
[1] Dalhousie Univ, Fac Comp Sci, Halifax, NS, Canada
来源：
SIAM JOURNAL ON COMPUTING | 2013年 / 42卷 / 04期
基金：
加拿大自然科学与工程研究理事会;
关键词：
fixed-parameter tractability; phylogenetics; subtree prune-and-regraft distance; lateral gene transfer; hybridization; agreement forest; HYBRIDIZATION NUMBER; PHYLOGENETIC TREES; COMPUTATION; EVENTS; FPT; APPROXIMATION; COMPLEXITY; DISTANCE;
D O I：
10.1137/110845045
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We present new and improved fixed-parameter algorithms for computing maximum agreement forests of pairs of rooted binary phylogenetic trees. The size of such a forest for two trees corresponds to their subtree prune-and-regraft distance and, if the agreement forest is acyclic, to their hybridization number. These distance measures are essential tools for understanding reticulate evolution. Our algorithm for computing maximum acyclic agreement forests is the first depth-bounded search algorithm for this problem. Our algorithms substantially outperform the best previous algorithms for these problems.
引用
收藏
页码：1431 / 1466
页数：36
相关论文
共 50 条
  • [31] On the Fixed-Parameter Tractability of the Maximum Connectivity Improvement Problem
    Coro, Federico
    D'Angelo, Gianlorenzo
    Mkrtchyan, Vahan
    THEORY OF COMPUTING SYSTEMS, 2020, 64 (06) : 1094 - 1109
  • [32] Fixed-Parameter Tractability of Maximum Colored Path and Beyond
    V. Fomin, Fedor
    Golovach, Petr a.
    Korhonen, Tuukka
    Simonov, Kirill
    Plattner, Hasso
    Stamoulis, Giannos
    ACM TRANSACTIONS ON ALGORITHMS, 2024, 20 (04)
  • [33] Subexponential fixed-parameter algorithms for partial vector domination
    Ishii, Toshimasa
    Ono, Hirotaka
    Uno, Yushi
    DISCRETE OPTIMIZATION, 2016, 22 : 111 - 121
  • [34] Fixed-parameter algorithms for CLOSEST STRING and related problems
    Gramm, J
    Niedermeier, R
    Rossmanith, P
    ALGORITHMICA, 2003, 37 (01) : 25 - 42
  • [35] Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem
    Stefan Kratsch
    Frank Neumann
    Algorithmica, 2013, 65 : 754 - 771
  • [36] Towards fixed-parameter tractable algorithms for abstract argumentation
    Dvorak, Wolfgang
    Pichler, Reinhard
    Woltran, Stefan
    ARTIFICIAL INTELLIGENCE, 2012, 186 : 1 - 37
  • [37] Fixed-Parameter Algorithms for CLOSEST STRING and Related Problems
    Algorithmica, 2003, 37 : 25 - 42
  • [38] Fixed-parameter tractable algorithms for testing upward planarity
    Healy, P
    Lynch, K
    SOFSEM 2005:THEORY AND PRACTICE OF COMPUTER SCIENCE, 2005, 3381 : 199 - 208
  • [39] Fixed-parameter tractable algorithms for Tracking Shortest Paths
    Banik, Aritra
    Choudhary, Pratibha
    Raman, Venkatesh
    Saurabh, Saket
    THEORETICAL COMPUTER SCIENCE, 2020, 846 : 1 - 13
  • [40] Fixed-Parameter Algorithms for Computing RAC Drawings of Graphs
    Brand, Cornelius
    Ganian, Robert
    Roeder, Sebastian
    Schager, Florian
    GRAPH DRAWING AND NETWORK VISUALIZATION, GD 2023, PT II, 2023, 14466 : 66 - 81
12345