Maximum Parsimony (MP) Method

Maximum parsimonyRH_Maximum_Parsimony_Principle (MP) methods originally were developed for morphological characters, and there are many different versions (see Nei and Kumar [2000]Nei_and_Kumar_2000 for a review).  In MEGA, we consider both of these methods for nucleotide and amino acid sequence data (Eck and Dayhoff 1966Eck_and_Dayhoff_1966; Fitch 1971Fitch_1971).

For constructing an MP tree, only sites at which there are at least two different kinds of nucleotides or amino acids, each represented at least twice, are used (parsimony-informative sites). Other variable sites are not used for constructing an MP tree, although they are informative for distance and maximum-likelihood methods.

MEGA estimates MP tree branch A branch is a line connecting either two internal nodes to each other or an external node to an internal node in a phylogenetic tree. The length of a branch denotes the genetic distance (e.g., number of substitutions per unit time) between the two taxa it connects. lengths by using the average pathway method for unrooted trees (see Nei and Kumar [2000]Nei_and_Kumar_2000, page 132).

To search for MP Trees, MEGA provides four different types of searches: the max-mini branch A branch is a line connecting either two internal nodes to each other or an external node to an internal node in a phylogenetic tree. The length of a branch denotes the genetic distance (e.g., number of substitutions per unit time) between the two taxa it connects.-and-bound searchRH_Max_mini_branch_and_bound_search, min-mini heuristic searchRH_Min_mini_algorithm, Subtree-Pruning-Regrafting (SPR) For any tree searching method, exhaustive search, where all possible topologies are considered is unfeasible for even a small number of taxa. Subtree Pruning And Regrafting is a tree topology search heuristic which reduces the number of topologies searched by performing the following operations on the tree. First, a subtree of the current best tree is selected and detached (pruned). Second, the detached subtree is regrafted onto another branch of the remaining tree, in such a way that a new topology is created and then likelihood of the new topology is calculated. This procedure is repeated for all regrafting positions that produce new topologies using the pruned subtree. The procedure is also repeated for each subtree (within the designated search level) and if the topology with best likelihood among those scored gives sufficient improvement over the current best tree, that topology becomes the current best tree. This is repeated until no significant further likelihood improvements are obtained. A single pass of the SPR algorithm examines O(N2) new trees, where N is the number of leaves in the original tree. This is because, for each subtree there are O(N) possible regraftings, and there are O(N) possible subtrees to consider. In contrast, NNI examines O(N) topologies at each pass of the algorithm.Subtree_Pruning_Regrafting, and Tree-Bisection-Reconnection (TBR)Tree_Bisection_Reconnection_TBR_ RH_Close_Neighbor_Interchange_CNI heuristic search.  Only the branch A branch is a line connecting either two internal nodes to each other or an external node to an internal node in a phylogenetic tree. The length of a branch denotes the genetic distance (e.g., number of substitutions per unit time) between the two taxa it connects.-and-bound search is guaranteed to find all the MP trees, but it takes prohibitive amount of time if the number of sequences is large (>15).  For details, please see chapter 7 in Nei and Kumar (2000)Nei_and_Kumar_2000