Abstract—Over the last few years, the exponential growth of biological diversity achievements brought to light the need for new efficient techniques to check evolutionary relationships. One of the main methods to illustrate such relationships are phylogenetic trees. A variety of approaches which are used for tree reconstruction issue fall into two main groups: distance based and sequence based. Sequence based methods, such as maximum parsimony, can be used when the tree is reconstructed on a sequence alignment. However, in most cases it is inconceivable to compute parsimony score for all trees. On the other hand, distance based methods are extremely faster because the tree is usually constructed from a given distance matrix; nevertheless, seldom can distance matrices show the true identity of organisms. Here, we propose a novel technique to approximate the parsimony tree with stepwise addition method utilizing clustering. In this strategy we only calculate parsimony score for a part of incompletely constructed tree (called “cluster”) at each step instead of the whole tree. Experiments confirm our hypothesis and do indicate that the algorithm is quite fast to build the phylogenetic tree, often with a satisfactory outcome, when there is a large dataset. We also believe that our method could prove useful as a starter tree for heuristic search approaches.

Index Terms—Phylogenetic tree construction, maximum parsimony, step-wise addition.

Abolfazl Ghavidel is with the Computer Engineering Department, Azad University of Mashhad, Mashhad, Iran (e-mail: a.ghavidel@mshdiau.ac.ir).
Mahmoud Naghibzadeh is with the Computer Engineering Department, Ferdowsi University of Mashhad, Mashhad, Iran.
Omid Mirshamsi is with the Department of Biology, Ferdowsi University of Mashhad, Mashhad, Iran.

Cite: Abolfazl Ghavidel, Mahmoud Naghibzadeh, and Omid Mirshamsi, "FSA: A Fast Stepwise Addition Algorithm for Constructing Phylogenetic Trees," International Journal of Bioscience, Biochemistry and Bioinformatics vol. 4, no. 5, pp. 369-376, 2014.