Counting nonshared butterfly quartets
For each pair of internal nodes v, v' we want to count the number of nonshared butterfly quartets claimed by both internal nodes, nonshared(v, v'). Such quartets have the property that a pair of leaves found in the same subtree of v will be found in different subtrees of v' and vice versa, i.e. a nonshared quartet with leaves a, b, c and d, has a ∈ Fi ∩ Gj, b ∈ Fi ∩ Gl, c ∈ Fk ∩ Gn and d ∈ Fm ∩ Gj (see Fig. 9). The following expression counts all nonshared quartets related to a pair of nodes v and v', obeying that if two leaves of the quartet are in one subtree of v they are in different subtrees of v' and vice versa:
Figure 9  Internal nodes v ∈ T claiming the quartet ab|cd and v' ∈ T' claiming the quartet ad|bc. ∑ i  ∑ j  | F i  ∩ G j  | | F i  ∩ G ¯  j  | | F ¯  i  ∩ G ¯  j  | | F ¯  i  ∩ G j  |           ( 6 )    MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaaeqbqaamaaqafabaGaeiiFaWNaemOray0aaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemOAaOgabeaakiabcYha8jabcYha8jabdAeagnaaBaaaleaacqWGPbqAaeqaaOGaeyykICSafm4raCKbaebadaWgaaWcbaGaemOAaOgabeaakiabcYha8jabcYha8jqbdAeagzaaraWaaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcuWGhbWrgaqeamaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWNaeiiFaWNafmOrayKbaebadaWgaaWcbaGaemyAaKgabeaakiabgMIihlabdEeahnaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWhaleaacqWGQbGAaeqaniabggHiLdaaleaacqWGPbqAaeqaniabggHiLdGccaWLjaGaaCzcamaabmGabaGaeGOnaydacaGLOaGaayzkaaaaaa@5F95@
Even though (6) satisfies the property of nonshared quartets, it possibly counts more than the number of nonshared quartets claimed by an internal node in each tree. The problem is that given two internal nodes, they do not nescessarily claim the quartets counted by (6). If we denote the leaves of an nonshared quartet a, b, c and d, the first, second, third and fourth factors in (6) counts the number of choices of a, b, c and d respectively. The first and second factor choose a and b from Fi, while the third and fourth choose c and d from F¯ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWGgbGrgaqeaaaa@2DD9@i. In the cases where c and d are chosen from the same subtree Fk, k ≠ i of v, v does not claim the quartet. We must subtract these quartets, which can be counted as:
∑ i  ∑ j  ∑ k ≠ i   | F i  ∩ G j  | | F i  ∩ G ¯  j  | | F k  ∩ G ¯  j  | | F k  ∩ G j  |           ( 7 )      MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaaeqbqaamaaqafabaWaaabuaeaacqGG8baFcqWGgbGrdaWgaaWcbaGaemyAaKgabeaakiabgMIihlabdEeahnaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWNaeiiFaWNaemOray0aaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcuWGhbWrgaqeamaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWNaeiiFaWNaemOray0aaSbaaSqaaiabdUgaRbqabaGccqGHPiYXcuWGhbWrgaqeamaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWNaeiiFaWNaemOray0aaSbaaSqaaiabdUgaRbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemOAaOgabeaakiabcYha8bWcbaGaem4AaSMaeyiyIKRaemyAaKgabeqdcqGHris5aaWcbaGaemOAaOgabeqdcqGHris5aOGaaCzcaiaaxMaadaqadiqaaiabiEda3aGaayjkaiaawMcaaaWcbaGaemyAaKgabeqdcqGHris5aaaa@6613@
Similarly there are cases where b and c are chosen from the same subtree Gl, l ≠ j of v', which we must also subtract. These can be counted as:
∑ i  ∑ j  ∑ l ≠ j   | F i  ∩ G j  | | F i  ∩ G l  | | F ¯  i  ∩ G l  | | F ¯  i  ∩ G j  |             ( 8 )    MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaaeqbqaamaaqafabaWaaabuaeaacqGG8baFcqWGgbGrdaWgaaWcbaGaemyAaKgabeaakiabgMIihlabdEeahnaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWNaeiiFaWNaemOray0aaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemiBaWgabeaakiabcYha8jabcYha8jqbdAeagzaaraWaaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemiBaWgabeaakiabcYha8jabcYha8jqbdAeagzaaraWaaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemOAaOgabeaakiabcYha8bWcbaGaemiBaWMaeyiyIKRaemOAaOgabeqdcqGHris5aaWcbaGaemOAaOgabeqdcqGHris5aaWcbaGaemyAaKgabeqdcqGHris5aOGaaCzcaiaaxMaadaqadiqaaiabiIda4aGaayjkaiaawMcaaaaa@6619@
The cases where both c and d are chosen from the same subtree Fk, k ≠ i of v and b and c are chosen from the same subtree Gl, l ≠ j of v' are included in both the expressions above and therefore they must be added again. The following expression counts the number of these cases:
∑ i  ∑ j  ∑ k ≠ i   ∑ l ≠ j   | F i  ∩ G j  | | F i  ∩ G l  | | F k  ∩ G l  | | F k  ∩ G j  |               ( 9 )    MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaaeqbqaamaaqafabaWaaabuaeaadaaeqbqaaiabcYha8jabdAeagnaaBaaaleaacqWGPbqAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdQgaQbqabaGccqGG8baFcqGG8baFcqWGgbGrdaWgaaWcbaGaemyAaKgabeaakiabgMIihlabdEeahnaaBaaaleaacqWGSbaBaeqaaOGaeiiFaWNaeiiFaWNaemOray0aaSbaaSqaaiabdUgaRbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemiBaWgabeaakiabcYha8jabcYha8jabdAeagnaaBaaaleaacqWGRbWAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdQgaQbqabaGccqGG8baFaSqaaiabdYgaSjabgcMi5kabdQgaQbqab0GaeyyeIuoaaSqaaiabdUgaRjabgcMi5kabdMgaPbqab0GaeyyeIuoaaSqaaiabdQgaQbqab0GaeyyeIuoaaSqaaiabdMgaPbqab0GaeyyeIuoakiaaxMaacaWLjaWaaeWaceaacqaI5aqoaiaawIcacaGLPaaaaaa@6C97@
Combining equations (6), (7), (8) and (9), gives a way of calculating the number of nonshared quartets between two internal nodes v and v':
n o n s h a r e d ( v , v ′   )  = ∑ i  ∑ j  ( | F i  ∩ G j  | | F i  ∩ G ¯  j  | | F ¯  i  ∩ G ¯  j  | | F ¯  i  ∩ G j  |          − ∑ k ≠ i   | F i  ∩ G j  | | F i  ∩ G ¯  j  | | F k  ∩ G ¯  j  | | F k  ∩ G j  |      − ∑ l ≠ j   | F i  ∩ G j  | | F i  ∩ G l  | | F ¯  i  ∩ G l  | | F ¯  i  ∩ G j  |      + ∑ k ≠ i   ∑ l ≠ j   | F i  ∩ G j  | | F i  ∩ G l  | | F k  ∩ G l  | | F k  ∩ G j  |      )            ( 10  )    MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaafaqadeabbaaaaeaaieaacqWFUbGBcqWFVbWBcqWFUbGBcqWFZbWCcqWFObaAcqWFHbqycqWFYbGCcqWFLbqzcqWFKbazdaqadiqaaGqaciab+zha2jab+XcaSiqb+zha2zaafaaacaGLOaGaayzkaaGaeyypa0ZaaabuaeaadaaeqbqaamaabeGabaGaeiiFaWNaemOray0aaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemOAaOgabeaakiabcYha8jabcYha8jabdAeagnaaBaaaleaacqWGPbqAaeqaaOGaeyykICSafm4raCKbaebadaWgaaWcbaGaemOAaOgabeaakiabcYha8jabcYha8jqbdAeagzaaraWaaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcuWGhbWrgaqeamaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWNaeiiFaWNafmOrayKbaebadaWgaaWcbaGaemyAaKgabeaakiabgMIihlabdEeahnaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWhacaGLOaaaaSqaaiabdQgaQbqab0GaeyyeIuoaaSqaaiabdMgaPbqab0GaeyyeIuoaaOqaceaawpGaaCzcaiabgkHiTmaaqafabaGaeiiFaWNaemOray0aaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemOAaOgabeaakiabcYha8jabcYha8jabdAeagnaaBaaaleaacqWGPbqAaeqaaOGaeyykICSafm4raCKbaebadaWgaaWcbaGaemOAaOgabeaakiabcYha8jabcYha8jabdAeagnaaBaaaleaacqWGRbWAaeqaaOGaeyykICSafm4raCKbaebadaWgaaWcbaGaemOAaOgabeaakiabcYha8jabcYha8jabdAeagnaaBaaaleaacqWGRbWAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdQgaQbqabaGccqGG8baFaSqaaiabdUgaRjabgcMi5kabdMgaPbqab0GaeyyeIuoaaOqaciaakpaa6pGaaCzcaiabgkHiTmaaqafabaGaeiiFaWNaemOray0aaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemOAaOgabeaakiabcYha8jabcYha8jabdAeagnaaBaaaleaacqWGPbqAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdYgaSbqabaGccqGG8baFcqGG8baFcuWGgbGrgaqeamaaBaaaleaacqWGPbqAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdYgaSbqabaGccqGG8baFcqGG8baFcuWGgbGrgaqeamaaBaaaleaacqWGPbqAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdQgaQbqabaGccqGG8baFaSqaaiabdYgaSjabgcMi5kabdQgaQbqab0GaeyyeIuoaaOqaamaabiGabiWaaO5aaibbaihbcaWLjaGaey4kaSYaaabuaeaadaaeqbqaaiabcYha8jabdAeagnaaBaaaleaacqWGPbqAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdQgaQbqabaGccqGG8baFcqGG8baFcqWGgbGrdaWgaaWcbaGaemyAaKgabeaakiabgMIihlabdEeahnaaBaaaleaacqWGSbaBaeqaaOGaeiiFaWNaeiiFaWNaemOray0aaSbaaSqaaiabdUgaRbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemiBaWgabeaakiabcYha8jabcYha8jabdAeagnaaBaaaleaacqWGRbWAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdQgaQbqabaGccqGG8baFaSqaaiabdYgaSjabgcMi5kabdQgaQbqab0GaeyyeIuoaaSqaaiabdUgaRjabgcMi5kabdMgaPbqab0GaeyyeIuoaaOGaayzkaaaaaiaaxMaacaWLjaWaaeWaceaacqaIXaqmcqaIWaamaiaawIcacaGLPaaaaaa@0F94@
Assuming that the trees have a nonshared quartet with topology form ab|cd in T, and ad|bc in T', there are two internal nodes in each tree claiming the quartet: vab|c|d and vcd|a|b in T and v′ad|b|c MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWG2bGDgaqbamaaBaaaleaacqWGHbqycqWGKbazcqGG8baFcqWGIbGycqGG8baFcqWGJbWyaeqaaaaa@3691@ and v′bc|a|d MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacuWG2bGDgaqbamaaBaaaleaacqWGIbGycqWGJbWycqGG8baFcqWGHbqycqGG8baFcqWGKbazaeqaaaaa@3691@ in T'. All of the four combinations of these will identify the quartet as nonshared. Therefore the total number of nonshared quartets between the two trees is:
nonshared ( T , T ′  ) = 1 4  ∑ v ∈ T   ∑ v ′  ∈ T ′    nonshared ( v , v ′  )       MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqqGUbGBcqqGVbWBcqqGUbGBcqqGZbWCcqqGObaAcqqGHbqycqqGYbGCcqqGLbqzcqqGKbazcqGGOaakcqWGubavcqGGSaalcuWGubavgaqbaiabcMcaPiabg2da9maalaaabaGaeGymaedabaGaeGinaqdaamaaqafabaWaaabuaeaacqqGUbGBcqqGVbWBcqqGUbGBcqqGZbWCcqqGObaAcqqGHbqycqqGYbGCcqqGLbqzcqqGKbazcqGGOaakcqWG2bGDcqGGSaalcuWG2bGDgaqbaiabcMcaPaWcbaGafmODayNbauaacqGHiiIZcuWGubavgaqbaaqab0GaeyyeIuoaaSqaaiabdAha2jabgIGiolabdsfaubqab0GaeyyeIuoaaaa@5F68@
Direct computation of nonshared(v, v') using (10) takes time O(dv2dv′2 MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGKbazdaqhaaWcbaGaemODayhabaGaeGOmaidaaOGaemizaq2aa0baaSqaaiqbdAha2zaafaaabaGaeGOmaidaaaaa@348C@). Each of the subtrees has to be intersected with two disjoint sets in each of the sums. This means that if a subtree is only a leaf, at least one of these intersections will be zero, and the term will be zero. Therefore we can ignore subtrees that consist of a single leaf, just like when computing shared(T, T'), and reduce the time usage to O(idv2idv′2 MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGPbqAcqWGKbazdaqhaaWcbaGaemODayhabaGaeGOmaidaaOGaemyAaKMaemizaq2aa0baaSqaaiqbdAha2zaafaaabaGaeGOmaidaaaaa@3742@). The time usage of the calculation of nonshared(v, v') can be further improved by rewriting (9):
∑ i  ∑ j  ∑ k ≠ i   ∑ l ≠ j   | F i  ∩ G j  | | F i  ∩ G l  | | F k  ∩ G l  | | F k  ∩ G j  |         =    ∑ i  ∑ j  | F i  ∩ G j  |     ∑ k ≠ i   | F k  ∩ G j  |   ∑ l ≠ j   | F i  ∩ G l  | | F k  ∩ G l  |   =    ∑ i  ∑ j  | F i  ∩ G j  |     ∑ k ≠ i   | F k  ∩ G j  |   ( ∑ l  | F i  ∩ G l  | | F k  ∩ G l  |   − | F i  ∩ G j  | | F k  ∩ G j  |  )        MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaafaqaaeWabaaabaWaaabuaeaadaaeqbqaamaaqafabaWaaabuaeaacqGG8baFcqWGgbGrdaWgaaWcbaGaemyAaKgabeaakiabgMIihlabdEeahnaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWNaeiiFaWNaemOray0aaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemiBaWgabeaakiabcYha8jabcYha8jabdAeagnaaBaaaleaacqWGRbWAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdYgaSbqabaGccqGG8baFcqGG8baFcqWGgbGrdaWgaaWcbaGaem4AaSgabeaakiabgMIihlabdEeahnaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWhaleaacqWGSbaBcqGHGjsUcqWGQbGAaeqaniabggHiLdaaleaacqWGRbWAcqGHGjsUcqWGPbqAaeqaniabggHiLdaaleaacqWGQbGAaeqaniabggHiLdaaleaacqWGPbqAaeqaniabggHiLdGccqGH9aqpaeaadaaeqbqaamaaqafabaGaeiiFaWNaemOray0aaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemOAaOgabeaakiabcYha8bWcbaGaemOAaOgabeqdcqGHris5aaWcbaGaemyAaKgabeqdcqGHris5aOWaaabuaeaacqGG8baFcqWGgbGrdaWgaaWcbaGaem4AaSgabeaakiabgMIihlabdEeahnaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWhaleaacqWGRbWAcqGHGjsUcqWGPbqAaeqaniabggHiLdGcdaaeqbqaaiabcYha8jabdAeagnaaBaaaleaacqWGPbqAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdYgaSbqabaGccqGG8baFcqGG8baFcqWGgbGrdaWgaaWcbaGaem4AaSgabeaakiabgMIihlabdEeahnaaBaaaleaacqWGSbaBaeqaaOGaeiiFaWhaleaacqWGSbaBcqGHGjsUcqWGQbGAaeqaniabggHiLdGccqGH9aqpaeaadaaeqbqaamaaqafabaGaeiiFaWNaemOray0aaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemOAaOgabeaakiabcYha8bWcbaGaemOAaOgabeqdcqGHris5aaWcbaGaemyAaKgabeqdcqGHris5aOWaaabuaeaacqGG8baFcqWGgbGrdaWgaaWcbaGaem4AaSgabeaakiabgMIihlabdEeahnaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWhaleaacqWGRbWAcqGHGjsUcqWGPbqAaeqaniabggHiLdGcdaqadiqaamaaqafabaGaeiiFaWNaemOray0aaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemiBaWgabeaakiabcYha8jabcYha8jabdAeagnaaBaaaleaacqWGRbWAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdYgaSbqabaGccqGG8baFaSqaaiabdYgaSbqab0GaeyyeIuoakiabgkHiTiabcYha8jabdAeagnaaBaaaleaacqWGPbqAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdQgaQbqabaGccqGG8baFcqGG8baFcqWGgbGrdaWgaaWcbaGaem4AaSgabeaakiabgMIihlabdEeahnaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWhacaGLOaGaayzkaaaaaaaa@F676@
Inspired by the precomputing of sums used in shared(v, v'), (5), we calculate for each i, k, k ≠ i the sum:
S i , k   = ∑ l  | F i  ∩ G l  |   | F k  ∩ G l  |       ( 11  )    MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGtbWudaWgaaWcbaGaemyAaKMaeiilaWIaem4AaSgabeaakiabg2da9maaqafabaGaeiiFaWNaemOray0aaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemiBaWgabeaakiabcYha8bWcbaGaemiBaWgabeqdcqGHris5aOGaeiiFaWNaemOray0aaSbaaSqaaiabdUgaRbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemiBaWgabeaakiabcYha8jaaxMaacaWLjaWaaeWaceaacqaIXaqmcqaIXaqmaiaawIcacaGLPaaaaaa@4ED6@
There are O(idv2 MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGPbqAcqWGKbazdaqhaaWcbaGaemODayhabaGaeGOmaidaaaaa@31EC@) of these sums and each takes time O(idv') to calculate, so the time complexity for calculating all sums is O(idv2idv′ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGPbqAcqWGKbazdaqhaaWcbaGaemODayhabaGaeGOmaidaaOGaemyAaKMaemizaq2aaSbaaSqaaiqbdAha2zaafaaabeaaaaa@364F@). In the case that idv' ≤ idv, we can switch v and v' and thus get time usage O(idvidv' min{idv, idv'}). Assuming that the sums have been calculated, (9) can now be calculated in time O(idvidv'min{idv, idv'}) by the expression:
∑ i  ∑ j  | F i  ∩ G j  |     ∑ k ≠ i   | F k  ∩ G j  | ( S i , k   − | F i  ∩ G j  | | F k  ∩ G j  |  )          ( 12  )    MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaaeqbqaamaaqafabaGaeiiFaWNaemOray0aaSbaaSqaaiabdMgaPbqabaGccqGHPiYXcqWGhbWrdaWgaaWcbaGaemOAaOgabeaakiabcYha8bWcbaGaemOAaOgabeqdcqGHris5aaWcbaGaemyAaKgabeqdcqGHris5aOWaaabuaeaacqGG8baFcqWGgbGrdaWgaaWcbaGaem4AaSgabeaakiabgMIihlabdEeahnaaBaaaleaacqWGQbGAaeqaaOGaeiiFaW3aaeWaceaacqWGtbWudaWgaaWcbaGaemyAaKMaeiilaWIaem4AaSgabeaakiabgkHiTiabcYha8jabdAeagnaaBaaaleaacqWGPbqAaeqaaOGaeyykICSaem4raC0aaSbaaSqaaiabdQgaQbqabaGccqGG8baFcqGG8baFcqWGgbGrdaWgaaWcbaGaem4AaSgabeaakiabgMIihlabdEeahnaaBaaaleaacqWGQbGAaeqaaOGaeiiFaWhacaGLOaGaayzkaaaaleaacqWGRbWAcqGHGjsUcqWGPbqAaeqaniabggHiLdGccaWLjaGaaCzcamaabmGabaGaeGymaeJaeGOmaidacaGLOaGaayzkaaaaaa@6E4A@
By substituting (9) with (12) in (10), we can calculate nonshared(v, v', in time O(idvidv'min{idv, idv'}). Since calculation of the sums is independent of the calculation of nonshared(v, v'), these calculations can be done serially as shown in the algorithm below.
ALGORITHM – CALCULATING THE NUMBER OF NONSHARED BUTTERFLY QUARTETS BETWEEN T AND T'
Requires: T, T' two input trees with the same leaf set.
Ensures: Res = nonshared(T, T')
Res ← 0
for v internal node in T do
   for v' internal node in T' do
      Calculate sums Si,k
      Res ← Res + nonshared(v, v')
   end for
end for
Res ← Res4 MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaWcaaqaaGqaciab=jfasjab=vgaLjab=nhaZbqaaiabisda0aaaaaa@31A0@
The time complexity of the algorithm is:
∑ v ∈ T   ∑ v ′  ∈ T ′    i d v  i d v ′   min ⁡ { i d v  , i d v ′    }  ≤ min ⁡ { i d , i d ′   }  ∑ v ∈ T   i d v  ∑ v ′  ∈ T ′    i d v ′   = O ( | V | | V ′  | min ⁡ { i d , i d ′   }   )            MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaaeqbqaamaaqafabaGaemyAaKMaemizaq2aaSbaaSqaaiabdAha2bqabaGccqWGPbqAcqWGKbazdaWgaaWcbaGafmODayNbauaaaeqaaOGagiyBa0MaeiyAaKMaeiOBa42aaiWabeaacqWGPbqAcqWGKbazdaWgaaWcbaGaemODayhabeaakiabcYcaSiabdMgaPjabdsgaKnaaBaaaleaacuWG2bGDgaqbaaqabaaakiaawUhacaGL9baacqGHKjYOcyGGTbqBcqGGPbqAcqGGUbGBdaGadeqaaiabdMgaPjabdsgaKjabcYcaSiabdMgaPjqbdsgaKzaafaaacaGL7bGaayzFaaWaaabuaeaacqWGPbqAcqWGKbazdaWgaaWcbaGaemODayhabeaakmaaqafabaGaemyAaKMaemizaq2aaSbaaSqaaiqbdAha2zaafaaabeaakiabg2da9iabd+eapnaabmGabaGaeiiFaWNaemOvayLaeiiFaWNaeiiFaWNafmOvayLbauaacqGG8baFcyGGTbqBcqGGPbqAcqGGUbGBdaGadeqaaiabdMgaPjabdsgaKjabcYcaSiabdMgaPjqbdsgaKzaafaaacaGL7bGaayzFaaaacaGLOaGaayzkaaaaleaacuWG2bGDgaqbaiabgIGiolqbdsfauzaafaaabeqdcqGHris5aaWcbaGaemODayNaeyicI4SaemivaqfabeqdcqGHris5aaWcbaGafmODayNbauaacqGHiiIZcuWGubavgaqbaaqab0GaeyyeIuoaaSqaaiabdAha2jabgIGiolabdsfaubqab0GaeyyeIuoaaaa@8E85@