الفهرس Only 14 pages are availabe for public view
 |  | from | 81 |  |  |
| | | from | 81 | | |
Abstract
A phylogenetic tree is a graphical representation of the relationship between biological species. Constructing a phylogenetic tree, from DNA or protein sequences needs a good result of a multiple sequence alignment (MSA) algorithm. The quality of the produced tree depends mainly on the quality of the alignment. The quality is usually measured as a distance between the produced tree and an optimal tree.
MSA is an NP-complete problem and therefore a heuristic solution is usually adopted. ClustalW is an open source MSA algorithm that is widely used. However, in case of divergent sequences (the sequences that have low similarity with each other) the algorithm produces inaccurate results. ClustalW algorithm consists of three steps: First, it determines all pair-wise alignment between sequences. Then, it constructs a guide tree using neighbor-joining algorithms. Finally, it combines the alignment - resulted from stepl - starting from the most closely related sequences to the most distantly related sequences using the generated merge plan.
In this research, we propose to modify the guide tree generation step of the ClustalW algorithm so that the tree reflects the divergent sequence before applying the neighbor¬joining algorithms. A divergent sequence is determined using a threshold derived from the pair-wise distances produced at the first step of the algorithm. In doing so, we assume that distance matrix is taken from a normal distribution and at a specific confidence level. In addition, we study the sensitivity of the quality of the resultant phylogenetic trees on divergence threshold decision.
BAliBASE benchmark is used in our empirical experiments that include 218 groups of references and their optimal MSA. The proposed algorithm is shown to enhance the accuracy of the produced phylogenetic trees in most of the cases (when compared to the original ClustalW algorithm).