dataesr/scientific-paragraphs-categorization huggingface dataset:
We denote as C ´In the set of all instances in the first group (in classes 1 ´10) having n items. The second set of industrial instances is retrieved from the real-world data. In our instances H ˆW P t50 ˆ100, 500 ˆ1000, 3000 ˆ6000u, |I| P t25, 50, 100u. The average demand of items is between 2 and 3. 15 instances were generated for each pair plate size/number of items. Thus, the second group contains 135 instances. We denote as R ´In the set of all instances in the second group having n items. The industrial instances are available on the ESICUP web-site: https:// paginas. fe. up. pt/~esicup/datasets.
Thus in columns gap all and t all , we give the average gap and the average solution time among all instances not solved optimally by heuristic peaq for all hypergraph configurations. Reported times are in seconds. In   One can see from the results in Tables  2  and 3  that the dynamic program is orders of magnitude faster than MIP for solving the pricing problem. The partial enumeration increases the running time of column generation only marginally. Moreover, this technique allows one to obtain a lower bound which is close to the "proper" lower bound, at least for the easiest instances that can be tackled by cg mip. Unfortunately, we were not able to determine how close is the lower bound obtained by cg dp∆3 to the "proper" bound for larger and harder instances, as the latter bound is very time consuming to obtain.
Each instance is composed of 10 or 15 batches, each batch b is composed of |I b | P t100, 150u items. As previously, average demand of items is between 2 and 3. For each class, we retrieved 25 instances. The class named LmIn contains instances with m batches, each of which having n items. All these instances are are available on the ESICUP web-site: https://paginas. fe. up. pt/~esicup/datasets. In Table  8 , we report the results obtained by the same heuristics tested before. Here we do not report results only for heuristic pdiv H q as it was shown to be dominated by pdivq. We also do not report results obtained by div 32 and ediv 32 since required computation time is very long and obtained solutions are only slightly better than the solutions obtained after only one dive. For each heuristic, we show the solution value obtained which equals to the average number of plates needed to cut items from all batches, as well as the average solution time in minutes.
Acknowledgment Experiments presented in this paper were carried out using the PLAFRIM experimental testbed, being developed under the  Inria PlaFRIM development action  with support from  Bordeaux INP, LABRI  and  IMB  and other entities:  Conseil Régional d'Aquitaine, Université de Bordeaux ,  CNRS  and  ANR  in accordance to the programme d'investissements d'Avenir (see https://www. plafrim. fr/).
We propose a new and easy approach to evaluate structural dissimilarities between frames issued from molecular dynamics, and we test this methodology on human hemagglutinin. This protein is responsible for the entry of the influenza virus into the host cell by endocytosis, and this virus causes seasonal epidemics of infectious disease, which can be estimated to result in hundreds of thousands of deaths each year around the world. We computed the three interfaces between the three protomers of the hemagglutinin H1 homotrimer (PDB code: 1RU7) for each of its conformations generated from molecular dynamics simulation. For each conformation, we considered the set of residues involved in the union of these three interfaces. The dissimilarity between each pair of conformations was measured with our new methodology, the symmetric difference distance between the associated set of residues.
Indeed, this pH variation induces a folding change of HA homotrimers, resulting in the three fusion peptides' exposure to the cell's membrane  [6]. HA is thus one of the two neutralizing antibody targets with neuraminidase, which is the second surface glycoprotein, allowing the virus to spread out from the cells  [7]. In a recent modeling study to design new inhibitors against HA, two Molecular Dynamics (MD) simulations were performed, one at pH = 7 and one at pH = 5, this acidic pH being the one inducing a conformational change  [8]. A motivation of this previous study was to compare the simulations at both pH values. Each protomer has two domains: HA1, responsible for the binding, and HA2 for the fusion, containing respectively 327 and 160 amino acid residues. The tridimensional structural data of HA were found in the Protein Data Bank (PDB), Code 1RU7, taken from  [3]  (see Figure  1 ).
This structure is the one of A/Puerto Rico/8/1934 H1N1. Figure  1. The tridimensional structure of the HA homotrimer (data found in the Protein Data Bank (PDB), Code 1RU7, taken from  [3] ). Each of the three protomers contains a subunit HA1 (in cyan in protomer 1) and a subunit HA2 (in green in protomer 1). HA1 domains are on the left. HA2 α-helices are on the right. The image was generated with PyMOL  [9]. Starting from an initial conformation, 40 conformations were extracted every 0. 5 ns for two performed simulations (see  [8]  for technical details about the protocol). The problem considered here is to evaluate, for each set of 41 conformations, the dissimilarities between pairs of conformations. For this purpose, we needed a simple procedure, easy to implement, and without spatial alignment because these latter generally involve unwanted contributions of meaningless parts of macromolecules, these parts being difficult to identify.
It was implemented in PROVAT software  [27]. The full mathematical description of the Voronoi tessellation can be found in  [28]. It is out of the scope of this paper. To summarize, each atom lies inside a convex polyhedral cell having its polygonal faces located at mid-distance from its neighboring atoms. Thus, two atoms are neighbors if their Voronoi cells share a common face. However, computing interfaces with the Voronoi method generates large cells, which induce the existence of meaningless long distances between neighboring atoms. This is why we needed to compute interfaces with another free parameter method: we retained the PPIC software. PPIC is publicly available with its documentation on a repository located at http://petitjeanmichel. free. fr/itoweb. petitjean. html. The method implemented in PPIC was introduced only in a very recent preprint  [29].
g. , consider three aligned points with abscissas x = 0, y = 2, and z = 3, for which the nearest neighbor of x is y, while the nearest neighbor of y is z, not x. When all atoms (or all heavy atoms) of the complex are used as inputs in the calculation of the interface, the pairs of atoms defined by the list of the RNN are a rough estimate of the location of potential interacting atom pairs. Moreover, to estimate the location of PPIs (Protein-Protein Interactions), looking at interacting atom pairs among the nearest neighbors makes more sense than looking at interacting atom pairs at farther distances than the nearest neighbors. PPIC was shown to be effective to compute interfaces on a database of 1050 protein homo-and hetero-dimers (  [29] ; data from  [32] ). It was used to compute HIV2 protease-ligand interfaces (  [29] ; data from  [33] ).
For both datasets, it was observed that the best agreement between the interface calculations produced on heavy atoms by PPIC and those produced by the cutoff method occurred for a cutoff near 3. 6-3. 7 Å (see Figure  1  in  [29] ). This is in agreement with the maximal donor-acceptor distance established in  [34]  at 3. 9 Å. It is significantly smaller than the 4. 5 Å cutoff distance between non-H atoms used by other authors  [33, 35, 36].
• Images of optimal superpositions of full macromolecules are too overloaded compared to those of optimal superpositions of interfaces. The software PPIC implementing our non-parametric algorithm of interfaces calculations is publicly available for free at http://petitjeanmichel. free. fr/itoweb. petitjean. html. The user can optionally run the cutoff method or the Voronoi tessellation method. As an example, we presented results about two MD simulations of influenza HA (PDB Code 1RU7, 1448 residues). Knowing from MD simulations at pH = 7 and pH = 5 that HA is stable, the magnitude of numerical values that we observed can serve as a first reference basis to discuss the results of MD simulations of other macromolecules or complexes. Our approach is neither claimed to overcome the previous ones, nor is it devoted to replacing them: it is just an additional tool devoted to helping structural biologists, which is simple to use and which can be easily reprogrammed by beginners.
More recent methods sample environmental DNA directly by shotgun sequencing (metagenomics), which resolves some of these biases. Different strategies have been introduced to determine microbial community compositions from metagenomic data. One approach is based on classifying sequencing reads using publicly available and taxonomically annotated reference genome sequences of 'known' species. The resulting read abundance distributions require subsequent normalization by genome length  5, 6  to derive relative abundances of individual species (Supplementary Figure  1 ). Rather than using whole genomes, an alternative approach is to quantify read coverage of genes that are found to be clade-specific based on analyzing current reference genome databases  7. If such marker genes occur only once per genome, then the resulting read coverages do not need to be normalized by copy number or genome length.
However, a downside to any method depending on prior knowledge of genome sequences is that genomically uncharacterized taxa remain unaccounted for, which can lead to inaccurate relative abundance estimates at species-level resolution (Supplementary Figure  1 ). Taxa that are missed by such reference-dependent methods can collectively be referred to as biological 'dark matter'  8. These include organisms-hereon referred to as 'unknown' speciesthat may be detected, but remain difficult to quantify using standard methods and up-to-date genome databases. To overcome this issue, we previously introduced a profiling tool that uses universally occurring, protein coding, single copy phylogenetic marker gene (MG)-based operational taxonomic units (mOTUs) as an approach to capture and quantify microbial taxa at species-level resolution in metagenomic samples  9.
mOTUs are built on the basis of MGs from both known and unknown species, the latter of which are extracted from existing metagenomes, enabling higher taxonomic resolution and more accurate quantification of species when profiling new microbial communities  9. Here, we present an updated and functionally extended profiling tool, the mOTU profiler version 2 (mOTUs2), which consolidates data from >3100 metagenomic samples into an updated mOTU database to substantially improve the representation of human-associated and ocean microbial species. Evaluations of mOTUs2 relative to state-of-the-art methods demonstrate improved sensitivity and quantification accuracy for both known and unknown species. We illustrate how species missed by other approaches can skew relative abundance estimates from compositional metagenomic data.
Results Reference-extended microbial community profiling with mOTUs2. We first identified 40 previously selected and benchmarked MGs in a total set of >25,000 sequenced genomes  13. To obtain species-level taxonomic groups of (possibly redundant) sequences, we clustered these genomes based on a calibrated cutoff of 96. 5% sequence identity  4  into 5232 non-redundant, reference MG-based operational taxonomic units (ref-mOTUs) that contained more than half of a subset of ten MGs that were found suitable for metagenomic analyses  9. Next, we assembled >3100 metagenomes from studies that included, as a requirement, a large number of systematically processed samples per biome (Supplementary Data 1). These comprised 1210 samples from major human body sites (oral, skin, gut and vaginal  14, 15  ), an additional 1693 samples from various human gut metagenomic studies including different disease cohorts  [16] [17] [18] [19] [20] [21]  and 243 ocean water samples  22.
After quality control, the resulting 2494 meta-mOTUs, together with the 5232 ref-mOTUs, comprise the updated mOTU database. Compared to the previous version, these numbers correspond to a 3-fold and 7-fold increase in known and unknown species, respectively, that can now be profiled using mOTUs2. Taxonomic ranks for each mOTU were assigned by a last common ancestor-based consensus assignment (Supplementary Figure  3 , Methods). Also, phylogenetic reconstruction shows that meta-mOTUs were sampled from a broad taxonomic distribution (Supplementary Figure  4 ), including from taxa that were hypothesized to represent novel phyla  23. Across all included biomes (four major human body sites and the ocean), the number and fraction of unknown species (85%) were highest in ocean water samples (Fig.
1b ), which is in congruence with previous results  22. Notably, even in presumably well-explored human gut samples, we found that more than half of the species still lacked sequenced representatives in our reference genome database  13  (Fig. 1b, c ). A breakdown of mOTUs by biome showed that ref-mOTUs are often detected in multiple biomes, while meta-mOTUs tend to be more biome-specific (Supplementary Figures  5a, b ). As shown by rank-abundance analyses, we find meta-mOTUs to be well distributed across the range from dominant to rare species (Supplementary Figure  6 ). Finally, the MGCs that could not be binned were used to quantify the cumulative abundance of organisms that are known to be present, but not quantified as mOTUs (Methods). This fraction was higher for the ocean than for samples from human body sites (Fig.
1c ), which may be improved by increasing the number of profiled ocean metagenomes in the future. We next evaluated the sensitivity of mOTUs2 for unknown species and assessed the resulting impact on relative abundance estimations compared to other approaches. To accomplish this, we analyzed the correspondence between mOTUs and metagenome assembled genomes (MAGs). MAGs involve binning assembled metagenomic contigs by sequence composition and/ or read abundance variation as a strategy to detect and genomically characterize organisms found in environmental samples  24. Thus, similar to meta-mOTUs, MAGs may include taxa that are not yet represented in genomic databases, and thus provide a way to test if and how many environmental microbes would be captured by mOTUs. More specifically, we reconstructed MAGs from 4880 published human gut metagenomes (Supplementary Data 2) and used 1845 MAGs identified in ocean water samples as a subset of 8000 recently published MAGs  23.
Using these MAGs, we determined how many of them could be assigned to previously known (ref-mOTUs) vs. unknown species (meta-mOTUs) and evaluated the impact on relative abundance estimations. We found that >97% of MAGs from human gut samples were represented by mOTUs (Fig. 1d ). Among these, 76% could be matched to ref-mOTUs and the remainder to meta-mOTUs. In addition, although the majority of the MAGs could be assigned to mOTUs, they represented only 42% of all human gut meta-mOTUs. For ocean water MAGs, 55% were represented by mOTUs (19% of these matching ref-mOTUs), while MAGs represented only 25% of ocean meta-mOTUs (Supplementary Figure  7 ). Our results indicate that the most abundant organisms in the human gut are already represented in public genome databases, whereas a substantial additional fraction becomes accessible through metagenomic data analysis.
While assembly opens possibilities for many additional analyses, higher sequence coverage is required for the reconstruction of high-quality MAGs than for mOTUs, explaining why meta-mOTUs capture many more species. In the ocean, even some of the most abundant species still appear to lack representative genomic information (Supplementary Figure  7 ). Next, we assessed the advantage of using a referenceindependent method for species quantification in microbial communities. To this end, we compared mOTUs2 with two popular reference-dependent approaches, as well as its original version (mOTUs1 9 ), using: (i) simulated metagenomes from human gut-associated MAGs (Supplementary Figures  8, 9  and Methods), (ii) the Critical Assessment of Metagenome Interpretation (CAMI) dataset  25  (Supplementary Figures 10, 11), and (iii) the simulated metagenomes used to evaluate MetaPhlan2 7 for benchmarking (Fig.
2 ; Supplementary Data 3, 4; Supplementary Table  1 ). Our results based on simulated MAGs show that in terms of precision, mOTUs2 and MetaPhlan2 outperformed mOTUs1 and Kraken (Fig. 2e ). The fact that the referencedependent methods MetaPhlan2 and Kraken can only detect genomes that are closely related to those present in current reference databases was well reflected in a reduced sensitivity, higher mean absolute error and deviations from expected taxonomic diversity estimates (Fig. 2e-g ). Additional simulations showed that relative abundance estimates may be highly inaccurate when solely relying on reference genomes if unknown species are present in medium to high abundance (Supplementary Figures  9, 11 ). For the CAMI dataset, our results show that the mOTUs2 profiler outperformed many other tools (Fig.
2h-o ; Supplementary Figures  10, 11 ). More specifically, mOTUs2 not only outperformed mOTUs1 at all taxonomic ranks, but also other tools, including MetaPhlan2 above the genus level for medium complexity simulations and above the species level for high complexity samples (Fig. 2k, o ). We should note that in the CAMI benchmark (and the OPAL evaluation tool  26  ) profiled abundance data are re-normalized based on the detected taxa (see  Fig. 2  Evaluation of mOTU profiling on simulated samples. Benchmarks of quantification accuracy (a-g) on ten simulated metagenomic samples (Methods) containing MAGs with (n = 50) and MAGs without (n = 50) a representative reference genome sequence, (h-o) and the CAMI challenge datasets  25. a-d A representative simulated metagenome (out of ten; Supplementary Figures  8, 9 ) analysed with four profilers.
e Precision-recall plot, where each data point corresponds to one of the ten simulated samples. Mean absolute error (MAE, also referred to as L1 norm) (f) and differences of the Shannon diversity index (g) from the expected values (error bars in f and g show standard deviation). h-j Average precision-recall values over the two medium complexity samples and (l-n) average precision-recall values over the five high complexity samples of the CAMI dataset (see also Supplementary Figure  10 ). Each precision-recall plot contains five values for mOTUs2, which correspond to different sets of parameters: high precision (-l 140 -g 6), default (-l 100 -g 3), recall (-l 75 -g 3), high recall (-l 50 -g 2) and maximum recall (-l 30 -g 1), indicating the versatility of mOTUs2 in optimising precision or recall.
This feature leads to improved quantification (hence, a further reduction of the mean absolute error), in particular at the species level (Fig. 2k , o; Supplementary Figure  11a ). Finally, since Kraken was not included in the CAMI benchmark  25  dataset, we compared the performance of mOTUs2 to the results reported for the evaluation of MetaPhlan2 7 , which included Kraken  6. We find that mOTUs2 and MetaPhlan2 performed similarly, while both (and mOTUs1) outcompeted Kraken (Supplementary Table  1 ). Given that profiling unknown species in addition to those represented in genome databases significantly improves relative abundance estimates, we sought to assess potential impacts on describing community structural properties. The total number of detected species and their relative abundance distribution determines the alpha diversity of a microbial community.
71, P < 0. 0001 and R = 0. 78, P < 0. 0001, respectively) than the reference-dependent methods (Fig. 3  and Supplementary Figure  12 ). We also assessed the performance of methods at estimating how similar taxonomic compositions are between samples (beta diversity). For this, we used data from healthy individuals who donated samples from four different major body sites on multiple sampling occasions  14  , so that composition similarities could be compared within and between individuals. Given that compositional differences are expected to be smaller within than between individuals  14  , we tested in how many cases a sample from one subject would be most similar to another sample from the same individual (and body site) than from any other sample in the set of >1200 samples tested. As a result, we found that mOTUs2 performed similarly to the reference-dependent, clade-specific gene-based method  7  , while both outperformed the whole genome-based method used by Kraken 6 (Supplementary Figure  13 ).
MG-based SNV profiling for microbial population analyses. Originally, the ten MGs were identified as a subset of candidate phylogenetic marker genes deemed suitable for reconstructing the tree of life 32 due to their universal occurrence and low rate of horizontal gene transfer  33. These properties provided us with the opportunity to test how well single nucleotide variation (SNV) profiles of microbial populations could be recapitulated by the MGs comprising mOTUs as a compute-efficient alternative to using whole reference genome sequences. To this end, we generated metagenomic SNV profiles  34  for sets of samples from different human body sites and ocean water using ref-mOTUs and representative genome sequences as reference databases. Despite some differences between biomes (Fig. 5a ) and a few species, we found overall that the distances of SNV profiles using MGs were highly correlated (R > 0.
In addition, we included not only more samples, but also data from a number of disease-related studies (e. g. , CRC, liver cirrhosis, type 2 diabetes) with large geographic distribution both contributing to an extended diversity of species that were not profiled previously. These may include species of particular relevance for differentiating healthy from diseased states. Furthermore, our results highlight the critical need to generate more reference genomes for the ocean environment where we find only 15% of species to have a representative genome sequenced. Future efforts could aim at extracting MGs from high-quality MAGs and single amplified genome sequences to incorporate these into the mOTU database. Although metagenomics data can be used to profile the abundance of microbial taxa in a given community, they do not inform us as to whether they are also (transcriptionally) active.
Generation and annotation of the mOTUs2 database. The mOTUs2 profiler relies on a custom-built database of MG sequences extracted from reference genomes (ref-MGs) and from metagenomic samples (meta-MGs). The reference genomes were grouped into species-level clusters (specI clusters) and MG sequences from these reference genomes were grouped based on their specI affiliation into reference marker gene clusters (ref-MGCs). These ref-MGCs were augmented by meta-MGs and the remaining meta-MGs were clustered into meta-MGCs. MGCs of different MGs were subsequently grouped based on their specI affiliation or binned based on co-abundance analysis into reference genome-based mOTUs (ref-mOTUs) and metagenomic mOTUs (meta-mOTUs), respectively. The resulting mOTUs were quality-controlled, compiled into a sequence database for short-read mapping and taxonomically annotated.