Hereditary maximum parsimony trees and not so hereditary ones,
Mareike Fischer
U Vienna
Austria

Abstract

Maximum Parsimony (MP) is one of the most freqently used methods for inferring phylogenetic trees, but deciding whether a given tree is most parsimonious for some DNA alignment has been found to be NP-hard. Therefore, an additional criterion ruling out certain trees as possible MP candidates would be desirable. It has recently been suggested that MP might be hereditary, i.e. that for every MP-tree (for some DNA alignment D) with n leaves there are a subtrees of size k for all k = 4,…, n-1 that are also MP (forr the alignment D restricted to the corresponding rows). In this case, the MP decision problem could be reduced to smaller trees, which would simplify the problem drastically.
Additionally, from the mathematical point of view, hereditary MP trees would allow for general statements on MP to be proved by means of induction. While it can be shown that for some special cases this desired property of MP indeed holds, it unfortunately turns out that in general, MP-trees do not necessarily have a sequence of MP-subtrees for the corresponding restrictions of the underlying data. In my poster, I will present an example to illustrate this case, and I will also demonstrate some more highly non-hereditary properties of MP, which are even more surprising.

Jornada Matemática SPM/CIM "Mathematical Biology"