期刊名称：International Journal of Distributed and Parallel Systems
印刷版ISSN：2229-3957
电子版ISSN：0976-9757
出版年度：2010
卷号：1
期号：2
出版社：Academy & Industry Research Collaboration Center (AIRCC)
摘要：In biological research, scientists often need to use the information of the species to infer the evolutionary relationship among them. The evolutionary relationships are generally represented by a labeled binary tree, called the evolutionary tree (or phylogenetic tree). The phylogeny problem is computationally intensive, and thus it is suitable for parallel computing environment. In this paper, a fast algorithm for constructing Neighbor-Joining phylogenetic trees has been developed. The CPU time is drastically reduced as compared with sequential algorithms. The new algorithm includes three techniques: Firstly, a linear array A[N] is introduced to store the sum of every row of the distance matrix (the same as SK), which can eliminate many repeated (redundancy) computations, and the value of A[i] are computed only once at the beginning of the algorithm, and are updated by three elements in the iteration. Secondly, a very compact formula for the sum of all the branch lengths of OTUs (Operational Taxonomic Units) i and j has been designed. Thirdly, multiple parallel threads are used for computation of nearest neighboring pair.
