An Optimized Algorithm to Find Maximum Parsimonious Tree Using PrimeNucleotide Based Approach

Abstract

Molecular phylogeny based on the nucleotide or amino acid sequence comparison has become a widespread tool for general taxonomy and evolutionary analysis. Molecular phylogeny methods are often free of problems which arise while applying phenotypic phylogeny. So, we prefer phylogenetic methods for classifying the organisms in any evolutionary situation. Phylogenetic inference methods like Maximum parsimony perform exhaustive search strategy to extract evolutionary information from genomic sequences. It is a simple but popular technique used in cladistics to infer a phylogenetic tree for a set of taxa (commonly of species or reproductively isolated populations of a single species) on the basis of some observed data on the similarities and differences among taxa. The relationships among organisms or genes are studied by comparing the homologues of DNA and protein sequences. However, complexity arises when we increase the number of sequences involved, as the number of possible solutions increase exponentially alongside. In our paper, we have proposed an algorithm which identifies the highest repeating nucleotide (PrimeNucleotide) from the informative site efficiently to fix one ParentNode with the best fitted nucleotide using a predefined WeightMatrix to find the most parsimonious phylogenetic tree in linear time. The algorithm has been applied on the genome sequences of different bacteria and viruses to ensure its efficiency and universality. The results obtained were similar to the traditional Transverse parsimony method and a significant improvement in both time consumption and memory usage rate were achieved.