Lattice-theoretic properties of MPR-posets in phylogeny
With biological sciences such as taxonomy, cladistics and phylogeny as a background, the principle of maximum parsimony also called Wagner Parsimony has been mathematically formulated and then a mathematical and algorithmic theory has been developing. Recently, a clear method for the character-state minimization problem called the First Most-Parsimonious Reconstruction (MPR) Problem under linearly ordered character-states has been presented by Hanazawa et al. (Appl. Math. 56 (1995) 245265), Narushima and Hanazawa (Discrete Appl. Math. 80 (1997) 231238). From a phylogenetic point of view, Minaka (Forma 8 (1993) 277296) has introduced two partial orderings on the set of MPRs to investigate the relationships among the MPRs. One is the usual ordering, and the other is a partial ordering that depends on a state of a specified root of a given el-tree, which is called a ?(r)-version ordering. In this paper, the following three theorems on MPR-posets induced by these orderings are shown: (1) a usual MPR-poset is a complete distributive lattice, (2) a ?(r)-version MPR-poset is a lower-complete semi-lattice, (3) any interval poset of a ?(r)-version MPR-poset is a complete distributive lattice. Some possible applications and meanings of the theorems are also mentioned.
lattice-theoretic properties mpr-poset maximum parsimony evolutionary tree character-state optimization