# Improved Duplication-Transfer-Loss Reconciliation with
## 3 Materials and Methods
### An \(O(mn)\)-Time Algorithm for O-DTLx  
Following along the lines of the previous dynamic programming framework described above, we define the core subproblem of dynamic programming algorithm as follows: Given any \(g\in V(G^{\prime\prime})\) and \(s\in V(S^{\prime})\), we define \(c(g,s)\) to be cost of an optimal DTLx reconciliation of the subtree \(G^{\prime\prime}(g)\) with \(S^{\prime}\) under the constraint that \(g\) maps to \(s\). Note that the hidden nodes of \(G^{\prime\prime}\) that are not used in a DTLx reconciliation do not contribute to the reconciliation cost of that reconciliation. These unused hidden nodes can therefore be trimmed out at the end to yield the final augmented gene tree \(G^{\prime}\). Thus, in accordance with the definition of DTLx reconciliation, the optimal reconciliation cost of reconciling \(G\) and \(S\) is given by \(\min_{s\in V(S^{\prime})}c(rt(G^{\prime\prime}),s)\). For each non-hidden internal node \(g\) of \(G^{\prime\prime}\), i.e., if \(g\in I(G^{\prime\prime})\cap I(G)\), we also define the following restricted subproblems: (i) \(c_{\Sigma}(g,s)\) denotes the cost of an optimal reconciliation of \(G^{\prime\prime}(g)\) with \(S^{\prime}\) under the constraint that \(g\) maps to \(s\) and \(g\in\Sigma\). (ii) \(c_{\Delta}(g,s)\) denotes the cost of an optimal reconciliation of \(G^{\prime\prime}(g)\) with \(S^{\prime}\) under the constraint that \(g\) maps to \(s\) and \(g\in\Delta\). Furthermore, (iii) \(c_{\Theta}(g,s)\) denotes the cost of an optimal reconciliation of \(G^{\prime\prime}(g)\) with \(S^{\prime}\) under the constraint that \(g\) maps to \(s\) and \(g\in\Theta\). Recall that only the hidden nodes of \(G^{\prime\prime}\) can represent \(\mathbb{TL}\) and \(\mathbb{TX}\) events. Accordingly, for each hidden node \(g\) of \(G^{\prime\prime}\), i.e., if \(g\in I(G^{\prime\prime})\setminus I(G)\), we define the following restricted subproblems: (i) \(c_{\Theta_{L}}(g,s)\) denotes the cost of an optimal reconciliation of \(G^{\prime\prime}(g)\) with \(S^{\prime}\) under the constraint that \(g\) maps to \(s\) and \(g\in\Theta_{L}\). (ii) \(c_{\Theta_{X}}(g,s)\) denotes the cost of an optimal reconciliation of \(G^{\prime\prime}(g)\) with \(S^{\prime}\) under the constraint that \(g\) maps to \(s\) and \(g\in\Theta_{X}\). The algorithm executes a nested post order traversal of \(G^{\prime\prime}\) and \(S^{\prime}\) to compute the value of \(c(g,s)\) for each \(g\) and \(s\). The base cases for the dynamic programming table are initialized as follows:  
\[c(g,s)= \begin{cases}0&\text{ if }g\in Le(G^{\prime\prime})\text{ and }s=\mathcal{L}(g),\\ \infty&\text{ if }g\in Le(G^{\prime\prime})\text{ and }s\
eq\mathcal{L}(g).\end{cases}  \tag{1}\]  
For internal nodes of \(G^{\prime\prime}\), \(c(g,s)\) can be computed based on the values of the restricted subproblems, defined above, as follows:  
\[c(g,s)= \begin{cases}\min\{c_{\Sigma}(g^{\prime},s),c_{\Delta}(g^{\prime},s),c_{ \Theta}(g^{\prime},s),c_{\Theta_{L}}(g,s),c_{\Theta_{X}}(g,s)\}&\text{if }g\in I(G^{\prime\prime}) \setminus I(G),\\ \min\{c_{\Sigma}(g,s),c_{\Delta}(g,s),c_{\Theta}(g,s)\}&\text{otherwise},\end{cases}  \tag{2}\]  
where \(g^{\prime}\) denotes the unique child of \(g\) in the case where \(g\) is a hidden node (i.e., \(g\in I(G^{\prime\prime})\setminus I(G)\)). Note that, when \(g\in I(G^{\prime\prime})\cap I(G)\), the value of \(c(g,s)\) is the minimum of the restricted subproblem values computed at \(g\) and \(g^{\prime}\). Essentially, if \(c(g,s)\) equals \(c_{\Sigma}(g,s)\), \(c_{\Delta}(g,s)\), or \(c_{\Theta}(g,s)\), then it means that the hidden node \(g\) is not required (i.e., it need not represent any event) in an optimal reconciliation corresponding to that value of \(c(g,s)\). For each \(g\) and \(s\), optimal values for the applicable restricted subproblems represented by \(c_{\Sigma}(g,s)\), \(c_{\Delta}(g,s)\), \(c_{\Theta}(g,s)\), \(c_{\Theta_{L}}(g,s)\), and \(c_{\Theta_{X}}(g,s)\) can be computed based on previously computed values of \(c(\cdot,\cdot)\) as shown below.