Research On Tree Containment Algorithm And Platform Implementation

Gene evolution is usually tree-like and related studies have been conducted for more than half a century.However,evolutionary processes are often characterized by reticulate evolutionary events,which can be described by phylogenetic networks.Phylogenetic networks are often constructed and validated by checking their compatibility with existing phylogenetic trees.The tree containment problem(TCP)is defined as the process of determining whether or not a phylogenetic tree is consistent with a phylogenetic network,and it plays an important role in the related researches.The exponential recursive(ER)algorithm is one of the most efficient algorithms for solving tree containment problems for arbitrary networks.However,the second step of the ER algorithm has two theoretical shortcomings: one is that only one reticulation is processed at a time,and the other is not to judge the correctness of the decomposed network.This thesis studies the algorithm to solve the tree containment problem.The contributions of the thesis are as follows:(1)Based on the in-depth study of algorithms for solving the tree containment problem,this thesis proposes two tree containment algorithms,common ancestor reduction network(CARN)algorithm and cluster matching reduction network(CMRN)algorithm,which are improvements on the ER algorithm.To address the two shortcomings of the ER algorithm,the CARN algorithm will process multiple reticulation under the common reticulate ancestor in parallel,while the CMRN algorithm will eliminate incorrect networks by matching the clusters below the tree components in the phylogenetic network with those in the phylogenetic tree.The experimental results show that firstly the CARM algorithm does not have substantial advantages over the ER algorithm,and secondly the running time and the effective reticulation number of the CMRN algorithm are about half of those of the ER algorithm,which means that the efficiency of the algorithm is improved.Meanwhile,the CMRN algorithm is more sensitive to the change of the number of reticulation and about 1/4 of all reticulation are effective ones.(2)For the convenience of researchers,a computational platform for solving the tree containment problem is designed and developed,which integrates the ER algorithm and the CMRN algorithm.