Phylogenetic Network Simplification

系统发育网络简化

• 批准号: 22H03550
• 负责人: ジャンソン ジェスパー
• 金额: $ 10.9万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-22H03550/
• 关键词: algorithm; computational complexity; phylogenetic network; distance functions; structural parameters; MUL-tree; pruning; phylogenetics

A multi-labeled tree (or MUL-tree, for short) is a phylogenetic tree in which every leaf label may appear more than once. Such trees have applications to the construction of phylogenetic networks by folding operations [Huber & Moulton, Mathematical Biology, 2006]. We considered the MUL-tree Set Pruning for Consistency problem (MULSETPC), which takes as input a set of MUL-trees and asks if there exists a perfect pruning of each MUL-tree that results in a consistent set of single-labeled trees. MULSETPC was known to be NP-complete [Gascon, Dondi, and El-Mabrouk, Proceedings of IWOCA 2021] when the MUL-trees are binary, each leaf label is used at most three times, and the number of MUL-trees is unbounded. We resolved an open question posed by Gascon et al. by proving a much stronger result, namely that MULULSETPC is NP-complete even when there are only two MUL-trees, every leaf label is used at most twice, and either every MUL-tree is binary or every MUL-tree has constant height. Furthermore, we introduced an extension of MULSETPC that we call MULSETPComp, which replaces the notion of consistency with compatibility, and proved that MULSETPComp is NP-complete even when there are only two MUL-trees, every leaf label is used at most thrice, and every MUL-tree has constant height. Finally, we designed a polynomial-time algorithm for instances of MULSETPC with a constant number of binary MUL-trees, in the special case where every leaf label occurs exactly once in at least one MUL-tree.

多标记树（或简称 MUL 树）是一种系统发生树，其中每个叶标签可能出现多次。这种树可用于通过折叠操作构建系统发育网络 [Huber & Moulton, Mathematical Biology, 2006]。我们考虑了 MUL 树集合剪枝一致性问题 (MULSETPC)，该问题将一组 MUL 树作为输入，并询问是否存在对每个 MUL 树的完美剪枝，从而产生一组一致的单标记树。当 MUL 树是二元树时，MULSETPC 被认为是 NP 完全的 [Gascon、Dondi 和 El-Mabrouk，Proceedings of IWOCA 2021]，每个叶子标签最多使用 3 次，并且 MUL 树的数量是无界的。我们解决了 Gascon 等人提出的一个悬而未决的问题。通过证明一个更强的结果，即即使只有两个 MUL 树，MULULSETPC 也是 NP 完全的，每个叶标签最多使用两次，并且每个 MUL 树都是二叉树，或者每个 MUL 树具有恒定的高度。此外，我们引入了 MULSETPC 的扩展，称为 MULSETPComp，它用兼容性取代了一致性的概念，并证明了即使只有两棵 MUL 树，每个叶子标签最多使用三次，并且每个 MUL 树具有恒定的高度，MULSETPComp 也是 NP 完全的。最后，我们为具有恒定数量的二叉 MUL 树的 MULSETPC 实例设计了一种多项式时间算法，在特殊情况下，每个叶标签在至少一个 MUL 树中只出现一次。

项目成果

Approximation Algorithms for the Longest Run Subsequence Problem

• DOI: 10.4230/lipics.cpm.2023.2
• 发表时间: 2023
• 期刊: Genome Biology
• 影响因子: 12.3
• 作者: Y. Asahiro;Hiroshi Eto;Mingyang Gong;J. Jansson;Guohui Lin;Eiji Miyano;H. Ono;Shunichi Tanaka

MUL-Tree Pruning for Consistency and Compatibility

用于一致性和兼容性的 MUL 树修剪

• 发表时间: 2023
• 期刊: LIPIcs, CPM 2023
• 作者: C. Hampson;D. J. Harvey;C. Iliopoulos;J. Jansson;Z. Lim;W.-K. Sung
• 通讯作者: W.-K. Sung