Supplementary Materials for "Polyhedral Combinatorics of UPGMA Cones"

This webpage contains supplementary material for the paper Polyhedral Combinatorics of UPGMA Cones by Ruth Davidson and Seth Sullivant. 

The material on this page is devoted to the calculations of the spherical volumes of the UPGMA cones. In particular, we provide two mathematica notebooks for computing spherical volumes.

The first notebook uses a simple method to compute spherical volumes. We generate spherically uniformly random points in the positive orthant and apply the UPGMA algorithm to them, recording the number of times a particular chain in the partition lattice arises for trees with a fixed number n of leaves. We ran this code on size n = 4, 5, 6, 7.

To check the computations from the first notebook, we also implemented a variation on the method from the paper (Eickmeyer et al 2007, On the optimality of the neighbor-joining algorithm) using Monte Carlo integration to compute the spherical volume of each cone directly. Stated simply, the spherical volume of a simplical cone can be approximated by taking uniformly random samples from the flat simplex and taking the average value of the Jacobian of the map that takes a point in the flat simplex and maps it to the associated spherical simplex. Hence we must first triangulate our cones into simplicial cones and then compute the volumes of the resulting simplicial cones. After triangulating the cone for a given chain using polymake, we were able to use directly the code from the companion website. That method worked for trees with n=4,5,6 leaves.

For n = 7 leaf trees, it was not possible to compute the triangulation for the cone of a full chain, so we used a combination of the method from (Eickmeyer et al 2007) with the simpler method described above. Namely, we compute a triangulation of a cone associatated to a partial chain, use that the generate random samples, and then apply the UPGMA algorithm to see which chain is produced. For a typical complete chain, we compute the average value of the Jacobian times the indicator function of lying in a particular cone. This method appears in the second mathematica notebook.

Simple Spherical Volume Code

Jacobian Numerical Integration Spherical Volume Code

Zipped Files with Triangulations

All triangulations were computed using polymake. For n = 4,5,6, the files contain triangulations of each symmetry class of cone. For n = 7 the cones for displayed are for partial chains up to a partition with 5 elements. This is necessary because it is not possible to compute a triangulations of cone of a saturated chain in the partition lattice. We then use a MonteCarlo sampling strategy together with an implementation of the UPGMA algorithm to calculate the volumes of the cones.

n File
4 ZipFour.zip
5 ZipFive.zip
6 ZipSix.zip
7 ZipSeven.zip

Spherical Volume Tables

The tables below display the results of our spherical volume computations. The both in terms of chains in the partition lattice (i.e. ranked trees) and simply rooted trees.

In the tables for chains, the first column gives the chain in the partition lattice (minus the bottom 1|2|3|4 and top 1234 elements, which appear in every chain). The second columns gives the number of orbits in the symmetry class. The third column gives the number of rays in the cone. The fourth column is the number of simplices in the triangulation, computed with polymake. The fifth column is the spherical volume of the cone. The sixth column is the fraction of all of the sphere in the positive orthant which is taken up by all chains in the orbit of the given chain.

In the tables for trees, the first column gives the tree. The second column gives the number of trees in that orbit under symmetry. The third column gives the number of cones which make up the UPGMA region for the given tree. The fourth column gives the positions in the tree list of a particular cone appearing in the UPGMA list, together with its multiplicity. The fifth column gives the volume of the UPGMA region, and the sixth column gives the fraction of all of the sphere in the positive orthant which is taken up by all trees in the orbit of the given tree.

n = 4

  Chain Orbit Rays Simplices Volume Fraction
1 3|4|12 < 4|123 12 8 3 0.0238 0.5895
2 3|4|12 < 12|34 6 9 5 0.0331 0.4099

 

  Tree Orbit Cones Multiplicities Volume Fraction
1 (((12)3)4) 12 1 1(1) 0.0238 0.5895
2 ((12)(34)) 3 2 2(2) 0.0662 0.4099

 

n=5

  Chain Orbit Rays Simplices Volume Fraction
1 3|4|5|12 < 4|5|123 < 5|1234 60 22 48 8.57e-5 0.206
2 3|4|5|12 < 4|5|123 < 123|45 30 24 85 1.07e-4 0.129
3 3|4|5|12 < 5|12|34 < 5|1234 30 29 128 1.73e-4 0.208
4 3|4|5|12 < 5|12|34 < 12|345 30 31 176 1.57e-4 0.189
5 3|4|5|12 < 5|12|34 < 34|125 30 31 204 2.21e-4 0.267

 

  Tree Orbit Cones Multiplicities Volume Fraction
1 ((((12)3)4)5) 60 1 1(1) 8.57e-5 0.206
2 (((12)3)(45)) 30 3 2(1) 4(1) 5(1) 5.01e-4 0.604
3 (((12)(34))5) 15 2 3(2) 3.14e-4 0.189

 

n = 6

  Chain Orbit Rays Simplices Volume Fraction
1 3|4|5|6|12 < 4|5|6|123 < 5|6|1234 < 6|12345 360 65 5970 2.05e-8 0.042
2 3|4|5|6|12 < 4|5|6|123 < 5|6|1234 < 1234|56 180 68 10707 2.18e-8 0.022
3 3|4|5|6|12 < 4|5|6|123 < 6|123|45 < 6|12345 180 85 19342 4.24e-8 0.043
4 3|4|5|6|12 < 4|5|6|123 < 6|123|45 < 45|1236 180 88 30014 5.22e-8 0.053
5 3|4|5|6|12 < 4|5|6|123 < 6|123|45 < 123|456 180 89 28333 3.14e-8 0.032
6 3|4|5|6|12 < 5|6|12|34 < 5|6|1234 < 6|12345 180 102 25748 5.26e-8 0.054
7 3|4|5|6|12 < 5|6|12|34 < 5|6|1234 < 1234|56 90 105 44775 5.68e-8 0.029
8 3|4|5|6|12 < 5|6|12|34 < 6|12|345 < 6|12345 180 122 49184 7.17e-8 0.073
9 3|4|5|6|12 < 5|6|12|34 < 6|12|345 < 12|3456| 180 125 60501 4.98e-8 0.051
10 3|4|5|6|12 < 5|6|12|34 < 6|12|345 < 345|126 180 126 85073 8.36e-8 0.085
11 3|4|5|6|12 < 5|6|12|34 < 6|34|125 < 6|12345 180 122 60987 1.01e-7 0.103
12 3|4|5|6|12 < 5|6|12|34 < 6|34|125 < 34|1256 180 125 79760 8.60e-8 0.088
13 3|4|5|6|12 < 5|6|12|34 < 6|34|125 < 125|346

180

126 103937 1.10e-7 0.112
14 3|4|5|6|12 < 5|6|12|34 < 12|34|56 < 12|3456 90 153 158634 1.04e-7 0.053
15 3|4|5|6|12 < 5|6|12|34 < 12|34|56 < 34|1256 90 153 167870 1.27e-7 0.065
16

3|4|5|6|12 < 5|6|12|34 < 12|34|56 < 56|1234

90 152 186418 1.65e-7 0.084

 

  Tree Orbit Cones Multiplicities Volume Fraction
1 (((((12)3)4)5)6) 360 1 1(1) 2.05e-8 0.042
2 ((((12)3)4)(56)) 180 4 2(1) 4(1) 9(1) 13(1) 2.10e-7 0.216
3 ((((12)3)(45))6) 180 3 3(1) 8(1) 11(1) 2.16e-7 0.223
4 (((12)3)((45)6)) 90 6 5(2) 10(2) 13(2) 4.50e-7 0.229
5 ((((12)(34))5)6) 90 2 6(2) 1.05e-7 0.054
6 (((12)(34))(56)) 45 8 7(2) 14(2) 15(2) 16(2) 9.06e-7 0.231

 

n = 7

 

  Tree Chain Orbit Volume Fraction
1 1

3|4|5|6|7|12 < 4|5|6|7|123 < 5|6|7|1234 < 6|7|12345 < 7|123456

2520 2.75e-13 0.0049744
2 2 3|4|5|6|7|12 < 4|5|6|7|123 < 5|6|7|1234 < 6|7|12345 < 12345|67 1260 2.51e-13 0.0022673
3 3 3|4|5|6|7|12 < 4|5|6|7|123 < 5|6|7|1234 < 7|1234|56 < 7|123456 1260 5.03e-13 0.0045417
4 2 3|4|5|6|7|12 < 4|5|6|7|123 < 5|6|7|1234 < 7|1234|56 < 56|12347 1260 6.05e-13 0.005459
5 4 3|4|5|6|7|12 < 4|5|6|7|123 < 5|6|7|1234 < 7|1234|56 < 1234|567 1260 2.98e-13 0.0026894
6 5 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 6|7|12345 < 7|123456 1260 8.07e-13 0.0072787
7 6 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 6|7|12345 < 12345|67 630 7.67e-13 0.0034593
8 3 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 7|45|1236 < 7|123456 1260 1.52e-12 0.0137008
9 2 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 7|45|1236 < 45|12367 1260 1.26e-12 0.011364
10 4 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 7|45|1236 < 1236|457 1260 1.34e-12 0.0120465
11 7 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 7|123|456 < 7|123456 1260 1.06e-12 0.0095354
12 4 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 7|123|456 < 123|4567 1260 5.52e-13 0.0049807
13 4 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 7|123|456 < 456|1237 1260 1.18e-12 0.0106398
14 6 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 123|45|67 < 45|12367 630 1.89e-12 0.0085127
15 6 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 123|45|67 < 67|12345 630 2.40e-12 0.0108365
16 8 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 123|45|67 < 123|4567 630 1.18e-12 0.0053149
17 9 3|4|5|6|7|12 < 5|6|7|12|34 < 5|6|7|1234 < 6|7|12345 < 7|123456 1260 8.64e-13 0.0077927
18 10 3|4|5|6|7|12 < 5|6|7|12|34 < 5|6|7|1234 < 6|7|12345 < 12345|67 630 7.71e-13 0.0034796
19 11 3|4|5|6|7|12 < 5|6|7|12|34 < 5|6|7|1234 < 7|1234|56 < 7|123456 630 1.57e-12 0.0071016
20 10 3|4|5|6|7|12 < 5|6|7|12|34 < 5|6|7|1234 < 7|1234|56 < 56|12347 630 1.90e-12 0.0085622
21 8 3|4|5|6|7|12 < 5|6|7|12|34 < 5|6|7|1234 < 7|1234|56 < 1234|567 630 9.12e-13 0.0041119
22 5 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 6|7|12345 < 7|123456 1260 1.50e-12 0.0135731
23 6 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 6|7|12345 < 12345|67 630 1.42e-12 0.0064276
24 3 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 7|12|3456 < 7|123456 1260 1.57e-12 0.0141924
25 2 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 7|12|3456 < 12|34567 1260 9.07e-13 0.0081846
26 4 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 7|12|3456 < 3456|127 1260 1.54e-12 0.0138995
27 7 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 7|345|126 < 7|123456 1260 3.14e-12 0.0283524
28 4 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 7|345|126 < 126|3457 1260 2.98e-12 0.0268784
29 4 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 7|345|126 < 345|1267 1260 2.20e-12 0.0198035
30 6 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 12|345|67 < 12|34567 630 2.06e-12 0.0092775
31 6 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 12|345|67 < 67|12345 630 3.88e-12 0.0174857
32 8 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 12|345|67 < 345|1267 630 2.53e-12 0.011412
33 5 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 6|7|12345 < 7|123456 1260 2.14e-12 0.0193047
34 6 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 6|7|12345 < 12345|67 630 2.02e-12 0.0091143
35 3 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 7|34|1256 < 7|123456 1260 2.73e-12 0.0245906
36 2 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 7|34|1256 < 34|12567 1260 1.79e-12 0.0161872
37 4 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 7|34|1256 < 1256|347 1260 2.62e-12 0.0236879
38 7 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 7|125|346 < 7|123456 1260 4.08e-12 0.0367775
39 4 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 7|125|346 < 125|3467 1260 2.64e-12 0.0237894
40 4 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 7|125|346 < 346|1257 1260 4.19e-12 0.0377749
41 6 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 34|125|67 < 34|12567 630 3.75e-12 0.0169126
42 6 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 34|125|67 < 67|12345 630 5.90e-12 0.0265927
43 8 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 34|125|67 < 125|3467 630 3.64e-12 0.0164409
44 11 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 7|12|3456 < 7|123456 630 4.00e-12 0.0180277
45 10 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 7|12|3456 < 12|34567 630 2.34e-12 0.0105574
46 8 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 7|12|3456 < 3456|127 630 4.00e-12 0.0180387
47 11 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 7|34|1256 < 7|123456 630 4.81e-12 0.0217117
48 10 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 7|34|1256 < 34|12567 630 3.18e-12 0.0143589
49 8 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 7|34|1256 < 1256|347 630 4.82e-12 0.0217402
50 11 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 7|56|1234 < 7|123456 630 6.30e-12 0.0284111
51 10 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 7|56|1234 < 56|12347 630 4.96e-12 0.0223498
52 8 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 7|56|1234 < 1234|567 630 5.63e-12 0.0254009
53 6 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 12|34|567 < 12|34567 630 3.49e-12 0.0157426
54 6 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 12|34|567 < 34|12567 630 3.97e-12 0.0178949
55 8 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 12|34|567 < 567|1234 630 5.78e-12 0.0260501
56 6 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 12|56|347 < 12|34567 630 4.88e-12 0.021997
57 6 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 12|56|347 < 56|12347 630 6.53e-12 0.0294707
58 8 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 12|56|347 < 347|1256 630 8.01e-12 0.0361477
59 6 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 34|56|127 < 34|12567 630 6.56e-12 0.0295797
60 6 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 34|56|127 < 56|12347 630 7.72e-12 0.034846
61 8 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 34|56|127 < 127|3456 630

8.51e-12

0.0383664

 

  Tree Orbit Cones Multiplicities Volume Fraction
1 ((((((12)3)4)5)6)7) 2520 1 1(1) 2.75e-13 0.0049744
2 (((((12)3)4)5)(67)) 1260 5 2(1) 4(1) 9(1) 25(1) 36(1) 4.82e-12 0.0434621
3 (((((12)3)4)(56))7) 1260 4 3(1) 8(1) 24(1) 35(1) 6.32e-12 0.0570255
4 ((((12)3)4)((56)7)) 1260 10

5(1) 10(1) 12(1) 13(1) 26(1) 28(1) 29(1) 37(1) 39(1) 40(1)

1.95e-11 0.1761900
5 (((((12)3)(45))6)7) 1260 3 6(1) 22(1) 33(1) 4.45e-12 0.0401565
6 ((((12)3)(45))(67)) 630 15 7(1) 14(1) 15(1) 23(1) 30(1) 31(1) 34(1) 41(1) 42(1) 53(1) 54(1) 56(1) 57(1) 59(1) 60(1) 5.72e-11 0.2581498
7 ((((12)3)((45)6))7) 630 6 11(2) 27(2) 38(2) 1.66e-11 0.0746653
8 (((12)3)((45)(67))) 315 20 16(2) 21(2) 32(2) 43(2) 46(2) 49(2) 52(2) 55(2) 58(2) 61(2) 9.00e-11 0.2030237
9 (((((12)(34))5)6)7) 630 2 17(2) 1.73e-12 0.0077927
10 ((((12)(34))5)(67)) 315 10 18(2) 20(2) 45(2) 48(2) 51(2) 2.63e-11 0.0593079
11 ((((12)(34))(56))7) 315 8 19(2) 44(2) 47(2) 50(2) 3.33e-11 0.0752521