Home | About | Journals | Submit | Contact Us | Français |

**|**Algorithms Mol Biol**|**v.12; 2017**|**PMC5356459

Formats

Article sections

- Abstract
- Introduction
- Preliminaries
- The display graph
- Testing ancestral compatibility
- Implementation
- Discussion
- References

Authors

Related links

Algorithms Mol Biol. 2017; 12: 7.

Published online 2017 March 16. doi: 10.1186/s13015-017-0099-7

PMCID: PMC5356459

0000 0004 1936 7312grid.34421.30Department of Computer Science, Iowa State University, Atanasoff Hall, Ames, IA USA

Yun Deng, Email: ude.etatsai@gnednuy.

Received 2016 December 23; Accepted 2017 March 4.

Copyright © The Author(s) 2017

Semi-labeled trees generalize ordinary phylogenetic trees, allowing internal nodes to be labeled by higher-order taxa. Taxonomies are examples of semi-labeled trees. Suppose we are given collection 𝒫 of semi-labeled trees over various subsets of a set of taxa. The ancestral compatibility problem asks whether there is a semi-labeled tree that respects the clusterings and the ancestor/descendant relationships implied by the trees in 𝒫. The running time and space usage of the best previous algorithm for testing ancestral compatibility depend on the degrees of the nodes in the trees in 𝒫.

We give a algorithm for the ancestral compatibility problem that runs in *O*(*M*_{𝒫}log^{2}*M*_{𝒫}) time and uses *O*(*M*_{𝒫}) space, where *M*_{𝒫} is the total number of nodes and edges in the trees in 𝒫.

Taxonomies enable researchers to expand greatly the taxonomic coverage of their phylogenetic analyses. The running time of our method does not depend on the degrees of the nodes in the trees in 𝒫. This characteristic is important when taxonomies—which can have nodes of high degree—are used.

In the *tree compatibility problem*, we are given a collection 𝒫 = {𝒯_{1}, 𝒯_{2}, …, 𝒯_{k}} of rooted phylogenetic trees with partially overlapping taxon sets. 𝒫 is called a *profile* and the trees in 𝒫 are the *input trees*. The question is whether there exists a tree 𝒯 whose taxon set is the union of the taxon sets of the input trees, such that 𝒯 exhibits the clusterings implied by the input trees. That is, if two taxa are together in a subtree of some input tree, then they must also be together in some subtree of 𝒯. The tree compatibility problem has been studied for over three decades [1–4].

In the original version of the tree compatibility problem, only the leaves of the input trees are labeled. Here we study a generalization, called *ancestral compatibility*, in which taxa may be *nested*. That is, the internal nodes may also be labeled; these labels represent *higher-order taxa*, which are, in effect, sets of taxa. Thus, for example, an input tree may contain the taxon *Glycine max* (soybean) nested within a subtree whose root is labeled Fabaceae (the legumes), itself nested within an Angiosperm subtree. Note that leaves themselves may be labeled by higher-order taxa. The question now is whether there is a tree 𝒯 whose taxon set is the union of the taxon sets of the input trees, such that 𝒯 exhibits not only the clusterings among the taxa, but also the ancestor/descendant relationships among taxa in the input trees. Our main result is a *O*(*M*_{𝒫}log^{2}*M*_{𝒫}) algorithm for the compatibility problem for trees with nested taxa, where *M*_{𝒫} is the total number of nodes and edges in the trees in 𝒫.

The tree compatibility problem is a basic special case of the *supertree problem*. A supertree method is a way to synthesize a collection of phylogenetic trees with partially overlapping taxon sets into a single supertree that represents the information in the input trees. The supertree approach, proposed in the early 90s [5, 6], has been used successfully to build large-scale phylogenies [7].

The original supertree methods were limited to input trees where only the leaves are labeled. Page [8] was among the first to note the need to handle phylogenies where internal nodes are labeled, and taxa are nested. A major motivation is the desire to incorporate *taxonomies* as input trees in large-scale supertree analyses, as way to circumvent one of the obstacles to building comprehensive phylogenies: the limited taxonomic overlap among different phylogenetic studies [9]. Taxonomies group organisms according to a system of taxonomic rank (e.g., family, genus, and species); two examples are the NCBI taxonomy [10] and the Angiosperm taxonomy [11]. Taxonomies spanning a broad range of taxa provide structure and completeness that might be hard to obtain otherwise. A recent example of the utility of taxonomies is the Open Tree of Life, a draft phylogeny for over 2.3 million species [12].

Taxonomies are not, strictly speaking, phylogenies. In particular, their internal nodes and some of their leaves are labeled with higher-order taxa. Nevertheless, taxonomies have many of the same mathematical characteristics as phylogenies. Indeed, both phylogenies and taxonomies are *semi-labeled trees* [13, 14]. We will use this term throughout the rest of the paper to refer to trees with nested taxa.

The fastest previous algorithm for testing ancestral compatibility, based on earlier work by Daniel and Semple [15], is due to Berry and Semple [16]. Their algorithm runs in *O*(log^{2}*n* · *τ*_{𝒫}) time using *O*(*τ*_{𝒫}) space. Here, *n* is the number of distinct taxa in 𝒫 and ${\mathit{\tau}}_{\mathcal{P}}={\sum}_{i=1}^{k}{\sum}_{v\in I({\mathcal{T}}_{i})}d{(v)}^{2}$, where *I*(𝒯_{i}) is the set of internal nodes of 𝒯_{i}, for each *i* ∈ {1, …, *k*}, and *d*(*v*) is the degree of node *v*. While the algorithm is polynomial, its dependence on node degrees is problematic: semi-labeled trees can be highly unresolved (i.e., contain nodes of high degree), especially if they are taxonomies.

As stated earlier, our main result is an algorithm to test ancestral compatibility that runs in *O*(*M*_{𝒫}log^{2}*M*_{𝒫}) time, using *O*(*M*_{𝒫}) space. These bounds are independent of the degrees of the nodes of the input trees, a valuable characteristic for large datasets that include taxonomies. To achieve our result, we extend ideas from our recent algorithm for testing the compatibility of ordinary phylogenetic trees [2]. As in that algorithm, a central notion in the current paper is the *display graph* of profile 𝒫, denoted *H*_{𝒫}. This is the graph obtained from the disjoint union of the trees in 𝒫 by identifying nodes that have the same label (see the section titled "Testing ancestral compatibility"). The term “display graph” was introduced by Bryant and Lagergren [17], but similar ideas have been used elsewhere. In particular, the display graph is closely related to Berry and Semple’s *restricted descendancy graph* [16], a mixed graph whose directed edges correspond to the (undirected) edges of *H*_{𝒫} and whose undirected edges have no correspondence in *H*_{𝒫}. The second kind of edges are the major component of the *τ*_{𝒫} term in the time and space complexity of Berry and Semple’s algorithm. The absence of such edges makes *H*_{𝒫} significantly smaller than the restricted descendancy graph. Display graphs also bear some relation to *tree alignment graphs* [18].

Here, we exploit the display graph more extensively than in our previous work. Although the display graph of a collection of semi-labeled trees is more complex than that of a collection of ordinary phylogenies, we are able to extend several of the key ideas—notably, that of a semi-universal label—to the general setting of semi-labeled trees. As in [2], the implementation relies on a dynamic graph data structure, but it requires a more careful amortized analysis based on a weighing scheme.

This paper has five sections, in addition to this introduction. The section titled "Preliminaries" presents basic definitions regarding graphs, semi-labeled trees, and ancestral compatibility. The section titled "The display graph" introduces the display graph and discusses its properties. The section titled "Testing ancestral compatibility" presents BuildNT, our algorithm for testing ancestral compatibility. We first present the algorithm recursively, and then show how to transform it into an iterative algorithm, BuildNT_{N}, that is easier to implement. We also give an example of the execution of BuildNT_{N}. The "Implementation" section gives the implementation details for BuildNT_{N}. The "Discussion" section gives some concluding remarks.

For each positive integer *r*, [*r*] denotes the set {1, …, *r*}.

Let *G* be a graph. *V*(*G*) and *E*(*G*) denote the node and edge sets of *G*. The *degree* of a node *v* ∈ *V*(*G*) is the number of edges incident on *v*. A *tree* is an acyclic connected graph. In this paper, all trees are assumed to be rooted. For a tree *T*, *r*(*T*) denotes the root of *T*. Suppose *u*, *v* ∈ *V*(*T*). Then, *u* is an *ancestor* of *v* in *T*, denoted *u*≤_{T}*v*, if *u* lies on the path from *v* to *r*(*T*) in *T*. If *u*≤_{T}*v*, then *v* is a *descendant* of *u*. Node *u* is a *proper descendant* of *v* if *u* is a descendant of *v* and *v* ≠ *u*. If {*u*, *v*} ∈ *E*(*T*) and *u*≤_{T}*v*, then *u* is the *parent* of *v* and *v* is a *child* of *u*. If neither *u*≤_{T}*v* nor *v*≤_{T}*u* hold, then we write *u*‖_{T}*v* and say that *u* and *v* are *not comparable* in *T*.

A *semi-labeled tree* is a pair 𝒯 = (*T*, *ϕ*) where *T* is a tree and *ϕ* is a mapping from a set *L*(𝒯) to *V*(*T*) such that, for every node *v* ∈ *V*(*T*) of degree at most two, *v* ∈ *ϕ*(*L*(𝒯)). *L*(𝒯) is the *label set* of 𝒯 and *ϕ* is the *labeling function* of 𝒯.

For every node *v* ∈ *V*(*T*), *ϕ*^{-1}(*v*) denotes the (possibly empty) subset of *L*(𝒯) whose elements map into *v*; these elements as the *labels of*
*v* (thus, each label is a taxon). If *ϕ*^{-1}(*v*) ≠ ∅, then *v* is *labeled*; otherwise, *v* is *unlabeled*. Note that, by definition, every leaf in a semi-labeled tree is labeled. Further, any node, including the root, that has a single child must be labeled. Nodes with two or more children may be labeled or unlabeled. A semi-labeled tree 𝒯 = (*T*, *ϕ*) is *singularly labeled* if every node in *T* has at most one label; 𝒯 is *fully labeled* if every node in *T* is labeled.

Semi-labeled trees, also known as *X*
*-trees*, generalize ordinary phylogenetic trees, also known as *phylogenetic*
*X*
*-trees* [14]. An ordinary phylogenetic tree is a semi-labeled tree 𝒯 = (*T*, *ϕ*) where *r*(*T*) has degree at least two and *ϕ* is a bijection from *L*(𝒯) into leaf set of *T* (thus, internal nodes are not labeled).

Let 𝒯 = (*T*, *ϕ*) be a semi-labeled tree and let *ℓ* and *ℓ*^{′} be two labels in *L*(𝒯). If *ϕ*(*ℓ*)≤_{T}*ϕ*(*ℓ*^{′}), then we write *ℓ*≤_{𝒯}*ℓ*^{′}, and say that *ℓ*^{′} is a *descendant* of *ℓ* in 𝒯 and that *ℓ* is an *ancestor* of *ℓ*^{′}. We write *ℓ*<_{𝒯}*ℓ*^{′} if *ϕ*(*ℓ*^{′}) is a proper descendant of *ϕ*(*ℓ*). If *ϕ*(*ℓ*)‖_{T}*ϕ*(*ℓ*^{′}), then we write *ℓ*‖_{𝒯}*ℓ*^{′} and say that *ℓ* and *ℓ*^{′} are *not comparable* in 𝒯. If 𝒯 is fully labeled and *ϕ*(*ℓ*) is the parent of *ϕ*(*ℓ*^{′}) in *T*, then *ℓ* is the *parent* of *ℓ*^{′} in 𝒯 and *ℓ*^{′} is a *child* of *ℓ* in 𝒯; two labels with the same parent are *siblings*.

Two semi-labelled trees 𝒯 = (*T*, *ϕ*) and 𝒯^{′} = (*T*^{′}, *ϕ*^{′}) are *isomorphic* if there exists a bijection *ψ*:*V*(*T*) → *V*(*T*^{′}) such that *ϕ*^{′} = *ψ* ∘ *ϕ* and, for any two nodes *u*, *v* ∈ *V*(*T*), (*u*, *v*) ∈ *E*(*T*) if and only (*ψ*(*u*), *ψ*(*v*)) ∈ *E*(*T*^{′}).

Let 𝒯 = (*T*, *ϕ*) be a semi-labeled tree. For each *u* ∈ *V*(*T*), *X*(*u*) denotes the set of all labels in the subtree of *T* rooted at *u*; that is, *X*(*u*) = ⋃_{v:u≤Tv}*ϕ*^{-1}(*v*). *X*(*u*) is called a *cluster* of *T*. Cl(𝒯) denotes the set of all clusters of 𝒯. It is well known [14, Theorem 3.5.2] that a semi-labeled tree 𝒯 is completely determined by Cl(𝒯). That is, if Cl(𝒯) = Cl(𝒯^{′}) for some other semi-labeled tree 𝒯^{′}, then 𝒯 is isomorphic to 𝒯^{′}.

Suppose *A* ⊆ *L*(𝒯) for a semi-labeled tree 𝒯 = (*T*, *ϕ*). The *restriction* of 𝒯 to *A*, denoted 𝒯|*A*, is the semi-labeled tree whose cluster set is Cl(𝒯|*A*) = {*X* ∩ *A*:*X* ∈ Cl(𝒯) and *X* ∩ *A* ≠ ∅}. Intuitively, 𝒯|*A* is obtained from the minimal rooted subtree of *T* that connects the nodes in *ϕ*(*A*) by suppressing all vertices of degree two that are not in *ϕ*(*A*).

Let 𝒯 = (*T*, *ϕ*) and 𝒯^{′} = (*T*^{′}, *ϕ*^{′}) be semi-labeled trees such that *L*(𝒯^{′}) ⊆ *L*(𝒯). 𝒯
*ancestrally displays*
𝒯^{′} if Cl(𝒯^{′}) ⊆ Cl(𝒯|*L*(𝒯^{′})). Equivalently, 𝒯 ancestrally displays 𝒯^{′} if 𝒯^{′} can be obtained from 𝒯|*L*(𝒯^{′}) by contracting edges, and, for any *ℓ*_{1}, *ℓ*_{2} ∈ *L*(𝒯^{′}),

- (i)if
*ℓ*_{1}<_{𝒯′}*ℓ*_{2}, then*ℓ*_{1}<_{𝒯}*ℓ*_{2}, and - (ii)if
*ℓ*_{1}‖_{𝒯′}*ℓ*_{2}, then*ℓ*_{1}‖_{𝒯}*ℓ*_{2}.

The notion of “ancestrally displays” for semi-labeled trees generalizes the well-known notion of “displays” for ordinary phylogenetic trees [14].

For a semi-labelled tree 𝒯, let us define *D*(𝒯) and *N*(𝒯) as follows.

$$\begin{array}{cc}\hfill D(\mathcal{T})& =\{(\ell ,{\ell}^{\prime}):\ell ,{\ell}^{\prime}\in L(\mathcal{T})\phantom{\rule{0.333333em}{0ex}}\text{and}\phantom{\rule{0.333333em}{0ex}}\ell {<}_{\mathcal{T}}{\ell}^{\prime}\}\hfill \\ \hfill N(\mathcal{T})& =\{\{\ell ,{\ell}^{\prime}\}:\ell ,{\ell}^{\prime}\in L(\mathcal{T})\phantom{\rule{0.333333em}{0ex}}\text{and}\phantom{\rule{0.333333em}{0ex}}\ell {\Vert}_{\mathcal{T}}{\ell}^{\prime}\}\hfill \end{array}$$

Note that *D*(𝒯) consists of *ordered* pairs, while *N*(𝒯) consists of *unordered* pairs.

(Bordewich et al. [13])* Let*
𝒯
* and*
𝒯^{′}
* be semi-labelled trees such that*
*L*(𝒯^{′}) ⊆ *L*(𝒯).* Then*
𝒯
* ancestrally displays*
𝒯^{′}
* if and only if*
*D*(𝒯^{′}) ⊆ *D*(𝒯)
* and*
*N*(𝒯^{′}) ⊆ *N*(𝒯).

Throughout the rest of this paper 𝒫 = {𝒯_{1}, 𝒯_{2}, …, 𝒯_{k}} denotes a set where, for each *i* ∈ [*k*], 𝒯_{i} = (*T*_{i}, *ϕ*_{i}) is a semi-labeled tree. We refer to 𝒫 as a *profile*, and write *L*(𝒫) to denote ⋃_{i∈[k]}*L*(𝒯_{i}), the *label set* of 𝒫. Figure 1 shows a profile where *L*(𝒫) = {*a*, *b*, *c*, *d*, *e*, *f*, *g*, *h*, *i*}. We write *V*(𝒫) for ⋃_{i∈[k]}*V*(*T*_{i}) and *E*(𝒫) for ⋃_{i∈[k]}*E*(*T*_{i}), The *size* of 𝒫 is *M*_{𝒫} = |*V*(𝒫)| + |*E*(𝒫)|.

A profile 𝒫 = {𝒯_{1}, 𝒯_{2}, 𝒯_{3}}—trees are ordered left-to-right. The* letters* are the original labels;* grey numbers* are labels added to make the trees fully labeled

𝒫 is *ancestrally compatible* if there is a rooted semi-labeled tree 𝒯 that ancestrally displays each of the trees in 𝒫. If 𝒯 exists, we say that 𝒯
*ancestrally displays*
𝒫 (see Fig. Fig.22).

Given a subset *X* of *L*(𝒫), the *restriction* of 𝒫 to *X*, denoted 𝒫|*X*, is the profile defined as

𝒫|*X* = {𝒯_{1}|*X* ∩ *L*(𝒯_{1}), 𝒯_{2}|*X* ∩ *L*(𝒯_{2}), …, 𝒯_{k}|*X* ∩ *L*(𝒯_{k})}.

The proof of the following lemma is straightforward.

*Suppose*
𝒫
* is ancestrally compatible and let*
𝒯
* be a tree that ancestrally displays*
𝒫.* Then, for any*
*X* ⊆ *L*(𝒫), 𝒯|*X*
* ancestrally displays*
𝒫|*X*.

For technical reasons, fully labeled trees are easier to handle than those that are not. Suppose 𝒫 contains trees that are not fully labeled. We can convert 𝒫 into an equivalent profile 𝒫^{′} of fully-labeled trees as follows. For each *i* ∈ [*k*], let *l*_{i} be the number of unlabeled nodes in *T*_{i}. Create a set *L*^{′} of *n*^{′} = ∑_{i∈[k]}*l*_{i} labels such that *L*^{′} ∩ *L*(𝒫) = ∅. For each *i* ∈ [*k*] and each *v* ∈ *V*(*T*_{i}) such that ${\mathit{\varphi}}_{i}^{-1}(v)=\mathrm{\varnothing}$, make ${\mathit{\varphi}}_{i}^{-1}(v)=\{\ell \}$, where *ℓ* is a distinct element from *L*^{′}. We refer to 𝒫^{′} as the *profile obtained by adding distinct new labels to*
𝒫 (see Fig. Fig.11).

(Daniel and Semple [15])* Let*
𝒫^{′}
* be the profile obtained by adding distinct new labels to*
𝒫.* Then*, 𝒫
* is ancestrally compatible if and only if*
𝒫^{′}
* is ancestrally compatible. Further, if*
𝒯
* is a semi-labeled phylogenetic tree that ancestrally displays*
𝒫^{′},* then*
𝒯
* ancestrally displays*
𝒫.

From this point forward, we make the following assumption.

For each *i* ∈ [*k*], 𝒯_{i} is fully and singularly labeled.

By Lemma 3, no generality is lost in assuming that all trees in 𝒫 are fully labeled. The assumption that the trees are singularly labeled is inessential; it is only for clarity. Note that, even with the latter assumption, a tree that ancestrally displays 𝒫 is not necessarily singularly labeled. Figure Figure22 illustrates this fact.

The *display graph* of a profile 𝒫, denoted *H*_{𝒫}, is the graph obtained from the disjoint union of the underlying trees *T*_{1}, *T*_{2}, …, *T*_{k} by identifying nodes that have the same label. Multiple edges between the same pair of nodes are replaced by a single edge. See Fig. Fig.33.

*H*_{𝒫} has *O*(*M*_{𝒫}) nodes and edges, and can be constructed in *O*(*M*_{𝒫}) time. By Assumption 1, there is a bijection between the labels in *L*(𝒫) and the nodes of *H*_{𝒫}. Thus, from this point forward, we refer to the nodes of *H*_{𝒫} by their labels. It is easy to see that if *H*_{𝒫} is not connected, then 𝒫 decomposes into label-disjoint sub-profiles, and that 𝒫 is compatible if and only if each sub-profile is compatible. Thus, without loss of generality, we shall assume the following.

*H*_{𝒫} is connected.

Our compatibility algorithm processes the trees in 𝒫 from the top down, starting at the roots. We refer to the set of nodes in 𝒫 currently being considered as a “position”. The algorithm advances from the current position to the next by replacing certain nodes in the current position by their children. Formally, a *position* (for 𝒫) is a vector *U* = (*U*(1), *U*(2), …, *U*(*k*)), where *U*(*i*) ⊆ *L*(𝒯_{i}), for each *i* ∈ [*k*]. Since labels may be shared among trees, we may have *U*(*i*) ∩ *U*(*j*) ≠ ∅, for *i*, *j* ∈ [*k*] with *i* ≠ *j*. For each *i* ∈ [*k*], let Desc_{i}(*U*) = {*ℓ*:*ℓ*^{′}≤_{𝒯i}*ℓ*, for some *ℓ*^{′} ∈ *U*(*i*)}, and let Desc_{𝒫}(*U*) = ⋃_{i∈[k]}Desc_{i}(*U*).

A position *U* is *valid* if, for each *i* ∈ [*k*],

- if |
*U*(*i*)| ≥ 2, then the elements of*U*(*i*) are siblings in 𝒯_{i}and - Desc
_{i}(*U*) = Desc_{𝒫}(*U*) ∩*L*(𝒯_{i}).

*For any valid position*
*U*,

𝒫|Desc_{𝒫}(*U*) = {𝒯_{1}|Desc_{1}(*U*), 𝒯_{2}|Desc_{1}(*U*), …, 𝒯_{k}|Desc_{k}(*U*)}.

By (V2), we have that 𝒯_{i}|Desc_{i}(*U*) and 𝒯_{i}|Desc_{𝒫}(*U*) ∩ *L*(𝒯_{i}) are isomorphic, for each *i* ∈ [*k*]. The lemma then follows from the definition of 𝒫|Desc_{𝒫}(*U*). □

For any valid position *U*, *H*_{𝒫}(*U*) denotes the subgraph of *H*_{𝒫} induced by Desc_{𝒫}(*U*).

*For any valid position*
*U*, *H*_{𝒫}(*U*)
* is the subgraph of*
*H*_{𝒫}
* obtained by deleting all labels in*
*V*(*H*_{𝒫})\Desc_{𝒫}(*U*),* along with all incident edges*.

A valid position of special interest to us is *U*_{root}, the *root position*, defined as follows.

$$\begin{array}{c}\hfill {U}_{\mathrm{root}}=({\mathit{\varphi}}_{i}^{-1}(r({T}_{1})),{\mathit{\varphi}}_{i}^{-1}(r({T}_{2})),\dots ,{\mathit{\varphi}}_{i}^{-1}(r({T}_{k}))).\end{array}$$

1

That is, for each *i* ∈ [*k*], *U*_{root}(*i*) is a singleton containing only the label of *r*(*T*_{i}). In Fig. Fig.3,3, *U*_{root} = ({1}, {2}, {*g*}). It is straightforward to verify that *U*_{root} is indeed valid, that Desc_{𝒫}(*U*_{root}) = *L*(𝒫), and that *H*_{𝒫}(*U*_{root}) = *H*_{𝒫}.

Let *U* be a valid position, and let *ℓ* be a label in *U*. Then, *ℓ* is *semi-universal in*
*U* if *U*(*i*) = {*ℓ*}, for every *i* ∈ [*k*] such that *ℓ* ∈ *L*(𝒯_{i}). In Fig. Fig.3,3, labels 1 and 2 are semi-universal in *U*_{root}, but *g* is not, since *g* is in both *L*(𝒯_{2}) and *L*(𝒯_{3}), but *U*_{root}(2) ≠ {*g*}.

The term “semi-universal”, borrowed from Pe’er et al. [19], derives from the following fact. Suppose that 𝒫 is ancestrally compatible, that 𝒯 is a tree that ancestrally displays 𝒫, and that *ℓ* is a semi-universal label for some valid position *U*. Then, as we shall see, *ℓ* must label the root *u*_{ℓ} of a subtree of 𝒯 that contains all the descendants of *ℓ* in 𝒯_{i}, for every *i* such that *ℓ* ∈ *L*(𝒯_{i}). The qualifier “semi” is because this subtree may also contain labels that do not descend from *ℓ* in any input tree, but descend instead from some other semi-universal label *ℓ*^{′} in *U*. In this case, *ℓ*^{′} also labels *u*_{ℓ}. We exploit this property of semi-universal labels in our ancestral compatibility algorithm and its proof of correctness (see "Testing ancestral compatibility").

For each label *ℓ* ∈ *L*(𝒫), let *k*_{ℓ} denote the number of input trees that contain label *ℓ*. We can obtain *k*_{ℓ} for every *ℓ* ∈ *L*(𝒫) in *O*(*M*_{𝒫}) time during the construction of *H*_{𝒫}.

*Let*
*U* = (*U*(1), …, *U*(*k*))
* be a valid position*.* Then, label*
*ℓ*
* is semi-universal in*
*U*
* if the cardinality of the set*
*J*_{ℓ} = {*i* ∈ [*k*]:*U*(*i*) = {*ℓ*}}
* equals*
*k*_{ℓ}.

By definition, *U*(*i*) = {*ℓ*}, for every *i* ∈ *J*_{ℓ}. Since |*J*_{ℓ}| = *k*_{ℓ}, the lemma follows. □

For every *i* ∈ [*k*] and every *ℓ* ∈ *L*(𝒯_{i}), let Ch_{i}(*ℓ*) denote the set of children of *ℓ* in *L*(𝒯_{i}). For a subset *A* of *L*(𝒯_{i}), let Ch_{i}(*A*) = ⋃_{ℓ∈A}Ch_{i}(*ℓ*). Let *U* be a valid position, and *S* be the set of semi-universal labels in *U*. The *successor of*
*U*
*with respect to*
*S* is the position *U*^{′} = (*U*^{′}(1), *U*^{′}(2), …, *U*^{′}(*k*)), where, for each *i* ∈ [*k*], *U*^{′}(*i*) is defined as follows.

$$\begin{array}{c}\hfill {U}^{\prime}(i)=\left\{\begin{array}{cc}{\mathrm{Ch}}_{i}(\ell )\hfill & \text{if}\phantom{\rule{0.333333em}{0ex}}U(i)=\{\ell \},\phantom{\rule{0.333333em}{0ex}}\text{for some}\phantom{\rule{0.333333em}{0ex}}\ell \in S,\hfill \\ U(i)\hfill & \text{otherwise.}\hfill \end{array}\right.\end{array}$$

In Fig. Fig.3,3, the set of semi-universal labels in *U*_{root} is *S* = {1, 2}. Since Ch_{1}(1) = {3, *f*} and Ch_{2}(2) = {*e*, *f*, *g*}, the successor of *U*_{root} is ${U}_{\mathrm{root}}^{\prime}=(\{3,f\},\{e,f,g\},\{g\})$.

*Let U be a valid position, and let*
*U*^{′}
* be the successor of*
*U*
* with respect to the set*
*S*
* of semi-universal labels in*
*U*.* Then*, *H*_{𝒫}(*U*^{′})
* can be obtained from*
*H*_{𝒫}(*U*)
* by doing the following for each*
*ℓ* ∈ *S*:* (1) for each*
*i* ∈ [*k*]
* such that*
*U*(*i*) = {*ℓ*},* delete all edges between*
*ℓ*
* and*
Ch_{i}(*ℓ*);* (2) delete*
*ℓ*.

Let *U* be a valid position, and *W* be a subset of Desc_{𝒫}(*U*). Then, *U*|*W* denotes the position (*U*(1) ∩ *W*, *U*(2) ∩ *W*, …, *U*(*k*) ∩ *W*). In Fig. Fig.3,3, the components of *H*_{𝒫}(*U*^{′}), where *U*^{′} is the successor of *U*_{root}, are *W*_{1} = {3, 4, *a*, *b*, *c*, *d*, *e*, *g*} and *W*_{2} = {*f*, *h*, *i*}. Thus, *U*^{′}|*W*_{1} = ({3}, {*e*, *g*}, {*g*}) and *U*^{′}|*W*_{2} = ({*f*}, {*f*}, ∅). We have the following result.

*Let*
*U*
* be a valid position, and*
*S*
* be the set of all semi-universal labels in*
*U*.* Let*
*U*^{′}
* be the successor of*
*U*
* with respect to*
*S*,* and let*
*W*_{1}, *W*_{2}, …, *W*_{p}
* be the label sets of the connected components of*
*H*_{𝒫}(*U*^{′}).* Then,*
*U*^{′}|*W*_{j}
* is a valid position, for each*
*j* ∈ [*p*].

It suffices to argue that *U*^{′} satisfies conditions (V1) and (V2). The lemma then follows from the fact that the connected components of *H*_{𝒫}(*U*^{′}) are label-disjoint.

*U*^{′} must satisfy condition (V1), since *U* does. Suppose *ℓ* ∈ *S*. Then, for each *i* ∈ [*k*] such that *ℓ* ∈ *L*(𝒯_{i}), Desc_{i}(*U*^{′}) = Desc_{i}(*U*)\{*ℓ*} and Desc_{𝒫}(*U*^{′}) ∩ *L*(𝒯_{i}) = (Desc_{𝒫}(*U*) ∩ *L*(𝒯_{i}))\{*ℓ*}. Thus, since (V2) holds for *U*, it also holds for *U*^{′}. □

BuildNT (Algorithm 1) is our algorithm for testing compatibility of semi-labeled trees. Its argument, *U*, is a valid position in 𝒫 such that *H*_{𝒫}(*U*) is connected. BuildNT relies on the fact—proved later, in Theorem 1—that if 𝒫|Desc_{𝒫}(*U*) is compatible, then *U* must contain a nonempty set *S* of semi-universal labels. If such a set *S* exists, the algorithm replaces *U* by its successor *U*^{′} with respect to *S*. It then processes each connected component of *H*_{𝒫}(*U*^{′}) recursively, to determine if the associated sub-profile is compatible. If all the recursive calls are successful, then their results are combined into a supertree for 𝒫|Desc_{𝒫}(*U*).

In detail, BuildNT proceeds as follows. Line 1 computes the set *S* of semi-universal labels in *U*. If *S* is empty, then, 𝒫|Desc_{𝒫}(*U*) is incompatible, and, thus, so is 𝒫. This fact is reported in Line 3. Line 4 creates a tentative root *r*_{U}, labeled by *S*, for the tree 𝒯_{U} for *L*(*U*). Line 5 checks if *S* contains exactly one label *ℓ*, with no proper descendants. If so, by the connectivity assumption, *ℓ* must be the sole member of Desc_{𝒫}(*U*); that is, *L*(*U*) = *ℓ*. Therefore, Line 6 simply returns the tree with a single node, labeled by *S* = {*ℓ*}. Line 7 updates *U*, replacing it by its successor with respect to *S*. Let *W*_{1}, *W*_{2}, ⋯ , *W*_{p} be the connected components of *H*_{𝒫}(*U*) after updating *U*. By Lemma 6, *U*|*W*_{j} is a valid position, for each *j* ∈ [*p*]. Lines 8–12 recursively invoke BuildNT on *U*|*W*_{j} for each *j* ∈ [*p*], to determine if there is a tree *t*_{j} that ancestrally displays 𝒫|Desc_{𝒫}(*U* ∩ *W*_{j}). If any subproblem is incompatible, Line 12 reports that 𝒫 is incompatible. Otherwise, Line 13 returns the tree obtained by making the *t*_{j}s the subtrees of root *r*_{U}.

Next, we argue the correctness of BuildNT.

*Let*
*U*
* be a valid position in*
𝒫.* If*
BuildNT(*U*)
* returns a tree*
𝒯_{U},* then*
𝒯_{U}
* is a phylogenetic tree such that*
*L*(𝒯_{U}) = *L*(*U*).

We use induction on |*L*(*U*)|. The base case, where |*L*(*U*)| = 1, is handled by Lines 5–6. In this case, *S* = *L*(*U*) = {*ℓ*} and BuildNT(*U*) correctly returns the tree consisting of a single node, labeled by {*ℓ*}. Otherwise, let *W*_{1}, …, *W*_{p} be the connected components of *H*_{𝒫}(*U*) in step 8. Since BuildNT(*U*) returns tree 𝒯_{U}, it must be the case that, for each *j* ∈ [*p*], the result *t*_{j} returned by the recursive call to BuildNT(*U*|*W*_{j}) in Line 10 is a tree. Since |*S*| ≥ 1, we have |*L*(*W*_{j})| < |*L*(*U*)|, for each *j* ∈ [*p*]. Thus, we can assume inductively that *t*_{j} is a phylogenetic tree for *L*(*W*_{j}). Since *S* ∪ ⋃_{j∈[p]}*L*(*W*_{j}) = *L*(*U*), the tree returned in Line 13 is a phylogeny with species set *L*(*U*). □

*Let*
𝒫 = {𝒯_{1}, 𝒯_{2}, …, 𝒯_{k}}
* be a profile and let*
*U*_{root}
*be the root position, as defined in Eq. *(1). * Then,*
BuildNT(*U*_{root})
* returns either (i) a semi-labeled tree*
𝒯
* that ancestrally displays*
𝒫,* if*
𝒫
* is ancestrally compatible, or (ii)*
incompatible
* otherwise*.

BuildNT(*U*_{root}) either returns a tree or incompatible. We consider each case separately.

- (i)Suppose that BuildNT(
*U*_{root}) returns a semi-labeled tree 𝒯. By Lemma 7,*L*(𝒯) =*L*(𝒫). We prove that 𝒯 ancestrally displays 𝒫. By Lemma 1, it suffices to show that*D*(𝒯_{i}) ⊆*D*(𝒯) and*N*(𝒯_{i}) ⊆*N*(𝒯), for each*i*∈ [*k*]. Consider any (*ℓ*,*ℓ*^{′}) ∈*D*(𝒯_{i}). Then,*ℓ*has a child*ℓ*^{′′}in 𝒯_{i}such that*ℓ*^{′′}≤_{𝒯i}*ℓ*^{′}—note that we may have*ℓ*^{′′}=*ℓ*. There must be a recursive call to BuildNT(*U*), for some valid position*U*, where*ℓ*is the set*S*of semi-universal labels obtained in Line 1. By Observation 2, label*ℓ*^{′′}, and thus*ℓ*^{′}, both lie in one of the connected components of the graph obtained by deleting all labels in*S*, including*ℓ*, and their incident edges from*H*_{𝒫}(*U*). It now follows from the construction of 𝒯 that (*ℓ*,*ℓ*^{′}) ∈*D*(𝒯). Thus,*D*(𝒯_{i}) ⊆*D*(𝒯). Now, consider any {*ℓ*,*ℓ*^{′}} ∈*N*(𝒯_{i}). Let*v*be the lowest common ancestor of*ϕ*_{i}(*ℓ*) and*ϕ*_{i}(*ℓ*^{′}) in 𝒯_{i}and let*ℓ*_{v}be the label of*v*. Then,*ℓ*_{v}has a pair of children,*ℓ*_{1}and*ℓ*_{2}say, in 𝒯_{i}such that*ℓ*_{1}≤_{𝒯i}*ℓ*, and*ℓ*_{2}≤_{𝒯i}*ℓ*^{′}. Because BuildNT(*U*_{root}) returns a tree, there are recursive calls BuildNT(*U*_{1}) and BuildNT(*U*_{2}) for valid positions*U*_{1}and*U*_{2}such that*ℓ*_{1}is semi-universal for*U*_{1}and*ℓ*_{2}is semi-universal for*U*_{2}. We must have*U*_{1}≠*U*_{2}; otherwise, |*U*_{1}(*i*)| = |*U*_{2}(*i*)| ≥ 2, and, thus, neither*ℓ*_{1}nor*ℓ*_{2}is semi-universal, a contradiction. Further, it follows from the construction of 𝒯 that we must have Desc_{𝒫}(*U*_{1}) ∩ Desc_{𝒫}(*U*_{2}) = ∅. Hence,*ℓ*‖_{𝒯}*ℓ*^{′}, and, therefore, {*ℓ*,*ℓ*^{′}} ∈*N*(𝒯). - (ii)Asssume, by way of contradiction, that BuildNT(
*U*_{root}) returns*incompatible*, but that 𝒫 is ancestrally compatible. By assumption, there exists a semi-labeled tree 𝒯 that ancestrally displays 𝒫. Since BuildNT(*U*_{root}) returns*incompatible*, there is a recursive call to BuildNT(*U*) for some valid position*U*such that*U*has no semi-universal label, and the set*S*of Line 1 is empty. By Lemma 2, 𝒯|Desc_{𝒫}(*U*) ancestrally displays 𝒫|Desc_{𝒫}(*U*). Thus, by Lemma 4, 𝒯|Desc_{𝒫}(*U*) ancestrally displays 𝒯_{i}|Desc_{i}(*U*), for every*i*∈ [*k*]. Let*ℓ*be any label in the label set of the root of 𝒯|Desc_{𝒫}(*U*). Then, for each*i*∈ [*k*] such that*ℓ*∈*L*(𝒯_{i}),*ℓ*must be the label of the root of 𝒯_{i}|Desc_{i}(*U*). Thus, for each such*i*,*U*(*i*) = {*ℓ*}. Hence,*ℓ*is semi-universal in*U*, a contradiction.

□

We now present BuildNT_{N} (Algorithm 2), an iterative version of BuildNT, which lends itself naturally to an efficient implementation. BuildNT_{N} performs a breadth-first traversal of BuildNT’s recursion tree, using a first-in first-out queue *Q* that stores pairs of the form (*U*, pred), where *U* is a valid position in 𝒫 and pred is a reference to the parent of the node corresponding to *U* in the supertree built so far. BuildNT_{N} simulates recursive calls in BuildNT by enqueuing pairs corresponding to subproblems. We explain this in more detail next.

BuildNT_{N} initializes its queue to contain the starting position, *U*_{root}, with a null parent. It then proceeds to the* while* loop of Lines 3–14. Each iteration of the loop starts by dequeuing a valid position *U*, along with a reference pred to the potential parent for the subtree for *L*(*U*) in the supertree. The body of the loop closely follows the steps performed by a call to BuildNT(*U*). Line 5 computes the set *S* of semi-universal labels in *U*. If *S* is empty, the algorithm reports that 𝒫 is incompatible and terminates (Lines 6–7). The algorithm then creates a tentative root *r*_{U} labeled by *S* for the tree 𝒯_{U} for *L*(*U*), and links *r*_{U} to its parent (Line 8). If *S* consists of exactly one element that has no proper descendants, we skip the rest of the current iteration of the* while* loop, and* continue* to the next iteration (Lines 9–10). Line 11 replaces *U* by its successor with respect to *S*. Lines 13–14 enqueue each of *U*|*W*_{1}, *U*|*W*_{2}, …, *U*|*W*_{p}, along with *r*_{U}, for processing in a subsequent iteration. If the* while* loop terminates without any incompatibility being detected, the algorithm returns the tree with root *r*_{Uroot}.

Although the order in which BuildNT_{N} processes connected components differs from that of BuildNT —breadth-first instead of depth-first—, it is straightforward to see that the effect is equivalent, and the proof of correctness of BuildNT (Theorem 1) applies to BuildNT_{N} as well. We thus state the following without proof.

*Let*
𝒫 = {𝒯_{1}, 𝒯_{2}, …, 𝒯_{k}}
* be a profile. Then,*
BuildNT_{N}(𝒫)
* returns either (i) a semi-labeled tree*
𝒯
* that ancestrally displays*
𝒫,* if*
𝒫 i*s ancestrally compatible, or (ii)*
incompatible
* otherwise*.

Let *Q* be BuildNT_{N}’s first-in first-out queue. In the rest of the paper, we will say that a valid position *U*
*is in*
*Q* if (*U*, pred) ∈ *Q*, for some pred. Let *H*_{Q} be the subgraph of *H*_{𝒫} induced by ⋃ {Desc(*U*):*U* is in *Q*}. By Observation 1, *H*_{Q} is obtained from *H*_{𝒫} through edge and node deletions.

*At the start of any iteration of*
BuildNT_{N}’*s*
* while loop, the set of connected components of*
*H*_{Q}
* is*
{*V*(*H*_{𝒫}(*U*)):*U* is in *Q*}.

The property holds at the outset, since, by Assumption 2, *H*_{𝒫} = *H*_{𝒫}(*U*_{root}) is a connected graph, and the only element of *Q* is (*U*_{root}, null). Assume that the property holds at the beginning of iteration *l*. Let (*U*, pred) be the element dequeued from *Q* in Line 4. Then, *H*_{𝒫}(*U*) is connected. In place of (*U*, pred), Lines 13–14 enqueue (*U*|*W*_{j}, *r*_{U}), for each *j* ∈ [*p*], where, by construction, *H*_{𝒫}(*U*|*W*_{j}) is a connected component of *H*_{𝒫}(*U*). Thus, the property holds at the beginning of iteration *l* + 1. □

In other words, Lemma 8 states that each iteration of BuildNT_{N}(𝒫) deals with a subgraph of *H*_{𝒫}, whose connected components are in one-to-one correspondence with the valid positions stored in *Q*. This is illustrated by the next example.

Figures Figures4,4, ,5,5, ,6,6, ,77 and and88 illustrate the execution of BuildNT_{N} on the profile 𝒫 = (𝒯_{1}, 𝒯_{2}, 𝒯_{3}) of Fig. Fig.1.1. The figures show how the graph *H*_{Q} —initially equal to *H*_{𝒫} = *H*_{𝒫}(*U*_{root}) (Fig. (Fig.3)—evolves3)—evolves as its edges and nodes are deleted.

In each figure, *H*_{Q} is shown on the left and the current supertree is shown on the right. For brevity, the figures only exhibit the state of *H*_{Q} and the supertree after all the nodes at each level are generated. The various valid positions processed by BuildNT_{N}(𝒫) are denoted by *U*_{α}, for different subscripts *α*; *S*_{α} denotes the semi-universal labels in *U*_{α}, and ${U}_{\mathit{\alpha}}^{\prime}$ denotes the successor of *U*_{α} with respect to *S*_{α}. We write *L*_{α} as an abbreviation for *L*(*U*_{α}) The root of the tree for *L*_{α} is *r*_{Uα} and is labeled by *S*_{α}.

Initially, *Q* = ((*U*_{root}, null)). In what follows, the elements of *Q* are listed from front to rear.

*Level 0.* Refer to Fig. Fig.4.4. As seen earlier, the set of semi-universal labels of *U*_{root} is *S*_{root} = {1, 2}. Thus, ${H}_{\mathcal{P}}({U}_{\mathrm{root}}^{\prime})$ has two components *W*_{1} and *W*_{2}. Let ${U}_{1}={U}_{\mathrm{root}}^{\prime}|{W}_{1}$ and ${U}_{2}={U}_{\mathrm{root}}^{\prime}|{W}_{2}$. Then,

After level 0 is processed, *Q* = ((*U*_{1}, *r*_{Uroot}), (*U*_{2}, *r*_{Uroot})). Thus, the roots of the subtrees for *L*_{1} and *L*_{2} will be children of *r*_{Uroot}.

*Level 1.* Refer to Fig. Fig.5.5. We have *S*_{1} = {3}, so ${H}_{\mathcal{P}}({U}_{1}^{\prime})$ has two components *W*_{11} and *W*_{12}. Let ${U}_{11}={U}_{1}^{\prime}|{W}_{11}$ and ${U}_{12}={U}_{1}^{\prime}|{W}_{12}$. Then,

We have *S*_{2} = {*f*}, so ${H}_{\mathcal{P}}({U}_{2}^{\prime})$ has two components *W*_{21} and *W*_{22}. Let ${U}_{21}={U}_{2}^{\prime}|{W}_{21}$ and ${U}_{22}={U}_{2}^{\prime}|{W}_{22}$. Then,

After level 1 is processed, *Q* = ((*U*_{11}, *r*_{1}), (*U*_{12}, *r*_{1}), (*U*_{21}, *r*_{2}), (*U*_{22}, *r*_{2})).

*Level 2.* Refer to Fig. Fig.6.6. We have *S*_{11} = {*g*}, so ${H}_{\mathcal{P}}({U}_{11}^{\prime})$ has two components *W*_{111} and *W*_{112}. Let ${U}_{111}={U}_{11}^{\prime}|{W}_{111}$ and ${U}_{112}={U}_{11}^{\prime}|{W}_{112}$. Then,

The only semi-universal labels in *U*_{12}, *U*_{21}, and *U*_{22} are, respectively, *e*, *h*, and *i*. Since none of these labels have proper descendants, each of them is a leaf in the supertree.

After level 2 is processed, *Q* = ((*U*_{111}, *r*_{11}), (*U*_{112}, *r*_{11})).

*Level 3.* Refer to Fig. Fig.7.7. We have *S*_{111} = {4, *a*}, so ${H}_{\mathcal{P}}({U}_{111}^{\prime})$ has two components *W*_{1111} and *W*_{1112}. Let ${U}_{1111}={U}_{111}^{\prime}|{W}_{1111}$ and ${U}_{1112}={U}_{111}^{\prime}|{W}_{1112}$. Then,

The only semi-universal label in *U*_{112} is *d*. Since *d* has no proper descendants, it becomes a leaf in the supertree.

After level 3 is processed, *Q* = ((*U*_{1111}, *r*_{111}), (*U*_{1112}, *r*_{111})).

*Level 4.* Refer to Fig. Fig.8.8. The only semi-universal labels in *U*_{1111} and *U*_{1112} are, respectively, *b* and *c*. Since neither of these labels have proper descendants, each of them is a leaf in the supertree.

After level 4 is processed, *Q* is empty, and BuildNT_{N}(𝒫) terminates.

Here we prove the following result.

*There is an algorithm that, given a profile*
𝒫
* of rooted trees, runs in*
*O*(*M*_{𝒫}log^{2}*M*_{𝒫})
* time, and either returns a tree that displays*
𝒫,* if*
𝒫
* is compatible, or reports that is*
𝒫
* is incompatible otherwise*.

We prove this theorem by showing how to implement BuildNT_{N} so that the algorithm runs in *O*(*M*_{𝒫}log^{2}*M*_{𝒫}) on any profile 𝒫.

As in the section titled "An iterative version", let *H*_{Q} denote the subgraph of *H*_{𝒫} associated with the valid positions in BuildNT_{N}’s queue. By Lemma 8, each valid position *U* in *Q* corresponds to one connected component of *H*_{Q} —namely Desc(*U*) —and vice-versa. We use this fact in the implementation of BuildNT_{N}: alongside each valid position *U* in *Q*, we also store a reference to the respective connected component, together with additional information, described next, to quickly identify semi-universal labels.

Let *U* be any valid set in *Q*, let *Y* = *V*(*H*_{𝒫}(*U*)) be the corresponding connected component of *H*_{Q}, and let *ℓ* be any label in *Y*. Our implementation maintains the following data fields.

- Let
*J*_{U}= {*i*∈ [*k*]:*U*(*i*) ≠ ∅}. Then,*Y*.map is a map from*J*_{U}to*L*(*U*), where, for each*i*∈*J*_{U},*Y*.map(*i*) =*U*(*i*). - For each
*ℓ*∈*Y*,*ℓ*.count equals the cardinality of the set {*i*∈ [*k*]:*Y*.map(*i*) = {*ℓ*}}. (Recall that*k*_{ℓ}is the number of input trees that contain*ℓ*.). *Y*.exposed, a set consisting of all*i*∈ [*k*] such that*Y*.map(*i*) = {*ℓ*} for some*ℓ*∈*Y*such that*ℓ*.count =*k*_{ℓ}.*Y*.weight, which equals ∑_{ℓ∈Y}*k*_{ℓ}. This field is needed for technical reasons, to be explained later.

For the purpose of analysis, we assume that the exposed fields are represented as balanced binary search trees (BSTs), which ensures *O*(log*k*) = *O*(log*M*_{𝒫}) time per access and update. The map fields are also implemented using BSTs. We store the set *J*_{U} = {*i* ∈ [*k*]:*U*(*i*) ≠ ∅} as a BST, enabling is to determine in *O*(log*k*) time if an index *i* is in *J*_{U}, and, if this is the case, to access *Y*.map(*i*). The latter is also stored as a BST, allowing us to search and update *Y*.map(*i*) in *O*(log|*U*(*i*)|) = *O*(log*M*_{𝒫}) time. Note that, in practice, hashing may be a better alternative for both exposed and map fields, as it offers expected constant time performance per operation.

The data fields listed above allow us to efficiently retrieve the set *S* of semi-universal labels in *U*, as needed in line 5 of BuildNT_{N}(𝒫). Indeed, suppose that *U* is the valid position extracted from *Q* at the beginning of an iteration of the* while* loop of Lines 3–14, and that *Y* = *V*(*H*_{𝒫}(*U*)). Then, by Lemma 5, we have *S* = {*v* ∈ *Y*.map(*i*):*i* ∈ *Y*.exposed}. What remains is to devise an efficient way to update these fields for each of the connected components of *H*_{𝒫}(*U*) created by replacing *U* with its successor in Line 11.

Let *U*^{′} be the value of *U* after Line 11; thus, *U*^{′} is the successor of *U*. By Observation 2, *H*_{𝒫}(*U*^{′}) is obtained from *H*_{𝒫}(*U*) through edge and node deletions. We need to

- Generate the new connected components resulting from these deletions, and
- Produce the required map, count, and exposed data fields for the various connected components.

We accomplish (a) using the dynamic graph connectivity data structure of Holm et al. [20], which we refer to as *HDT*. HDT allows us to maintain the list of nodes in each component, as well as the number of these nodes so that, if we start with no edges in a graph with *N* nodes, the amortized cost of each update is *O*(log^{2}*N*). Since *H*_{𝒫} has *O*(*M*_{𝒫}) nodes, each update takes *O*(log^{2}*M*_{𝒫}) time. The total number of edge and node deletions performed by BuildNT_{N}(𝒫) —including all deletions in the interations—is at most the total number of edges and nodes in *H*_{𝒫}, which is *O*(*M*_{𝒫}). HDT allows us to maintain connectivity information throughout the entire algorithm in *O*(*M*_{𝒫}log^{2}*M*_{𝒫}) time, which is within the time bound claimed in Theorem 3.

For part (b), we need to augment HDT in order to maintain the the required data fields for the various connected components created during edge and node deletion. In the next subsections, we describe how to do this. We begin by explaining how to initialize all the required data fields for *H*_{𝒫} = *H*_{𝒫}(*U*_{root}).

Graph *H*_{𝒫}(*U*_{root}) has a single connected component, *Y*_{root} = *L*(𝒫), which is the entire vertex set of the graph. We initialize the data fields as follows.

- For each
*i*∈ [*k*],*Y*_{root}.map(*i*) = {*r*(*T*_{i})}. This takes*O*(*k*) time. *Y*_{root}.weight = ∑_{ℓ∈L(𝒫)}*k*_{ℓ}. This takes*O*(*M*_{𝒫}) time.

We initialize the count fields in *O*(*M*_{𝒫}) time as follows:

- Set
*ℓ*.count to 0 for all*ℓ*∈*L*(𝒫). - For each
*i*∈ [*k*], do the following.- Let
*ρ*_{i}denote the label of*r*(*T*_{i}). - Increment
*ρ*_{i}.count by one.

Once the count fields are initialized, it is easy to initialize *Y*_{root}.exposed in *O*(*k*) time. Thus, we can initialize all the required fields in *O*(*M*_{𝒫}) time.

Suppose that all data fields fields are correctly computed for every connected component that is in *Q* at the beginning of an iteration of the* while* loop in 3–14 of BuildNT_{N}. We now show how to generate the same fields efficiently for the new connected components created by Line 11.

Let *U* be the valid position extracted from *Q* at the beginning of an iteration of BuildNT_{N}’s* while* loop, and let *Y* = *V*(Desc(*U*)) be the associated connected component. Assume all the data fields for *Y* have been correctly computed. To obtain the successor of *U* in Line 11 of BuildNT_{N}, we perform the following steps.

- Identify the set
*S*of semi-universal labels in*U*. As we saw, this set is given by*S*= {*ℓ*∈*Y*.map(*i*):*i*∈*Y*.exposed}. - Set
*Y*.map(*i*) = ∅, for every*i*∈*Y*.exposed. - Make
*Y*.exposed = ∅. - For each
*ℓ*∈*S*and each*i*such that*ℓ*∈*L*(*T*_{i}), do the following.- If Ch
_{i}(*ℓ*) ≠ ∅, replace*Y*.map(*i*) by Ch_{i}(*ℓ*). If Ch_{i}(*ℓ*) is a singleton set {*α*}, increment*α*.count by one. If*α*.count =*k*_{ℓ}, add*i*to*Y*.exposed. - Otherwise,
*Y*.map(*i*) is undefined.

- For each label
*ℓ*in*S*, delete the edges incident on*ℓ*and then*ℓ*itself, updating the data fields as necessary after each deletion.

The total number of operations on map and exposed fields in Steps 1–4 is *O*(∑_{ℓ∈S}*k*_{ℓ}). Since each label becomes semi-universal at most once, the total number of operations on map fields over the entire execution of BuildNT_{N}(𝒫) is *O*(∑_{ℓ∈L(𝒫)}*k*_{ℓ}), which is *O*(*M*_{𝒫}). The same bound holds for updates to count and exposed fields.

Next let us focus on how to handle the deletion of a single edge in Step 5.

To delete an edge between *ℓ* and a child *α* of *ℓ*, we proceed as follows.

- Delete (
*ℓ*,*α*), querying HDT to determine whether this disconnects*Y*.- If
*Y*remains connected, skip the next steps and proceed directly to the next child of*ℓ*. - Otherwise,
*Y*is split into two components,*Y*_{1}and*Y*_{2}.

- Update
*Y*_{1}.weight and*Y*_{2}.weight. - Identify which of
*Y*_{1}and*Y*_{2}has the smaller weight field. Without loss of generality, assume that*Y*_{1}.weight ≤*Y*_{2}.weight. - Initialize
*Y*_{1}.map and*Y*_{1}.exposed to null. - Initialize
*Y*_{2}.map and*Y*_{2}.exposed to*Y*.map and*Y*.exposed, respectively. - For each label
*β*in*Y*_{1}, perform the following steps for each*i*such that*β*∈*L*(𝒯_{i}).- Delete
*β*from*Y*_{2}.map(*i*) and add*β*to*Y*_{1}.map(*i*). - Adjust count and exposed fields as necessary.

The connectivity test in Step 1 is done by querying HDT. Steps 3–5 are trivial. We thus focus on Steps 2 and 6.

To perform Step 2, we use the well-known technique of scanning the smaller component [21]. We first consult HDT to determine which of *Y*_{1} or *Y*_{2} has fewer nodes. Assume, without loss of generality, that |*Y*_{1}| ≤ |*Y*_{2}|. We initialize *Y*_{1}.weight to 0 and *Y*_{2}.weight to *Y*.weight. We then scan the labels of *Y*_{1}, incrementing *Y*_{1}.weight by *k*_{ℓ} for each label *ℓ* ∈ *Y*_{1}. When the scan of *Y*_{1} is complete, we make *Y*_{2}.weight = *Y*_{2}.weight - *Y*_{1}.weight. We claim that any label *ℓ* ∈ *L*(𝒫) is scanned *O*(log*M*_{𝒫}) times over the entire execution of BuildNT_{N}(𝒫). To verify this, let *N*(*ℓ*) be the number of nodes in the connected component containing *ℓ*. Suppose that, initially, *N*(*ℓ*) = *N*. Then, the *r*th time we scan *ℓ*, *N*(*ℓ*) ≤ *N*/2^{r}. Thus, *ℓ* is scanned *O*(log*N*) times. The claim follows, since *N* = *O*(*M*_{𝒫}). Therefore, the total number of updates over all labels is *O*(*M*_{𝒫}log*M*_{𝒫}).

Each execution of Step 6(a) updates each of *Y*_{1}.map(*i*) and *Y*_{2}.map(*i*) once. Step 6(b) is more complex, but can also be accomplished with *O*(1) data field updates. We omit the (tedious) details. In summary, each execution of step 6 for some *β* ∈ *L*(𝒫) performs *O*(*k*_{β}) data field updates.

Let us track the number of data field updates in Step 6 that can be attributed to some specific label *β* ∈ *L*(*P*) over the entire execution of BuildNT_{N}(𝒫). Let *w*_{r}(*β*) be the weight of the connected component containing *β* at the beginning of Step 6, on the *r*th time that *β* is considered in that step. Thus, *w*_{0}(*β*) ≤ ∑_{ℓ∈L(𝒫)}*k*_{ℓ}. We claim that *w*_{r}(*β*) ≤ *w*_{0}(*β*)/2^{r}. The reason is that we only consider *β* if (a) *β* is contained in one of the two components that result from deleting an edge in step 1 and (b) the component containing *β* has the smaller weight. Hence, the number of times *β* is considered in step 6 over the entire execution of BuildNT_{N}(𝒫) is *O*(log*w*_{0}(*β*)), which is *O*(log*M*_{𝒫}), since *w*_{0}(*β*) = *O*(*M*_{𝒫}). Therefore, the total number of data field updates in Step 6, over all labels in *L*(𝒫) considered throughout the entire execution of BuildNT_{N}(𝒫), is *O*(log*M*_{𝒫} · ∑_{ℓ∈L(𝒫)}*k*_{ℓ}), which is *O*(*M*_{𝒫}log*M*_{𝒫}).

Let us review the running times of each aspect of our implementation of BuildNT_{N}.

*Initializing the data structures*. This has two parts.*Setting up the HDT data structure for**H*_{𝒫}. This takes*O*(*M*_{𝒫}log^{2}*M*_{𝒫}) time.*Initializing the data fields for the single connected component of**H*_{𝒫}. This takes*O*(*M*_{𝒫}) time.

*Maintaining the data structures*. This also has two parts.*Updating the HDT data structure*. There are*O*(*M*_{𝒫}) edge and node deletions, at an amortized cost of*O*(log^{2}*M*_{𝒫}) per deletion, yielding a total time of*O*(*M*_{𝒫}log^{2}*M*_{𝒫}).*Maintaining the relevant data fields for the connected components.*We have seen that the total number of updates is*O*(*M*_{𝒫}log*M*_{𝒫}). Assume, conservatively, that each update can be done in*O*(log*M*_{𝒫}) time. Then, this part takes a total of*O*(*M*_{𝒫}log^{2}*M*_{𝒫}) over the entire execution of BuildNT_{N}.

We conclude that the total running time of BuildNT_{N}(𝒫) is *O*(*M*_{𝒫}log^{2}*M*_{𝒫}), completing the proof of Theorem 3.

Like our earlier algorithm for compatibility of ordinary phylogenetic trees, the more general algorithm presented here, BuildNT_{N}, is a polylogarithmic factor away from optimality (a trivial lower bound is Ω(*M*_{𝒫}), the time to read the input). BuildNT_{N} has a linear-space implementation, using the results of Thorup [22]. A question to be investigated next is the performance of the algorithm on real data. Another important issue is integrating our algorithm into a synthesis method that deals with incompatible profiles.

Algorithms and proofs were developed jointly by YD and DFB. The first draft of the paper was written by DFB, with substantial contributions from YD. YD and DFB both proofread the manuscript. Both authors read and approved the final manuscript.

The authors were supported in part by the National Science Foundation under Grant CCF-1422134.

The authors declare that they have no competing interests.

Yun Deng and David Fernández-Baca contributed equally

Yun Deng, Email: ude.etatsai@gnednuy.

David Fernández-Baca, Email: ude.etatsai@ednanref.

1. Aho AV, Sagiv Y, Szymanski TG, Ullman JD. Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM J Comput. 1981;10(3):405–421. doi: 10.1137/0210030. [Cross Ref]

2. Deng Y, Fernández-Baca D. Fast compatibility testing for rooted phylogenetic trees. In: Grossi R, Lewenstein M (editors) 27th annual symposium on combinatorial pattern matching (CPM 2016). Leibniz International Proceedings in Informatics. Schloss Dagstuhl—Leibniz-Zentrum für Informatik. Dagstuhl Publishing; 2016. p. 12. doi:10.4230/LIPIcs.CPM.2016.12.

3. Henzinger MR, King V, Warnow T. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica. 1999;24:1–13. doi: 10.1007/PL00009268. [Cross Ref]

4. Steel MA. The complexity of reconstructing trees from qualitative characters and subtrees. J Classif. 1992;9:91–116. doi: 10.1007/BF02618470. [Cross Ref]

5. Baum BR. Combining trees as a way of combining data sets for phylogenetic inference, and the desirability of combining gene trees. Taxon. 1992;41:3–10. doi: 10.2307/1222480. [Cross Ref]

6. Ragan MA. Phylogenetic inference based on matrix representation of trees. Mol Phylogenet Evol. 1992;1:53–58. doi: 10.1016/1055-7903(92)90035-F. [PubMed] [Cross Ref]

7. Bininda-Emonds ORP, Cardillo M, Jones KE, MacPhee RDE, Beck RMD, Grenyer R, Price SA, Vos RA, Gittleman JL, Purvis A. The delayed rise of present-day mammals. Nature. 2007;446:507–512. doi: 10.1038/nature05634. [PubMed] [Cross Ref]

8. Page RM. Taxonomy, supertrees, and the tree of life. In: Bininda-Emonds ORP, editor. Phylogenetic supertrees: combining information to reveal the tree of life. Dordrecht: Kluwer; 2004. pp. 247–265.

9. Sanderson MJ. Phylogenetic signal in the eukaryotic tree of life. Science. 2008;321(5885):121–123. doi: 10.1126/science.1154449. [PubMed] [Cross Ref]

10. Sayers EW, et al. Database resources of the national center for biotechnology information. Nucl Acids Res. 2009;37(Database issue):5–15. doi: 10.1093/nar/gkn741. [PMC free article] [PubMed] [Cross Ref]

11. The Angiosperm Phylogeny Group et al. An update of the Angiosperm Phylogeny Group classification for the orders and families of flowering plants: APG IV. Bot J Linn Soc. 2016;181:1–20. doi: 10.1111/boj.12385. [Cross Ref]

12. Hinchliff CE, Smith SA, Allman JF, Burleigh JG, Chaudhary R, Coghill LM, Crandall KA, Deng J, Drew BT, Gazis R, Gude K, Hibbett DS, Katz LA, Laughinghouse HD, IV, McTavish EJ, Midford PE, Owen CL, Reed RH, Reesk JA, Soltis DE, Williams T, Cranston KA. Synthesis of phylogeny and taxonomy into a comprehensive tree of life. Proc Natl Acad Sci. 2015;112(41):12764–12769. doi: 10.1073/pnas.1423041112. [PubMed] [Cross Ref]

13. Bordewich M, Evans G, Semple C. Extending the limits of supertree methods. Ann Comb. 2006;10:31–51. doi: 10.1007/s00026-006-0272-z. [Cross Ref]

14. Semple C, Steel M. Phylogenetics. Oxford lecture series in mathematics. Oxford: Oxford University Press; 2003.

15. Daniel P, Semple C. Supertree algorithms for nested taxa. In: Bininda-Emonds ORP, editor. Phylogenetic supertrees: combining information to reveal the tree of life. Dordrecht: Kluwer; 2004. pp. 151–171.

16. Berry V, Semple C. Fast computation of supertrees for compatible phylogenies with nested taxa. Syst Biol. 2006;55(2):270–288. doi: 10.1080/10635150500541649. [PubMed] [Cross Ref]

17. Bryant D, Lagergren J. Compatibility of unrooted phylogenetic trees is FPT. Theor Comput Sci. 2006;351:296–302. doi: 10.1016/j.tcs.2005.10.033. [Cross Ref]

18. Smith SA, Brown JW, Hinchliff CE. Analyzing and synthesizing phylogenies using tree alignment graphs. PLoS Comput Biol. 2013;9(9):1003223. doi: 10.1371/journal.pcbi.1003223. [PMC free article] [PubMed] [Cross Ref]

19. Pe’er I, Pupko T, Shamir R, Sharan R. Incomplete directed perfect phylogeny. SIAM J Comput. 2004;33(3):590–607. doi: 10.1137/S0097539702406510. [Cross Ref]

20. Holm J, de Lichtenberg K, Thorup M. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J ACM. 2001;48(4):723–760. doi: 10.1145/502090.502095. [Cross Ref]

21. Even S, Shiloach Y. An on-line edge-deletion problem. J ACM. 1981;28(1):1–4. doi: 10.1145/322234.322235. [Cross Ref]

22. Thorup M. Near-optimal fully-dynamic graph connectivity. In: Proceedings of the 32nd annual ACM symposium on theory of computing. ACM; 2000. p. 343–350.

Articles from Algorithms for Molecular Biology : AMB are provided here courtesy of **BioMed Central**

PubMed Central Canada is a service of the Canadian Institutes of Health Research (CIHR) working in partnership with the National Research Council's national science library in cooperation with the National Center for Biotechnology Information at the U.S. National Library of Medicine(NCBI/NLM). It includes content provided to the PubMed Central International archive by participating publishers. |