Phylogenetic Network Simplification

系统发育网络简化

基本信息

批准号：
22H03550
负责人：
ジャンソンジェスパー
金额：
$ 10.9万
依托单位：
Kyoto University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
2022
资助国家：
日本
起止时间：
2022-04-01 至 2025-03-31
项目状态：
未结题

项目摘要

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 树是二元树、每个叶子标签最多使用 3 次且 MUL 树的数量无界时，MULSETPC 被认为是 NP 完全的 [Gascon、Dondi 和 El-Mabrouk，IWOCA 2021 论文集] 。我们解决了 Gascon 等人提出的一个悬而未决的问题。通过证明一个更强的结果，即即使只有两个 MUL 树，MULULSETPC 也是 NP 完全的，每个叶标签最多使用两次，并且每个 MUL 树都是二叉树，或者每个 MUL 树具有恒定的高度。此外，我们引入了 MULSETPC 的扩展，称为 MULSETPComp，它用兼容性取代了一致性的概念，并证明了 MULSETPComp 是 NP 完全的，即使只有两棵 MUL 树，每个叶子标签最多使用三次，并且每棵 MUL 树都有恒定的高度。最后，我们为具有恒定数量的二叉 MUL 树的 MULSETPC 实例设计了一种多项式时间算法，在特殊情况下，每个叶标签在至少一个 MUL 树中只出现一次。

项目成果

期刊论文数量（3）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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
通讯作者：
Y. Asahiro;Hiroshi Eto;Mingyang Gong;J. Jansson;Guohui Lin;Eiji Miyano;H. Ono;Shunichi Tanaka

MUL-Tree Pruning for Consistency and Compatibility

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