Reconstructing phylogenetic trees from multipartite quartet systems
Reconstructing phylogenetic trees from multipartite quartet systems
复制标题
从多部分四重系统重建系统发育树
DOI：
10.1007/s00453-022-00945-9
复制
发表时间：
2022
期刊：
影响因子：
1.1
通讯作者：
Hirai Hiroshi and Iwamasa Yuni
中科院分区：
文献类型：
--
作者：
Yuho Tanaka;Kazunori Uruma;Tomoki Nakao;Yuni Iwamasa;田中 勇帆，雨車 和憲，中尾 朋喜;Hirai Hiroshi and Iwamasa Yuni
系统发生树是分类群进化历史的图形表示，其中叶对应于分类群，非叶对应于物种形成。系统发育分析中的一个重要问题是如何从较小的系统发育树，特别是四叉树中组装出一棵全局系统发育树，四叉树的可组装性（quartetability）是判断是否存在一棵系统发育树，如果存在，则如何构建这样一棵系统发育树。众所周知，四分位数可解性是NP-困难的，并且对于多项式时间可解的子类只有很少的结果。本文引入了两类新的四重系统，称为完全多部四重系统和完全多部四重系统，并给出了这两类系统的四重性的多项式时间算法.
A phylogenetic tree is a graphical representation of an evolutionary history of taxa in which the leaves correspond to the taxa and the non-leaves correspond to speciations. One of important problems in phylogenetic analysis is to assemble a global phylogenetic tree from small phylogenetic trees, particularly, quartet trees.QuartetCompatibilityis the problem of deciding whether there is a phylogenetic tree inducing a given collection of quartet trees, and to construct such a phylogenetic tree if it exists. It is known thatQuartetCompatibilityis NP-hard and that there are only a few results known for polynomial-time solvable subclasses. In this paper, we introduce two novel classes of quartet systems, called complete multipartite quartet system and full multipartite quartet system, and present polynomial-time algorithms forQuartetCompatibilityfor these systems.