Computational Phylogenetics - Maximum Parsimony

Maximum Parsimony

Maximum parsimony (MP) is a method of identifying the potential phylogenetic tree that requires the smallest total number of evolutionary events to explain the observed sequence data. Some ways of scoring trees also include a "cost" associated with particular types of evolutionary events and attempt to locate the tree with the smallest total cost. This is a useful approach in cases where not every possible type of event is equally likely - for example, when particular nucleotides or amino acids are known to be more mutable than others.

The most naive way of identifying the most parsimonious tree is simple enumeration - considering each possible tree in succession and searching for the tree with the smallest score. However, this is only possible for a relatively small number of sequences or species because the problem of identifying the most parsimonious tree is known to be NP-hard; consequently a number of heuristic search methods for optimization have been developed to locate a highly parsimonious tree, if not the best in the set. Most such methods involve a steepest descent-style minimization mechanism operating on a tree rearrangement criterion.

Read more about this topic:  Computational Phylogenetics

Famous quotes containing the words maximum and/or parsimony:

    I had a quick grasp of the secret to sanity—it had become the ability to hold the maximum of impossible combinations in one’s mind.
    Norman Mailer (b. 1923)

    There is nothing worse than being ashamed of parsimony or poverty.
    Titus Livius (Livy)