An Algorithm for Consensus Trees

We consider the tree consensus problem, an important problem in bioinformatics. Given a rooted tree $t$ and another tree $T$, one would like to incorporate compatible information from $T$ to $t$. This problem is a subproblem in the tree refinement problem called the RF-Optimal Tree Refinement Problem defined by in Christensen, Molloy, Vachaspati and Warnow [WABI'19] who employ the greedy algorithm by Gawrychowski, Landau, Sung, and Weimann [ICALP'18] that runs in time $O(n^{1.5}\log n)$. We give a faster algorithm for this problem that runs in time $O(n\log n)$. Our key ingredient is a bipartition compatibility criteria based on amortized-time leaf counters. While this is an improvement, the fastest solution is an algorithm by Jansson, Shen, and Sung [JACM'16] which runs in time $O(n)$.


Introduction
We consider the tree consensus problem, an important problem in bioinformatics. Given a rooted tree t and another rooted tree T , we would like to combine "information" from T into t. More over, we would like to only greedily take information that is currently consistent with our current t. (See definitions below.) This problem is a subproblem in the tree refinement problem called RF-Optimal Tree Refinement Problem defined by in Christensen, Molloy, Vachaspati and Warnow [1] who employ the greedy algorithm by Gawrychowski, Landau, Sung, and Weimann [2] that runs in time O(n 1.5 log n). We give a faster algorithm for this problem that runs in time O(n log n). Our key ingredient is a bipartition compatibility criteria based on amortizedtime leaf counters. While this is an improvement, the fastest solution is an algorithm by Jansson, Shen, and Sung [3] which runs in time O(n).
The algorithm by Gawrychowski et al [2] works in a more general case where the goal is the find the greedy consensus trees from k trees. In this case, their algorithm runs in time O(kn 1.5 log n), an improvement over O(kn 2 ) of Jansson et al [3]. For this problem, Sung [4] also present an algorithm that runs in time O(k 2 n), improving over Gawrychowski et al [2] when k = O( √ n log n). In an earlier version, we erroneously claimed that our algorithm works for the case with many trees. We thank Pawel Gawrychowski and Oren Weiman for pointing this out. Jittat Fakcharoenphol who help advising the author on this manuscript would like to take the full responsibility for this mistake.

Definitions
We start with definitions related to trees and consistency.
Let V (T ), E(T ) and R(T ) be vertex set, edge set and the root of tree T . For every vertex u ∈ V (T ) − {R(T )}, let par(u) be parent node of node u. For every vertex u ∈ V (T ), let depth(u) be depth of node u. We can denote as depth(u) = depth(par(u)) + 1, for every vertex u ∈ V (T ) − {R(T )} and depth(R(T )) = 1. For every vertex u ∈ V (T ), let L(u) be set of all leaves on subtree u. Let size(u) = |L(u)| for each u ∈ V (T ). For each node u ∈ V (T ) − {R(T )}, we call Λ(u) be set of bipartition at edge (u, par(u)). For each bipartition, Λ(u), we can represent into two clusters, A = L(u) and B = L(R(T ))−L(u), and denoted by A|B. The set of bipartitions of T can denoted by C(T ) = {Λ(u) : u ∈ V (T ) − {R(T )}}. Let RF (T a , T b ) be Robinson-Foulds distance between trees T a and T b . RF-distance can denoted by RF (T a , The set S of bipartitions is compatible if there exists tree T such that C(T ) = S. leaves set A is compatible with t ′ when have node u that for all In this section, we describe a simpler version of the algorithm and prove its correctness and its running time (in Subsection 3.1). We improve its running time in Section 4 We assume that both T and the current t ′ are equipped with a data structure that given an id of a bipartition b, find vertex u in the trees such that Λ(u) = b. Since t ′ changes over time, we assume that our data structures can handle the tree update efficiently. We discuss this in Subsection 3.2.
The main loop of the algorithm iterates over all bipartition of T recursively and, if possible, add each bipartition to t ′ .
We define variables used in the main loop. Let z be the node that have minimum depth in tree t ′ for each bipartition in T . The main loop is described below.
Step, referred to in Section 4 4: if IsCompatible(t, u, z) then 5: The main loop uses the following function.
⊲ After this step we say that v has been added. 4: if z = null or depth(p) < z then 5: z ← p 6: end if 7: end for 8: return z Our algorithm maintains variable counter for each vertex in t ′ . We also keep a list of dirty vertices so that ClearCounter can run in O(1) time. Variable counter is updated in function UpdateCounterLeaf. Note that counter changes over time as UpdateCounterSubtree keeps adding leaves in L(u). The algorithm ensures that counter(u) is exactly as follows. If u is a leaf vertex, we let For other internal vertex u, we let For each call this function, it can take amortized O(1) time (to be proved later). The following algorithm describes function UpdateCounterLeaf.
Next, we have algorithm that check that add from previous algorithm is compatible to t ′ . We can track the node u that have minimum depth and have counter(u) > 0 in the while loop at the previous algorithm.
We prove the correctness of the algorithm. We note that it considers all bipartitions.

Lemma 1. The main loop considers all bipartitions in T .
Proof. From definition, Λ(u) can represent all bipartitions of T and for each bipartition, we have consider all node in Λ(u). From this, we can consider all bipartitions in T .
For clarity, for each vertex w ∈ t ′ we denote by L t ′ (w) its leaf set in t ′ . Note each call to UpdateCoun-terLeaf increases counter for each vertex by at most 1, and we call UpdateCounterLeaf exactly |L(u)| times. This implies the next lemma, which can be formally proven by induction.
i.e., the counter attains its maximum.
The following the key lemma. Proof. Note that after the call to UpdateCounterSubtree(u), we have called UpdateCounterLeaf(v) for every leaf v in L(u). From Claim 1, we only need to consider the case when counter(z ′ ) ≤ |L(u)|.
The algorithm maintains vertex z, which is the vertex closest to the root that UpdateCounterLeaf has touched. We first consider the case that z = z ′ .
On the other hand, if L(u) is compatible with t ′ , we show that counter(z ′ ) = |L(u)|. We prove a stronger statement: if L(u) is compatible with t ′ for every vertex v ∈ t ′ in the subtree rooted at z ′ , i.e., the upper bound in Claim 1 attains its maximum. To do so, we prove inductively on the structure of t ′ . Clearly, the claim is true when v is a leaf. Consider vertex v = z ′ in the subtree of t ′ rooted at z ′ . If L t ′ (v) ∩ L(u) = ∅, counter(v) = 0; thus the property follows. Now, consider v such that L t ′ (v) ∩ L(u) = ∅. Let w be a child of z ′ such that v belongs to subtree rooted at w.
Finally, consider z ′ . Note that since z ′ is the common ancestor of leaves in L(u), L t ′ (z ′ ) ⊇ L(u). For each child w of z ′ , when L t ′ (w) ∩ L(u) = ∅, w is complete and propagate |L t ′ (w) ∩ L(u)| to counter(z ′ ). Summing all children of z ′ , we have that counter(z ′ ) = |L(u)|.
This completes the proof of the lemma.

Lemma 3. Tree compatibility condition works
From above condition, our algorithm have add function counter(u). for each subtree L(u) have fully resolved when counter(u) = |L(u)|

Running time analysis
We first analyze the running time of the algorithm except the calls to UpdateCounterSubtree. We show that this part runs in linear time.
We start with UpdateCounterLeaf.
Proof. We use the potential method. Our data structure consists of variables counter for all vertices in t ′ . Denote the data structure at time i by D i . We say that a vertex u ∈ t ′ is incomplete if 0 < counter(u) < |L(u)|. Let potential function Φ(D i ) be the number of incomplete vertices in t ′ time i. Using the potential method, when the data structure changes from D i−1 to D i , the amortized cost of an operation isĉ = c + ∆Φ, where c is an actual cost, and ∆Φ = Φ(D i )−Φ(D i−1 ). Let D 0 be initial data structure after ClearCounter is called; thus Φ(D 0 ) = 0. Note that Φ(D i ) ≥ Φ(D 0 ) = 0 for any i. When invoking UpdateCounterLeaf at time i, let k be number of times the while loop in Lines 2 -6 is executed. Clearly, the actual cost c of the operation is k + 1.
We claim that Φ(D i ) = Φ(D i−1 ) − k + 1, i.e., the number of incomplete vertices decreases by k − 1. Let v ′ be the actual leaf that UpdateCounterLeaf is called on. Note that each time the loop is executed, counter(v) = size(v) = |L(v)|. Except when v = v ′ , previously at time i − 1, we know that 0 < counter(v) < |L(v)|, because v is an internal vertex with at least 2 children; hence v was incomplete at time i − 1. Since counter(v) = |L(v)| at time i, v is no longer incomplete; thus the number of incomplete vertices decreases by k − 1 as claimed.
We now analyze the running time of UpdateCounterSubtree.

Updating t
In this section, we show that when the bipartition defined by L(u) is compatible with t ′ , we can update t ′ to include that bipartition efficiently in time deg(u). When t ′ is compatible with a bipartition defined by L(u) for u ∈ T , to update t ′ we have to create a new child of z that consists of only children of z that corresponds to the bipartition L(u). Note that these children are those "full" counter that also propagate the counter to z. Therefore, when a child propagate a counter to any vertex, we keep a list of them. When we need to update t ′ at z, we can take every vertex in this list, and create a new child z ′ of z with these vertices as z ′ 's children and update their counter accordingly. This can be done in time O(deg(u)).

The faster algorithm: heavy child optimization
In this section, we describe a simple method to speed up the algorithm from the previous section. Note that the only bottle-neck to a nearly linear time algorithm is the counting procedure.
As a preprocessing, we assume that for each vertex u ∈ T , we know |L(u)|. This can be computed in O(n) time. The improved algorithm is described below.

Algorithm 5 Solve(u)
if u is not leaf then let c 1 , c 2 be children of u ⊲ There are exactly two children, since T is binary if |L(c 1 )| > |L(c 2 )| then swap node c 1 and node c 2 end if Solve(c 1 ) ⊲ Solve smaller subtree ClearCounter() Solve(c 2 ) ⊲ Solve larger subtree end if z ← UpdateCounterSubtree(c 1 ) ⊲ Update the counter for the smaller subtree if IsCompatible(t, u, z) then update t ′ end if To see that this algorithm is the correct implementation of the Main loop, we essentially need to show that at the end of Solve(u), variable counter is exactly equal to variable counter right after the "Update Step" in Line 3 in the Main loop while processing u, i.e., variable counter is exactly equal to the case when every leaf in L(u) has been added while no other leaves have been added. This can be shown by induction on the calls of Solve. We omit the proof in this version of the manuscript.
We are left to analyze its running time. Note that UpdateCounterSubtree(u) for u ∈ T runs in time linearly in the number of leaves, |L(u)|, from Lemma 5. Hence, we can charge the cost to these leaves.
We analyze the running time by counting the number of times each leaf is involved in this charging scheme. Note that we only call UpdateCounterSubtree at c 1 , which is the lighter subtree. Clearly, each leaf u belongs to at most O(log n) light subtrees; hence, it is charged by at most O(log n) time. Summing all leaves, we have that the total running time for UpdateCounterSubtree is O(n log n).