Fast supertree construction using quartet joining

曾经生活过的所有种类的有机体都通过共同的祖先和血统在一棵生命之树上联系在一起，这是生物科学的主要见解之一。这些系统发育关系的知识有助于科学家了解我们今天看到的生命的巨大多样性是如何起源的，为推断生物如何进化提供了一个框架，并允许测试试图解释这种多样性的假设，并确定产生它的机制。系统发育关系可以通过形态学来推断，但越来越多地通过DNA或氨基酸序列数据来推断。然而，推断的单个基因的亲缘关系可能与真实的物种亲缘关系不同（不一致），这要么是由于推断中的错误，要么是因为基因树与物种树不相同。例如，当基因在物种之间水平转移时，后者可能会出现，就像某些细菌产生抗生素耐药性时发生的那样，或者当基因复制并随后丢失时。这就提出了如何最好地进行基因组学（基因组规模数据的系统发育分析）的问题，目前正在追求两种替代策略（1）将所有基因结合到一个单一的分析中，以及（2）构建一个超级树-单个基因树的合成。超树方法可以被认为是一种“分而治之”的方法，其中一个大的系统发育问题被分解成较小的问题，然后将其组合起来给出一个全局解决方案。支持这一点的是，人们期望单个基因树可以更容易或更有效地分析，因为它们更小，因为它们只包括那些特定基因可用的分类群。这也假设各个树中的信息可以有效地组合，但不幸的是，目前在实践中最依赖的超树方法具有许多明显不期望的属性，例如产生与每个输入树都为真的关系相矛盾的超树（因此，如果任何输入树为真，则必须为真）。我们建议开发一种新的超树方法，使用逻辑推理，使物种从基因树的集合，在软件中实现它，并测试它与模拟和经验数据。在这种方法中，通过添加叶子来生长超树;在输入树中，关于在哪里放置新叶子的推断由“四元组”给出，这可以被认为是系统发育信息的量子。需要新的方法，使研究人员能够充分利用数量迅速增加的完整基因组序列，这可能与了解代谢途径的演变，耐药性，药物发现，流行病学和与历史气候变化有关的多样化研究有关。技术的进步已经见证了新基因组数据生产速度的大幅增长;原核生物的完整基因组现在可以在一个下午产生。现在需要在分析这一大量数据的方法方面取得进展，目的是用更有根据的替代方法取代临时方法。基于其逻辑基础、灵活性和计算速度，我们预计这将是基因组分析中的一种选择方法，但这需要通过模拟来证实，以显示其特性并确定其错误率，并通过经验测试来提供概念证明。

That all kinds of organisms that have ever lived are related through common ancestry and descent in one Tree of Life is one of the major insights of bological science. Knowledge of these phylogenetic relationships helps scientists to understand how the great diversity of life we see today has originated, provides a framework for inferring how living things have evolved, and allows testing hypotheses that seek to explain this diversity and identify the mechanisms that have generated it. Phylogenetic relationships can be inferred using morphology but are increasingly inferred from DNA or amino acid sequence data. However, the inferred phylogeny of a single gene may differ from (be incongruent with) the true species phylogeny, either due to errors in the inference or because the gene tree is not identical to the species tree. The latter can arise when, for example, genes are transferred horizontally between species, as has happened in the development of antibiotic resistance in some bacteria, or when genes are duplicated and subsequently lost. This raises questions of how best to do phylogenomics (the phylogenetic analysis of genomic scale data) with two alternative strategies currently being pursued (1) combining all genes into a single analysis and (2) building a supertree - a synthesis of the individual gene trees. Supertree methods can be considered a 'divide-and-conquer' approach where a large phylogenetic problem is decomposed into smaller problems which are then combined to give a global solution. Underpinning this is the expectation that individual gene trees can be more easily or effectively analysed because they are smaller and because they include only those taxa for which particular genes are available. This also assumes that the information in the individual trees can be combined efficiently, but unfortunately the supertree methods that are currently most relied upon in practice have a number of obviously undesirable properties, such as producing supertrees that contradict relationships that are true of every input tree (and which therefore must be true if any input tree is true). We propose to develop a new supertree method that uses logical inference to make species phylogenies from collections of gene trees, to implement it in software, and to test it with simulations and empirical data. In this method a supertree is grown by adding leaves; the inference about where to put new leaves is given by 'quartets', which can be considered the quanta of phylogenetic information, in the input trees. The new method is needed to enable researchers to make best use of the rapidly expanding number of complete genome sequences which may be of relevance to understanding the evolution of metabolic pathways, of drug resistance, to drug discovery, epidemiology, and diversification studies linked to historical climate change. Technical advances have seen the massive increases in the rate of production of new genomic data; complete genomes of prokaryotes can now be produced in an afternoon. Advances are now needed in the methods used to analyse this flood of data, and aim to replace ad hoc methods with better-founded alternatives. Based on its logical foundation, its flexibility, and on the speed of its computation, we expect that this will be a method of choice in phylogenomic analysis, but this needs to be confirmed through simulation to show its properties and determine its error rates, and through empirical tests that will provide proof of concept.