{'fraction_non_alphanumeric': 0.05354447475041708, 'fraction_numerical': 0.01774223446230437, 'mean_word_length': 3.39218422889044, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 23, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the Ancestral Compatibility of Two Phylogenetic Trees with Nested Taxa

Compatibility of phylogenetic trees is the most important concept underlying widely-used methods for assessing the agreement of different phylogenetic trees with overlapping taxa and combining them into common supertrees to reveal the tree of life. The notion of ancestral compatibility of phylogenetic trees with nested taxa was introduced by Semple et al in 2004. In this paper we analyze in detail the meaning of this compatibility from the points of view of the local structure of the trees, of the existence of embeddings into a common supertree, and of the joint properties of their cluster representations. Our analysis leads to a very simple polynomial-time algorithm for testing this compatibility, which we have implemented and is freely available for download from the BioPerl collection of Perl modules for computational biology.


Introduction
A rooted phylogenetic tree can be seen as a static description of the evolutive history of a family of contemporary species: these species are located at the leaves of the tree, and their common ancestors are organized as the inner nodes of the tree. These interior nodes represent taxa at a higher level of aggregation or nesting than that of their descendents, ranging for instance from families over genera to species. Phylogenetic trees with nested taxa have thus all leaves as well as some interior nodes labeled, and they need not be fully-resolved trees and may have unresolved polytomies, that is, they need not be binary trees.
Often one has to deal with two or more phylogenetic trees with overlapping taxa, probably obtained through different techniques by the same or different researchers. The problem of combining these trees into a single supertree containing the evolutive information of all the given trees has recently received much attention, and it has been identified as a promising approach to the reconstruction of the tree of life [2]. This information corresponds to evolutive precedence, and hence it is kept when every arc in each of the trees becomes a path in the supertree.
It is well known that it is not always possible to combine phylogenetic trees into a single supertree: there are incompatible phylogenetic trees that do not admit their simultaneous inclusion into a common supertree. Compatibility for leaf-labeled phylogenetic trees was first studied in [15]. Incompatible phylogenetic trees can still be partially combined into a maximum agreement subtree [14]. Compatible phylogenetic trees, on the other hand, can be combined into a common supertree, two of the most widely used methods being matrix representation with parsimony [1,8] and mincut [5,12] and it is clear that, because of Occam's razor, one is interested in obtaining not only a common supertree of the given phylogenetic trees, but the smallest possible one. The relationship between the largest common subtree and the smallest common supertree of two leaf-labeled phylogenetic trees was established in [9] by means of simple constructions, which allow one to obtain the largest common subtree from the smallest common supertree, and vice versa.
The study of the compatibility of phylogenetic trees with nested taxa, also known as semilabeled trees, was asked for in [6]. Polynomial-time algorithms were proposed in [3,10] for testing a weak form of compatibility, called ancestral compatibility, and a stronger form called perfect compatibility. Roughly, two or more semi-labeled trees are ancestrally compatible if they can be refined into a common supertree, and they are perfectly compatible if there exists a common supertree whose topological restriction to the taxa in each tree is isomorphic to that tree.
In this paper, we are concerned with the notion of ancestral compatibility of semi-labeled trees. In particular, we establish the equivalence between this notion and the absence of certain 'incompatible' pairs and triples of labels in the trees under comparison. We also prove the equivalence between ancestral compatibility and a certain property of the cluster representations of the trees. These equivalences lead to a new polynomial-time algorithm for testing ancestral compatibility of semi-labeled trees, which we have implemented and is freely available for download from the BioPerl collection of Perl modules for computational biology [13].
The rest of the paper is organized as follows. Basic notions and notation are recalled in Section 2. A notion of local compatibility as the absence of incompatible pairs and triples of labels is introduced in Section 3, together with some basic results about a relaxed notion of semi-labeled trees. Weak topological embeddings, and the notion of ancestral compatibility that derives from them, are studied in Section 4. In Section 5, the equivalence between local compatibility in the sense of Section 3 and ancestral compatibility in the sense of Section 4 is established, as well as a characterization in terms of cluster representations. The BioPerl implementation of the algorithm for testing compatibility of two semi-labeled trees is described in Section 6. Finally, some conclusions and further work are outlined in Section 7.

Preliminaries
Throughout this paper, by a tree we mean a rooted tree, that is, a directed finite graph T = (V, E) with V either empty or containing a distinguished node r ∈ V , called the root, such that for every other node v ∈ V there exists one, and only one, path from the root r to v. Recall that every node in a tree has in-degree 1, except the root, which has in-degree 0.
Henceforth, and unless otherwise stated, given a tree T we shall denote its set of nodes by V (T ) and its set of arcs by E(T ). The children of a node v in a tree T are those nodes w such that (v, w) ∈ E(T ). The nodes without children are the leaves of the tree, and we shall call elementary the nodes with only one child.
Given a path (v 0 , v 1 , . . . , v k ) in a tree T , its origin is v 0 , its end is v k , and its intermediate nodes are v 1 , . . . , v k−1 . Such a path is non-trivial when k 1. We shall represent a path from v to w, that is, a path with origin v and end w, by v w. When there exists a path v w, we say that w is a descendant of v and also that v is an ancestor of w. Every node is both an ancestor and a descendant of itself, through a trivial path.
Two non-trivial paths (a, v 1 , . . . , v k ) and (a, w 1 , . . . , w ℓ ) in a tree T are said to diverge when the only node they have in common is their origin a. Notice that, by the uniqueness of paths in trees, it is equivalent to the condition v 1 = w 1 . For every two nodes v, w of a tree that are not connected by a path, there exists one, and only one, common ancestor a of v and w such that there exist divergent paths from a to v and to w. We shall call it the most recent common ancestor of v and w. When there is a path v w, we say that v is the most recent common ancestor of v and w.

A -trees
Let A be throughout this paper a fixed set of labels. In practice, we shall use the first capital letters, A, B,C . . ., as labels.

Definition 1. A semi-labeled tree over A is a tree with some of its nodes, including all its leaves and all its elementary nodes, injectively labeled in the set A .
To simplify several proofs, we shall usually allow the existence of unlabeled elementary nodes. This motivates the following definition.

Definition 2. An
A -tree is a tree with some of its nodes, including all its leaves, injectively labeled in the set A .
We shall always use the same name to denote an A -tree and the (unlabeled) tree that supports it. Furthermore, for every A -tree T , we shall use henceforth the following notations: -L (T ) and A (T ) will denote, respectively, the set of the labels of its leaves and the set of the labels of all its nodes. -For every v ∈ V (T ), we shall denote by A T (v) the set of the labels of all its descendants, including itself, and we shall call it, following [11], the cluster of v in T ; if T is irrelevant or clearly determined by the context, we shall usually write Notice that / 0 / ∈ C A (T ) unless T is empty. If T is a semi-labeled tree over A , then C A (T ) coincides with the cluster representation [11] of T , up to the trivial cluster for the root of T . Consequently, even for A -trees, we shall call C A (T ) the cluster representation of T .
-For every X ⊆ A (T ), we shall denote by v T,X the most recent common ancestor of the nodes of T with labels in X ; when T is irrelevant or clearly determined by the context, we shall usually write v X instead of v T,X . Moreover, when X is given by the list of its members between brackets, we shall usually omit these brackets in the subscript. So, in particular, for every A ∈ A (T ), we shall denote the node of T labeled A by v T,A or simply v A . Notice that A (v T,X ) = X if and only if X ∈ C A (T ).
We shall often use the following easy results, usually without any further mention.

Lemma 1.
Let T be an A -tree, and let x, y ∈ V (T ). If A (x)∩ A (y) = / 0, then x is a descendant of y or y is a descendant of x.
Proof. Let A ∈ A (x) ∩ A (y), so that there exist paths x v A and y v A , and let r be the root of T . Then, both x and y appear in the path r v A . This entails that either x appears in the path y v A or y appears in the path x v A , meaning that there is either a path from y to x or from x to y. Proof. By Lemma 1, if A (x) = A (y), there is either a path x y or a path y x. If the origin or some intermediate node in this path is labeled or if any one of these nodes has more children that those appearing in this path, then the set of labels will decrease from this node to its child in the path, and a fortiori from the origin to the end of the path.
In particular, in a semi-labeled tree over A , which does not contain any unlabeled elementary node, A (x) = A (y) if and only if x = y, and A (x) A (y) if and only if there exists a non-trivial path y x. This entails that the cluster representation C A (T ) of a semi-labeled tree T over A determines T up to isomorphism [11,Theorem 3.5.2]. Definition 3. The restriction T |X of an A -tree T to a set X ⊆ A of labels is the subtree of T supported on the set of nodes and where a node is labeled when it is labeled in T and this label belongs to X , in which case its label in T |X is the same as in T .
If X ∩ A (T ) = / 0, then T |X is the empty A -tree, while if X ∩ A (T ) = / 0, then T |X has the same root as T and leaves the nodes of T with labels in X that do not have any descendant with label in X . Now we introduce the notion of locally compatible A -trees as the absence of incompatible pairs and triples of labels.

Definition 4. Two
A -trees T 1 and T 2 are locally compatible when they satisfy the following two conditions: Any pair of labels A, B violating condition (C1) and any triple of labels A, B,C violating condition (C2) in a pair of trees T 1 and T 2 are said to be incompatible. Two A -trees T 1 and T 2 are locally incompatible when they are not locally compatible, that is, when they contain an incompatible pair or triple of labels.
So, if T 1 and T 2 represent phylogenetic trees with nested taxa, an incompatible pair of labels in T 1 and T 2 corresponds to a pair of taxa whose evolutive precedence is different in both trees, while an incompatible triple of labels in T 1 and T 2 corresponds to three taxa whose evolutive divergence is different in both trees.    Fig. 1 Indeed, since no two among v A , v B , v C are connected in T 1 by a path, condition (C1) implies that no two among the nodes in T 2 labeled A, B,C are connected by a path, either. Beside the structures shown in Fig. 1, only the structures T ′ 2 and T ′′ 2 shown in Fig. 2 satisfy this property. Now, T 1 contains a non-trivial path v A,C v A,B , while T ′ 2 contains a non-trivial path v A,B v A,C ; and T 1 contains a non-trivial path v B,C v A,B , while T ′′ 2 contains a non-trivial path v A,B v B,C . So, in both cases we find incompatible triples of labels. On the other hand, in the A -tree T 2 shown in Fig. 1, v A,B = v A,C = v B,C , and therefore this A -tree clearly satisfies condition (C2) with T 1 as far as the labels A, B,C go.  Indeed, in order to satisfy condition (C1), the existence in T 1 of paths v C v A , v C v B and the fact that v A and v B are not connected by a path in this A -tree, entail that T 2 also contains paths v C v A , v C v B and that v A and v B are not connected by a path either. Therefore, T 2 must either contain the same structure above , it is clear that in the last case the labels A, B,C do not form an incompatible triple in T 1 and T 2 . Fig. 4, then T 2 must contain the same Indeed, it is a simple consequence of the application of condition (C1). In the left-hand side structure, T 1 contains a path v B v A , and v B and v C are not connected by a path in it, and therefore the same must happen in T 2 and this leads to the same structure. And in the right-hand side structure, T 1 contains paths v C v B v A , and then the same must happen in T 2 , entailing again the same structure in this tree.
The following construction will be used henceforth several times. Fig. 4. These two A -trees are only locally compatible with themselves Notice that, by construction, every leaf of eachT i is labeled, and thereforeT 1 andT 2 are A -trees. Notice also that if A (T 1 ) = A (T 2 ), thenT 1 = T 1 andT 2 = T 2 . In general,

Definition 5. For every pair of A -trees T 1 and T 2 , let
Since local compatibility of two A -trees refers to labels appearing in both A -trees, we clearly have the following result.

Weak topological embeddings
Compatibility of phylogenetic trees is usually stated in terms of the existence of simultaneous embeddings of some kind into a common supertree. In this section we introduce the embeddings that will correspond to local compatibility.
First, recall from [10] the definition of ancestral displaying, which we already present translated into our notations.

Definition 6. An A -tree T ancestrally displays an A -tree S if the following properties hold:
We introduce now the following, more algebraic in flavour, definition of embedding that will turn out to be equivalent to ancestral displaying, up to the removal of elementary unlabeled nodes: cf. Proposition 1 below.

Definition 7.
A weak topological embedding of trees f : S → T is a mapping f : V (S) → V (T ) satisfying the following conditions: -It preserves and reflects paths: for every a, b ∈ V (S), there is a path from a to b in S if and only if there is a path from f (a) to f (b) in T .
When a weak topological embedding of A -trees f : S → T exists, we say that S is a weak A -subtree of T and that T is a weak A -supertree of S. Example 4. Let S and T be the A -trees described in Fig. 5, and let f : This mapping is injective, preserves labels and preserves paths, but it does not reflect paths: there is a path v T, Example 5. Let S and T the A -trees described in Fig. 6. Let f : V (S) → V (T ) be the mapping that sends the root r of S to the root r ′ of T , and every leaf of S to the leaf of T with the same label. This mapping is injective, preserves labels, and preserves and reflects paths. Therefore, it is a weak topological embedding f : Fig. 6. The A -trees in Example 5 Example 6. For every A -tree T and for every X ⊆ A (T ), the inclusion of the restriction T |X into T is a weak topological embedding.
We shall sometimes use this alternative formulation without any further mention.
The following lemmas will be used several times in the sequel.
is a direct consequence of the fact that f preserves labels and paths, while the converse inclusion is a direct consequence of the fact that f preserves labels and reflects paths.
As far as (ii) goes, let us prove first that This proves that f (V (S)) ⊆ V (T ′ ). And then it is straightforward to deduce that f : S → T ′ is injective, preserves labels, and that it preserves and reflects paths, from the corresponding properties for f : S → T . Now we can prove that, as we announced, weak topological embeddings capture ancestral displaying.

Proposition 1. Let S and T be two A -trees, and let S ′ be the semi-labeled tree obtained from S by removing the elementary unlabeled nodes in it and replacing by arcs the maximal paths with all their intermediate nodes elementary and unlabeled. Then, T ancestrally displays S if and only if there exists a weak topological embedding
Proof. Assume that T ancestrally displays S, and in particular that A (S) ⊆ A (T ) and C A (S) ⊆ C A (T |A (S)); to simplify the notations, we shall denote T |A (S) by T ′′ . Since elementary unlabeled nodes do not contribute any new member to the cluster representation, We define the mapping Let us check that this mapping defines a weak topological embedding f : S ′ → T ′′ .
-It is injective. Let v, w be two different nodes of S ′ . Since every node in S ′ is the most recent common ancestor of its labeled descendants, that is, because, by the second property of ancestral displaying, the labeled nodes in S ′ that are descendants of v are exactly the labeled nodes in T ′′ that are descendants of v T ′′ ,A , and therefore v T ′′ ,A is the least common ancestor of the nodes with labels in , as we claimed. -It preserves and reflects paths.
The implications ⇐ in the first equivalence and ⇒ in the last equivalence are given by Corollary 1, while the converse implication in both cases is entailed by the fact that v, w, f (v), and f (w) are most recent common ancestors of sets of labeled nodes, and then non-trivial paths between them imply strict inclusions of sets of labels of descendants.
So, we have a weak topological embedding f : S ′ → T ′′ , and since T ′′ is a weak A -subtree of T , it induces a weak topological embedding f : S ′ → T , as we wanted to prove.
Conversely, assume that we have a weak topological embedding f : S ′ → T . Then: Therefore, X ∈ C (T |A (S)), and, being X arbitrary, we conclude that C A (S) ⊆ C (T |A (S)).
This proves that T ancestrally displays S. Now, recall from [10] the notion of ancestral compatibility.

Definition 8. Two
A -trees T 1 , T 2 are ancestrally compatible when there exists an A -tree that ancestrally displays both of them. If two A -trees are not ancestrally compatible, we say that they are ancestrally incompatible.
Weak topological embeddings have been defined as they have so ancestral compatibility turns out to be exactly the same as 'compatibility for weak topological embeddings.' Assume that there exist weak topological embeddings f 1 : T 1 → T and f 2 : T 2 → T of T 1 and T 2 into a same A -tree T . Since each T ′ ℓ is a weak A -subtree of the corresponding T ℓ , each one of these weak topological embeddings induces a weak topological embedding f ′ ℓ : T ′ ℓ → T , showing that T ancestrally displays T 1 and T 2 .
Conversely, assume that there exist weak topological embeddings g 1 : T ′ 1 → T and g 2 : T ′ 2 → T of T ′ 1 and T ′ 2 into a same A -tree T . LetT be the A -tree obtained from T in the following way. For every arc (v, w) ∈ E(T ), if there exists an arc (v ℓ , w ℓ ) in one T ℓ such that g ℓ (v ℓ ) = v and g ℓ (w ℓ ) = w, we split the arc (v, w) in T into a path v w, with all its intermediate nodes elementary and unlabeled, of length equal to the length of the path v ℓ w ℓ ; if there are arcs (v 1 , w 1 ) ∈ E(T 1 ) and (v 2 , w 2 ) ∈ E(T 2 ) such that g 1 (v 1 ) = g 2 (v 2 ) = v and g 1 (w 1 ) = g 2 (w 2 ) = w, then we split the arc (v, w) in T into a path v w as before, but now of length the maximum of the lengths of the paths v 1 w 1 and v 2 w 2 . It is clear then that each g T : T → T 0 can be extended to a weak topological embeddingg T : T →T .
From now on, we shall use this characterization of ancestral compatibility as the working definition of it.
The main result of this paper will establish that ancestral compatibility is equivalent to local compatibility. To prove it, we shall need a preliminary result, Proposition 3, which establishes that ancestral compatibility of two A -trees can be checked at the level ofT 1 andT 2 , as it was also the case for local compatibility. Proof. Assume that T 1 and T 2 are ancestrally compatible. Then, sinceT 1 andT 2 are weak Asubtrees of T 1 and T 2 , respectively, it is clear that they are also ancestrally compatible; let f 1 :T 1 → T and f 2 :T 2 → T be weak topological embeddings. Recall that A (T 1 ) = A (T 2 ).
If A ∈ L (T 1 ), then AT 1 (vT 1 ,A ) = {A} and hence which says that vT 2 ,A is a leaf ofT 2 and thus A ∈ L (T 2 ). This proves that L (T 1 ) ⊆ L (T 2 ) and, by symmetry, the equality between these two sets. Proof. As we have seen in the proof of the last lemma, if T 1 and T 2 are ancestrally compatible, thenT 1 andT 2 are also so. Conversely, let f 1 :T 1 → T and f 2 :T 2 → T be two weak topological embeddings. By the last lemma, we know that L (T 1 ) = L (T 2 ). Recall, moreover, By Lemma 4, f 1 and f 2 induce weak topological embeddings into the restriction of T to A (T 1 ) = A (T 2 ). Therefore, by replacing T by this A -subtree if necessary, we shall assume without any loss of generality that L (T ) = L (T 1 ) = L (T 2 ). We shall also assume, again without any loss of generality, that A (T ) = A (T 1 ) = A (T 2 ): we simply remove from T the labels that do not belong to this set.
Finally, we shall assume that there does not exist any pair of different labels A 1 , A 2 such that v T 1 ,A 1 ∈ V (T 1 ) and v T 2 ,A 2 ∈ V (T 2 ) and f 1 (v T 1 ,A 1 ) = f 2 (v T 2 ,A 2 ). Indeed, assume that such a pair of labels exists. Then, to begin with, A 1 , A 2 / ∈ A (T 1 )∩A (T 2 ): if, say, A 2 ∈ A (T 1 )∩A (T 2 ) then, since f 1 and f 2 preserve labels, it happens that f 2 (v T 2 ,A 2 ) = f 1 (v T 1 ,A 2 ) and then v T 1 ,A 2 = v T 1 ,A 1 , that is, A 2 = A 1 . Therefore, v T 1 ,A 1 and v T 2 ,A 2 do not keep their labels inT 1 andT 2 . Now, given the node w = f 1 (v T 1 ,A 1 ) = f 2 (v T 2 ,A 2 ) (which, by what we have just discussed, will be unlabeled, either), we 'blow out' it by adding a new node w ′ , splitting the arc going from w's parent w 0 to w into two arcs (w 0 , w ′ ), (w ′ , w) -if w was the root of T , we simply add a new arc (w ′ , w)-and redefining f 1 by sending v T 1 ,A 1 to w ′ while we do not change f 2 (alternatively, we could have redefined f 2 , by sending v T 2 ,A 2 to w ′ , and left f 1 unchanged). It is straightforward to check that the new mapping f 1 obtained in this way and the 'old' f 2 are still weak topological embeddings from T 1 and T 2 to the new A -tree. After repeating this process as many times as necessary, and still calling T the target A -tree obtained at the end, we obtain weak topological embeddings f 1 :T 1 → T and f 2 :T 2 → T as we assumed at the beginning of this paragraph.
We shall expand this common weak A -supertree T ofT 1 andT 2 to a common weak Asupertree of T 1 and T 2 . To begin with, we expand T to an A -labeled graph T ′ by "adding T 1 −T 1 " to it. More specifically, to obtain T ′ , we add to T all nodes in V (T 1 ) −V (T 1 ), and arcs of two types: on the one hand, those between these nodes in T 1 , and on the other hand, for every arc (a, b) ∈ E(T 1 ) with a ∈ V (T 1 ) and b ∈ V (T 1 ) −V (T 1 ), an arc between f 1 (a) and b in T ′ . As far as the labels go, on the one hand the nodes of T ′ belonging to V (T 1 ) −V (T 1 ) inherit their labels, and on the other hand the nodes in T ′ that are images of nodes inT 1 labeled in A (T 1 ) − A (T 1 ), are labeled with this label. None of the labels we add in this way could be present in T , because otherwise they would have belonged to A (T 1 ), which is impossible, and no already labeled node in T receives a second label, because the nodes labeled in T received their labels fromT 1 .
This T ′ is clearly an A -tree, and has T as a weak A -subtree: actually, T = T ′ |L (T ). Therefore, it is a weak A -supertree ofT 2 . And it is also a weak A -supertree of T 1 . Indeed, consider the mapping f ′ 1 : as the original embedding f 1 : V (T 1 ) → V (T ) and on V (T 1 ) − V (T 1 ) as the identity. It is clearly injective and preserves labels. Moreover, it preserves paths, because f 1 sends arcs inT 1 to paths in T , and arcs outsidē T 1 become arcs in T ′ ; and it reflects paths, because it reflects paths in T and the arcs that have been added come from arcs in T 1 .
So, T ′ is a common weak A -supertree of T 1 andT 2 . Now, we expand T ′ to a new A -tree T ′′ by means of a similar process, but now "adding T 2 −T 2 " to it. We add to T ′ all nodes in V (T 2 ) −V (T 2 ), all arcs between these nodes in T 2 , an arc ( f 2 (a), b) for every arc (a, b) ∈ E(T 2 ) with a ∈ V (T 2 ) and b ∈ V (T 2 )−V (T 2 ). The new nodes, coming from V (T 2 )−V (T 2 ), are labeled as they were in T 2 , while the old ones receive their labels from T 2 , if any and necessary. No new label added in this way could be already present in T ′ . And no already labeled node receives a second label, because the images of f ′ 1 : T 1 → T ′ and f 2 :T 2 → T ′ are still disjoint except for the nodes with labels in A (T 1 ) ∩ A (T 2 ).
The A -labeled graph T ′′ obtained in this way is again an A -tree, and now it is a weak Asupertree of T 1 and of T 2 : the proof is similar to the previous one in the case of T ′ . Therefore, T 1 and T 2 are ancestrally compatible, as we wanted to prove.

Example 7.
Consider the semi-labeled trees T 1 and T 2 described in Fig. 7. The corresponding A -treesT 1 andT 2 , which are no longer semi-labeled trees, are described in Fig. 8; notice that the nodes c, h and i are no longer labeled in these trees.
The A -treesT 1 andT 2 are ancestrally compatible. A weak common A -supertree of them is given by the A -tree T described in Fig. 9, together with the weak topological embeddings f 1 :T 1 → T and f 2 :T 2 → T that are indicated by assigning in the picture to each non-labeled node in T its preimages under f 1 and f 2 . Notice that To avoid it, we blow up this node into an arc and we separate these two images: the corresponding new weak A -supertree T is described in Fig. 10. Now, the new weak topological embeddings f 1 and f 2 satisfy the assumptions in the proof of the last proposition.
The A -trees T ′ and T ′′ that are successively obtained by first 'adding T 1 −T 1 to T ' and then 'adding T 2 −T 2 to T ′ ' are described in Figs. 11 and 12, respectively. At the end, T ′′ is a weak common A -supertree of T 1 and T 2 under the embeddings indicated as before.  Fig. 8. The A -treesT 1 ,T 2 corresponding to the semi-labeled trees T 1 , T 2 in Fig. 7 Definition 9. Let T 1 and T 2 be two A -trees.
(a) Assume that A (T 1 ) = A (T 2 ). In this case, the join of T 1 and T 2 is the A -labeled graph T 1,2 defined as follows.
For every ℓ = 1, 2 and for every Y ∈ C A (T ℓ ), let . Then: -Its nodes are w Y, j with Y ∈ C and j = 1, . . . , n Y ,  Fig. 11. The A -tree T ′ obtained by 'adding T 1 −T 1 ' to T -Its arcs are: for some label A ∈ A , then the node w Y,1 is labeled with this A. In particular, the nodes w A,1 , with {A} any singleton in C , are labeled with the corresponding label A.  Fig. 12. The weak common A -supertree T ′′ of T 1 and T 2 obtained by 'adding T 2 −T 2 ' to T ′ Now, for every ℓ = 1, 2, we define a mapping f ℓ : , letT 1 andT 2 be the A -subtrees of T 1 and T 2 described in Definition 5. Then, the join T 1,2 of T 1 and T 2 is the result of applying the construction in the proof of Proposition 3 to the joinT 1,2 ofT 1 andT 2 (that is, first blowing out into arcs the nodes that are images of pairs of nodes labeled with different labels, next 'adding T 1 −T 1 ' to this A -tree, and finally 'adding T 2 −T 2 ' to the result), and the mappings f ℓ : V (T ℓ ) → V (T 1,2 ), ℓ = 1, 2, are obtained by extending the mappings f ℓ : V (T ℓ ) → V (T 1,2 ) also in the way described in that proof.
Notice that, by construction, the mappings f l : V (T l ) → V (T 1,2 ), l = 1, 2, are jointly surjective, that is, every node of T 1,2 belongs to the image of one or the other. (iii) C A (T 1 ) and C A (T 2 ) satisfy jointly the following two conditions: • For every A ∈ A (T 1 ) = A (T 2 ), the smallest member of C A (T 1 ) containing A is equal to the smallest member of C A (T 2 ) containing this label. • For every X ∈ C A (T 1 ) and Y ∈ C A (T 2 ), if X ∩Y = / 0, then X ⊆ Y or Y ⊆ X . (iv) The join T 1,2 of T 1 and T 2 is an A -tree and the mappings f 1 : V (T 1 ) → V (T 1,2 ) and f 2 : Proof. (i)=⇒(ii) Assume that T 1 and T 2 are ancestrally compatible, and let f 1 : T 1 → T and f 2 : T 2 → T be two weak topological embeddings. To prove that they are locally compatible, we shall show that they satisfy conditions (C1) and (C2).
(C1) Assume that T 1 contains a path v A v B . Since f 1 preserves this path, there exists a path v A v B in T , and then this path must be reflected by and assume that there is a non-trivial path z y; see Fig. 13. In particular, y cannot be an ancestor of v C : otherwise, it would be a common ancestor of v B and v C , which would entail a path from y to z that cannot exist. Moreover, Indeed, there are paths z v A , through y, and z v C , and therefore z is a common ancestor of v A and v C . Then, v T 1 ,A,C must be a node in the path z v A . Assume that it is an intermediate node of this path. If it is an intermediate node of the path z y, then it will be a common ancestor of v B , through y, and v C , and therefore z cannot be the most recent common ancestor of these two nodes. And if v T 1 ,A,C is a node of the path y v A , then y will be an ancestor of v C , something that, as we have seen above, cannot happen. Then, T contains paths f 1 (y) y ′ and f 1 (z) z ′ , and it turns out that there is a non-trivial path z ′ f 1 (y). Indeed, there are paths from z ′ and from f 1 (y) to v B , and therefore there must exist either a non-trivial path z ′ f 1 (y) or a path f 1 (y) z ′ ; but the latter cannot exist, because if it existed, then composing it with z ′ v C we would obtain a path f 1 (y) v C that, when reflected by f 1 , would entail a path y v C in T 1 that does not exist. In particular, there is a non-trivial path z ′ y ′ in T . Arguing as in T 1 , this implies that z ′ is also the most recent common ancestor of v A and v C in T . See Fig. 14 for a representation of the structure of T between f 1 (z) and v A , v B , v C .
Consider finally the A -tree T 2 , and set x = v T 2 ,B,C . Then, f 2 (x) will be a common ancestor of v B and v C in T and therefore there will be a path f 2 (x) z ′ . Composing this path with z ′ v A we obtain a path f 2 (x) v A which entails, since f 2 reflects paths, the existence of a path x v A . Therefore, x is also an ancestor of v A , and thus there exists a path x v T 2 ,A,B . But then, there cannot exist a non-trivial path v T 2 ,A,B x.
This finishes the proof that T 1 and T 2 satisfy condition (C2). .
if this path does not exist, then there must exist a path v T 1 ,A,B v T 1 ,B,C that will entail that C ∈ A (v T 1 ,A,B ).
In a similar way, we have that A / ∈ A (v T 2 ,B,C ) and this entails a path v T 2 ,A,B v T 2 ,B,C in T 2 . In all, if there exist X ∈ C A (T 1 ) and Y ∈ C A (T 2 ) such that X ∩Y = / 0, but X ⊆ Y and Y ⊆ X , then there exist three labels A, B,C ∈ A (T 1 ) ∩ A (T 2 ) and non-trivial paths v T 1 ,B,C v T 1 ,A,B in T 1 and v T 2 ,A,B v T 2 ,B,C in T 2 , which would contradict the assumption that T 1 and T 2 satisfy condition (C2).
(iii)=⇒(iv) Assume that T 1 and T 2 satisfy the conditions stated in point (iii). Notice that the first condition in (iii) entails that L (T 1 ) = L (T 2 ), because labels of leaves in an A -tree are characterized by the fact that the smallest member of the cluster representation containing the label is a singleton.
To simplify the notations, we shall denote the join of T 1 and T 2 by simply T . In this case, since A (T 1 ) = A (T 2 ), this join T is obtained using the construction given in Definition 9.(a). Let us check that it is an A -tree: • It is clear that its leaves are the nodes of the form w A,1 , and they are labeled.
-The nodes of T are injectively labeled: it is impossible the existence of two different sets of labels Y 1 ,Y 2 ∈ C such that because in this case Y 1 ∩ Y 2 = / 0 and therefore Y 1 Y 2 or Y 2 Y 1 , which would entail that one of them contains a member of C that already contains A.
As we shall see below, A (T ) = A (T 1 ) = A (T 2 ).
• It is a tree. To prove it, assume first that a node w Z, j has two parents. Then, by construction, it must happen that j = n Z and then the parents are nodes w Y 1 ,1 and w Y 2 ,1 with Y 1 ,Y 2 ∈ C , Y 1 = Y 2 , such that Z Y 1 , Z Y 2 and in both cases such that no other member of C lies strictly between Z and the corresponding Y i . But then Y 1 ∩ Y 2 = / 0 and therefore , by Lemma 1, and if each one of them belongs to a different cluster representation, by assumption. This forbids that both Y 1 and Y 2 are minimal over Z. Therefore, each w Z, j can have only one parent. Now, if X ,Y ∈ C and Y ⊆ X , there is a unique path w X,i w Y, j for every i = 1, . . . , n X and j = 1, . . . , n Y (if X = Y , then this happens for every 1 j i n X ). If X = Y , it is obvious by construction, and when Y X , if is a maximal chain of sets of labels between Y and X with Z 1 , . . . , Z k ∈ C , then this path is obtained as the composition of paths And this path is unique because every node has at most one parent. Then, since A (T 1 ) = A (T 2 ) ∈ C , because it is the cluster of the roots of both trees, every node w Y, j is a descendant of w A (T 1 ),1 , that is, w A (T 1 ),1 is the root of T .
This A -tree T satisfies the following properties that we shall use below: • A (w Y, j ) = Y , for every node w Y, j . This is easily proved by algebraic induction over the structure of T . If Y = {A} and j = 1, then w Y,1 is a leaf of T labeled A, while if Y = {A} and j > 1, then the only labeled descendant of w Y, j in T is the leaf w Y,1 . Thus, A (w A, j ) = {A} for every A ∈ L (A 1 ) = L (A 2 ) and j = 1, . . . , n A . Now assume that A (w Z, j ) = Z for every Z Y and j = 1, . . . , n Z , and let us prove it for Y and every j = 1, . . . , n Y . If j = 1, then the children of w Y,1 are the nodes w Z,n Z with Z Y and maximal with this property. And then, if w Y,1 is not labeled, (in the second equality we use that if Z Y , then there exists some maximal Z 0 Y such that Z ⊆ Z 0 , and then there exists a path w Z 0 ,1 w Z,1 that entails that A (w Z,1 ) ⊆ A (w Z 0 ,1 )), while, if w Y,1 is labeled, say with label A, then Finally, if j > 1, then there is a path w Y, j w Y,1 with the origin and all its intermediate nodes elementary and unlabeled, and therefore A (w Y, j ) = A (w Y,1 ) = Y . An application of Bio::Tree::Compatible is shown in Fig. 16. The input consists of two phylogenetic trees describing the evolution of angiosperms (plants that flower and form fruits with seeds), obtained from study S11x5x95c19c35c30 in the TreeBASE [4] Fig. 16. Two incompatible phylogenetic trees, obtained from study S11x5x95c19c35c30 in TreeBASE. The clusters shown with thick lines are incompatible.
Another application of Bio::Tree::Compatible is shown in Fig. 17. The input consists of two semi-labeled trees describing the evolution of Skinnera (a group of four Fuchsia species that grows spontaneously out of the American continent, in New Zealand and on Tahiti), obtained from study S11x4x95c21c16c44 in TreeBASE.
A third application of Bio::Tree::Compatible is shown in Fig. 18. The input consists of two semi-labeled trees describing the evolution of net-veined Lilliaflorae, obtained from study S2x4x96c17c14c22 in TreeBASE.  Fig. 18. Two incompatible semi-labeled trees, obtained from study S2x4x96c17c14c22 in Tree-BASE. The clusters shown with thick lines are incompatible.
Using the Bio::Tree::Compatible module, we have performed a systematic study of tree compatibility on TreeBASE, which currently contains 2,592 phylogenies with over 36,000 taxa among them. In this study, we have found 2,527 pairs of incompatible trees (like those shown in Figs. 16 to 18) from a total of 3,357,936 pairs of trees. The resulting ratio of 0.075% shows the high internal consistency among the phylogenies, and it complements previous largescale analyses of TreeBASE [7].

Conclusions
Phylogenetic tree compatibility is the most important concept underlying widely-used methods for assessing the agreement of different phylogenetic trees with overlapping taxa and combining them into common supertrees to reveal the tree of life. The study of the compatibility of phylogenetic trees with nested taxa, also known as semi-labeled trees, was asked for in [6], and the notion of ancestral compatibility was introduced in [3,10].
We have analyzed in detail the meaning of the ancestral compatibility of semi-labeled trees from the points of view of the local structure of the trees, of the existence of embeddings into a common supertree, and of the joint properties of their cluster representations. We have established the equivalence between ancestral compatibility and the absence of certain incompatible pairs and triples of labels in the trees under comparison, and have also proved the equivalence between ancestral compatibility and a certain property of the cluster representations of the trees.
Our analysis has lead to a very simple polynomial-time algorithm for testing ancestral compatibility, which we have implemented and is freely available for download from the BioPerl collection of Perl modules for computational biology. Future work includes extending the Bio::Tree::Compatible implementation into a Bio::Tree::Supertree module for building a common supertree of two compatible semi-labeled trees.