In this article we prove that the distance $d_{\mathrm{MP}}(T_1,T_2) = k$ between two unrooted binary phylogenetic trees $T_1, T_2$ on the same set of taxa can be defined by a character that is convex on one of $T_1, T_2$ and which has at most $2k$ states. This significantly improves upon the previous bound of $7k-5$ states. We also show that for every $k \geq 1$ there exist two trees $T_1, T_2$ with $d_{\mathrm{MP}}(T_1,T_2) = k$ such that at least $k+1$ states are necessary in any character that achieves this distance and which is convex on one of $T_1, T_2$. We augment these lower and upper bounds with an empirical analysis which shows that in practice significantly fewer than $k+1$ states are usually required.

In a recent study, Bryant, Francis and Steel investigated the concept of “future-proofing” consensus methods in phylogenetics. That is, they investigated if such methods can be robust against the introduction of additional data like added trees or new species. In the present manuscript, we analyze consensus methods under a different aspect of introducing new data, namely concerning the discovery of new clades. In evolutionary biology, often formerly unresolved clades get resolved by refined reconstruction methods or new genetic data analyses. In our manuscript we investigate which properties of consensus methods can guarantee that such new insights do not disagree with previously found consensus trees, but merely refine them, a property termed monotonicity . Along the lines of analyzing monotonicity, we also study two established supertree methods, namely Matrix Representation with Parsimony (MRP) and Matrix Representation with Compatibility (MRC), which have also been suggested as consensus methods in the literature. While we (just like Bryant, Francis and Steel in their recent study) unfortunately have to conclude some negative answers concerning general consensus methods, we also state some relevant and positive results concerning the majority rule ( M R ) and strict consensus methods, which are amongst the most frequently used consensus methods. Moreover, we show that there exist infinitely many consensus methods which are monotonic and have some other desirable properties. • Investigation of established consensus methods for monotonicity and non-contradiction. • Investigation of established supertree methods for monotonicity and non-contradiction. • Introduction of infinitely many theoretical consensus methods that are regular, monotonic and non-contradictory.

Given two phylogenetic trees on the same set of taxa X, the maximum parsimony distance dMPis defined as the maximum, ranging over all characters x on X, of the absolute difference in parsimony score induced by x on the two trees. In this note, we prove that for binary trees there exists a character achieving this maximum that is convex on one of the trees (i.e., the parsimony score induced on that tree is equal to the number of states in the character minus 1) and such that the number of states in the character is at most 7dMP- 5. This is the first non-trivial bound on the number of states required by optimal characters, convex or otherwise. The result potentially has algorithmic significance because, unlike general characters, convex characters with a bounded number of states can be enumerated in polynomial time.

Phylogenetic networks are used to display the relationship among different species whose evolution is not treelike, which is the case, for instance, in the presence of hybridization events or horizontal gene transfers. Tree inference methods such as maximum parsimony need to be modified in order to be applicable to networks. In this paper, we discuss two different definitions of maximum parsimony on networks, “hardwired” and “softwired,” and examine the complexity of computing them given a network topology and a character. By exploiting a link with the problem Multiterminal Cut, we show that computing the hardwired parsimony score for 2-state characters is polynomial-time solvable, while for characters with more states this problem becomes NP-hard but is still approximable and fixed parameter tractable in the parsimony score. On the other hand we show that, for the softwired definition, obtaining even weak approximation guarantees is already difficult for binary characters and restricted network topologies, and fixed-parameter tractable algorithms in the parsimony score are unlikely. On the positive side we show that computing the softwired parsimony score is fixed-parameter tractable in the level of the network, a natural parameter describing how tangled reticulate activity is in the network. Finally, we show that both the hardwired and the softwired parsimony scores can be computed efficiently using integer linear programming. The software has been made freely available.