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.