Efficient Algorithms for 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.