previous section previous page next page next section
CMB

Online Lectures on Bioinformatics

navigation


Phylogenetic Trees and Multiple Alignments



Parsimony

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.
luz@molgen.mpg.de