Research On Parallel Algorithm Of Distance-based Phylogenetic Tree System

With the fast development of biology sequencing technology,more and more biological data need to be processed.Traditinoal serial algorithms cost much time in processing biological data.They run with low efficience.In order to improve the performance of processing biological data,this paper analyze serial algorithms in the process of constructing phylogenetic tree.According to the analysis,this paper regards biological sequence data as research object and mine the potential of serial algorithms in parallel improvement.Then the paper proposes corresponding parallel algorithms.That makes algorithms of processing biological data get much better performance.It also lays a solid foundation for subsequent biological research.First of all,multiple sequence alignment contains three parts.They are multi-sequence pairwise alignment,constructing guide tree and multi-sequence progressive alignment sequentially.In the first part,every pairwise alignment result is independent.This paper uses that characteristic to analyze different parallel strategy.Then every pairwise alignment is regarded as parallel particles.This paper improves serial algorithm for better parallelization.And parallel algorithm based on matrix dimensionality reduction is proposed.This paper compares the performence of serial and parallel algorithm by experiments.Secondly,in the stage of calculating distance matrix,considering that the calculation of upper triangular elements on the matrix is independent,this paper implements a parallel algorithm based on OpenMP.In order to take full advantage of the computer's processor resources,this paper proposes mixed parallel algorithm based on OpenMP+GPU.Serial algorithm is divided into several parts.Different parts are assigned to the appropriate processors and calculated by different processors.Device and host parallelly process different parts at the same time.Program gets far better performence.At last,the biological sequence of influenza A virus is used as experimental data in this paper.Exprimental data includes genome sequences of influenza A virus' 116 subtype.This paper uses the serial algorithm and the parallel algorithm to construct their evolutionary tree respectively.Experiment results show that parallel construction takes much less time than serial construction.After the phylogenetic tree was obtained,the evolutionary relationship of these sequences was analyzed.