基于有根系统树的系统发生网络构建算法研究

Phylogenetic networks are able to describe reticulate evolutionary events that species occurred during evolution, and are able to represent conflicting evolutionary information implied by phylogenetic trees. In view of the current status of phylogenetic network construction algorithms, such as high time complexity and the constructed network dependent on the order of inpt data, this project study the phylogenetic network construction algorithms based on rooted phylogenetic tree. First the project studies the phylogenetic tree construction algorithms. An improved Neighbor-Joining (NJ) algorithm is proposed by means of extending the theory of NJ algorithm, by combining the improved NJ algorithm with the search strategy of RapidNJ and the external storage style of ERapidNJ, a novel method for constructing phylogenetic trees is created so that the method is more quickly and efficiently, especially for large data. Then the project researches the definition of metrics on the space of phylogenetic networks. In the process of constructing phylogenetic networks, one needs to compute the distance between phylogenetic networks, such as the distance between the constructed networks and the simulation networks or the real networks. The project defines a new metric that can measure the difference between the more network than other metrics. Finally the projest focuses on the phylogenetic network construction algorithms, designs a new algorithm based on the clouster incompatibility and seed-growing algorithm, the new algorithm has lower time complexity and the constructed network is more accurate and efficient.

系统发生网络可以描述物种在进化过程中发生的网状进化事件，也可以表示多棵系统树所隐含的冲突进化信息。鉴于目前系统发生网络构建算法的一些缺点，如时间复杂度高及所构建的网络依赖于输入数据顺序等，本项目研究基于有根系统树的系统发生网络构建算法。本项目首先改进系统树构建算法，通过扩展邻接法理论基础的方式改进邻接法，并且将改进的邻接法与RapidNJ 的搜索策略及 ERapidNJ 的外存方式相结合提出新的系统树构建方法，使得此方法在处理大数据集时更加快速有效。其次研究系统发生网络空间上度量的定义。在系统发生网络的构建过程中，需要计算系统发生网络间的距离，例如计算得到的网络与仿真网络或者真实网络之间的距离。本项目定义新的度量，使得此度量可以衡量更多网络之间的差异。最后提出系统发生网络构建新算法——基于簇集的不相容性及种子增长算法，使得此算法时间复杂度更低，同时所构建的网络更加准确有效。

系统发生网络可以描述物种在进化过程中发生的网状进化事件，也可以表示多棵系统树所隐含的冲突进化信息。鉴于目前系统发生网络构建算法的一些缺点，如时间复杂度高及所构建的网络依赖于输入数据顺序等，本项目研究基于有根系统树的系统发生网络构建算法。.（1）提出了基于距离矩阵构建系统发生树的 ENJ 算法，它是邻接法的一种改 进。邻接法是目前有效构建系统发生树算法之一，它运算速度快，准确率高，且适用于大数据集。但是它会出现结果进化树不唯一现象。ENJ 算法可以有效合并三个邻接节点，解决了邻接法产生多个结果树的问题。设计并实现了系统发生树距离计算的在线系统 CDRPT（http://bioinformatics.imu.edu.cn/tree/），其中实现了簇算法、分割算法、三倍数算法和等价算法。并设计实现了依据邻接法及其改进算法构建系统发生树的可安装应用软件及应用平台 INJ（http://bioinformatics.imu.edu.cn/INJ/）。.（2）提出了系统发生网络空间上度量，此度量所定义的空间是目前最大的空间，即k阶简化系统发生网络空间，此度量可以衡量更多网络之间的差异。设计并实现了系统发生网络距离计算的在线系统 CDRPN（http://bioinformatics.imu.edu.cn/distance/），其中实现了半等价算法、等价算法、向量算法和三分割算法。.（3）提出了基于有根系统树构建系统发生网络的 Frin 算法，Frin算法基于物种频率和不相容度选择去除物种，削弱了输入数据顺序的影响，加快了系统发生网络的构建。通过实验得到，相比 Cass、Lnetwork 和 BIMLR 算法，Frin 算法明显削弱了输入数据顺序的影响； Frin 算法构建的网络更简单，多余簇的数量更少；Frin 算法为禾本科植物有效地构建了系统发生网络。设计并实现了构建系统发生网络的在线系统 IGNET（http://bioinformatics.imu.edu.cn/）。