AF: Small: Algorithmic Foundations of Phylogenetic Tree Reconciliation

AF：Small：系统发育树重建的算法基础系统发育树代表一组物种的系谱。计算生物学中的重大挑战之一是建立生命树，这是一棵描述所有现存物种进化史的系统发育树。可靠地组装这棵树或任何一棵大树的一个主要障碍是现有基因组数据提供的覆盖范围稀少。也就是说，我们可能不会对所有物种使用相同的遗传信息。例如，一个基因可能没有为感兴趣的物种测序，或者该基因可能只是在该物种中缺失。解决这个问题的一种方法是找到物种的重叠子集的集合，每个子集都具有这样的属性，即子集中的每个物种都可以获得类似的基因数据。为每个子集构建一棵系统发育树，然后将这些树合并成整个物种集的单个超树。构建超树不是一件容易的事，因为它涉及协调不同输入树之间关于特定物种放置的冲突。拟议的研究将解决将多个相互冲突的系统发育树协调成代表它们所有的单个超树所产生的基本算法问题。协调问题将被视为寻找与输入树完全不同的超树的问题。本研究将研究不同措施下的树协调的数学和计算特性。其中一些将纯粹基于树的结构；例如，树在其物种集合上暗示了什么分组。PI还将研究有时被称为基因树简约问题。这里，差异度量试图识别复杂进化事件的可能发生，例如基因复制和随后的丢失，以及水平基因转移。本研究旨在促进树协调理论的发展，并将结果作为新的算法方法的基础。这项工作将建立在该领域最近的重大理论发展基础上。技术将包括图论，快速局部搜索，树协调方法的公理特征，不可能性证明，紧凑整数线性规划公式，以及固定参数可处理性。要解决的具体问题包括开发处理非二叉树的方法，扩展距离度量来解释丢失的数据，了解特定方法或任何方法可以或不能满足哪些属性，以及解决基因树简约中的一些公开问题。这项研究将受到进化生物学社区的需求的影响，两个PI与该社区有着广泛和长期的合作。结果将在该社区内广泛传播。预计在该项目中开发的几种算法技术将在系统发育树数据库中直接有用。

AF: Small: Algorithmic Foundations of Phylogenetic Tree ReconciliationA phylogenetic tree represents the genealogy of a set of species. One of the grand challenges in computational biology is to build the Tree of Life, the phylogenetic tree describing the evolutionary history of all extant species. A major obstacle to assembling this or indeed any large tree reliably is the sparseness of the coverage provided by the available genomic data. That is, the same genetic information may not be at our disposal for all species. For example, a gene may not have been sequenced for a species of interest or the gene may simply be absent from that species. One approach to address this problem is to find a collection of overlapping subsets of the species, each of which has the property that similar genetic data is available for every species in the subset. A phylogenetic tree is built for each subset and then the trees are combined into a single supertree for the entire set of species. Building supertrees is nontrivial, as it involves reconciling conflicts among the various input trees with regard to the placement of certain species.The proposed research will address the fundamental algorithmic problems that arise in reconciling multiple conflicting phylogenetic trees into a single supertree that represents them all. The reconciliation problem will be treated as one of finding a supertree whose total dissimilarity with the input trees is minimum. The research will study the mathematical and computational properties of tree reconciliation under a variety of measures. Some of these will be based purely on tree structure; for example, on what groupings a tree implies on its species set. The PIs will also study what are sometimes referred to as gene tree parsimony problems. Here, the dissimilarity measures attempt to identify the possible occurrence of complex evolutionary events such as gene duplication and subsequent loss, and horizontal gene transfer. The research aims to advance the theory of tree reconciliation and to use the results as the foundation for novel algorithmic methods. The work will build on significant recent theoretical developments in the field. Techniques will include graph theory, fast local search, axiomatic characterizations of tree reconciliation methods, impossibility proofs, compact integer linear programming formulations, and fixed parameter tractability. Specific questions to be addressed include developing methods to handle non-binary trees, extending distance measures to account for missing data, understanding which properties can or cannot be satisfied by a particular method or by any method, and resolving a number of open problems in gene tree parsimony.The research will be informed by the needs of the evolutionary biology community, with which both PIs have an extensive and longstanding collaboration. The results will be widely disseminated within that community. It is anticipated that several of the algorithmic techniques developed in this project will be of direct utility in phylogenetic tree databases.