An optimized algorithm to find maximum parsimonious tree using PrimeNucleotide based approach

Phylogenetic inference methods like Maximum-parsimony perform exhaustive search strategy to extract evolutionary information from genomic sequences. Complexity arises when we increase the number of sequences involved, as the number of possible solutions increase exponentially alongside. In this 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.