Efficient Algorithms for Constructing Phylogenetic Networks

构建系统发育网络的有效算法

• 批准号: RGPIN-2018-05435
• 负责人: Zeh, Norbert
• 金额: $ 2.48万
• 依托单位: Dalhousie University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=713680
• 关键词: Efficient; Algorithms; Constructing; Phylogenetic; Networks

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.

我的研究重点是开发可证明有效的算法，用于构建这些算法的系统发育网络和工程有效实现。 系统发育树和系统发育网络用于代表一组分类单元的进化历史。可以使用各种方法从这些分类单元的基因序列构建系统发育树。包括非树样过程（例如横向基因转移和杂交）的进化历史，允许分类单元从多个父母或不相关的分类单元中获取遗传物质，最好将其作为网络建模。对于一组进化史而不是树的分类单元，代表这些分类单元基因演变的系统发育树不同。 系统发育学中的一个重要问题是尝试重建代表这些“基因树”一组分类单元演变的网络。在合理的假设下，这变成了NP-HARD组合优化问题。我的研究计划着重于在与给定树木的网络的各种一致性概念下为该问题开发有效的算法。以前的工作导致了非常有效的算法，用于为两棵树构建系统发育网络，但是许多树木的网络仍处于起步阶段。这将是我研究的主要重点。从理论方面来说，我的研究旨在生成可证明有效的算法，用于构建系统发育网络和下限，以建立对这种算法的有效效率的限制。这项研究将利用参数化的复杂性和确切的指数算法的技术。从实际方面来说，我将重点介绍开发算法的工程有效实现，从业人员可以将其用作其系统发育分析管道的一部分。这项工程工作的一部分将包括使用有效的数据结构并调整低级实现细节的开发算法的低级细节。工程工作的一个更基本的方面将集中于寻找启发式改进，例如减少群集，它们有可能在实践中提供算法的指数加速，同时证明可以保留计算出的解决方案的正确性。