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

进化分析是现代医学和生物学的基础。例如，致病细菌会产生抗药性，而流感病毒由于变异率高，每年都需要新的疫苗。世界各地的研究人员使用进化树构建技术，称为系统发育学，从DNA和蛋白质序列等数据中了解这些进化过程。系统发育的“家谱”是研究进化的主要工具。系统发育推论在生物学中有广泛的应用，从通过突变和基因共享重建抗菌素耐药性的传播到理解为什么大西洋鲑鱼的一些亚种在从海洋返回之前变得更大。尽管全世界有成千上万的研究人员在使用系统发育推论方法，但新的系统发育算法的发展并没有跟上可用数据惊人增长的步伐。目前的系统发育推断方法依赖于能够有效地搜索非常大的可能的系统发育树集合。然而，人们对这种数学上的“树空间”仍然知之甚少。直接的结果是，当前的系统发育方法要么快速寻求单一估计，要么需要数周时间来探索具有统计代表性的候选树集合。此外，一棵树只显示了图像的一部分，我们需要考虑像基因转移和重组这样的进化过程，而不是只跟随一棵树。我们需要新的、快速的算法来解决这些问题。这项建议包括三个互补的项目，它们将提高我们推断、比较和评估系统发育的能力。首先，我们将开发新的系统发育推断软件“系统发育拓扑师”(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.