# Improved Duplication-Transfer-Loss Reconciliation with
## 3 Materials and Methods
### An \(O(mn)\)-Time Algorithm for O-DTLx
For ease of presentation and to help compute these values more efficiently, we also define, for each \(g\in V(G^{\prime\prime})\) and \(s\in V(S^{\prime})\), the following:  
\[in(g,s) =\min_{x\in V(S^{\prime}(s))}\{P_{loss}\cdot d_{S^{\prime}}(s,x)+ c(g,x)\}\] \[out(g,s) =\min_{x\in V(S^{\prime})}\min_{\text{incomparable to }s}c(g,x)\] \[inAlt(g,s) =\min_{x\in V(S^{\prime}(s))}c(g,x).\]  
Now, consider any \(g\in I(G^{\prime\prime})\cap I(G)\), and let \(\{g^{\prime},g^{\prime\prime}\}=Cl_{G^{\prime\prime}}(g)\). If \(s\
ot\in Le(S^{\prime})\) then let \(\{s^{\prime},s^{\prime\prime}\}=Cl_{S^{\prime}}(s)\). Then,  
\[c_{\Sigma}(g,s)= \begin{cases}\infty&\text{if }s\in Le(S^{\prime}),\\ \min\{in(g^{\prime},s^{\prime})+in(g^{\prime\prime},s^{\prime\prime}),in(g^{ \prime\prime},s^{\prime})+in(g^{\prime},s^{\prime\prime})\}&\text{otherwise}, \end{cases}  \tag{3}\]  
\[c_{\Delta}(g,s)= \begin{cases}P_{\Delta}+c(g^{\prime},s)+c(g^{\prime\prime},s) &\text{if }s\in Le(S^{\prime}),\\ P_{\Delta}+in(g^{\prime},s)+in(g^{\prime\prime},s)&\text{otherwise},\end{cases}  \tag{4}\]  
and  
\[c_{\Theta}(g,s)= \begin{cases}\infty&\text{if }s=rt(S^{\prime}),\\ P_{\Theta}+\min\{in(g^{\prime},s)+out(g^{\prime\prime},s),in(g^{\prime\prime},s )+out(g^{\prime},s)\}&\text{otherwise}.\end{cases}  \tag{5}\]  
Similarly, if \(g\in I(G^{\prime\prime})\setminus I(G)\), i.e., \(g\) is a hidden node, and \(g^{\prime}\) represents the unique child of \(g\) in \(G^{\prime\prime}\), then,  
\[c_{\Theta_{L}}(g,s)= \begin{cases}\infty&\text{if }s=rt(S^{\prime})\text{ or }s\in\mathcal{X}(S^{\prime}),\\ P_{\mathbb{T}\mathbb{T}}+out(g^{\prime},s)&\text{otherwise},\end{cases}  \tag{6}\]  
and  
\[c_{\Theta_{X}}(g,s)= \begin{cases}\infty&\text{if }s=rt(S^{\prime})\text{ or }s \
ot\in\mathcal{X}(S^{\prime}),\\ P_{\mathbb{T}\mathbb{T}}+out(g^{\prime},s)&\text{otherwise},\end{cases}  \tag{7}\]The O-DTLx problem can now be easily solved using dynamic programming based on Equations (1)-(7). The pseudocode given in Algorithm 1, i.e., Algorithm _Compute-O-DTLx_, shows how this can be done within \(O(mn)\) time by efficiently computing the values of \(in(\cdot,\cdot)\), \(out(\cdot,\cdot)\), and \(inAlt(\cdot,\cdot)\). Observe that Algorithm 1 only computes the optimal reconciliation cost. However, as with any dynamic programming algorithm, it is straightforward to compute an actual reconciliation that achieves this optimal reconciliation cost through backtracking. Furthermore, observe that it is trivial to \"trim down\" any reconciliation of \(G^{\prime\prime}\) and \(S^{\prime}\) constructed through backtracking by simply removing any hidden node in \(G^{\prime\prime}\) that is not assigned a \(\mathbb{TL}\) or \(\mathbb{TX}\) event in that reconciliation. This would yield the augmented gene tree \(G^{\prime}\), along with its reconciliation with \(S^{\prime}\), as required by the definition of DTLx reconciliation (Definition 5). **Theorem 1**. : _The \(O\)-DTLx problem can be solved in \(O(mn)\) time, where \(m=|\,Le(G)|\) and \(n=|\,Le(S)|\)._  
Proof. : It suffices to show that Algorithm 1 correctly computes the value of \(c(g,s)\), for each \(g\in V(G^{\prime})\) and \(s\in V(S^{\prime})\), within \(O(mn)\) time. _Correctness:_ We will show that the values of \(in(g,s)\), \(inAlt(g,s)\), \(out(g,s)\), \(c_{\Sigma}(g,s)\), \(c_{\Delta}(g,s)\), \(c_{\Theta_{\Delta}}(g,s)\), and \(c_{\Theta_{X}}(g,s)\) are computed correctly for each \(g\) and \(s\) where applicable. For each \(g\in Le(G^{\prime})\), consider the values of \(in(g,s)\), \(inAlt(g,s)\), \(out(g,s)\) and \(c(g,s)\). These values are assigned correctly in accordance with their definitions during the execution of the 'for' loop in Steps 8-11. These values serve as the base case of our inductive argument. Consider the case when \(g\in I(G^{\prime\prime})\setminus I(G)\), and \(g^{\prime}=Ch(g)\). By the induction hypothesis, we may assume that the values of \(in(g^{\prime},x)\), \(inAlt(g^{\prime},x)\), and \(c(g^{\prime},x)\) have been computed correctly for each \(x\in V(S^{\prime})\).