Completing gene trees without species trees in sub-quadratic time
Completing gene trees without species trees in sub-quadratic time
复制标题
DOI：
10.1093/bioinformatics/btab875
复制
发表时间：
2022-01-03
期刊：
影响因子：
5.8
通讯作者：
Mirarab, Siavash
中科院分区：
文献类型：
--
作者：
Mai, Uyen;Mirarab, Siavash
动机：随着系统发育树的全基因组重建变得更加广泛，人们比以往任何时候都更加认识到可用数据的局限性。一个问题是系统发育数据集充满了缺失的数据，特别是基因树，几乎总是缺乏数据集中其他可用物种的代表。由于基因树的许多下游应用需要或可以从访问完整的基因树中受益，因此通过算法完成基因树将是有益的。此外，基因树通常是无根的，对它们进行生根对于下游应用很有用。虽然已经研究了针对给定物种树的基因树的完成和生根，但当我们缺乏这样的参考物种树时，这些问题就没有得到深入研究。结果：我们研究了不需要参考物种树的基因树的完成。我们制定了一个优化问题来完成基因树，同时最小化它们与给定基因树集的四重距离。我们扩展了 Brodal 等人的开创性算法。在准线性时间内解决这个问题。在模拟研究和大量经验数据中，我们表明使用其他基因树完成基因树是相对准确的，并且与可用物种树的情况不同，是无偏差的。
Motivation: As genome-wide reconstruction of phylogenetic trees becomes more widespread, limitations of available data are being appreciated more than ever before. One issue is that phylogenomic datasets are riddled with missing data, and gene trees, in particular, almost always lack representatives from some species otherwise available in the dataset. Since many downstream applications of gene trees require or can benefit from access to complete gene trees, it will be beneficial to algorithmically complete gene trees. Also, gene trees are often unrooted, and rooting them is useful for downstream applications. While completing and rooting a gene tree with respect to a given species tree has been studied, those problems are not studied in depth when we lack such a reference species tree.Results: We study completion of gene trees without a need for a reference species tree. We formulate an optimization problem to complete the gene trees while minimizing their quartet distance to the given set of gene trees. We extend a seminal algorithm by Brodal et al. to solve this problem in quasi-linear time. In simulated studies and on a large empirical data, we show that completion of gene trees using other gene trees is relatively accurate and, unlike the case where a species tree is available, is unbiased.