AF: Medium: Algorithmic Foundations for Phylogenetic Networks

系统发生学，或称进化历史，在生物学中扮演着核心角色，作为理解所有生命多样性的框架。在查尔斯·达尔文的《物种起源》中，物种进化史的描述以一棵树的形状呈现。从那以后，树一直是最常用的结构来模拟进化历史。然而，虽然树木能够捕捉到，例如，一个物种如何分裂成两个物种并随后多样化，以及遗传物质如何从祖先传递给后代，但它们无法捕捉到其他进化事件。例如，一些植物物种是由于其他物种对之间的杂交而产生的。在微生物界，细菌通过各种方式水平传播遗传物质。在这些情况下，一棵树最多只能给出一个不完整的进化史，而在最坏的情况下则是一个非常具有误导性的图像。事实上，在这些情况下，一个更合适的进化历史模型是一个系统发育网络，它通过结合进化事件，如杂交和水平基因转移，扩展了树模型。尽管近年来在系统发育网络领域的研究活动有所增加，但它们的重建和评估仍然主要是临时过程，并且在特定数据集的适用性方面受到限制。为了开发系统重建和评估系统发育网络的方法，本项目旨在开发(1)使用基因组数据评估系统发育网络质量的算法，以及(2)搜索系统发育网络空间以实现进化史自动推断的算法。这项工作的结果将有助于极大地扩展系统发育的适用性到不适合树的生物群体，以及理解系统发育网络模型，从而允许更系统地开发其准确重建的方法。此外，这些结果将有助于更准确地重建生命之树，帮助揭示微生物基因组多样性，促进植物和其他生物群体杂交场景的重建，并有助于了解微生物对抗生素产生耐药性的机制。该项目为培养跨学科研究领域的研究生和本科生提供了绝佳的机会。

Phylogenies, or evolutionary histories, play a central role in biology as a framework within which to understand all of Life's diversity. In Charles Darwin's Origin of Species, the depiction of an evolutionary history of species took the shape of a tree. Ever since, trees have been the most commonly used structure to model evolutionary histories. However, while trees capture how, for example, one species splits into two that subsequently diversify and how genetic material is transmitted from ancestor to descendants, they fail to capture other evolutionary events. For example, some plant species arise due to hybridization between pairs of other species. In the microbial world, bacteria transmit genetic material horizontally by various means. In these cases, a tree gives an incomplete picture of the evolutionary history at best, and a very misleading one in the worst case. Indeed, a more appropriate model of evolutionary histories in these cases is a phylogenetic network, which extends the tree model by incorporating evolutionary events such as hybridization and horizontal gene transfer. Despite an increased research activity in the area of phylogenetic networks in recent years, their reconstruction and evaluation remain largely ad hoc processes and limited in their applicability to specific datasets. To enable the development of methodologies for systematic reconstructing and evaluating phylogenetic networks, this project is aimed at developing (1) algorithms for evaluating the quality of phylogenetic networks using genomic data, and (2) algorithms for searching the phylogenetic network space to enable automatic inference of evolutionary histories. The outcome of the proposed work will help significantly extend the applicability of phylogeny to groups of organisms for which trees are inappropriate, as well as to understand the phylogenetic network model, thus allowing for a more systematic development of methodologies for its accurate reconstruction. Further, the results will enable a more accurate reconstruction of the Tree of Life, help unravel microbial genome diversification, facilitate the reconstruction of hybridization scenarios in plants and other groups of organisms, and help understand the mechanisms by which microbes develop resistance to antibiotics. The project provides outstanding opportunities for training graduate and undergraduate students in an interdisciplinary research area.