Efficient Algorithms for Constructing Phylogenetic Networks

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

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.