2.3 General approach

Depending on the specific question addressed, we did not work with the same sample of the
whole dataset. However, in all cases, the general approach for comparing two classifications
was the same and can be broken down into four steps.

In step 1, we selected the sub-sample: either the whole dataset with filters, or only the
individuals of a particular order, or a particular family. We then extracted the sub-matrix
corresponding to the *n* individuals in the sample from the global dissimilarity matrix.

In step 2, we built the classifications corresponding to AHC with the three aggregation
methods, Ward, Complete Linkage (CL) and Single Linkage (SL), and to SBM (see SI for
a description of these methods). The number of clusters *K* was provided by the botanical
classification of the individuals of the sub-sample. For instance if we wanted to study
adequacy between the classification into families and the molecular-based ones, we cut the
AHC hierarchy of classifications at *K* equal to the number of families in the sample, and
we ran SBM for the same value. At the end of step 2, we had five different classifications
of the individuals in the sub-sample.

In step 3, we compared the classifications, two by two, for each possible pair of classifi-
cations (10 pairs in total). We used a visual tool for preliminary analysis of the adequacy
between two classifications, with Sankey plots. A Sankey plot is a flow chart in which the
width of an arrow is proportional to the flow. For instance, if there are *n*<sub>kk'</sub> sequences that
are in class *k* for the botanical classification and *k'* for a numerical classification, there
is a flow of intensity *n*<sub>kk'</sub> between those two clusters. We computed an index as well, to
quantify the adequacy. Classification comparison is equivalent to the comparison of two
partitions of the same set, a dynamic research area with several surveys (Pfitzner et al.,
2009). Several indices were proposed and we chose the Normalised Mutual Information
(NMI1 in Pfitzner et al., 2009), which we will refer to as NMI (see SI for a formal def-
inition). It is not empirical and has a sound basis in information theory, as opposed to
indices based on counting pairs of elements that may be non-symmetric or non-bounded or even be dependent on *K* or *n*, making comparison difficult. NMI is normalised and, as such, bounded by 0 and 1, facilitating interpretation and comparison of indices. A NMI of 0 indicates independence between the two classifications, while a NMI of 1 indicates a perfect adequacy.

Finally, when replicates of the experiment are performed like in Section 2.4, in a fourth step, we analysed the distributions of the NMIs for a given pair of classifications in order to study trends in the adequacy, using histogram representation, boxplots and computing statistics on the distribution (mean, median, etc).

## 2.4 Comparison of botanical and molecular-based classification at the family and genus levels, on replicates

We worked with 30 sub-samples of the whole dataset, corresponding to the individuals of 10 orders and 20 families. We selected only orders (resp. families) composed of at least 15 individuals, and structured into more than one family (resp. genus). We then looked for the families present in one order or the genera present in one family. The orders are Malpighiales, Ericales, Sapindales, Laurales, Myrtales, Magnoliales, Gentianales, Rosales, Oxalidales and Malvales.

We structured the empirical analysis of the NMIs obtained (30 × 10 values) into four different analyses addressing the following questions: (i) What is the level of adequacy between the botanical classification and each of the four molecular-based ones? (ii) Are the classifications provided by the four molecular-based clusterings similar? (iii) Can we identify elements of the dissimilarity matrix that explain the variability observed in the answer to question (i) and that would be indicators of the adequacy/independence between the botanical classification and the molecular-based ones? (iv) How does the adequacy change between the botanical classification and the molecular-based ones when substituting
kmer-based distances for SW dissimilarities? In practice, for question (i), we considered only the NMIs involving the botanical classification and any of the four molecular-based ones, whereas for question (ii), we only considered the NMIs between any pairs of the molecular-based classifications. For question (iii), we studied three factors: the taxonomic level of the groups, the entropy of the botanical classification (defined as the entropy of the normalised vector of the group size), and the structure of the dissimilarity matrix. The latter was measured by three different ratios between the within-group dissimilarities and the between-group dissimilarities (see SI). We only present the one here that lead to the most interesting results, *r*<sub>mean</sub>, defined as the mean of the larger within-class dissimilarity over the mean of the smaller between-class dissimilarity.

## 2.5 Comparison of botanical and molecular-based classification with a wide scope of diversity

We looked at whether or not clustering on the whole dataset could directly retrieve botanical classification at levels higher than species (genera, families, orders). In addition, the same comparison was done for species as well, as a benchmark. Since several taxa are singletons, regardless of the level, or have a very small number of sequences (e.g. Apiales are represented by three sequences only in the whole sample), we built one subsample for each taxonomic level by filtering out taxa with less sequences than a given threshold. The size of those subsamples are given in Table 1, with the number of sequences and of different taxa per level, and the threshold selected for filtering sequences.

We ran SBM and Aggregative Hierarchical Clustering (AHC) with Ward, CL and SL, both on the matrix of dissimilarities between scores of the Smith-Waterman algorithm and on distances between tetramer frequencies. We compared each of these four classifications with the botanical one using NMI. As for the study of the replicates, we also computed the entropy and the *r*<sub>mean</sub> ratio of the botanical orders, families, genera and species clas-
267 sifications. For each of the taxonomic levels, we produced a visual graphical analysis by
268 generating Sankey plots.

269 **3 Results**

270 **3.1 Visualisation of the whole dataset using MDS**

271 We represented the shape of the point cloud on the first two axes built with MDS on the
272 dissimilarity matrix, with points coloured according to the order that they belong to (see
273 Figures 1 and 2). For Smith-Waterman-based dissimilarities, axis 1 clearly distinguishes
274 Ericales (in purple) and Sapindales (dark green), and axis 2, Malpighiales (in light green).
275 Axis 3 distinguishes Fabales (blue), and the set of Laurales and Magnoliales (red and
276 orange), which are primitive Eudicots. The organisation of the point cloud is different
277 for kmer-based dissimilarities. The point cloud is more compact. Axis 1 distinguishes
278 the same set of Laurales and Magnoliales, and axis 2 distinguishes Fabales. Clearly, the
279 shape of the point cloud based on Smith-Waterman distances is more closely related to the
280 organisation of specimens in botanical orders. Such a connection is blurred for kmer-based
281 distances. This allowed us to predict that adequacy between the botanical classification
282 and the molecular-based ones will be lower when using kmer-based distances.

283 **3.2 Comparison of botanical and molecular-based classification**
284 **at the family and genus levels on replicates**

285 We present first the results obtained with SW scores for points (i) to (iii) raised in Section
286 2.4. We then show how results change when working with kmer-based distances (point
287 (iv)).

288 (i) Level of adequacy between the botanical classification and the molecular-based ones. For SBM, Ward, SL and CL, the shape of the histogram of the 30 NMIs
289
290 is the same (see Figure 1 of SI). The mode is observed at large values: NMIs are larger
291 than 0.9 for one-third of the replicates. Then, intermediate values of the NMI are not often
292 observed, in particular, in the case of the NMIs between SL and the botanical classification.
293 Median values of the histograms vary between 0.68 (for SBM) and 0.87 (for Ward) (see
294 Table 3). So globally we observe a good to very good adequacy between the botanical and
295 the molecular-based classification, with better performance for the Ward method.

296 (ii) **Mutual adequacy of the responses of the four molecular-based clustering**
297 methods. There is a strong adequacy between the three AHC methods. We observed
298 larger NMIs between Ward and CL than between Ward and SL or CL and SL. The SBM
299 classification is globally in good adequacy with the three AHC ones (NMI median larger
300 than 0.64) and is closer to the CL and the Ward classifications (see Table 4 with statistics
301 of the NMI distributions).

302 (iii) **Factors explaining variability in the results.** When pooling the results for
303 the four molecular-based classifications, we observed no clear difference in the distribution
304 of the NMIs (NMIs are between the botanical classification and the molecular-based ones)
305 computed on replicates whose groups are at the family level and those at the genus level.
306 We observed a trend towards an increase in adequacy between botanical and molecular-
307 based classifications when the entropy of the sub-sample increases (Figure 3 left side). This
308 effect is observed for both dissimilarities.

309 We also observed a clear decrease of the adequacy when $r_{mean}$ increases (see Figure 3 right
310 side). Adequacy is good to strong (larger than 0.7) for a ratio lower than 1. When a
311 dissimilarity matrix is associated with a large ratio, it means that several sequences exist
312 that are closer to sequences belonging to a different genus or family than to sequences in
313 their own genus or family.

314 (iv) **Influence of the choice of dissimilarity.** We observed a systematic decrease
315 of the NMIs when substituting the SW dissimilarity with the kmer-based distance (Table
316 2). This decrease ranged between 5 % to 39 % depending on the taxonomic level of the
groups and the molecular-based clustering method, and it appear to be higher for SL. The adequacy with the botanical classification is the highest for the Ward-based classification, and we still observed the influence of the entropy of the botanical classification and of $r_{mean}$ on the adequacy (Figure 2 in SI).

In conclusion, adequacy between the botanical classification and molecular-based ones can be good to very good. However, there are also situations where the adequacy is low. We have identified several factors that can influence the level adequacy: the choice of the clustering method, with Ward leading to the greatest adequacy; the choice of the dissimilarity, with a greater adequacy for SW dissimilarities than for kmer-based distances; the entropy of the botanical classification, with greater adequacy for larger entropies; $r_{mean}$, with greater adequacy for lower ratios.

## 3.3 Comparison of botanical and molecular-based classification with a wide scope of diversity

The results presented here extend the results on the points (i), (iii) and (iv) with four new experiments: we compared, on the one hand, the botanical classifications of the whole dataset partitioned into 11 orders, 20 families and 36 genera, as well as 55 species as a benchmark, (see Table 1) and, on the other, the molecular-based classifications obtained for the same number of classes.

(i) Level of adequacy between the botanical classification and the molecular-based ones. On Figure 4 one curve per method displays the evolution of the NMI along a gradient of taxonomic levels running over species, genera, families and orders. All curves, regardless of the molecular-based clustering method and the dissimilarity, display a decrease from species to orders. All of the methods are excellent for identifying species (NMI ~ 0.8), and decreases depend on the method: a slight decrease for the Ward method, a sharp
decrease for the SL method, and an intermediate decrease for CL or SBM. SL seems to
display poorer indices regardless of the distance for orders or even families. To illustrate
this, the correspondence between botanical, Ward and SBM classifications obtained with
SW dissimilarities are graphically visualised in Figure 5 for orders and Figure 6 for families,
with Sankey plots. We can note two types of behaviour: a botanical group is split into
several groups in Ward or SBM classifications or, on the contrary a Ward or SBM group
is composed of individuals from several botanical groups. The latter is more problematic
when interpreting molecular-based classifications. On Figure 7, we can observe that the
low NMI for SL at the order level is due to the creation of a giant cluster formed by almost
all of the orders present in the dataset.

(iii) **Factors explaining variability in the results.** The fact that adequacy between the molecular-based and the botanical-based classifications decreases when the taxonomic level of the groups searched increases is in agreement with the influences of the entropy and of the *r*<sub>mean</sub> observed on the replicates. Indeed entropy here decreases and *r*<sub>mean</sub> increases when moving from the classification into species and genera towards families and orders (see Table 5).

(iv) **Influence of the choice of dissimilarity.** Regardless of the AHC method and the taxonomic level, NMI is higher for SW-based dissimilarities than with kmer-based distances. The decrease in the NMIs is stronger when the groups are families or orders: NMIs varied between 7% and 67% with the larger decrease observed for SL. SBM seems to be less sensitive to the measure of dissimilarities between sequences, with even, in some cases, a larger NMI with the kmer-based distances.

4 Discussion

In this study, several numerical methods were compared on a well-known dataset of ap-
proximately 1,500 specimens of trees in a French Guianese forest for the purpose of quan-
367 tifying the adequacy between, on the one hand, botanical classification and, on the other,
368 molecular-based classification on an array of genetic distances, on deep nodes of classifica-
369 tions. We discuss here the results provided for this purpose.

4.1 Adequacy between botanical and molecular-based classifica-
tions

372 There is one pattern common to the study based on the clusterings of the 30 replicates
373 and the clusterings performed on the whole dataset: regardless of the combination between
374 taxonomic level and dissimilarity, AHC with the Ward aggregation criterion provides the
375 best adequacy. Other methods rank differently depending on these combinations. Ade-
376 quacy can be high, in particular when the molecular-based clustering is based on the SW
377 dissimilarity. However, we also occasionally observed low adequacy, and we will discuss
378 the reasons for this. When interpreting NMI values, it is important to have in mind that
379 NMI is conservative in the sense that a strong adequacy is required to obtain a large NMI
380 value. The strength of the adequacy could be higher with another choice of index, but we
381 selected NMI partly for this conservative behaviour.

382 A strong assumption in our study is that the number of groups *K* in the botanical
383 classification is known when performing the molecular-based clustering. This is obviously
384 not the case in real situations, like in metabarcoding of environmental samples. When *K*
385 is not available, classical tools for model selection can be used to estimate a number of
386 groups that lead to a trade-off between a good explanation of the dissimilarity matrix and
387 parsimony. However, these criteria do not include a goal of adequacy with the botanical
388 classification. In White et al. (2010), to compare molecular-based clustering at the OTU
389 level and the taxonomic classification, the authors used partial assignment of the sequences
390 and the VI-cut method to automatically determine the number of OTUs. The method relies
391 on the Value of Information to compare two clusterings, which we did not select for our
study because it is not normalised. However, the VI-cut method could easily be extended
to the NMI index and therefore provide a way to estimate the number of groups, driven by
the partial taxonomic knowledge that is available on some sequences of the inventory.

Although neighbor-joining (Saitou and Nei, 1987) is one of the reference methods in
phylogenies, and based on distances, we have not retained it in our study for two reasons.
First, the adequacy between orders and clades<fnref n="2" /> (monophyly of orders) in the tree is not
excellent (see section 5 and Figure 5 in SI), and second, neighbor-joining is not a clustering
method: the outcome cannot be automatically organized as a partition into clusters.

## 4.2 Adequacy of botanical classification and the AHC classifications

In our result, a variability of quality is observed according to the linkage method. If the
dataset is organised as a set of isolated clusters, all linkage methods will find it and provide
the same classification. If not, different linkage methods will yield different classifications.
Not surprisingly, we recover these behaviours in our experiments on molecular-based clus-
tering of the tree specimens.

**Ward method:** The Ward method nearly always led to the best adequacy with botanical classification, regardless of the measurement of distance (SW or kmers) and the taxonomic level of the groups (Sections 3.2 and 3.3).

**Complete linkage Method** The CL method generally led to the second-best adequacy with the botanical classification. It provided classifications very similar to those obtained with the Ward method (see Table 4).

<footnote n="2">²A clade here is an internal node with its descent.</footnote>
**Single linkage method:** On the contrary, adequacy between the classification provided by the SL method and the botanical classification was highly variable and could be either very good or very poor. The adequacy was very poor with the classification into orders of the whole dataset (NMI = 0.06 for SW dissimilarities and NMI = 0.02 for kmer-based distances, which is very close to independence), better but still low for the classification into families (NMI = 0.44 for SW dissimilarities, and NMI = 0.34 for kmer-based distances). A reason for that can be seen on Figure 7: the SL classification is composed of a huge cluster, containing sequences from all orders, and a set of much smaller clusters, each containing one, seldom two, orders. The creation of the huge cluster may be due to low dissimilarities existing between the orders. By nature, the SL criterion will link these orders. This is a well-known drawback of SL.

## 4.3 Interest of SBM models for molecular-based classification

Even if the SBM clustering and the botanical one are in very good adequacy in some of the experiments, globally, the NMI values for SBM are lower than the NMIs for the best AHC method (see Table 2 and Figure 4). When adequacy with the botanical classification is good, then the SBM classification resembles the one obtained with the Ward method (Table 4). This is the case where the dissimilarity matrix is well structured into communities, and all clustering methods will perform well. When adequacy is low, our interpretation is the following. The main difference between AHC and SBM clustering is that AHC looks for groups with small within-group dissimilarity (communities), while SBM seeks for groups such that an individual in group *k* shares, with the other members of group *k*, the same pattern of connections with the other groups, and members of group *k* are almost at the same distance to each others. However, this distance is not necessarily small, meaning that SBM groups should not be systematically interpreted as communities. When the matrix of the pairwise dissimilarities is not clearly structured according to the botanical groups, SBM clustering can create groups with individuals that are far from each other. This is
what we observed on the SBM classification of the whole dataset into orders (both for the SW and the kmer-based clustering). For several SBM groups, the estimated parameter characterising the mean within group distance (mean of the Poisson distribution or of the Gaussian distribution) was larger than the lower mean distance with the other groups. In these situations, the NMI between the botanical and the SBM classification will obviously be low, and the ratio *r*<sub>mean</sub> will be large. A SBM classification with groups of large within-group mean distances should be a warning that the matrix of dissimilarities is not entirely structured according to the botanical classes. For similar reasons, SBM will also be able to detect outlier individuals by gathering them into a group, while methods looking for communities will force them to enter a community. For these reasons, we think SBM should be considered as a valuable tool for (meta)barcoding.

## 4.4 Factors explaining the variations in the adequacy.

One of the two main factors influencing the quality of adequacy between the botanical and the molecular-based classifications is the relative difference between the dissimilarities within and between groups in botanical classification. This notion was well captured by the *r*<sub>mean</sub> ratio and, we obtained a clear tendency for NMIs to decrease when the ratio increases on the 30 replicates (Figure 3). When considering the clustering of the whole dataset, the same tendency was observed. The other factor influencing the quality of adequacy is the value of the entropy of the distribution of the group sizes in the botanical classification. We observed a tendency for an increase in adequacy when entropy increases, both on the 30 replicates and when clustering the whole dataset at different taxonomic levels.

In the latter experiments we obtained a clear decrease of adequacy when the taxonomic level increases, whereas in the experiments on the 30 replicates, adequacy was better at the family level than at the genus level. These apparent contradictory results are actually explained by the fact that they correspond to two different protocols. On the 30 replicates the targeted set of sequences to cluster is different for each replicate: we did not search for
families and genera among the same set of individuals. We instead searched for families (resp. genera) of sequences of the same order (resp. family).

The negative influence of the *r*<sub>mean</sub> ratio and the positive influence of the entropy are global tendencies. We also observed variations around these main tendencies, which means that they are probably not the only factors explaining the NMI values. Still, they are strong signals.

## 4.5 Biological interpretation

We can expect that it is more difficult to cluster a set of individuals in a right way when the number of targeted groups increases (more possibilities to ill-classify). It is not that simple and actually depends on the structure of the dissimilarity matrix. Indeed, in our study on the whole dataset, the adequacy between the molecular-based and the botanical-based classification is better when groups are at a low taxonomic level, hence more numerous, regardless of the method and the distance (see Figure 4). As discussed in Section 4.4, the *r*<sub>mean</sub> ratio, implying distances within a group over distances between groups, is smaller when groups are families than when they are orders. This suggests that families are better delineated than orders by pairwise distances. The results shown in Figure 4 extend this observation to species over genera, and show that molecular-based delineation of taxa is more accurate at fine taxonomic levels than at coarse ones. This can be related to the observation that only species have a sound biological meaning, whereas genera, families and orders are constructions based on similarities.

## 4.6 Comparison between SW and kmer-based dissimilarities

Computing SW dissimilarity between two sequences is the most precise way to compare them. However, it is time-consuming. Computing kmer-based distances is much quicker, but at the cost of approximations. The two 1D histograms of SW dissimilarities and kmer-
based distances are provided on Figures 3 and 4 of SI). A coarse correlation can be observed between both quantifications of dissimilarities (see Figure 8), stronger for small dissimilarities. However, a significant number of pairs of sequences exists with a very low SW dissimilarity and a significant kmer-based distance. This is due to the high variability in length of the trnH marker. For instance, a small SW dissimilarity means that the smallest sequence is nearly identical to a contiguous sub-sequence of the larger one. However, due to the dissimilarity in length of the two sequences, the kmer histograms cannot be similar, and the kmer-based distance is large. Therefore, some small values of the SW dissimilarity can be associated with median values of the kmer-based distance. Since the AHC classification (regardless of the linkage) builds groups of individuals with small within group distances, it can be expected that the SW-based and the kmer-based classifications will be different. In practice, as expected, we observed that adequacy decreases when substituting kmers for SW regardless of the combination between the taxonomic level and the clustering method. However, substituting kmer-based distances for SW dissimilarities did not lead to a real collapse of molecular-based methods.

It can be observed that NMIs between the botanical classification and the SBM one seem to be less sensitive to the dissimilarity used than NMIs between botanical and AHC classifications (see Figure 4 and Table 2). This is probably due to the fact that, as opposed to AHC, SBM does not build the groups on a criterion that minimises within-group distances, as explained in section 4.3.

## 4.7 Perspectives for metabarcoding

The dataset is sufficiently small for all calculations to be run on a laptop in a reasonable time, making it possible to focus on a comparison of the methods. Some methods are clearly more accurate than others to retrieve orders or families in our dataset. The expectation is that those methods are those that will permit inventories or clustering at higher taxonomic levels like families, orders or phyla in metabarcoding. We therefore make two
515 recommendations.

516 First, we recommend using AHC with the Ward method for clustering regardless of the
517 taxonomic level, and not using AHC with Single Linkage which may produce poor results,
518 despite the observation that current softwares scaling up with NGS massive datasets make
519 it possible to use it (like MOTHUR) or yield results very close to it (like SWARM, see
520 Mahé et al., 2014). It can be observed that SWARM, close to SL, yields giant clusters that
521 are cut into pieces by a sort of pruning.

522 Second we recommend using SBM classification to detect, via the estimated distribution
523 of within cluster distances, situations where the molecular-based classifications may be
524 poorly related to the morphological-based one (because the dissimilarity matrix is not
525 clearly structured into communities).

526 These results and observations lead us to recommend the pursuit of methodological
527 efforts to analyse metabarcoding data for building inventories at the coarse level (i.e.,
528 between phyla and orders). Inventories at the coarse level are a first step towards the
529 global exploration of diversity of unknown groups. This can be done in two ways. First,
530 nearly all surveys about clustering emphasize that there is no method that is perfect and
531 better than some others for all evaluation criteria (see, e.g., Fahad et al., 2014). Therefore,
532 it may be useful to produce classifications by several numerical methods and to extract
533 the shared elements. These are the ones in which the user can be more confident that
534 they effectively reflect an actual structure in the data. Second, scaling-up methods that
535 have proven themselves to properly perform on well-known datasets, like AHC with Ward
536 linkage or SBM-based clustering, is a key issue. A very efficient method for clustering may
537 be like "divide and conquer": first, dividing the problem by building connected components
538 in a graph built from pairwise distances and, second, conquering by implementing AHC
539 Ward or SBM in each connected component.

540 More globally, connecting these efforts with studies on wider classes of methods un-
541 der development for clustering for big-data (Fahad et al., 2014) is a challenging issue for
542 metabarcoding.

543

# 5 Acknowledgements

544

545

546

547

548

549

550

The authors acknowledge support of an “Investissement d'Avenir” grant managed by the Agence Nationale de la Recherche (CEBA, ref. ANR-10-LABX-25-01). M.A. Abouabdallah PhD is funded by INRAE and by INRIA. The authors acknowledge the work done by H. Caron (sequencing), D. Sabatier and J.F. Molino (botanical assignation of trees) for a previous work that we have used here. We thank Jean-Marc Frigerio for many useful discussions for data management and analysis, as well as Philippe Chaumeil for his contribution to the programs to compute dissimilarities.

551

# 6 Author contributions

552

553

554

A.F. and N.P. designed the study. M.A.A., A.F. and N.P. performed the research and analyzed the data. The paper was drafted by M.A.A., A.F. and N.P. and written by A.F. and N.P. All authors commented on and approved the final manuscript.

555

# 7 Data accessibility

556

557

558

559

Sequences used to compute distances are in NCBI under accession number KX247940–KX249593.

A fasta file with these sequences, a file with taxonomical assignation for each tree, as well as pairwise Smith-Waterman and kmer distances are publicly available at

https://doi.org/10.15454/XSJ079 in Inrae Data Portal.

560

# References

561

562

Altschul, S. F., Gish, W., Miller, W., Myers, E. W., and Lipman, D. J. (1990). Basic local alignment search tool. *Journal of Molecular Biology*, 215:403–410.
563 Barbillon, P., Donnet, S., Lazega, E., and Bar-Hen, A. (2017). Stochastic block-models for multiplex networks: An application to a multilevel network of researchers. *Journal of the Royal Statistical Society: Series A Statistics in Society*, 180(1):295-314.

566 Bik, H. M., Porazinska, D. L., Creer, S., Caporaso, J. G., Knight, R., and Thomas, W. K. (2012). Sequencing our way towards understanding global eukaryotic biodiversity. *Trends in Ecology and Evolution*, 27:233-243.

569 Blaxter, M., Mann, J., Chapman, T., Thomas, F., Whitton, C., Floyd, R., and Abebe, E. (2005). Defining operational taxonomic units using DNA barcode data. *Philosophical Transactions of the Royal Society B*, 360:1935-1943.

572 Caron, H., Molino, J.-F., Sabatier, D., Léger, P., Chaumeil, P., Scotti-Saintagne, C., Frigério, J.-M., Scotti, I., Franc, A., and Petit, R. J. (2019). Chloroplast DNA variation in a hyperdiverse tropical tree community. *Ecology and Evolution*, 9(8):4897-4905.

575 Cole, A. J., editor (1969). *Numerical Taxonomy*. Academic Press, London & New York.

576 Cox, T. and Cox, M. A. A. (2001). *Multidimensional Scaling - Second edition*, volume 88 of *Monographs on Statistics and Applied Probability*. Chapman & al.

578 Daudin, J.-J., Picard, F., and Robin, S. (2008). A mixture model for random graphs. *Statistics and Computing*, 18:173-183.

580 Edgar, R. C. (2010). Search and clustering orders of magnitude faster than BLAST. *Bioinformatics*, 26:2460-2461.

582 Fahad, A., Alshatri, N., Tari, Z., Alamri, A., Khalil, I., Zomaya, A. Y., Foufou, S., and Bouras, B. (2014). A Survey of Clustering Algorithms for Big Data: Taxonomy and Empirical Analysis. *IEEE Transactions on Emerging Topics on Computing*, 2(4):267-279.

586 Faskowitz, J., Yan, X., Zuo, X.-N., and Sporns, O. (2018). Weighted stochastic block models of the human connectome across the life span. *Scientific Reports*, 8.

588 Felsenstein, J. (2004). *Inferring phylogenies*. Sinauer.

589 Floyd, R., Abebe, E., Papert, A., and Blaxter, M. (2002). Molecular barcodes for soil nematode identification. *Molecular Ecology*, 11:839-850.

591 Fontaneto, D., Boschetti, C., and Ricci, C. (2008). Cryptic diversification in ancient asexuals: evidence from the bdelloid rotifer *Philodina flaviceps*. *Journal of Evolutionary Biology*, 21:580-587.

594 Frigerio, J.-M., Caron, H., Sabatier, D., Molino, J.-F., and Franc, A. (2021). Guiana Trees. Portail Data INRAE, V1, DOI: 10.15454/XSJ079.

596 Gusfield, D. (1997). *Algorithms on strings, trees, and sequences*. Cambridge University Press, Cambridge, UK.
598

Hajibabaei, M., Shokralla, S., Zhou, X., Singer, G. A. C., and Baird, D. J. (2011). Environmental barcoding: a next generation sequencing approach for biomonitoring applications using river benthos. *PLoS One*, 6(4):e17497.

599

600

601

Hao, X., Jiang, R., and Chen, T. (2011). Clustering 16S rRNA for OTU prediction: a method of unsupervised Bayesian clustering. *Bioinformatics*, 27(5):611-618.

602

603

Hebert, P. D. N., Cywinska, A., Ball, S. L., and deWaard, J. R. (2003). Biological identifications through DNA barcodes. *Proceedings of the Royal Society of London B*, 270:313-321.

604

605

Hillis, D. M., Moritz, C., and Mable, B. (1996). *Molecular Systematics*. Sinauer, Sunderland, Mass.

606

607

Holland, P., Laskey, K., and Leinhardt, S. (1983). Stochastic blockmodels: First steps. *Social Networks*, 5(2):109-137.

608

609

Izenman, A. J. (2008). *Modern Multivariate Statistical Techniques*. Springer, NY.

610

Ji, Y., Ashton, L., Pedley, S. M., Edwards, D. P., Tang, Y., Nakamura, A., Kitching, R., Dolman, P. M., Woodcock, P., Edwards, F. A., Larsen, T. H., Hsu, W. X., Benedick, S., Hamer, K. C., Wilcove, D. S., Bruce, C., Wang, X., Levi, T., Lott, M., Emerson, B. C., and Yu, D. W. (2013). Reliable, verifiable and efficient monitoring of biodiversity via metabarcoding. *Ecology Letters*, 16(10):1245-1257.

611

612

613

614

615

Kermarrec, L., Franc, A., Rimet, F., Chaumeil, P., Humbert, J.-F., and Bouchez, A. (2013). Next-generation sequencing to inventory taxonomic diversity in eukaryotic communities: a test for freshwater diatoms. *Molecular Ecology Resources*, 13:607-619.

616

617

618

Lee, C. and Wilkinson, D. (2019). A review of stochastic block models and extensions for graph clustering. *Applied Network Science*, 4(122).

619

620

Leray, M. and Knowlton, N. (2015). DNA barcoding and metabarcoding of standardized samples reveal patterns of marine benthic diversity. *PNAS*, 112(7):2076-2081.

621

622

López-García, P., Rodriguez-Valera, F., Pedros-Alio, C., and Moreira, D. (2001). Unexpected diversity of small eukaryotes in deep-sea Antarctic plankton. *Nature*, 409:603-607.

623

624

Mahé, F., Rognes, T., Quince, C., de Vargas, C., and Dunthorn, M. (2014). Swarm: robust and fast clustering method for amplicon-based studies. *PeerJ*, 2:e593.

625

626

Miele, V. and Matias, C. (2017). Revealing the hidden structure of dynamic ecological networks. *Royal Society Open Science*, 4(6).

627

628

Munch, K., Boomsma, W., Huelsenbeck, J. P., Willerslev, E., and Nielsen, R. (2008). Statistical Assignment of DNA Sequences Using Bayesian Phylogenetics. *Systematic Biology*, 57(5):750-757.

629

630

631

Murtagh, F. (1983). A survey of recent advances in hierarchical clustering algorithms. *The Computer Journal*, 26(4):354-359.

632
633

634

Müllner, D. (2013). `fastcluster`: Fast Hierarchical, Agglomerative Clustering Routines for R and Python. *Journal of Statistical Software*, 53(9):1–18.

635

636

Pfitzner, D., Leibbrandt, R., and Powers, D. (2009). Characterization and evaluation of similarity measures for pairs of clusterings. *Knowledge and Information Systems*, 19(361).

637

638

639

Pons, J., Barraclough, T. G., Gomez-Zurita, J., Cardoso, A., Duran, D. P., Hazell, S., Kamoun, S., Sumlin, W. D., and Vogler, A. (2006). Sequence-Based Species Delimitation for the DNA Taxonomy of Undescribed Insects. *Systematic Biology*, 55(4):595–609.

640

641

642

Puillandre, N., Modica, M. V., Zhang, Y., Sirovich, L., Boisselier, M.-C., Cruaud, C., Holford, M., and Samadi, S. (2012). Large-scale species delimitation method for hyperdiverse groups. *Molecular Ecology*, 21:2671–2691.

643

644

645

Sabatier, D., Grimaldi, M., Prévost, M., Guillaume, J., Godron, M., Dosso, M., and Curmi, P. (1997). The influence of soil cover organization on the floristic and structural heterogeneity of a guianan rain forest. *Plant Ecology*, 131:81–108.

646

647

Saitou, N. and Nei, M. (1987). The neighbor-joining method: a new method for reconstructing phylogenetic trees. *Molecular Biology and Evolution*, (4):406–425.

648

649

Smith, P. D. and Waterman, M. S. (1981). Identification of common molecular sub sequences. *Journal of Molecular Biology*, 147:195–197.

650

Sneath, R. H. A. and Sokal, R. R. (1973). *Numerical taxonomy*. Freeman, San Francisco.

651

652

653

Sogin, M. L., Morrison, H. G., Huber, J. A., Welch, D. M., Huse, S. M., Neal, P. R., Arrieta, J. M., and Herndl, G. J. (2006). Microbial diversity in the deep sea and the underexplored “rare biosphere”. *PNAS*, 103(32):12115–12120.

654

655

656

Sun, Y., Cai, Y., Liu, L., Yu, F., Farrell, M. L., McKendree, W., and Farmerie, W. (2009). *ESPRIT: estimating species richness using large collections of 16S rRNA pyrosequences*. *Nucleic Acids Research*, 37(10):e76.

657

658

659

Taberlet, P., Coissac, E., Pompanon, F., Brochman, C., and Willerslev, E. (2012). Towards next-generation biodiversity assessment using DNA metabarcoding. *Molecular Ecology*, 21:2045–2050.

660

661

662

Talavera, G., Dinca, V., and Vila, R. (2013). Factors affecting species delimitations with the GMYC model: insights from a butterfly survey. *Methods in Ecology and Evolution*, 4:1101–1110.

663

664

665

666

667

The Angiosperm Phylogeny Group, Chase, M. W., Christenhusz, M. J. M., Fay, M. F., Byng, J. W., Judd, W. S., Soltis, D. E., Mabberley, D. J., Sennikov, A. N., Soltis, P. S., and Stevens, P. F. (2016). An update of the Angiosperm Phylogeny Group classification for the orders and families of flowering plants: APG IV. *Botanical Journal of the Linnean Society*, 181(1):1–20.
668

669

Torgerson, W. S. (1952). Multidimensional Scaling: I. Theory and Method. *Psychometrika*, 17(4):401–419.

670

671

672

White, J. R., Navlakha, S., Nagarajan, N., Ghodsi, M.-R., Kingsford, C., and Pop, M. (2010). Alignment and clustering of phylogenetic markers - implications for microbial diversity studies. *BMC Bioinformatics*, 11(152):1471–2105.

673

674

Yang, Z. (2006). *Computational Molecular Evolution*. Oxford Series in Ecology and Evolution. Oxford University Press.

675

676

Zhang, J., Kapli, P., Pavlidis, P., and Satamakis, A. (2013). A general species delimitation method with applications to phylogenetic placements. *Bioinformatics*, 29(22):2869–2876.
# 8 Tables

<table><caption>Table 1: Properties of the four subsamples of sequences, one per taxonomic level. The number of sequences in the sample is lower for low taxonomic levels because we selected only taxa composed of a minimal number of sequences, and there are less sequences of a given species than of a given genera, etc. Each subsample is used for a comparison between the molecular-based clustering methods and the botanical classification.</caption><thead><tr><th>Taxonomic level</th><th>Number of sequences</th><th>Number of taxa</th><th>Minimal size of a taxon</th></tr></thead><tbody><tr><td>Species</td><td>313</td><td>55</td><td>5</td></tr><tr><td>Genera</td><td>845</td><td>36</td><td>10</td></tr><tr><td>Families</td><td>1349</td><td>30</td><td>10</td></tr><tr><td>Orders</td><td>1357</td><td>11</td><td>15</td></tr></tbody></table>

<table><caption>Table 2: Normalised Mutual Information between the botanical classification (into families or into genera) and the four molecular-based classifications (row) for two dissimilarities (column). SW stands for Smith-Waterman and kmer for kmer-based distances computed with kmers of length *k* = 4. Results for families are median values over 10 samples and results for genera are median values over 20 samples. A sample is the set of sequences of an order (10 of them) or a family (20 of them).</caption><thead><tr><th rowspan="2">Method</th><th rowspan="2"></th><th colspan="2">Families</th><th colspan="2">Genera</th><th colspan="2">Pooled</th></tr><tr><th>SW</th><th>kmers</th><th>SW</th><th>kmer</th><th>SW</th><th>kmer</th></tr></thead><tbody><tr><td rowspan="3">AHC</td><td>Ward</td><td>1</td><td>0.61</td><td>0.83</td><td>0.73</td><td>0.87</td><td>0.71</td></tr><tr><td>SL</td><td>0.88</td><td>0.54</td><td>0.75</td><td>0.59</td><td>0.76</td><td>0.58</td></tr><tr><td>CL</td><td>0.85</td><td>0.63</td><td>0.75</td><td>0.71</td><td>0.75</td><td>0.67</td></tr><tr><td>SBM</td><td></td><td>0.57</td><td>0.52</td><td>0.82</td><td>0.66</td><td>0.68</td><td>0.63</td></tr></tbody></table>
<table><caption>Table 3: Statistics on the distribution of the Normalised Mutual Information (NMI) computed between each molecular-based classification and the botanical one. The statistics are computed on the NMIs obtained on 30 replicates (10 classifications into families and 20 into genera). A sample is the set of sequences of an order (10 of them) or a family (20 of them). Results obtained using the Smith-Waterman dissimilarity.</caption><thead><tr><th>Pairs of methods</th><th>Min.</th><th>1st Qu.</th><th>Median</th><th>Mean</th><th>3rd Qu.</th><th>Max.</th></tr></thead><tbody><tr><td>SL vs. botanical</td><td>0.013</td><td>0.27</td><td>0.76</td><td>0.64079</td><td>1.00</td><td>1.00</td></tr><tr><td>Ward vs. botanical</td><td>0.05</td><td>0.40</td><td>0.87</td><td>0.73</td><td>1.00</td><td>1.00</td></tr><tr><td>CL vs. botanical</td><td>0.03</td><td>0.47</td><td>0.75</td><td>0.68</td><td>1.00</td><td>1.00</td></tr><tr><td>SBM vs. botanical</td><td>0.10</td><td>0.33</td><td>0.68</td><td>0.64</td><td>0.98</td><td>1.00</td></tr></tbody></table>

<table><caption>Table 4: Statistics on the distribution of the Normalised Mutual Information (NMI) computed between each pair of molecular-based classifications. The statistics are computed on the NMIs obtained on 30 replicates (10 classifications into families and 20 into genera). A sample is the set of sequences of an order (10 of them) or a family (20 of them). Results obtained using the Smith-Waterman dissimilarity.</caption><thead><tr><th>Pairs of methods</th><th>Min.</th><th>1st Qu.</th><th>Median</th><th>Mean</th><th>3rd Qu.</th><th>Max.</th></tr></thead><tbody><tr><td>SBM Vs SL</td><td>0.039</td><td>0.30</td><td>0.65</td><td>0.59</td><td>0.98</td><td>1.00</td></tr><tr><td>SBM vs. Ward</td><td>0.31</td><td>0.52</td><td>0.74</td><td>0.74</td><td>1.00</td><td>1.00</td></tr><tr><td>SBM vs. CL</td><td>0.11</td><td>0.47</td><td>0.65</td><td>0.67</td><td>0.91</td><td>1.00</td></tr><tr><td>SL vs. Ward</td><td>0.04</td><td>0.34</td><td>0.78</td><td>0.69</td><td>1.00</td><td>1.00</td></tr><tr><td>SL vs. CL</td><td>0.05</td><td>0.56</td><td>0.84</td><td>0.74</td><td>1.00</td><td>1.00</td></tr><tr><td>Ward vs CL</td><td>0.05</td><td>0.70</td><td>0.86</td><td>0.80</td><td>1.00</td><td>1.00</td></tr></tbody></table>

<table><caption>Table 5: Entropy and r<sub>mean</sub> ratio (describing the ratio between mean within-group and mean between-group dissimilarities) for the botanical classifications of the dataset into orders, families, genera and species. SW stands for Smith-Waterman and kmer for kmer-based distances computed with kmers of length k = 4. Samples (one per taxonomic level) are those which have been built with the filters presented in table 1.</caption><thead><tr><th></th><th>Orders</th><th>Families</th><th>Genus</th><th>Species</th></tr></thead><tbody><tr><td>Entropy</td><td>2.15</td><td>3.01</td><td>3.39</td><td>3.98</td></tr><tr><td>r<sub>mean</sub> with SW</td><td>2.22</td><td>1.3</td><td>0.60</td><td>0.30</td></tr><tr><td>r<sub>mean</sub> with kmer</td><td>1.89</td><td>1.29</td><td>0.77</td><td>0.14</td></tr></tbody></table>
9 Figures

<figure><img src="image_87.png" /><figcaption>Figure 1: MDS on the dissimilarity matrix of the dataset of orders with 15 individuals or more, projected on axis 1 and 2. One dot is one sequence. Dissimilarities are computed with the Smith-Waterman algorithm on the left panel, and as distances between kmer histograms (length *k* = 4) on the right one.</figcaption></figure>

<figure><img src="image_88.png" /><figcaption>Figure 2: MDS on the dissimilarity matrix of the dataset of orders with 15 individuals or more, projected on axis 1 and 3. One dot is one sequence. Dissimilarities are computed with the Smith-Waterman algorithm on the left panel, and as distances between kmer histograms (length *k* = 4) on the right one.</figcaption></figure>
<figure><img src="image_89.png" /><figcaption>Figure 3: Normalised Mutual Information as a function of the entropy (left) and the ratio $r_{mean}$ (right) computed on the botanical classification. Each point corresponds to one of the four molecular-based clustering method applied to one of the 30 replicates. Clustering is made using the Smith-Waterman dissimilarity.</figcaption></figure>

<figure><img src="image_90.png" /><figcaption>Figure 4: Adequacy between botanical and molecular-based classifications along a gradient of taxonomic levels, x axis: taxonomic levels y axis: Normalised Mutual Information (NMI) between molecular-based classification and botanical classification. One curve corresponds to one molecular-based classification. NMI are computed for classifications obtained of the samples (one per taxonomic level) presented in table 1. Left panel: Smith-Waterman dissimilarities. Right panel: kmer-based distances.</figcaption></figure>
<figure><img src="image_91.png" /><figcaption>Figure 5: Sankey plot of correspondences between AHC with Ward (left column), botanical (central column) and SBM classification (right column) at the order level. The width of a flow between two classes is proportional to the number of sequences belonging to the two classes.</figcaption></figure>
<figure><img src="image_92.png" /><figcaption>Figure 6: Sankey plot of correspondences between AHC with Ward (left column), botanical (central column) and SBM classification (right column) at the family level. The width of a flow between two classes is proportional to the number of sequences belonging to the two classes.</figcaption></figure>
<figure><img src="image_93.png" /><figcaption>Figure 7: Sankey plot of correspondences between botanical classification (left column) and AHC with Single Linkage (right column), at the order level. The width of a flow between two classes is proportional to the number of sequences belonging to the two classes.</figcaption></figure>
<figure><img src="image_94.png" /><figcaption>Figure 8: Comparison between Smith-Waterman and kmer-based dissimilarities (length $k = 4$). Density heatmap with logarithmic scale. x axis: kmer-based distance; y axis: Smith-Waterman dissimilarity. The color at a given pixel represents the logarithm of the number of pairs of sequences.</figcaption></figure>
Bibliographie

[46108] IEEE standard for floating-point arithmetic. *IEEE Std 754-2008*, pages 1-70, 2008.

[AGM+90] S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman. Basic local alignment search tool. *Journal of Molecular Biology*, 215:403-410, 1990.

[And01] Christophe Andrieu. An Introduction to MCMC for Machine Learning. page 39, 2001.

[APF22] Mohamed Anwar Abouabdallah, Nathalie Peyrard, and Alain Franc. Does clustering of DNA barcodes agree with botanical classification directly at high taxonomic levels? *Trees in French Guiana as a case study*. *Molecular Ecology Resources*, 22(5):1746-1761, July 2022.

[AS66] S. M. Ali and SAMUEL D. Silvey. A general class of coefficients of divergence of one distribution from another. *Journal of the royal statistical society series b-methodological*, 28:131-142, 1966.

[Bay13] Burak Bayramli. Svd factorization for tall-and-fat matrices on map/reduce architectures. *arXiv preprint arXiv:1310.4664*, 2013.

[BDLBH15] Pierre Barbillon, Sophie Donnet, Emmanuel Lazega, and Avner Bar-Hen. Stochastic block models for multiplex networks: an application to networks of researchers, 2015.

[BE99] Stephen P Borgatti and Martin G Everett. Models of corerperiphery structures. 1999.

[Bis06] Christopher M. Bishop. *Pattern recognition and machine learning*. Information science and statistics. Springer, New York, 2006.

[BLW86] Norman Biggs, Lloyd, and Robin J. Wilson. *Graph theory, 1736-1936*. Clarendon Press, February 1986.

[BLZ16] Charles Bouveyron, Pierre Latouche, and Rawya Zreik. The stochastic topic block model for the clustering of vertices in networks with textual edges. *Statistics and Computing*, 2016.

[BMD20] H. R. Bhapkar, Parikshit N. Mahalle, and Prashant S. Dhotre. *Virus Graph and COVID-19 Pandemic: A Graph Theory Approach*, pages 15-34. Springer International Publishing, Cham, 2020.

[BRU67] STEPHEN G. BRUSH. History of the lenz-ising model. *Rev. Mod. Phys.*, 39:883-893, Oct 1967.

[Cic14] Andrzej Cichocki. Tensor networks for big data analytics and large-scale optimization problems, 2014.

[CLBD22] Saint-Clair Chabert-Liddell, Pierre M Barbillon, and Sophie Donnet. Impact of the mesoscale structure of a bipartite ecological interaction network on its robustness through a probabilistic modeling. *Environmetrics*, 33(2), March 2022.
[CMS+19a] H. Caron, J.-F. Molino, D. Sabatier, P. Léger, P. Chaumeil, C. Scotti-Saintagne, J.-M. Frigério, I. Scotti, A. Franc, and Rémy J. Petit. Chloroplast DNA variation in a hyperdiverse tropical tree community. *Ecology and Evolution*, 9(8):4897-4905, 2019.

[CMS+19b] Henri Caron, Jean-François Molino, Daniel Sabatier, Patrick Léger, Philippe Chaumeil, Caroline Scotti-Saintagne, Jean-Marc Frigério, Ivan Scotti, Alain Franc, and Rémy J. Petit. Chloroplast DNA variation in a hyperdiverse tropical tree community. *Ecology and Evolution*, 9(8):4897-4905, March 2019.

[DBB20] Hussam Al Daas, Grey Ballard, and Peter Benner. Parallel algorithms for tensor train arithmetic. Technical Report 2011.06532, arXiv, 2020.

[DBC+21] Hussam Al Daas, Grey Ballard, Paul Cazeaux, Eric Hallman, Agnieszka Miedlar, Mirjeta Pasha, Tim W. Reid, and Arvind K. Saibaba. Randomized algorithms for rounding in the tensor-train format, 2021.

[DBNW20] Gaspard Ducamp, Philippe Bonnard, Anthony Nouy, and Pierre-Henri Wuillemin. An efficient low-rank tensors representation for algorithms in complex probabilistic graphical models. In Manfred Jaeger and Thomas Dyhre Nielsen, editors, *Proceedings of the 10th International Conference on Probabilistic Graphical Models*, volume 138 of *Proceedings of Machine Learning Research*, pages 173-184. PMLR, 23-25 Sep 2020.

[DH19] Amelia Drew and Alexander Heinecke. Training neural machine translation (nmt) models using tensor train decomposition on tensorflow (t3f), 2019.

[DLR77] A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the em algorithm. *Journal of the Royal Statistical Society. Series B (Methodological)*, 39(1):1-38, 1977.

[DPR08] J.-J. Daudin, F. Picard, and S. Robin. A mixture model for random graphs. *Statistics and Computing*, 18(2):173-183, June 2008.

[ER59] P. Erdös and A. Rényi. On random graphs i. *Publicationes Mathematicae Debrecen*, 6:290, 1959.

[EY36] G. Eckart and G. Young. The approximation of one matrix by another of lower rank. *Psychotnetiku*, (1):211-218, 1936.

[FB19] Thorben Funke and Till Becker. Stochastic block models : A comparison of variants and inference methods. *PLOS ONE*, 14(4):e0215296, April 2019.

[FCS+21] J.-M. Frigerio, H. Caron, D. Sabatier, J.-F. Molino, and A. Franc. Guiana Trees. 2021. Portail Data INRAE, V1, DOI: 10.15454/XSJ079.

[FH82] Ove Frank and Frank Harary. Cluster Inference by Using Transitivity Indices in Empirical Graphs. *Journal of the American Statistical Association*, 77(380):835-840, 1982. Publisher: [American Statistical Association, Taylor & Francis, Ltd.].

[FHP91] Peter Fletcher, Hughes Hoyle, and C. Wayne Patty. *Foundations of Discrete Mathematics (International student ed.)*. 1991.

[Fra22a] Alain Franc. Tensor ranks for the pedestrian for dimension reduction and disentangling interactions, 2022.

[Fra22b] Alain Franc. Tensor Ranks for the Pedestrian for Dimension Reduction and Disentangling Interactions, January 2022. arXiv:2201.07473 [cs, math, stat].

[FYZS18] Joshua Faskowitz, Xiaoran Yan, Xi-Nian Zuo, and Olaf Sporns. Weighted Stochastic Block Models of the Human Connectome across the Life Span. *Scientific Reports*, 8(1):12997, December 2018.
[Gen98] James E. Gentle. Numerical linear algebra for applications in statistics. 1998.

[GVL96] Gene H. Golub and Charles F. Van Loan. *Matrix Computations (3rd Ed.)*. Johns Hopkins University Press, USA, 1996.

[Hac19] W. Hackbusch. *Tensor Spaces and Numerical Tensor Calculus*, volume 56 of Springer Series in Computational Mathematics. Springer, second edition, 2019.

[HJ12] R. A. Horn and C. R. Johnson. *Matrix Analysis*. Cambridge, second edition, 2012.

[HLL83] Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. *Social Networks*, 5(2):109–137, 1983.

[Hub01] S.P. Hubbell. *The Unified Neutral Theory of Biodiversity and Biogeography*. Princeton University Press, 2001.

[JBO02] Pedro Jordano, Jordi Bascompte, and Jens M. Olesen. Invariant properties in coevolutionary networks of plant-animal interactions. *Ecology Letters*, 6:69–81, 2002.

[JZS09] Qixia Jiang, Yan Zhang, and Maosong Sun. Community detection on weighted networks: A variational bayesian method. In Zhi-Hua Zhou and Takashi Washio, editors, *Advances in Machine Learning*, pages 176–190, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.

[KB09] T. G. Kolda and B. W. Bader. Tensor decomposition and applications. *SIAM Review*, 51(3):455–500, 2009.

[KBCG12] Christine Keribin, Vincent Brault, Gilles Celeux, and Gérard Govaert. Model selection for the binary latent block model. In *20th International Conference on Computational Statistics (COMPSTAT 2012)*, pages 379–390, Limassol, Cyprus, August 2012.

[KBKK] Patrick Kalmbach, Andreas Blenk, Markus Kluegel, and Wolfgang Kellerer. Generating Synthetic Internet- and IP-Topologies using the Stochastic-Block-Model. page 6.

[KN11] Brian Karrer and M. E. J. Newman. Stochastic blockmodels and community structure in networks. *Physical Review E*, 83(1):016107, January 2011.

[LBA11] Pierre Latouche, Etienne Birmelé, and Christophe Ambroise. Overlapping stochastic block models with application to the french political blogosphere. *The Annals of Applied Statistics*, 5(1):309–336, 2011.

[LBA12] Pierre Latouche, Etienne E. Birmelé, and Christophe Ambroise. Variational Bayesian Inference and Complexity Control for Stochastic Block Models. *Statistical Modelling*, 12(1):93–115, 2012.

[LC15] Namgil Lee and Andrzej Cichocki. Estimating a few extreme singular values and vectors for large-scale matrices in tensor train format. *SIAM Journal on Matrix Analysis and Applications*, 36(3):994–1014, jan 2015.

[LC18] Namgil Lee and Andrzej Cichocki. Fundamental tensor operations for large-scale data analysis using tensor network formats. *Multidimensional Syst. Signal Process.*, 29(3):921–960, jul 2018.

[Leg16] Jean-Benoist Leger. Blockmodels: A r-package for estimating in latent block model and stochastic block model, with various probability functions, with or without covariates, 2016.

[Les06] Annick Lesne. Complex Networks: from Graph Theory to Biology. *Letters in Mathematical Physics*, 78(3):235–262, December 2006.
[LK15] M. Leray and N. Knowlton. DNA barcoding and metabarcoding of standardized samples reveal patterns of marine benthic diversity. *PNAS*, 112(7):2076-2081, 2015.

[LMZ+20] Chunxiao Liu, Zhendong Mao, Tianzhu Zhang, Hongtao Xie, Bin Wang, and Yong-dong Zhang. Graph structured network for image-text matching. In *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)*, June 2020.

[LR13] Pierre Latouche and Stéphane Robin. Estimation de la fonction graphon d'un W-graphe. Application au réseau de la blogosphere politique française. In *45èmes journées de Statistique*, Actes des 45èmes journées de Statistique, page JdS, Toulouse, France, 2013.

[LW19] C. Lee and D.J. Wilkinson. A review of stochastic block models and extensions for graph clustering. *Applied Network Science*, 4(122), 2019.

[MB09] D. König Michael and Stefano Battiston. *From Graph Theory to Models of Economic Networks. A Tutorial*, pages 23-63. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.

[MIR60] L. MIRSKY. SYMMETRIC GAUGE FUNCTIONS AND UNITARILY INvariant NORMS. *The Quarterly Journal of Mathematics*, 11(1):50-59, 01 1960.

[MRV10] Mahendra Mariadassou, Stéphane Robin, and Corinne Vacher. Uncovering latent structure in valued graphs : A variational approach. *The Annals of Applied Statistics*, 4(2):715-742, 2010.

[Mur83] F. Murtagh. A survey of recent advances in hierarchical clustering algorithms. *The Computer Journal*, 26(4):354-359, 1983.

[Mü13] D. Müllner. fastcluster : Fast Hierarchical, Agglomerative Clustering Routines for R and Python. *Journal of Statistical Software*, 53(9):1-18, 2013.

[NIK+20] Alexander Novikov, Pavel Izmailov, Valentin Khrulkov, Michael Figurnov, and Ivan Oseledets. Tensor train decomposition on tensorflow (t3f). *Journal of Machine Learning Research*, 21(30):1-7, 2020.

[Nis09] Martin Niss. History of the lenz-ising model 1950-1965 : from irrelevance to relevance. *Archive for History of Exact Sciences*, 63(3):243-287, 2009.

[NLTK19] Zhenguo Nie, Roby Lynn, Tommy Tucker, and Thomas Kurfess. Voxel-based analysis and modeling of mrr computational accuracy in milling process. *CIRP Journal of Manufacturing Science and Technology*, 27:78-92, 2019.

[NPOV15a] Alexander Novikov, Dmitrii Podoprikhin, Anton Osokin, and Dmitry P Vetrov. Tensorizing Neural Networks. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, *Advances in Neural Information Processing Systems*, volume 28. Curran Associates, Inc., 2015.

[NPOV15b] Alexander Novikov, Dmitry Podoprikhin, Anton Osokin, and Dmitry Vetrov. Tensorizing neural networks, 2015.

[NROV14] Alexander Novikov, Anton Rodomanov, Anton Osokin, and Dmitry Vetrov. Putting MRFs on a Tensor Train. *Proceedings of The 31st International Conference on Machine Learning*, 2014.

[NS01a] Krzysztof Nowicki and Tom A. B. Snijders. Estimation and prediction for stochastic blockstructures. *Journal of the American Statistical Association*, 96:1077-1087, 2001.
[NS01b] Krzysztof Nowicki and Tom A. B Snijders. Estimation and prediction for stochastic blockstructures. *Journal of the American Statistical Association*, 96(455):1077–1087, 2001.

[OD12] I. V. Oseledets and S. V. Dolgov. Solution of linear systems and matrix inversion in the tt-format. *SIAM Journal on Scientific Computing*, 34(5):A2718–A2739, 2012.

[Orú14] Román Orús. A practical introduction to tensor networks: Matrix product states and projected entangled pair states. *Annals of Physics*, 349:117–158, oct 2014.

[Orú19] Román Orús. Tensor networks for complex quantum systems. *Nature Reviews Physics*, 1(9):538–550, aug 2019.

[Ose09] I. V. Oseledets. A new tensor decomposition. *Dokl. Math.*, 80(1):495–496, 2009.

[Ose10] I. V. Oseledets. Approximation of $2^d \times 2^d$ matrices using tensor decomposition. *SIAM Journal on Matrix Analysis and Applications*, 31(4):2130–2145, 2010.

[Ose11] I. V. Oseledets. TENSOR-TRAIN DECOMPOSITION. page 24, 2011.

[OTZ11] Ivan Oseledets, Eugene Tyrtyshnikov, and Nickolai Zamarashkin. Tensor-Train Ranks for Matrices and Their Inverses. page 10, 2011.

[PLP09] D. Pfitzner, R. Leibbrandt, and D. Powers. Characterization and evaluation of similarity measures for pairs of clusterings. *Knowledge and Information Systems*, 19(361), 2009.

[RC04] C.P. Robert and G. Casella. *Monte Carlo statistical methods (second edition)*. Springer Verlag, 2004.

[Sni97] Snijders, Tom A. B. and Nowicki, Krzysztof. Estimation and Prediction for Stochastic Blockmodels for Graphs with Latent Block Structure. 14:75–100, 1997.

[SST03] Eric M. Schwarz, Martin Schmookler, and Son Dao Trong. Hardware implementations of denormalized numbers. In *Proceedings of the 16th IEEE Symposium on Computer Arithmetic (ARITH-16'03)*, ARITH '03, page 70, USA, 2003. IEEE Computer Society.

[Ste93] G. W. Stewart. On the early history of Singular Value Decomposition. *SIAM review*, 35(4):551–566, 1993.

[Str19] G. Strang. *Linear Algebra and Learning from Data*. Wellesley Cambridge Press, 2019.

[SW81] P. D. Smith and M. S. Waterman. Identification of common molecular subsequences. *Journal of Molecular Biology*, 147:195–197, 1981.

[Syl] James Sylvester. Chemistry and algebra. *Nature*, 17:284–284.

[TBC17] Timothée Tabouy, Pierre Barbillon, and Julien Chiquet. Variational Inference for Stochastic Block Models from Sampled Data. working paper or preprint, September 2017.

[TL10] Lei Tang and Huan Liu. *Graph Mining Applications to Social Network Analysis*, pages 487–513. Springer US, Boston, MA, 2010.

[Wis69] David Wishart. 256. note: An algorithm for hierarchical classifications. *Biometrics*, 25(1):165–170, 1969.

[WRR03] Michael E. Wall, Andreas Rechtsteiner, and Luis M. Rocha. *Singular Value Decomposition and Principal Component Analysis*, pages 91–109. Springer US, Boston, MA, 2003.
[WW87] Yuchung J. Wang and George Y. Wong. Stochastic blockmodels for directed graphs. *Journal of the American Statistical Association*, 82(397):8-19, March 1987.

[YFW03] J.S. Yedidia, W.T. Freeman, and Y. Weiss. Understanding belief propagation and its generalizations. In G. Lakemeyer and B. Nebel, editors, *Exploring Artificial Intelligence in the New Millennium*, chapter 8, pages 239-236. Morgan Kaufmann Publishers, January 2003.

[ZYO+15] Zheng Zhang, Xiu Yang, Ivan V. Oseledets, George E. Karniadakis, and Luca Daniel. Enabling high-dimensional hierarchical uncertainty quantification by anova and tensor-train decomposition. *IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems*, 34(1):63-76, 2015.