Efficient Algorithms for Constructing Phylogenetic Networks

我的研究重点是开发可证明有效的算法来构建系统发育网络，并在工程上有效地实现这些算法。系统发育树和系统发育网络被用来表示一组分类群的进化历史。根据这些分类群的基因序列，可以使用各种方法构建系统发育树。进化历史包括非树状的过程，如横向基因转移和杂交，允许分类群从一个以上的亲本或从不相关的分类群获得遗传物质，最好将其建模为网络。对于进化历史不是树的分类群，代表这些分类群个别基因进化的系统发育树是不同的。系统发育学中的一个重要问题是试图从这些“基因树”中重建代表一组分类群进化的网络。在合理的假设下，这是一个NP难的组合优化问题。我的研究计划专注于在网络与给定树的一致性的各种概念下，为这个问题开发有效的算法。以前的工作已经导致了非常有效的算法来构建两棵树的系统发育网络，但针对许多树的网络的构建仍处于初级阶段。这将是我的主要研究重点。在理论方面，我的研究旨在产生可证明有效的算法，用于构建系统发育网络，并为此类算法的效率设定下限。这项研究将利用参数复杂性和精确指数算法中的技术。在实践方面，我将重点介绍开发的算法的工程高效实现，这些算法可以被从业者用作其系统发育分析管道的一部分。这一工程工作的一部分将包括使用高效的数据结构实现所开发算法的低级别细节，并调整低级别实现细节。工程工作的一个更基本的方面将集中在寻找启发式改进，如簇减少，这有可能在实践中提供算法的指数加速，同时可证明保持计算解的正确性。

My research focuses on developing provably efficient algorithms for constructing phylogenetic networks and engineering efficient implementations of these algorithms. Phylogenetic trees and phylogenetic networks are used to represent the evolutionary history of a set of taxa. Phylogenetic trees can be constructed from the gene sequences of these taxa using various methods. Evolutionary histories that include non-tree-like processes such as lateral gene transfer and hybridization, which allow taxa to acquire genetic material from more than one parent or from unrelated taxa, are best modelled as networks. For sets of taxa whose evolutionary history is not a tree, the phylogenetic trees representing the evolution of individual genes of these taxa differ. An important problem in phylogenetics is to try to reconstruct the network representing the evolution of a set of taxa from these "gene trees". Under reasonable assumptions, this turns into an NP-hard combinatorial optimization problem. My research program focuses on developing efficient algorithms for this problem under various notions of consistency of a network with the given trees. Previous work has led to very efficient algorithms for constructing phylogenetic networks for two trees, but the construction of networks for many trees is still in its infancy. This will be the main focus of my research. On the theoretical side, my research aims to produce provably efficient algorithms for constructing phylogenetic networks and lower bounds that establish limits on how efficient such algorithms can be. This research will utilize techniques from parameterized complexity and exact exponential algorithms. On the practical side, I will focus on engineering efficient implementations of the developed algorithms that can be used by practitioners as part of their phylogenetic analysis pipelines. Part of this engineering effort will consist of implementing the low-level details of the developed algorithms using efficient data structures and tuning low-level implementation details. A more fundamental aspect of the engineering work will focus on finding heuristic improvements such as cluster reduction, which have the potential to offer exponential speed-ups of the algorithms in practice while provably preserving the correctness of the computed solution.