previous section previous page next page next section

Online Lectures on Bioinformatics


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.