III: Small: RUI: Algorithms and Tools for Phylogenetic Tree Reconciliation

协调分析是研究物种与基因、寄主与寄生虫、地理区域与物种的基本方法。虽然这些应用是不同的，但基本的数学和计算问题是相似的。基因和物种通过复杂的进化过程相互作用，如基因复制、水平基因转移和基因丢失。寄生虫和它们的宿主通过同时和独立的物种形成、宿主交换和灭绝等过程共同进化。而且，物种及其地理栖息地在地质时间尺度上通过替代、同域物种形成、扩散和灭绝相互作用。因此，基因和物种、寄生虫和宿主、物种及其地理区域的系统发育树本质上是不一致的。这项研究将开发新的算法、可视化方法和软件工具，用于研究基因和物种、宿主和寄生虫、物种及其地理栖息地等实体对的进化史，并有助于培养下一代研究人员。基因和物种通过基因复制、水平基因转移和基因丢失等复杂的进化过程相互作用。寄生虫和它们的宿主通过同时和独立的物种形成、宿主交换和灭绝等过程共同进化。而且，物种及其地理栖息地在地质时间尺度上通过替代、同域物种形成、扩散和灭绝相互作用。因此，基因和物种、寄生虫和宿主、物种及其地理区域的系统发育树本质上是不一致的。系统发育树协调试图通过假设解释它们不一致的进化事件来重建相关实体对的进化史。传统的树协调的最大简约度方法要求用户为每种类型的进化事件选择代价。众所周知，这些成本参数很难估计，它们的值可能会对结果和结论产生重大影响。该方法使用帕累托最优方法，该方法不需要用户先验地选择事件成本，从而提供了所有可能的最优调节的集合的系统视图。这项工作最终将产生跨生命科学应用的软件工具，包括基因组学、寄生虫学、病毒学和生物地理学。此外，这个项目将涉及大量的本科生，从而帮助培养下一代计算生物学的研究人员。

Reconciliation analysis is a fundamental method in the study of species and genes, hosts and parasites, and geographical areas and species. While these applications are different, the underlying mathematical and computational problems are analogous. Genes and species interact through complex evolutionary processes such as gene duplication, horizontal gene transfer, and gene loss. Parasites and their hosts coevolve through processes including both contemporaneous and independent speciation, host switch, and extinction. And, species and their geographical habitats interact over geological time scales through vicariance, sympatric speciation, dispersal, and extinction. Consequently, the phylogenetic trees for genes and species, parasites and hosts, and species and their geographic regions are inherently incongruent. This research will develop new algorithms, visualization methods, and software tools for studying the evolutionary histories of pairs of entities such as genes and species, hosts and parasites, and species and their geographical habitats and also help to train the next generation of researchers.Genes and species interact through complex evolutionary processes such as gene duplication, horizontal gene transfer, and gene loss. Parasites and their hosts coevolve through processes including both contemporaneous and independent speciation, host switch, and extinction. And, species and their geographical habitats interact over geological time scales through vicariance, sympatric speciation, dispersal, and extinction. Consequently, the phylogenetic trees for genes and species, parasites and hosts, and species and their geographic regions are inherently incongruent. Phylogenetic tree reconciliation seeks to reconstruct the evolutionary histories of pairs of related entities by positing the evolutionary events that explain their incongruence. Traditional maximum parsimony methods for tree reconciliation require the user to select costs for each type of evolutionary event. These cost parameters are notoriously difficult to estimate and their values can substantially affect the results and conclusions. This approach uses a Pareto-optimal methodology that does not require the user to select event costs a priori, thereby providing a systematic view of the set of all possible optimal reconciliations. This work will ultimately result in software tools with applications across the life sciences including genomics, parasitology, virology, and biogeography. In addition, this project will involve a substantial number of undergraduates, thereby helping prepare the next generation of researchers in computational biology.