Phylogenetic networks capture complex evolutionary relationships, including hybridization and gene flow, that are not easily represented by tree-based models. Orchards are a class of phylogenetic networks that have proven valuable for reconstructing evolution from ancestral profiles, and in which reticulation arcs model lateral gene transfers. Several methods exist to infer orchards, and distance measures between networks can be used to evaluate them against simulations or gold-standard datasets. One such measure is the maximum agreement cherry-reduced subnetwork (MACRS) of two orchards. Recently, Landry et al. proved that finding such a MACRS of two binary level-1 orchards is fixed-parameter tractable (FPT) with respect to the number of reticulations in both networks. In this paper, we show that this problem can be solved on arbitrary binary orchards, in FPT time with respect to the maximum level of the two networks. In particular, a MACRS of two binary level-1 orchards can be found in polynomial time.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Cherry-Picking Distance Between Binary Orchards Parameterized by Level

  • Manuel Lafond,
  • Kaari Landry,
  • Olivier Tremblay-Savard,
  • Hamza Wahed,
  • Christopher Whidden,
  • Norbert Zeh

摘要

Phylogenetic networks capture complex evolutionary relationships, including hybridization and gene flow, that are not easily represented by tree-based models. Orchards are a class of phylogenetic networks that have proven valuable for reconstructing evolution from ancestral profiles, and in which reticulation arcs model lateral gene transfers. Several methods exist to infer orchards, and distance measures between networks can be used to evaluate them against simulations or gold-standard datasets. One such measure is the maximum agreement cherry-reduced subnetwork (MACRS) of two orchards. Recently, Landry et al. proved that finding such a MACRS of two binary level-1 orchards is fixed-parameter tractable (FPT) with respect to the number of reticulations in both networks. In this paper, we show that this problem can be solved on arbitrary binary orchards, in FPT time with respect to the maximum level of the two networks. In particular, a MACRS of two binary level-1 orchards can be found in polynomial time.