Multi-Objective Phylogenetic Tree Reconstruction Based On Consensus And Parallelization

Inferring phylogenetic tree is one of most fundamental problems in evolutionary biology.Also,it is a important problem of bioinformatics.The aim of phylogeny inference is rebuilding a tree that can precisely and authentically depict the evolutionary relationship between given molecular sequences.The methods for rebuilding a phylogenetic tree have been split into the following three categories:(1)Distance-matrix methods.(2)Maximum Parsimony.(3)Maximum Likelihood.Because Maximum Parsimony and Maximum Likelihood can both be treated as method of evaluating evolutionary tree,inferring phylogenetic tree can also be seen as a multi-objective optimization problem(MOP).Base on inferring phylogenetic tree is treated as a MOP in this papar,a new multi-objective evolutionary algorithm called MOEA-RC,which combines consensus,was proposed to solve phylogeny inference problem.Consensus are tree branch structures that present in several trees.It is assumed that those consensus are right branches.So all consensus will be found out and protected from following crossover and mutation operator in process of evolutionary algorithm.To validate the proposed algorithm,we conducted a series of experiments runs on three real-world datasets.The results show that the proposed algothrim is superior to several classical MOEAs and phylogeny inference softwares.Because there are two objective functions in algorithm,the algorithm runs too long.Therefore,a another new parallel MOEA was proposed in this thesis.This algorithm uses island model to enhance solution's variety and uses consensus to accelerate the algorithm's convergence.Also,a series of experiments was conducted for proposed algorithm.In experiments,the proposed algorithm was compared with MOEA-RC to valid it's convergency.After gained well result about convergency,another experiment was conducte to find out the parallel efficiency of proposed algorithm.Based on well performance,the proposed algorithm has been packaged into a web server,thus the users can only use a personal computer to run the algorithm that needs amounts of computational resources.