dataesr/scientific-paragraphs-categorization huggingface dataset:
Conclusion In this article, we present a new semi-supervised consensus clustering approach named Semi-MultiCons. During the development of this approach, we optimized the implementation of the initial MultiCons approach for multiple consensus clustering  [12] , and we designed a new iterative constraint-based consensus function to integrate supervision information into the consensus clustering process. The experiments conducted on four reference benchmark datasets from the UCI Machine Learning Repository and on the MNIST large dataset have led to the following conclusions: • The prior knowledge, i. e. , supervision information, represented as pairwise constraints between instances is useful for improving the quality of clustering. • Semi-MultiCons manages to infer the correct number of clusters in output, while processing base clustering ensemble members with different numbers of clusters.
• Semi-MultiCons is able to process datasets with large number of instances contrarily to several other approaches, and has a linear scalability in the number of dataset instances. • Semi-MultiCons has the ability to solve operational clustering problems encountered when data is imbalanced, the number of clusters is large and/or the number of clusters is ambiguous or unknown. In the general case of operational applications, where the intrinsic number of clusters in the data space is unknown, the Semi-Multi-Cons approach can be used as a pre-processing step to contribute to the discovery of the appropriate number of clusters, as well as a consensus clustering method to achieve better clustering quality. Although Semi-MultiCons is more time consuming than the most efficient baseline semi-supervised consensus clustering approaches like HE and DWH, its execution times remain acceptable even for large and complex datasets such as the MNIST benchmark dataset.
Acknowledgments This project was carried out as part of the  IDEX UCA JEDI MC 2 joint project between Amadeus  and the  Université Côte d'Azur. This work has been supported by the  French government , through the  UCA JEDI Investments  in the  Future  project managed by the  French National Research Agency (ANR)  with the reference number  ANR-15-IDEX-01.
Genome search and/or classification is a key step in microbiome studies and has recently become more challenging due to the increasing number of available (reference) genomes and the fact that traditional methods do not scale well with larger databases. By combining a kmer hashing-based genomic distance metric (ProbMinHash) with a graph based nearest neighbor search algorithm (called Hierarchical Navigable Small World Graphs, or HNSW), we developed a new program, GSearch, that is at least ten times faster than alternative tools due to O(log(N)) time complexity while maintaining high accuracy. GSearch can identify/classify 8,000 query genomes against all available microbial and viral species with sequenced genome representatives (n=~65,000) within several minutes on a personal laptop, using only ~6GB of memory.
This threshold represents convenient means in searching and identifying new genomes against the already descried species and determining whether or not they represent novel species  10. The number of curated draft or complete prokaryotic genomes has reached 317,542 in the newest release of the GTDB database, and 2,332,702 in the latest IMG/VR database for viruses, representing 65,703 prokaryotic and 935,122 viral distinct species at the 95% ANI level  11, 12. Searching of query genomes against these large databases to find closely-related database/reference genomes for taxonomy classification based on the traditional brute-force methods, meaning, performing all vs. all searches, has become impractical, even for fast searching algorithms and/or small-to-medium computer clusters. For this task, faster search strategies are necessary.
In addition to the searching strategy, the actual algorithm used to determine overall genetic relatedness between the query and the databased genomes is critical. While the traditional blast-based ANI among closely related genomes at the species level, and the genome-aggregate average amino acid identity (AAI) for genomes related at the genus level or above, have been proven to be highly accurate for genetic relatedness estimation across microbial and viral genomes  13- 15  , they are too slow to use when dealing with more than a few dozen of genomes. Faster implementations based on k-mer counting have been recently described to alleviate this bottleneck such as FastANI and MASH  16, 17  , but these methods still do not scale with an increasing number of database (or query) genomes, especially based on an all vs.
Proximity graph, as implemented for example in the hierarchical navigable small world graph (HNSW)  31  , has been shown to be one of the fastest ANN search algorithms  32. HNSW incrementally builds a multi-layer structure consisting of a hierarchical set of proximity graphs (layers) for nested subsets of the stored elements. Then, through smart neighbor selection heuristics, inserting and searching the query elements in the proximity graphs can be very fast while preserving high accuracy, even for highly clustered data  29, 31. Therefore, finding the closest genomes in a database can be substantially accelerated by using HNSW. Here, we describe GSearch (for Genome Search), a tool that combines one of the most efficient nearest neighbor search approaches (HNSW) with a universal approach to measure genetic relatedness among any microbial genome, including viral genomes, ProbMinHash  33  , implemented in the Rust language for higher speed.
ProbMinHash is based on shared kmers, weighted by their abundance and normalized by total kmer count, which can account for genome incompleteness of prokaryotic genomes and repeats commonly found in eukaryotic and sometimes in prokaryotic genomes. Essentially, ProbMinHash computes the normalized weighted Jaccard distance between each pair of genomes and subsequently, the weighted Jaccard distance normalized by total kmer count is used as input to build HNSW to create the graph of the database genomes. Accordingly, the search of the query genome(s) against the graph to find the nearest neighbors for classification purposes becomes an ultra-fast step using GSearch and can be universally applied to all microbial genomes. The novelty of GSearch also includes a hierarchical pipeline that involves both nucleotide-level (when query genomes have close relatives at the species level) and amino-acid-level searching (when query genomes represent novel species), which provides robust classification for query genomes regardless of their degree of novelty relative to the database genomes, as well as a database-splitting strategy that allows GSearch to scale up well to millions of database genome sequences.
90, P<0. 01, Supplementary Figure  S2a  and S2b ). Below ~50% AAI, both ProbMinHash and MASH distance lose accuracy compared to AAI. However, AAI of just universal genes provides a robust measurement of genetic relatedness at this level of distantly related genomes  21  , and we show here that ProbMinHash distance for the same set of universal genes is also robust (Spearman rho=0. 9390, P<0. 001, Supplementary Figure  S3 ). Thus, for query genomes of organisms with only distant relatives in the database (i. e. , deep-branching), for which their closest represented genome in the database is related at the order level or higher, restricting the search to the universal genes can provide robust classifications.
Graph building and search against reference prokaryotic genomes is faster than alternative methods To build the database graph for the entire GTDB v207 database (65,703 unique, nonredundant, at the species level, prokaryotic genomes) at the nucleotide level, the tohnsw module of GSearch took 2. 3 h on a 24-thread computing node and scaled moderately well with increasing number of threads (Figure  2a ). Maximum memory (RAM) required for the building step was 28. 3 GB. The total size of written database files on disk was ~3. 0 GB. There are 3 layers for the resulting graph, 65180, 519, and 4 genomes for layer 0,1 and 2 respectively. The searching of query genomes against this database graph, requesting best 50 neighbors for 1000 query genomes, which represented different previously known as well as novel species of eight bacterial phyla (see Methods for details on query genome selection), took 2.
3 min (database loading 6 seconds) on a 24-thread machine and also scaled well with increasing number of threads (Figure  3a ). The memory requirement for the request (search) step was only 3. 0 GB for storing the entire database file in memory. To evaluate the accuracy of these results, we compared the best neighbors found by GSearch with brute-force FastANI and GTDB-Tk. All best neighbors found by brute-force FastANI and GTDB-Tk for query genomes with close relatives in the database (e. g. , ANI > 78%) were found by GSearch (Supplemental File 1). Top 5 neighbors were 99. 4% overlapping and top 10 were 96. 3% overlapping between GSearch and the other two methods for the testing query genomes. We also compared the speed with MASH for the same kmer and sketch size and the MASH dist step took 7.
51 min to compare 1000 genomes with database using 24 threads. The speed difference compared to MASH was even greater for ~8,000 query genomes. Specifically, it took 12. 5 min for GSearch to find the top 50 best hits (Supplementary Figure  S4a ) while MASH took 80. 8 minutes on the same 24-thread machine. However, for a given number of database genomes, the speedup of GSearch is saturated to log(N) as the number of query genome increases, where N is the number of database genomes. Therefore, GSearch will be orders of magnitude faster than MASH for larger species database with millions of genomes (see also viral section below). GSearch search time for a given number of query genomes is related to the number of database genomes in a O(log(N)) manner while brute-force methods are O(N), and our empirical analysis is consistent with the theoretical log(N) prediction (Supplementary Figure  S4b  and Supplementary Note 3).
To build the amino-acid-level graph for moderately related query genomes, all GTDB v207 genomes were used for gene calling by FragGeneScanRs and subsequently, the predicted amino acid sequences for each genome were used for the tohnsw module. The graph building step took 1. 4 h (Figure  2b ) with a maximum memory required for the building step to be 37. 7 GB. The total size of written database files on disk by GSearch was 5. 9 GB. There were 65158, 543 and 2 genomes for layer 0,1 and 2 respectively. Requesting 50 neighbors for 1000 genomes at the amino-acid level took 1. 52 minutes with a memory requirement of ~6. 0 GB (database loading 9 seconds; Figure  3b ). The top 5 neighbors had a 98. 9% recall compared to the brute-force MASH or blast-based AAI approaches, with 97. 1% overlap for the 10 top neighbors.
In comparison, MASH dist took 5. 96 min using 24 threads; for 8000 query genomes, MASH dist took 47. 2 min while GSearch took 5. 6 min. Finally, for most distantly related query genomes, the graph building for the universal gene set follows the same logic as the amino acid level graph mentioned above except for using a smaller kmer size (k=5) due to the smaller kmer space of ~120 universal genes vs. the whole-genome level (e. g. , a few thousand genes). It took 7. 76 min to build the database (Figure  2c ) and 32 seconds to request 50 neighbors for 1000 queries on a 24 threads node (Figure  3c ) with a recall similarly high to the amino-acid level search (with top 5 and top 10 recall ranging between 98. 2% and 96. 1%, respectively). We also evaluated the effect of genome completeness on search and classification accuracy given that bacterial genomes recovered from environmental metagenomes are frequently incomplete.
Graph database building and searching for viral and fungal genomes Graph building and requesting for viral genomes is not effective at the nucleotide level because many viral genera are too diverse and do not have close relatives in the public genomic database; that is, the database is too sparse. Accordingly, kmer-based methods (e. g. , MASH and ProbMinHash) will often lead to imperfect graph structure for viral genomes. Therefore, we build only an amino acid level graph for viral genomes, using all genes in the genome due to the lack of universal genes for viral genomes. Database building took 13. 895 h on a 24-thread node and graph file on disk is 15. 8 GB (Supplementary Figure  S6 (a) ). Requesting 1000 neighbors scaled well with increasing number of threads and took about 3. 63 min (database load takes additional 1.
1 min) using 24 threads (Supplementary Figure  S6 (b) ). The top 10 neighbors for 1000 query phage genomes were still highly overlapping (98. 32% recall; Supplemental Table  S1 ) with the brute-force MASH-based approach. For such large database, GSearch is about 20X faster than the brute-force MASH (Supplementary Tables  S1 ). We also compared GSearch with a new database building method called PhageCloud, which relies on manually curated genome labels (e. g. , environmental source) for graph database building in Neo4j database software and Dashing software for distance/relatedness computation. Since PhageCloud provides only a website and allows only one genome query at a time, we searched only one viral genome at a time with GSearch and MASH against the same database (Gut Phage Database  34  ).
It took 37 seconds to find the two best matches with PhageCloud while GSearch took 15 seconds (database loading 14 seconds, search 1 second) for the same search. MASH on the other hand took 4 minutes to find the same 2 best matches. It should be noted, however, that, because the database is already available (loaded) on PhageCloud's website, 37 seconds is only for search and website responses (average value for 5 runs on 5 different days) whereas GSearch took only 1. 5 second for the same step. Graph building for fungal genomes is slower compared to prokaryotic genomes, despite the smaller number of available fungal genomes (n=9700) because the average fungal genome size is much larger and kmer and sketch size are accordingly much larger (k=21, s=48000). It took 2. 3 h on a 24-thread node to build the nucleotide level graph for these fungal genomes.
Searching step was also slower due to the larger kmer space. Accordingly, it took 3. 13 min to identify 50 neighbors for 50 query fungal genomes while MASH tool 4. 4 min. Nonetheless, top 5 recall was still very high (~99. 4%) against MASH and MUMMER-based ANI for the same datasets. For the amino acid level graph, the time for graph building was only 0. 61 h, shorter than the corresponding prokaryotic graph due to the lower coding density of fungal genomes relative to the prokaryotic genomes. Identifying 50 neighbors for 50 query fungal genomes at the amino-acid level took 1. 24 min (MASH took 2. 59 min) with similarly high top 5 and top 10 recall (99. 7% and 98. 5%, respectively) against brute-force MASH (-a) and blastp-based AAI. Note that the difference in run time will be much larger between MASH and GSearch as the number of fungal database genomes increases in the future, as also exemplified above for the bacterial genomes.
Combining the three graphs/levels together and comparison with GTDB-Tk for prokaryotic genome classification A three-step pipeline was developed to allow the identification and classification of a query genome, depending on its level of novelty compared to the database genomes (Figure  4 ). Specifically, when the query genome does not find a match in the database better than ANI > 78%, corresponding to ProbMinHash distance 0. 9850, the nucleotidelevel graph is abandoned, and the amino-acid level is used instead. If no match against the latter graph is found above 52% AAI, corresponding to 0. 9375 ProbMinHash distance, the amino-acid level is abandoned, and the universal gene graph is used instead (uAAI based on universal gene below 80% indicates new order or higher taxonomic rank; Figure  4 ).
The overall running time to classify 1000 prokaryotic genomes of varied levels of taxonomic novelty on different computing platforms is showed in Table  1. On a 24-thread Linux node with Intel Xeon Gold 6226 CPU, it took a total of 5. 85 minutes while it took 19. 49 minutes on an intel Core i7 laptop (2017 release) CPU personal laptop (6. 02 minutes on the most recent ARM64 CPU laptop). Classifying 1000 genomes using GTDB-Tk took 5. 91 h on the same Linux node with 24 threads (Figure  3  (d), memory requirement was ~328G) while MASH took 53. 7 min for 1000 genomes using 24 threads for the 3 steps. In terms of accuracy, all query genomes that had a best match higher than 78% ANI against the GTDB database genomes (i. e. , a match at the same or closely related species, 699 out of the total 1000) were identically classified by GSearch, GTDB-Tk and FastANI (Supplementary File 1, only 100/699 are shown for simplicity).
For the remaining 301 genomes that did not have same or closely related species-level matches, for 266 of them (or 87. 1%), GSearch also provided the same classification with GTDB-Tk but several inconsistencies were observed for 39/301 genomes (Supplementary Figure  S5 ). Specifically, we noticed that for GTDB-Tk, which relies on RED values and tree topology, several genomes (n=14) were still classified at the genus level even though the AAI value against the best database genome in these case was below 60% (typically, genomes assigned to the same genus show >65% AAI  21  ), and some genomes (n=16) were still classified at the family level but not at the genus level even though their best AAI value was above 65%. Similarly, several genomes (n=9) were classified at the order level but not family level even though their best AAI value was above 52%.
Database split for large genomic species database For large databases (for example, >1 million bacterial genomes), the graph building and requesting step could require a large amount of memory (due to the larger kmer space) that is typically not available in a single computer node. We therefore provide a database split solution for such large databases. The average database building time on each node (for each piece of the database after the splitting step) scales linearly with increasing nodes/processors (Supplementary Figure  S7(a) ) and requires much less memory (1/n total memory compared to when building in one node where n is the number database pieces after splitting; for GTDB v207 nucleotide graph building and n=5, it will be only 28. 3 G/5=5. 66 G). The searching time scales sub-linearly with increasing number of nodes (Supplementary Figure  S7(b) ), but offers the advantage of a reduced memory footprint with respect to the single-node search.
The top 10 best neighbor by splitting the database were exactly the same as the non-splitting strategy (Supplementary file 2). Note that without multi-node support (e. g. , run database build sequentially), database build time is nearly the same with non-split strategy, but memory requirement is only 1/n (GTDB v207, 28. 3G/5=5. 66G at nucleotide level and 37. 7G/5=7. 54G at amino acid level), despite the fact that total request time will be larger (time*n in Supplementary Figure  S7(b) ). However, since the request step is very fast with only 1/n memory requirement (e. g. , loaded graph database files for GTDB v207 will be about only 3G/5=0. 6G), even for a decent number of pieces, overall runtime is still short with the database split approach. The database split strategy is especially useful when memory requirement is not satisfied on host machine for larger genomic species database (e.
Discussion A popular way to assess genetic relatedness among genomes is ANI, which corresponds well to both 16S/18S rRNA gene identity and DNA-DNA hybridization values, the golden standards of fungal and prokaryotic taxonomies  13. However, the number of available microbial genomes has recently grown at an unprecedented speed. For example, there are 30% more (new) species in GTDB v202 (2020) vs. v207 (2022), and the number of bacterial species represented by genomes alone is expected to surpass 1 million soon. Therefore, the traditional way that blast-based ANI or faster kmer-based implementations (e. g. , FastANI or MASH) are applied as an all vs. all search strategy (brute-force) does not scale because the running time grows linearly with increasing number of query genomes and/or genomes in the database.
Phylogenetic approaches based on quick (approximate) maximum likelihood algorithms and a handful of universal genes as implemented -for example-in GTDB-Tk could be faster than brute-force approaches but are often not precise and require a large amount of memory for the querying step  20, 36  while the database building step could take several weeks of run time because the underlying multiple sequence alignment of the database genomes is computationally intensive. Further, approaches that reply on k-medoid clustering to avoid all vs. all comparisons could be sometimes trapped into local minima because of arbitrary partitioning of database genomes into clusters, a known limitation of these methods  21. Our GSearch software effectively circumvents these limitations by combining a new kmer hashing-based algorithm for fast computation of genetic relatedness among genomes (ProbMinHash) with a graph based nearest neighbor search algorithm (HNSW).
Accordingly, GSearch is at least an order of magnitude faster than alternative approaches for the same purposes. Note that GSearch could also be applied to whole metagenome search and identification of the most similar metagenomes in a series because ProbMinHash can estimate metagenomic distance in a similar way to genomes. To the best of our knowledge, no current tool can efficiently search very large genome databases. GSearch is able to handle a million microbial genomes on a smallto-average computer cluster since the dumped database file size is proportional to the total number of genomes in database for fixed sketch size and graph parameters. Specifically, with one million genomes, the dumped file size (amino acid) will be 5. 9G*20=118 GB (now we have only ~60K, for which database file size is 5.
9G), a modest computational requirement for current computer clusters or even personal laptop computer. Further, due to the nature of graph based NNS algorithms, there is no need to build the entire database at once, but the database can be split it into smaller pieces and thus, a separate graph database be built for each piece as exemplified above and depending on the computational resources available. For a modern laptop with 16 GB memory, a database on one million species can be split into 10 pieces, so the dumped file for each piece will be only 11. 8 GB, which can be loaded into memory, and then collect the results from each piece within an approximate total running time of 30 minutes (assuming each part will be 3 minutes for 1000 query genomes against 0. 1 million database genomes). With this logic, a computing node with 24 threads and 256 GB of memory available can easily deal with 20 million bacterial database genomes.
In the meanwhile, ProbMinHash was used in GSearch because it is metric  33, 38  , which ensures neighbor diversity when building the graph, but it is equally applicable to any microbial genome, including viral and fungal genomes, in addition to its advantages for kmer weighting and normalization mentioned above. Another distinguishing aspect of GSearch (tohnsw module) is the speed and flexibility in building reference databases. Users could build reference databases (graphs) for any number and type (e. g. , prokaryotic vs. viral) of genomes, up to several millions of genomes. The high efficiency in building graphs allows users to also test and optimize the key parameters of the graph, the M and ef_construct parameters. For any given database size, M and ef_construct determine the quality of the graph and graph build speed.