系统发生网络难解问题核心化与参数算法研究

在系统发生学中，因为以往常用于表示物种进化过程的系统发生树不能诠释一类统称为网状进化事件的新物种形成事件，所以人们提出了一种更一般化的进化模型，系统发生网络。但是与系统发生网络相关的许多计算问题被证明是NP难解的。人们故引入了近些年发展起来的参数计算理论，利用其中的算法设计技术求解这些难解问题。虽然人们已利用该技术手段就这些问题取得了一些进展，但是相关研究还仍处于起步阶段，有待进一步改进和完善。本项目将对与系统发生网络相关的一系列难解问题展开研究，探讨影响其复杂性的结构参数，建立相应的参数化模型，并分析其参数复杂性；利用全局或局部的核心化设计与分析技术，为其设计新的核心化方法；尝试各种新的算法设计与分析技术，为其设计高效的固定参数算法。本项目还将对所获得的算法在真实生物数据集上的运行效率进行分析，对实验结果进行生物意义上的探讨。本项目的研究将对系统发生学的发展起到重要推动作用。

In Phylogeny, the phylogenetic trees that were widely used to represent the tree-like evolution of a collection of species, are unable to represent a special collection of evolutionary events named reticulation events. Hence, a more general evolutionary model, phylogenetic network, was presented. However, most of the related computational problems in the area of phylogenetic network were proved to be NP-hard. Thus parameterized computing theory that has been developing in recent years was introduced to solve these NP-hard problems. Although some results have been presented under this research direction, the related research is still at an initial stage, and many aspects of it need to be further explored. In the project, we will focus on a series of hard problems. Firstly, we will analyze the structural parameters that affect the complexities of these problems, and study their parameterized complexities under the corresponding parameterized models. Secondly, we will use the global or local kernelization design and analysis techniques, to give new kernelizations for them. Thirdly, we will attempt all kinds of algorithm design and analysis techniques, to present new fixed-parameter algorithms for them. Finally, we will analyze the runtime efficiencies of the algorithms that we present based on the real biological data, and discuss the experimental results from the aspect of biological meaning. Our research will advance the development of Phylogeny.