Department of Evolutionary and Environmental Biology, University of Haifa, Haifa 31905, Israel.
Mol Phylogenet Evol. 2012 Jan;62(1):1-8. doi: 10.1016/j.ympev.2011.06.021. Epub 2011 Jul 6.
Accurate phylogenetic reconstruction methods are inherently computationally heavy and therefore are limited to relatively small numbers of taxa. Supertree construction is the task of amalgamating small trees over partial sets into a big tree over the complete taxa set. The need for fast and accurate supertree methods has become crucial due to the enormous number of new genomic sequences generated by modern technology and the desire to use them for classification purposes. In particular, the Assembling the Tree of Life (ATOL) program aims at constructing the evolutionary history of all living organisms on Earth. When dealing with unrooted trees, a quartet - an unrooted tree over four taxa - is the most basic piece of phylogenetic information. Therefore, quartet amalgamation stands at the heart of any supertree problem as it concerns combining many minimal pieces of information into a single, coherent, and more comprehensive piece of information. We have devised an extremely fast algorithm for quartet amalgamation and implemented it in a very efficient code. The new code can handle over a hundred millions of quartet trees over several hundreds of taxa with very high accuracy.
准确的系统发育重建方法在计算上非常复杂，因此仅限于相对较少的分类单元。超级树构建是将小的树通过部分数据集合并成一个包含完整分类单元集的大树的任务。由于现代技术产生的大量新基因组序列以及将它们用于分类目的的需求，快速准确的超级树方法变得至关重要。特别是，构建生命之树 (ATOL) 计划旨在构建地球上所有生物的进化历史。在处理无根树时，四分体——一个由四个分类单元组成的无根树——是最基本的系统发育信息。因此，四分体合并是任何超级树问题的核心，因为它涉及将许多最小的信息组合成一个单一、连贯和更全面的信息。我们设计了一种非常快速的四分体合并算法，并在一个非常高效的代码中实现了它。新代码可以非常准确地处理超过数亿个四分体树，每个树有数百个分类单元。
