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-Tree）是系统发育树，其中每个叶子标签可能不止一次出现。这样的树木通过折叠操作应用了系统发育网络的构建[Huber＆Moulton，Mathagical Biological，2006]。我们考虑了一致性问题（MulsetPC）的Mul-Tree集修剪，它将其作为输入一组Mul-Trees，并询问是否存在每个Mul-Tree的完美修剪，从而导致一组一套一套单标记的树。已知MulsetPC是NP完整的[Gascon，Dondi和El-Mabrouk，Iwoca 2021的会议论文集]，当时Mul-Trees是二进制的，每个叶子标签最多使用三遍，并且Mul-Strees的数量是没有结合的。我们解决了Gascon等人提出的一个空旷的问题。通过证明一个更强的结果，即使只有两个mul-trees，MululsetPC即使是NP完整的，每个叶子标签最多都使用两次，并且每个Mul-Tree都是二进制的，或者每个Mul-Tree都有恒定的高度。此外，我们引入了MulsetPC的扩展名，我们称之为MulsetPcomp，该扩展代替了与兼容性的一致性概念，并证明MulsetPcomp即使只有两个MUL-Trees，即使每个叶子标签都在大多数情况下使用，并且每个MUL-TREE都使用，并且每个MUL-TREE都有恒定的高度。最后，我们为具有恒定数量的二进制MUL-Trees数量的MulsetPC实例设计了多项式时算法，在特殊情况下，每个叶子标签至少在至少一个mul-tree中恰好出现一次。

项目成果

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