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.