Explosions and hot spots in supertree methods
Introduction
explode vt. 1. to cause to be rejected; expose as false; discredit
hot spot [Slang] 1. an area of actual or potential trouble or violence
— Webster's New World Dictionary (1972).
A provocative feature of classical logic concerns how contradiction and logical inference interact. This logic's inference relation is explosive since according to it a contradiction entails everything, i.e., for any logical propositions and , . When this condition occurs the set of contradictory propositions is said to explode and the logical consequent is an explosive, and therefore logically meaningless, inference from that set. Thus if is “Integer 2 is prime” and is “Bill's supertree method (SM) is best” then the logical implication , although valid, provides no support for using Bill's SM, just as , although also valid, provides no support for not using Bill's SM.
In several ways exploding sets, and explosive inferences from exploding sets, pertain when inferring super- (or consensus) trees. (i) When inferring rooted phylogenies let an SM be presented with a set of rooted triplets (defined in the next section). Each triplet is a logical proposition that and are more closely related than either is to . If at least two triplets of are in input or result then at least a subset of or explodes. (ii) Let be any supertree (or consensus) method that when presented with a set of trees infers a set of super- (or consensus) trees; if explodes, i.e., if is logically equivalent to a contradiction, then could be viewed as an explosive, and therefore logically meaningless, inference from . (iii) For this reason if is any supertree (or consensus) method that when presented with a set of trees infers a set of super- (or consensus) trees, it would be instructive to characterize the sets that cause to explode, i.e., to understand precisely the circumstances in which becomes a logically meaningless inference from .
For example let be a consensus method and for the leaf set let 's input comprise the rooted trees of Fig. 1. can be represented as a union of triplet sets. is contained in and and is their triplet strict consensus (Sokal and Rohlf, 1981, p. 312). contains contradictory pairs of triplets; if is a region of contradiction in then should not derive from any explosive, and therefore logically meaningless, inferences from .
This paper presents the basic ideas and issues of how explosions affect the inference of rooted trees by SMs. We define the concepts needed to specify explosions. We use the semi-strict SM (Goloboff and Pol, 2002) and a new semi-closed SM to illustrate properties of exploding SMs and to characterize when those SMs explode trivially. With such characterizations we can identify input hot spots from which those SMs may make explosive inferences that cannot be logically justified. We suggest how to avoid explosive, and therefore logically meaningless, inferences from hot spots. We summarize why users should worry when explosions occur while inferring phylogenies.
Section snippets
Concepts and terms
Our SMs are based on the concept of rooted tree, i.e., an acyclic connected graph with each leaf (vertex of degree 1) uniquely labeled, with one interior vertex that is distinguished and called the root, and with no vertices of degree 2 except possibly the root. Always our trees are rooted with more than two labeled leaves and one interior vertex. A way to study sets of such trees is to replace each tree by a set of its phylogenetically informative subtrees, which may be taken to be binary
Trivial explosions
If an SM can be defined in terms of logical propositions then it may be possible to characterize the sets at which explodes trivially. Our examples are SMs that generalize from the consensus (e.g., Bremer, 1990, Day and McMorris, 2003) to the supertree context.
Hot spots
Let be any SM with a characterization (#) of any triplet set such that explodes trivially at . We could use (#) to identify regions of contradiction (with respect to ) in any set by applying (#) to the subsets of . Specifically let be any maximal subset of that satisfies ; since explodes trivially at then is a hot spot in for . explodes trivially at if and only if is itself a hot spot in for . Informally, although itself need not explode, any hot spot
Discussion
We have studied explosive inferences in a simple phylogenetic context where explosions and hot spots have natural formulations in logical rather than statistical terms. Seen through a statistical lens, an explosive inference may be a best inference in some sense, e.g., using maximum likelihood under some reasonable model, and may be meaningful. Nor would we necessarily condemn majority-rule or median SMs as giving logically meaningless inferences from contradictions, for such results could be
Acknowledgments
We thank P.A. Goloboff and an anonymous referee for their criticisms of a draft of this paper. M.W. was supported in part by BBSRC Grant 40/18385.
References (12)
- et al.
Extension operations on sets of leaf-labeled trees
Adv. Appl. Math.
(1995) - et al.
Semi-strict supertrees
Cladistics
(2002) - et al.
Closure operations in phylogenetics
Math. Biosci.
(2007) Combinable component consensus
Cladistics
(1990)- et al.
Tree structures for proximity data
Br. J. Math. Stat. Psychol.
(1981) - Day, W.H.E., McMorris, F.R., 2003. Axiomatic consensus theory in group choice and biomathematics. In: SIAM Frontiers in...
Cited by (4)
Coalescent methods for estimating phylogenetic trees
2009, Molecular Phylogenetics and EvolutionConservative supertrees
2011, Systematic BiologyRobinson-Foulds supertrees
2010, Algorithms for Molecular BiologyA maximum pseudo-likelihood approach for estimating species trees under the coalescent model
2010, BMC Evolutionary Biology