Recent studies have shown that phylogenetic trees fail to capture certain evolutionary processes, such as reticulation events. To address this, phylogenetic networks were introduced as a more expressive model. This led to the fundamental Tree Containment Problem, which is NP-hard even in the binary case and has been extensively studied, primarily through exponential-time algorithms for binary networks and biologically relevant subclasses. Prior to this work, the best-known fixed-parameter algorithm for binary networks ran in \( O(1.618^k n^2) \) , where \( k \) is the reticulation number and \( n \) is the number of vertices. In this paper, we study the Tree Containment Problem on rooted multifurcating phylogenetic networks, proposing a parameterized algorithm with a runtime of \( O(1.618^k m^3) \) , where \( m \) is the number of arcs. We then adapt this algorithm for parameterization by the level number \( l \) , achieving a runtime of \( O(1.618^l m^3) \) . Since \( l \le k \) , this provides a more efficient solution when \( l \) is significantly smaller.

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

Parameterized Algorithms for the Tree Containment Problem on Multifurcating Phylogenetic Network

  • Feng Shi,
  • Zhanglian Lin,
  • Xin Zeng,
  • Jingyi Liu

摘要

Recent studies have shown that phylogenetic trees fail to capture certain evolutionary processes, such as reticulation events. To address this, phylogenetic networks were introduced as a more expressive model. This led to the fundamental Tree Containment Problem, which is NP-hard even in the binary case and has been extensively studied, primarily through exponential-time algorithms for binary networks and biologically relevant subclasses. Prior to this work, the best-known fixed-parameter algorithm for binary networks ran in \( O(1.618^k n^2) \) , where \( k \) is the reticulation number and \( n \) is the number of vertices. In this paper, we study the Tree Containment Problem on rooted multifurcating phylogenetic networks, proposing a parameterized algorithm with a runtime of \( O(1.618^k m^3) \) , where \( m \) is the number of arcs. We then adapt this algorithm for parameterization by the level number \( l \) , achieving a runtime of \( O(1.618^l m^3) \) . Since \( l \le k \) , this provides a more efficient solution when \( l \) is significantly smaller.