AF: Small: Algorithmic Foundations of Phylogenetic Tree Reconciliation

AF：小：系统发育树协调的算法基础系统发育树代表一组物种的谱系。计算生物学的一个重大挑战是建立生命之树，即描述所有现存物种进化历史的系统发生树。可靠地组装这棵或任何一棵大树的一个主要障碍是现有基因组数据所提供的覆盖范围的稀疏性。也就是说，相同的遗传信息可能并不适用于所有物种。例如，一个基因可能没有对某个感兴趣的物种进行测序，或者该基因可能只是在该物种中缺失。解决这个问题的一种方法是找到一个物种重叠子集的集合，每个子集都具有子集中每个物种可用的相似遗传数据的特性。为每个子集构建一个系统发育树，然后将这些树组合成一个针对整个物种集的单一超树。构建超级树并非易事，因为它涉及到协调不同输入树之间关于特定物种位置的冲突。提出的研究将解决在将多个相互冲突的系统发育树调和成一个代表它们的单一超树时出现的基本算法问题。调和问题将被视为寻找与输入树的总不相似度最小的超树的问题。该研究将研究在各种措施下树调和的数学和计算性质。其中一些将完全基于树形结构；例如，一棵树在它的物种集合上暗示了什么分组。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.