Enhanced Character Based Algorithm for Small Parsimony

Authors: Parvinder Singh Sandhu, Sumeet Kaur Sehra, Karmjit Kaur

Abstract:

Phylogenetic tree is a graphical representation of the evolutionary relationship among three or more genes or organisms. These trees show relatedness of data sets, species or genes divergence time and nature of their common ancestors. Quality of a phylogenetic tree requires parsimony criterion. Various approaches have been proposed for constructing most parsimonious trees. This paper is concerned about calculating and optimizing the changes of state that are needed called Small Parsimony Algorithms. This paper has proposed enhanced small parsimony algorithm to give better score based on number of evolutionary changes needed to produce the observed sequence changes tree and also give the ancestor of the given input.

Keywords: Phylogenetic Analysis, Small Parsimony, EnhancedFitch Algorithm, Enhanced Sakoff Algorithm.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1060455

References:

[1] D. Huson "Algorithms in Bioinformatics", Syst. Zoology. 20:406-416., 2007.
[2] F. Arndt Peter and Hwa Terence "Identification and measurement of neighbor-dependent nucleotide substitution processes". Bioinformatics Original Paper Vol. 21 No. 10, Pages 2322-2328., 2005.
[3] F. Arndt Peter December 2006 "Reconstruction of ancestral nucleotide sequences and estimation of substitution frequencies in a star phylogeny". Gene 390 (2007) 75-83., 2006.
[4] H. Oakley Todd And W. Cunningham Clifford () "Independent Contrasts Succeed Where Ancestor Reconstruction Fails In A Known Bacteriophage Phylogeny". Evolution, 54(2), 2000, pp. 397-405., 2000.
[5] K. A. K. Strandberg and A. Salter Laura "A comparison of methods for estimating the transition:transversion ratio from DNA sequences". Department of Mathematics and Statistics, University of New Mexico, Albuquerque, NM 87131, USA. Molecular Phylogenetics and Evolution 32 (2004) 495-503. , 2004.
[6] R. Bruce, P. John Huelsenbeck, Yang Ziheng And Nielsen Rasmus "Taxon Sampling and the Accuracy of Large Phylogenies". Department of Ecology and Evolution, State University of New York, Stony Brook, NY 11794-5245, USA. Syst. Biol. 47 (4), 710-718, 1998.
[7] R. Fredrik "Parsimony: Counting Changes" (2) 73-86., 2005.
[8] S.Wing-Kin, Weiwei Cheng, Liang Yang "Combinatorial methods in bioinformatics: Phylogenetic Trees Reconstruction". Vol-2, Page-7-17,. 2004.