Efficient Algorithms for Constructing Phylogenetic Networks

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

• 批准号: RGPIN-2018-05435
• 负责人: Zeh, Norbert
• 金额: $ 2.48万
• 依托单位: Dalhousie University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=685230
• 关键词: 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难的组合优化问题。我的研究计划的重点是开发有效的算法，这个问题下的各种概念的一致性网络与给定的树。以前的工作已经导致了非常有效的算法来构建系统发育网络的两棵树，但网络的建设，许多树仍处于起步阶段。这将是我研究的重点。在理论方面，我的研究旨在产生可证明有效的算法来构建系统发育网络和下限，以限制这些算法的效率。这项研究将利用技术从参数化的复杂性和精确指数算法。在实践方面，我将专注于开发算法的工程有效实现，这些算法可以被从业者用作系统发育分析管道的一部分。这项工程工作的一部分将包括使用有效的数据结构实现所开发算法的低级别细节，并调整低级别实现细节。工程工作的一个更基本的方面将集中在寻找启发式的改进，如集群减少，这有可能提供指数加速的算法在实践中，同时可证明保持计算解决方案的正确性。