Phylogenetic Trees and Multiple Alignments
Given a tree topology and i.e. DNA-sequences as leaves. Parsimony means to minimize the number of mutations, which are necessary to explain the DNA-sequences: Find the assignment of characters to the interior nodes, such that the number of mutations along the edges is minimale.
There exists a dynamic programming algorithm by Fitch and Hartigan.
If the tree-topolgy is not given, the task is to find the topology, which minimizes the parsimony-score. The most pasimonious tree problem is NP-complete (use branch and bound methods).
Comments are very welcome.