Advancing algorithm design for phylogenetic inference using agreement forests and graph exploration

进化分析是现代医学和生物学的基础。例如，致病细菌会产生耐药性，流感病毒由于其高突变率每年都需要新的疫苗。世界各地的研究人员使用进化树构建技术，称为遗传学，从DNA和蛋白质序列等数据中了解这些进化过程。系统发生的“家谱”是研究进化的主要工具。系统发育推断在生物学中有着广泛的应用，从通过突变和基因共享重建抗菌素耐药性的传播，到理解为什么大西洋鲑鱼的一些亚种在从海洋返回之前会变大。虽然系统发育推断方法在世界范围内被成千上万的研究人员所使用，但新的系统发育算法的发展并没有跟上可用数据的惊人增长。目前的系统发育推断方法依赖于能够有效地搜索非常大的可能的系统发育树。然而，这种数学上的“树空间”仍然知之甚少。作为一个直接的结果，目前的系统发育方法要么迅速寻求一个单一的估计或需要几个星期来探索统计上有代表性的候选树集。此外，一棵树只显示了图片的一部分，我们需要考虑进化过程，如基因转移和重组，而不是只遵循一棵树。我们需要新的快速算法来解决这些问题。这个建议包括三个互补的项目，将提高我们的能力，推断，比较和评估的遗传学。首先，我们将开发新的系统发育推理软件“Phylogenetic Topographer”（PT），该软件使用对树空间的更好理解来直接探索最可能的树并估计它们的概率。这将实现具有统计置信度的快速树推断。其次，我们将通过结合所有可能的转移场景开发新的基因转移推理软件。这将提供特定细菌之间的特定转移的推断，而不是我以前在基因转移的“高速公路”上的工作。第三，我们将开发新的算法来计算时间树之间的距离和协调时间树之间的差异。这将能够快速分析病毒（如新型冠状病毒）中的重组。我的研究计划将使系统发育算法的发展赶上现代数据集的规模。总的来说，这些算法将帮助我们以统计学的置信度估计数千种生物的进化树，并帮助我们理解偏离该树的进化模式。特别是，这项研究将帮助我们发现细菌之间抗生素耐药性的特异性转移和病毒感染性状的特异性重组。在我们试图找到解决生物多样性和人类健康方面的许多问题的办法时，这种理解将是必不可少的。

Evolutionary analysis is fundamental to modern medicine and biology. For example, disease-causing bacteria evolve drug resistance and influenza viruses require new vaccines annually due to their high mutation rates. Researchers around the world use evolutionary tree-building techniques, called phylogenetics, to learn about these evolutionary processes from data such as DNA and protein sequences. Phylogenetic "family trees" are a primary tool used for studying evolution. Phylogenetic inferences have applications across biology, from reconstructing the spread of antimicrobial resistance through mutation and gene sharing to understanding why some subspecies of Atlantic salmon grow larger before returning from the ocean. Although phylogenetic inference methods are used worldwide by thousands of researchers, the development of new phylogenetic algorithms has not kept pace with the astounding increase in available data. Current phylogenetic inference methods rely on being able to effectively search through very large sets of possible phylogenetic trees. However, this mathematical "tree space" is still poorly understood. As a direct result, current phylogenetic methods either rapidly seek a single estimate or require weeks to explore statistically representative sets of candidate trees. In addition, a tree shows only part of the picture and we need to consider evolutionary processes like gene transfer and recombination that don't follow only one tree. We need new, fast algorithms for these problems. This proposal encompasses three complementary projects that will advance our ability to infer, compare, and evaluate phylogenies. First, we will develop new phylogenetic inference software "Phylogenetic Topographer" (PT) that uses a better understanding of tree space to directly explore the most likely trees and estimate their probability. This will enable fast tree inference with statistical confidence. Second, we will develop new gene transfer inference software by combining all plausible transfer scenarios. This will provide inference of specific transfers between specific bacteria as opposed to my previous work on "highways" of gene transfer. Third, we will develop novel algorithms for computing distances between and reconciling differences in time trees. This will enable rapid analysis of recombination in viruses such as the novel coronavirus. My research program will enable phylogenetic algorithm development to catch up to the scale of modern datasets. Taken together, these algorithms will help us estimate the evolutionary tree for thousands of organisms with statistical confidence and help us understand evolutionary patterns that deviate from that tree. In particular, this research will help us find specific transfers of antibiotic resistance between bacteria and specific recombination of infection traits in viruses. This understanding will be essential as we try to find solutions to many problems in biodiversity and human health.