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

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.

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

在本基金的支持下，本课题组针对系统发生网络领域中的若干NP-难解问题以及与系统发生树构造紧密联系的层次聚类问题分别开展了固定参数算法和近似算法的研究，并受系统发生网络背景的启发，学习利用进化算法解决若干图论组合优化问题。主要成果如下：(1)面向系统发生网络领域中的若干NP-难解问题（包含树包含问题、树组装问题、最小树剪切/粘贴距离问题等），基于系统发生网络的结构特征或问题本身性质，提出其合理的参数化模型，并结合各种固定参数算法设计技术和传统算法设计技术，为它们设计了高效的固定参数算法，证明了它们的固定参数可解性；(2)鉴于系统发生树构造与层次聚类问题之间的紧密联系，对若干聚类问题（包含有色k-中值问题、k-聚类问题、惩罚τ-色中值问题、带容量下限的k-中值问题）开展了近似算法研究，灵活利用采样、局部搜索、归约等算法设计技术，为它们设计了近似算法，改进了相关近似结果；(3)受系统发生网络背景的启发，学习利用进化算法解决若干图论组合优化问题（包含加权最小点覆盖问题、动态加权最小点覆盖问题、两跳-(1,2)-最小生成树问题），结合图结构性质和进化计算中经典的漂移分析理论，详细地分析了进化算法在解决这些图论组合优化问题的期望时间复杂度表现。