Equivalence Classes. In this section we explain how to count the number of ∼1-equivalence classes by enumer- ating one representative reconciliation for each of them. Observe that, by definition of ∼1, the only difference between reconciliations in the same class are the nodes u ∈ V (P ) for which α(u) exists and if we can impose a univoque mapping for them, we identify a representative for each class. With the aid of the next Lemma we show that we can enumerate all these representative reconciliations if they are characterize by the following property: ˜ If (u, v) ∈ Θ(q∗) with p(v)= u, then q∗(u)= q∗(s(v)). This is how we collected the data obtained from the experimental results displayed in Section 2.6.
Equivalence Classes. We present here the experimental results that we obtained applying the equivalence classes described in Section 2.6 to the datasets of Table 2.2 taken from [25]. There are five tables, one for each of the cost vectors: (-0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 2, 1), (0, 2, 3, 1) and (1, 1, 3, 1), which are some of the most common [25]. log(#sol) In all the tables, # solutions indicates the number of all optimal reconciliations, while # ∼1, # ∼2 and # ∼2 + ∼1 indicate the number of equivalence classes when relations ∼1, ∼2 or both are applied; the last column, called NMR, indicates the value of the Normalized Magnitude Reduction, rounded to two digits after the decimal point, which is given by log(#sol)−log(#∼1+∼2)) . Such value is 1 when all optimal solutions are reduced to a single parsimonious reconciliation when applying the two equivalences. Inversely, the closer this value is to 0, the less the two equivalences were able to reduce by similarity the number of solutions. Observe that for Wolbachia, the number of solutions is so huge that, for space reason, we rounded the number to fit the table. Regarding alternative choices to NMR for evaluating our results could have been a simple #sol proportion ∼2+∼1 but just obtaining, for instance, 0.001% of (equivalence classes of) reconcilia- tions it could be meaning less when facing huge numbers of solutions as in the Wolbachia case. Indeed, we would have obtained, in this way, the score of score 0.001, where the optimum would be reached at 1/#sol, passing from ∼ 1048 to ∼ 1047 objects which are actually. Hence we decide to measure the exponents of the base 10 so in this way in this example it would be 47/48 ∼ 0.97. Now halving the order of magnitude it could obtained both passing from 100 to 10 solutions and passing from ∼ 1048 to ∼ 1024. Although having to treat 10 solutions and ∼ 1024 could not be evaluated at the same way. We decide then to rapport the reduction of the magnitude w.r.t. the overall magnitude (See Figure 2.26): · log(a 10x) NMR =1 − log(b · 10y) = y + log(b) − x − log(a) y + log(b) ROcUGH y − x y When y ≥ x 1 and assuming 0 ≤ a, b < 10 =⇒ 0 ≤ log(a), log(b) < 1. Figure 2.26: green-to-red points: NMR(x = Index, y = 10000). Black line: rough super- extimation of NMR obtained by approximating numbers involved in the computation as a · 10x ∼ x; in particular the function is constant in the intervals of the form [10x, 10x+1). From the previous tables we can deduce a number of observations. 94 Dataset # ...
