dataesr/scientific-paragraphs-categorization huggingface dataset:
While 𝑘-mers can easily be encoded as numerical values, which is widely used for instance in 𝑘-mer counting  [12, 13] , such representations are unable exploit the overlapping structure of the 𝑘-mers present in typical datasets that is usually referred to as the so-called spectrum-like property (SLP) of 𝑘-mer sets  [14]. More compact approaches of 𝑘-mer set representations were developed later, incorporating SLP as an implicit structural assumption and using it to compact 𝑘-mers overlapping by 𝑘 -1 nucleotides (review in  [15] ). First of them were unitigs  [16, 17] , which can be seen as non-ambiguous contiguous sequences in the data's de Bruijn graphs; unitigs had been previously well-studied and implemented in other contexts, such as genome assembly, and were thus easy to use. However, unitigs tend to impose large computational overheads due to the requirement of stopping at all branching nodes in the underlying de Bruijn graphs  [18, 19].
Setup and preliminaries We consider the standard setup of the problem of 𝑘-mer set textual representations  [15]. We assume that 𝑘 is a positive integer and 𝐾 is a set of 𝑘-mers to be represented. We consider the bi-directional version of the setup, in which 𝑘-mer and its reverse complement are considered a single mathematical object, with the exception of illustrations and examples that are always provided in the uni-directional model for simplicity. To unify the terminology throughout the paper, we call the simplitig/SPSS representation  [20, 18, 19] , which does not allow multiple occurrences of the same 𝑘-mer, simply SPSS (Spectrum-Preserving String Set) and call its members simplitigs. For the more general matchtig representation  [22] , which does allow multiple occurrences of the same 𝑘-mer, we use the term rSPSS (Repetitive Spectrum-Preserving String Set) and for its members the term matchtigs.
For a reference to either of these representations, we use simply the term (r)SPSS. Fig. 1a, b  depicts an example of a 𝑘-mer set 𝐾 and the corresponding de Bruijn and overlap graphs (see Appendix B for definitions). Fig. 1c  shows the corresponding examples of the state-of-the-art (r)SPSS representations of 𝐾 (rows 1-4 in the 'Strings' column).
The concept of masked superstrings We developed masked superstrings as a generalizing concept, comprising the state-of-the-art textual representations for 𝑘-mer sets that follow the spectrum-like property (SLP)  [14]  (a structural assumption characterizing typical 𝑘-mer sets encountered across bioinformatics in mainstream applications), allowing better compression capabilities, and also adding support for other types of 𝑘-mer data that do not follow SLP. We built upon the observation that the state-of-the-art (r)SPSS representations are deeply rooted in to the concept of superstring  [18, 15] , which has been deeply studied in many areas of computer science (for a primer of the shortest superstring problem, see Appendix B). The core idea behind masked superstrings is shifting from a set of strings, whose 𝑘-mers are exactly the 𝑘-mers to be represented, to some superstring of the 𝑘-mers, with the goal of their better compaction that can be achieved through the relaxation of restrictions on the lengths of 𝑘-mer overlaps.
Relation of masked superstrings to (r)SPSS and their associated algorithms Masked superstrings naturally generalize the concept of (r)SPSS. To see that, we note that the problem of representing 𝑘-mer sets always involves two major aspects: "How can 𝑘-mer sets be represented as compact mathematical objects?" and "How can these representations be computed efficiently?" In the case of (r)SPSS, the compact mathematical object is a set of strings whose 𝑘-long substrings form exactly 𝐾, and the efficient algorithms are greedy methods such as ProphAsm  [18] , UST  [19] , or greedy matchtigs  [22]. Both of these (r)SPSS concepts can be directly translated to the realm of superstrings through the following relations. enc4: "GGACCGACTT" Algorithms: Every (r)SPSS algorithm is an approximation of the shortest 𝑘-mer superstring.
Given a 𝑘-mer set 𝐾 and an associated ordered (r)SPSS, the concatenation of its strings is a superstring of 𝐾. Moreover, when omitting artificial edge-cases that would never be encountered in practice, the total length of the superstring is no bigger than the number of 𝑘-mers (|𝐾|) multiplied by 𝑘 (a superstring with such length corresponds to concatenating all 𝑘-mers together, which is the most naïve and wasteful approach). As the resulting superstring length is always bounded from below by |𝐾|, every such superstring of an (r)SPSS is necessarily a 𝑘-approximation of the optimal solution. Representations: Every (r)SPSS defines a masked superstring (but not conversely). Transforming an (ordered) (r)SPSS to a masked superstring is straightforward. Indeed, we just need to accompany individual strings by their corresponding masks and then concatenate the strings and masks in the same order.
Specifically, for every string in an (r)SPSS, its corresponding mask is set to all 1s, with the exception of the last 𝑘 -1 characters that are set to 0s. On the other hand, a general masked superstring does not translate to an (r)SPSS in the form of a split of the superstring (unless all runs of 0s in the mask are of the length 𝑘 -1). We illustrate the translation of (r)SPSS to masked superstrings in Fig. 1c  and further characterize their relations in Tab. 3 in Appendix A.
1d ). • Size after compression using a general-purpose method such as xz (implementing the Lempel-Ziv Markov Chain Algorithm, available from http://tukaani. org/xz/) or RRR  [25]. The 𝑜 and 𝑟 quantities generalize the number of sequences in the (r)SPSS representations with respect to different data structure implementations, and in addition to that, 𝑟 can be seen as a first-order proxy to the mask compressibility.
The extension proceeds by brutal force, first testing all four nucleotides, then testing all combinations of two of them, etc. , while testing for the presence of the created 𝑘-mer. This process is repeated until all 𝑘-mers are covered. Note that setting 𝑑 𝑚𝑎𝑥 = 1 corresponds to the original ProphAsm. Mask optimization using linear programming. Although the minimization of the number of runs is an NP-complete problem (Sec 3. 4), real-life instances of similar problems tend to be far from the worst-case scenarios, and often can be "attacked" by a reduction to a well-studied optimization problem and a subsequent use of highly optimized solvers. Following this approach, we model the minimization of the number of runs as an integer linear program (ILP) and run an efficient ILP solver. The key idea is to find all maximal possible runs of ones in a mask for the given superstring and then select the minimum number of these runs such that all 𝑘-mers are covered, i.
Implementation We implemented the two superstring heuristics in a program called KmerCamel🐫, which first reads a user-provided FASTA file with genomic sequences, computes the corresponding 𝑘-mer set, computes a masked superstring using a user-specified heuristic and core data structure, and prints it in the enc2 encoding. KmerCamel🐫 was developed in C++ and is available under the MIT license from Github (https: //github. com/GordonHoklinder/kmercamel). Each of the two heuristics was implemented using two distinct data structures: a hash table and the Aho-Corasick automaton. The hash-table-based implementations follow the greedy algorithms as described in Appendices C (local) and D (global). The implementations of the two 𝑘-mer superstring heuristics using the Aho-Corasick automaton are described in Appendix E.
For the mask optimization, we implemented the greedy minimization and maximization of ones in custom Python scripts. For minimizing the number of runs, we created a transformation script that reads a provided masked superstring, builds the corresponding ILP problem according to Appendix H, and solves it using the PULP solver  [28]. All the scripts are provided as a part of the evaluation pipelines in the Github supplementary repository (https://github. com/karel-brinda/masked-superstrings-supplement).
7 M, total genome length 430 Gbp), and we found exactly the same patterns as previously with the pneumococcal data (data and plots provided in the supplementary Github repository https://github. com/karel-brinda/ masked-superstrings-supplement). Comparison of mask optimization algorithms. We envision the computation of masked superstrings as a two-step process, where the actual superstring is first computed with a pre-selected heuristic and accompanied by the default mask (dependent on the underlying data structures used for computing the superstring). Then, the default mask can be re-optimized for the specific end use-cases. To evaluate the impact of mask optimization, we re-used the masked superstring computed previously and applied the following four re-optimization strategies: Default (D, preserving the current mask), MaxOne (O, maximizing the number of ones, i.
1c  and Tab. 3), which is a highly compressible pattern. Third, for the other local and the global superstring heuristics, MinRun was always preferential and MaxOnes performed nearly equally well in most scenarios, while imposing much lower computational overhead. We then hypothesized that mask compressibility is proportional to the number of runs, and tested this using an analogical plot, depicting the number of runs per 1 superstring character (Fig. 3b ). This number can be interpreted as the probability of starting a new block of 𝑘-mers within a superstring, and its lower values are better. We found that the observed patterns indeed clearly correlate with mask compressibility (Fig. 3a ). Overall, this suggests that the best strategy is preserving default masks for the traditional (r)SPSS and minimizing the number of runs otherwise; if the latter is computationally infeasible, we suggest maximizing the number of ones.
Comparison to other existing approaches. Finally, we compared the masked superstring computed using the proposed local and global greedy heuristics to the state-of-the-art (r)SPSS representations, including eulertigs (optimal simplitigs)  [21] , and greedily and optimally computed matchtigs  [22]  (Tab. 1 and Tab. 2). The results for the pneumococcal pan-genome in Tab. 1a and Tab. 2a imply that simplitigs (even optimal) and local greedy achieve worse results than global greedy or matchtigs. The performances of global greedy and matchtigs are comparable, with matchtigs being slightly better for the highly-branching case of 𝑘 = 12. However, once we moved to datasets that do not satisfy the spectrum-like property that we created by subsampling the pneumococcal pan-genome to 10% of 𝑘-mers, we obtained a completely different story as displayed in Tab.
Conclusions and discussion In this paper, we developed a new concept for text-based 𝑘-mer set representations, called the masked superstring of 𝑘-mers, and showed it generalizes the existing (r)SPSS, comes with better compression properties, and provides additional flexibility for data that do not satisfy the spectrum-like property. We For all algorithms, the mask was optimized for the minimum number of runs. We were not able to compute optimal matchtigs for streptococcus pan-genome with 𝑘 ∈ {12, 14} within reasonable time limit (several hours). For all algorithms, the mask was optimized for the minimum number of runs. We were not able to compute optimal matchtigs for streptococcus pan-genome with 𝑘 ∈ {12, 14} within reasonable time limit (several hours). further demonstrated that the computation of optimal superstring and optimal masks are NP-hard tasks, we developed efficient local and global heuristic approaches, and implemented them in KmerCamel🐫 using hash tables and the Aho-Corasick automaton.
We evaluated the proposed algorithms experimentally using viral, bacterial, and eukaryotic genomes and demonstrated that masked superstrings provide better compression characteristics than simplitigs, and can provide an improvement of up to several factors over the (r)SPSS, especially in applications involving subsampling. Due to the experimental nature of our algorithms and their implementations, we focused in our evaluations predominantly on rather small genomes, which is the main limitation of this paper. However, we note that in many applications, such as bacterial pan-genomics, datasets tend to be small in terms of the overall 𝑘-mer diversity per one pan-genome. We also note that the proposed experimental methods, implemented in KmerCamel🐫, can be substantially optimized, especially the parts related to the Aho-Corasick automaton.
Finally, the experiments with subsampled indexes demonstrate masked superstrings be suitable in applications where (r)SPSS could not be used efficiently. Finally, multiple other challenges are to be addressed in order to transition masked superstrings to real bioinformatics applications. While the moving from unitigs to simplitigs/SPSS was nearly effortless in applications such as Bifrost  [30]  or SSHash  [31] , using masked superstrings in common data structures such as FM index  [23]  will require additional representation of the mask (while freeing other space). On the other hand, masked superstrings may enable a better compression in scenarios where the (r)SPSS representations were too limited, such as spaced-seed indexes in metagenomics  [32]. Overall, we see masked superstrings as a unifying and generalizing concept that enables to better mathematically study and optimize textual 𝑘-mer-set representations, as well as it will provide new ways of increasing the efficiency bioinformatics software, especially in variation-heavy applications such as pangenomics.
Representation Restriction on 𝑆 = 𝑠 (1) + … + 𝑠 (𝑝)  Restriction on 𝑀 Restriction on 𝕂 Optimality Algorithms (optimal) Heuristics (suboptimal) 𝑘-mer list ∀𝑖 (|𝑠 (𝑖) | = 𝑘) and ∀𝑖 ≠ 𝑗 (𝑠 (𝑖) ≠ 𝑠 (𝑗) ) runs of 0s always of len. 𝑘 -1 and runs of 1s always of len. 1 max 𝑄∈𝐾 𝑓 𝕂 (𝑄) = 1 (trivial) (trivial) (optimal by definition) unitigs  [16]  terminating 𝑠 (𝑖)  whenever multiple 𝑘-mer extensions admitted runs of 0s always of len. 𝑘 - eulertigs  [21]  (in theory linear * ) •ProphAsm  [18]  (linear) •UST  [19]  (in theory linear * ) matchtigs  [22]  (rSPSS) (none) runs of 0s always of len. 𝑘 -1 (none) min |𝑆| optimal matchtigs  [22]  (polynomial) •greedy matchtigs  [22]  (in theory linear * ) •ProphAsm  [18]  (linear) •UST  [19]  (in theory linear * ) masked superstring [Sec. Table  3 : Overview of textual 𝑘-mer set representations and their constraints.
The constraints are formulated over the superstring 𝑆 (and its components 𝑠 (1) , … , 𝑠 (𝑝) for (r)SPSS), the 𝑘-mer mask 𝑀, the multiset 𝕂 of all represented 𝑘-mers with their frequencies, the optimality criteria, the algorithms for computing the optimal representation, and the associated heuristics, including their time complexities. In bold, we highlight the change of the restrictions from the previous representation. * In theory linear: The involved algorithms could in theory be linear, however their implementations involve the use of BCALM2 for computing unitigs, and as such do not have the guarantee of linearity. Remark about restrictions on 𝕏: None of these representations restricts the multiset 𝕏 of all ghost 𝑘-mers in any way (for representations with more components, ghost 𝑘-mers appear only if those components are concatenated into a superstring).
Whenever this happens, we erase this 𝑘-mer from the prefix hash table. • The edge does not go from a string to its reverse complement. We provide a pseudocode for this hashing-based implementation of BiDir-GlobalGreedy in Algorithm 2. The construction of the prefix hash table runs in expected time 𝒪(𝑘 ⋅ 𝑛) provided that we can compute any prefix (or suffix) of a 𝑘-mer with bit operations in constant time; namely, our implementation using 64-bit integers thus requires for 𝑘 < 32. Therefore, the only potentially expensive part is finding the first 𝑘-mer in the prefix table that fulfills the conditions above. Note, however, that this does not increase the time complexity. For a fixed 𝑑, the second case can happen in total at most 𝑛 times as we can remove each 𝑘-mer only once, and similarly, the first case can happen at most once per 𝑘-mer  [33].
Acknowledgment. We are all grateful to  Nicolaos Matsakis  for the many fruitful discussions and for sharing his expertise on the shortest superstring problem. We also thank  Ekaterina Milyutina  for the discussions in the early stages of the project. O. Sladký  and  P. Veselý  were partially supported by  GA ČR  project  22-22997S. P. Veselý  was also partially supported by  Center for Foundations of Modern Computer Science (Charles University  project  UNCE/SCI/004 ).
Important developments were the emergence of large-scale vegetation-plot databases like the European Vegetation Archive (EVA;  Chytrý et al. 2016 ) and Grass-Plot  (Dengler et al. 2018) , a European vegetation classification system (EuroVegChecklist;  Mucina et al. 2016 ) and an automated supervised habitat classification for vegetation plots in Europe  (Chytrý et al. 2020; Bruelheide et al. 2021). Rapid environmental change over large regions increases the need to perform broad-scale analyses of changes and trends in community composition and environmental conditions  (Kempel et al. 2020; Leclère et al. 2020; Hallman et al. 2022). However, most of the large European vegetation-plot databases (e. g. Chytrý et al. 2016)  do not contain in situ measured environmental data, at least not in easily accessible forms (but see  Dengler et al.
In doing so, we also implemented several novelties that should facilitate the future application of EIVE: (i) all indicators were scaled from 0 to 10 on a continuous interval scale and (ii) for each indicator we provide one value for niche position and one for niche width. In this paper, we describe the development of EIVE and release version 1. 0 as an open access database to initiate a community-based approach for future updates and extensions.
", "var. " and "×". Additions like "sensu lato" and "sensu stricto" were retained at this step, but harmonised in spelling to "s. l. " and "s. str. " to support name interpretation in the following steps. Taxonomic authorities were disregarded, as there is a huge variety of spelling variants and they rarely aid in the discrimination of false vs. correct interpretations. This first step resulted in the assignment of a (preliminary) harmonised original taxon name. In a second step, we retrieved the database underlying the Euro+Med Plantbase with accepted taxon names and all synonymy and parent-child relationships on 2022-03-21 (Euro+Med 2022). When a harmonised original taxon name (not considering s. l. and s. str. ) matched an accepted Euro+Med name, this name was assigned as our preliminary accepted name; when it matched a synonym in Eu-ro+Med (  2022 ), we assigned it to the accepted Euro+Med name.
The corresponding approx. 145 million distribution records were subsequently thinned to one coordinate per species and 30 arc second grid cell to reduce the bias of local oversampling. In addition, occurrences marked as managed in the GBIF database (field EstablishmentMeans) were not used for further analysis. From the remaining approx. 65. 8 million coordinates, we extracted for each species nineteen bioclimatic variables from CHELSA V2. 1  (Karger et al. 2017 (Karger et al. , 2021) )  with the same spatial resolution of 30 arc seconds and calculated the median of each variable. Out of all nineteen bioclimatic variables, the variable bio10, i. e. mean daily mean air temperature of the warmest quarter, showed the highest Pearson correlation with our EIVE-T values (in each of the three variants, see above).
Subsequently, we compared the three variants to combine the rescaled individual EIV systems into a European consensus system with bio10 median values, defining the best-performing approach as EIVE 1. 0. This system was then used for further comparisons, namely with the T values of the 23 source EIV systems that contained T. Moreover, we also compared EIVE 1. 0 with the European T values recently proposed by  Tichý et al. (2023). For all comparisons, Pearson correlations were calculated for the subset of species co-occurring in EIVE and the respective EIV system, and the most highly correlated bioclimatic variable was determined for both EIVE and the EIV system. For the evaluation of our three variants to calculate EIVE niche width, we used the same CHEL-SA bioclimatic data and GBIF coordinates but calculated the interquartile range (IQR) and the standard deviation of bio1 and bio10.
Data processing After taxonomic harmonisation, the 31 source EIV systems contained between 34 (Sweden_Diekmann) and 6,470 (Alps) vascular plant taxa with at least one of the five niche dimensions assessed. The combined data comprised 77,795 rows of taxon name × EIV system combinations, corresponding to 14,835 accepted taxa: 22 sections, 60 aggregates s. l. , 664 aggregates, 11,148 species, 2,899 subspecies and 42 varieties. Of these, 13,017 were from Euro+Med (2022) while 1,819 were EIVE additions to the taxonomic backbone. Only 22 (0. 03%) of all taxon name × EIV system combinations remained unresolved for the time being, meaning that we did not decide whether they are separate taxa or synonyms of other taxa. The European consensus system of the five niche dimensions contains between 13,748 and 14,714 accepted taxa, with an average of 4 and more assessments underlying each EIVE value (Table  2 ).
Database The main part of the EIVE 1. 0 database is a table with (1) the accepted taxon names, (2) the taxon rank, (3) the source of the taxon concept (Euro+Med, EIVE addition, unresolved) and then for each of the five niche dimensions (M, N, R, L, T) (4) the niche position value (e. g. EIVE-M for moisture), (5) the niche width indicator (e. g. EIVE-M. nw) and (  6 ) the number of source EIV systems on which the consensus values were based (EIVE-M. n) (Suppl. material 8). Further, we provide all source EIV systems with their original and harmonised taxon names and the corresponding name in our taxonomic backbone, together with the original and rescaled niche position and, where available, niche width information (Suppl. material 2). Finally, our documentation of all taxonomic deviations from Euro+Med (2022) forms part of the database (Suppl.
material 3). In addition to the online appendix of this paper, the EIVE 1. 0 database is available at https://zenodo. org/record/7534792. The R code to derive EIVE from the source files and to produce the figures and statistics of this papers is available upon request from F. J. A source file to be used for the calculation of mean EIVEs in the software JUICE  (Tichý 2002 ) is provided at: https://www. sci. muni. cz/botany/juice/?idm=10. An interactive tool to compare regional EIVs with the European variants for niche position and niche width is available as a Shiny App at https:// data. loe. auf. uni-rostock. de/EIVE. Tichý et al. (2023)  with EIVE. For a fair comparison, the bioclimatic variables with the highest correlations were determined separately for both EIV and EIVE indicator values ("best"), and correlations for EIVE ("EIVE cor.
Taxonomic scope and concepts We decided to follow the nomenclature and taxonomic concepts of the Euro+Med PlantBase (Euro+Med 2022) as much as possible, as this was considered the most complete and authoritative taxonomic database covering all of Europe. However, most of our sources were based on national and older taxonomic references. Many discrepancies could be corrected automatically with our R code based on the lists of synonymous names included in the Euro+Med database. However, some species (mostly neophytes and hybrids) found in our source lists were absent from Eu-ro+Med (2022) and thus had to be added manually using other sources. Such handling may introduce errors, but all of the taxa we added are fully documented (Suppl. material 3) and may thus easily be reassigned in future versions of EIVE if errors are encountered and reported.