# Improved Duplication-Transfer-Loss Reconciliation with
## 3 Materials and Methods
### An \(O(mn^{2})\)-Time Algorithm for O-DTLx-Sampling  
As with any dynamic programming algorithm, Algorithm 1 can be easily extended to keep track of all optimal choices at each step of the algorithm and to use these optimal choices to (1) compute all possible optimal reconciliations, and/or (2) perform probabilistic backtracking to sample from the space of optimal reconciliations uniformly at random. Since there is often a very large number of optimal reconciliations [11; 12], making it infeasible to enumerate all possible optimal reconciliations in practice, we will show how to perform probabilistic backtracking to sample from the space of optimal DTLx reconciliations uniformly at random. Our sampling algorithm builds on the very similar sampling algorithm previously developed for DTL reconciliation [11] and implemented in RANGER-DTL 2.0 [17]. Given the similarity with [11], here we only provide a high level description of the overall approach, focusing primarily on describing the handling of hidden nodes and \(\mathbb{TL}\) and \(\mathbb{TX}\) events. The key idea that enables uniform random sampling is to keep track of the number of optimal DTLx reconciliations associated with each subproblem. Accordingly, we define the following: Given any \(g\in V(G^{\prime\prime})\) and \(s\in S^{\prime}\), let \(N(g,s)\) denote the number of optimal reconciliations for \(G^{\prime\prime}(g)\) and \(S^{\prime}\) such that \(g\) maps to \(s\). Thus, \(N(g,s)\) is the number of distinct DTLx reconciliations of \(G^{\prime\prime}(g)\) and \(S^{\prime}\), under the constraint that \(g\) maps to \(s\), that have a reconciliation cost of exactly \(c(g,s)\). These \(N(g,s)\) values can be easily computed alongside the corresponding \(c(g,s)\) values using the same overall dynamic programming framework as in Algorithm 1. Analogous to \(c_{\Sigma}(g,s)\), \(c_{\Delta}(g,s)\), and \(c_{\Theta}(g,s)\), we define, for each non-hidden internal node \(g\) of \(G^{\prime\prime}\) (i.e., \(g\in I(G^{\prime\prime})\cap I(G)\)), \(N_{\Sigma}(g,s)\), \(N_{\Delta}(g,s)\), and \(N_{\Theta}(g,s)\). Similarly, analogous to \(c_{\Theta_{L}}(g,s)\) and \(c_{\Theta_{X}}(g,s)\), we define, for each hidden node \(g\) of \(G^{\prime\prime}\) (i.e., \(g\in I(G^{\prime\prime})\setminus I(G)\)), \(N_{\Theta_{L}}(g,s)\) and \(N_{\Theta_{X}}(g,s)\). The dynamic programming table for \(N(\cdot,\cdot)\) can be initialized as follows for each \(g\in Le(G^{\prime\prime})\):  
\[N(g,s)= \begin{cases}1&\text{if }g\in Le(G^{\prime\prime})\text{ and }s= \mathcal{L}(g),\\ 0&\text{if }g\in Le(G^{\prime\prime})\text{ and }s\
eq\mathcal{L}(g).\end{cases}  \tag{8}\]  
It is easy to see that, for internal nodes of \(G^{\prime\prime}\), \(N(\cdot,\cdot)\) can be computed based on the values of the restricted counts defined above as follows:  
\[N(g,s)= \begin{cases}\sum_{x\in\{\Sigma,\Delta,\Theta\}}\text{ where }c_{x}(g^{\prime},s)=c(g,s)\ N_{x}(g^{\prime},s)+\sum_{x\in\{\Theta_{L}, \Theta_{X}\}}\text{ where }c_{x}(g,s)=c(g,s)\ N_{x}(g,s)&\text{if }g\in I(G^{\prime \prime})\setminus I(G),\\ \sum_{x\in\{\Sigma,\Delta,\Theta\}}\text{ where }c_{x}(g,s)=c(g,s)\ N_{x}(g,s)& \text{otherwise},\end{cases}  \tag{9}\]  
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)\)). Now, for any \(g\in I(G^{\prime\prime})\cap I(G)\), the values of \(N_{\Sigma}(g,s)\), \(N_{\Delta}(g,s)\), and \(N_{\Theta}(g,s)\) can be computed exactly as described in [11] for DTL reconciliation. It therefore suffices to show how to compute the values \(N_{\Theta_{L}}(g,s)\) and \(N_{\Theta_{X}}(g,s)\) when \(g\) is a hidden node. Suppose \(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}\). For any \(s\in V(S^{\prime})\), let \(A\) denote the set of all mappings of \(g^{\prime}\) that are optimal for \(c_{\Theta_{L}}(g,s)\), i.e., for any \(x\in A\) we must have \(c_{\Theta_{L}}(g,s)=P_{\mathbb{TL}}+c(g^{\prime},x)\).