dataesr/scientific-paragraphs-categorization huggingface dataset:
We also design a network structure with multiple branches to capture intra-and inter-task correlations in cell selection. • Traditional RL methods need to firstly collect a large amount of data for training, which is very ineffective for MCS tasks. Hence, we propose a novel two-stage online framework to eliminate this costly initial data collection process. In the first stage, we use QBC to select cells, while at the same time collect the data for RL training. After the RL training is finished, we move to the second stage, i. e. , switch to RL-based cell selection method to perform Sparse MCS. • We evaluate the proposed algorithms on two typical urban sensing datasets with multiple tasks, and show the effectiveness of our proposed algorithms on reducing the number of sensed values and improving the accuracy of the inferred results for the multi-dimensional urban sensing.
Rana et al. [16]  used compressive sensing to recover the urban noise map from the incomplete and random crowdsourcing data. Zhu et al. [17]  proposed an approach for traffic estimation from the periodically collected locations and speeds in probe vehicles. Leye Wang et al. [8] ,  [9]  presented a complete framework for Sparse MCS by using the compressive sensing, Bayesian inference, and active learning techniques, which achieved very good performances on temperature, air quality and traffic monitoring datasets. He and Shin  [18]  proposed a signal map crowdsensing framework, which uses Bayesian compressive sensing to construct the urban signal map. All these works used the compressive sensing as the data inference method, but they focused on the single-task scenarios. Wang et al. [11]  first considered the intradata and interdata correlations, while they only exploited the correlations to the data inference without jointly considering the cell selection.
B. REINFORCEMENT LEARNING Reinforcement Learning (RL)  [19]  is a technique of machine learning which learns to make a sequence of decisions via trial and error. Recently, combining with the deep learning, RL becomes one of the most popular research topics and has shown its effectiveness on a wide variety of sequential decision making tasks. Mnih et al. [21]  proposed the first deep RL model and applied it to play seven Atari 2600 games. Silver et al. [22] ,  [23]  applied RL and presented the famous AlphaGo, which was the first program to defeat world-class players in Go. More recently, researchers pay more attention to apply RL in various areas to solve practical problems. Xiao et al. [24]  formulate the interactions between a server and vehicles as a vehicular crowdsensing game. Then they propose the Q-learning based strategies to help server and vehicles make the optimal decisions for the dynamic game.
A. SYSTEM MODEL We consider a multi-dimensional urban sensing scenario where the requester wants to get the multiple types of data (e. g. temperature, humidity) in the large-scale urban regions. The main notations used throughout this paper are illustrated in Table  1. Specifically, we have k heterogeneous sensing tasks on the large-scale target sensing areas. These target sensing areas are split into m cells (subareas) and each sensing task is divided into n sensing cycles for the whole sensing campaign. The sizes of cells and the lengths of cycles are determined according to the requirements of requesters. For example, if the requester would like to know the finegrained temperature variation in the urban regions, the cells and cycles should be set to the proper sizes, such as 1km * 1km for each cell and update data every one hour  [11].
We formalize the multi-dimensional urban sensing as the multi-task Sparse MCS, which allows us to sense only a few cells and effectively provide the multi-dimensional sensing services. For each sensing task, we use the ground truth data matrix D m×n to record the true data in m cells at n cycles. The set of ground truth data matrices for k sensing tasks can be denoted by D = {D 1 , D 2 ,. , D k }. At each cycle, we select l i cells out of the total m cells and recruit the participants in these cells (or steer the nearby participants by some incentive mechanisms) to perform task i. We study the multi-task Sparse MCS under two constraints in practical use, e. g. , budget constraint and accuracy constraint, respectively. With the budget constraint, we consider a general budget B = k i=0 l i for the selected cell, task pairs at each sensing cycle, which is practical and implementable.
Then, can we use a small amount of data to train our model and achieve a good enough performance? In most urban sensing systems, the answer is yes. As shown in Figure  4 , we try out all of the possible cell, task pairs and count the times of one cell selected per the 100 cycles in our experiments over Sensor-Scope  [31]  dataset in Section VI. We can see that 30% of cells have been selected more than 10 times while the others are less than 10 times. Moreover, the central cells have been selected more frequently than the corner ones, which fits our analysis and proves the effectiveness of cell selection. Therefore, we consider that a few cells are more important and they can help more on data inference. We don't need too much data to train all of the possible states and actions from all cells.
A. DATASETS We adopt two well-known urban sensing datasets, Sensor-Scope  [31]  and U-Air  [34]. Sensor-Scope contains some environment readings (temperature and humidity) and U-Air has the air quality data (PM2. 5 and PM10), which are the representative urban sensing datasets. These data were collected by the fixed sensors, while the mobile devices can also be used to obtain them. Thus, we can use them to evaluate our proposed algorithms effectively. The detailed statistics of the two datasets are listed in Table  2  and the descriptions are shown as follow: Sensor-Scope  [31] : The Sensor-Scope dataset contains various environment readings collected in the EPFL campus. We select two representative sensing data, temperature and humidity, to evaluate our methods for multi-dimensional urban sensing.
Actually, temperature and humidity present some inherent correlations. For example, a higher temperature usually leads to a lower humidity  [15]. Our methods can capture their intra-and inter-task correlations well. U-Air  [34] : The Sensor-Scope dataset collects the air quality data, i. e. , PM2. 5 and PM10, in Beijing. As shown in Table  2 , the air quality readings have the large fluctuations and we use the air quality index category  [34]  instead of the original readings. 7 The PM2. 5 and PM10 have the strong inter-task correlations, especially for the bad air quality, both of them may get the higher readings  [27]. Thus, our method can achieve the better performances.
2) DATA INFERENCE We evaluate the data inference on two datasets and each with two sensing tasks. For all the compared algorithms, we use RL-based cell selection algorithm to select the next sensed cells. In order to reflect the improvement of inference accuracy in data inference and cell selection respectively, we change the number of selected cells for each sensing cycles and evaluate the average error rates for each methods. The results are shown in Figure  7. The average error rates over four urban sensing tasks have the similar tendencies and our Multi-CS achieves the best performance. Along with the increase of the number of selected cells, the average error rates become lower, since the more selected cells provide more information to help the data inference. The CS and Multi-CS are relatively closer and achieve better performances when we have less selected cells.
3) CELL SELECTION Then, we evaluate the cell selection over two multidimensional urban sensing datasets, Temperature-Humidity and PM2. 5-PM10, as shown in Figure  9. Similar with data inference, we use Multi-CS for all compared algorithms. We change the number of selected cells for each sensing cycles and evaluate the average error rates for each methods. Note that our Multi-RL selects the cell, task pairs for multiple tasks, which means that we may select more cells for the task which will help more. Along with the increase of the number of selected cells, the results have the similar tendencies with data inference, since the more selected cell, task pairs may provide more information to improve the accuracies. Our Multi-RL always achieves the best performance, especially when we only select less cell, task pairs.
At the 100th cycles, we turn to the running stage for Temperature-Humidity and PM2. 5-PM10, and their performances are closed to the RL models which have been trained offline. We can see that when we use only 20 cycles for training, the error rates are very high. The reason is that our RL has learned that a few cells are good, and always select them, which makes the data inference so difficult. In addition, since our datasets are limited as shown in Table  2 , we only use the first 100 cycles for training and the rest are used for testing. In our future work, we would like to conduct our experiments on some larger datasets, which may achieve better performances.
5) RUNNING TIME Finally, we test the average running time for each method, as shown in Table  3. Our experiment platform is equipped with Intel Xeon CPU E2630 v4 @ 2. 20GHz and 32 GB RAM. The Muti-CS costs 0. 91s and 0. 66s to infer the full sensing data for Temperature-Humidity and PM2. 5-PM10, which are totally acceptable in real-life deployments. For cell selection, we implement our RL-based algorithms in TensorFlow (CPU version) and they obtain the great advantages than QBC on the running times. RL-based algorithms only need less than 1ms during the running stage. The training can be conducted offline/online, which costs around 10-30 minutes to converge, since we design a simple but effective network structure with multiple branches.
This work was supported in part by the  National Natural Science Foundation of China  under Grant  61772230 , in part by the  Natural Science Foundation of China for Young Scholars  under Grant  61702215 , in part by the  China Postdoctoral Science Foundation  under Grant  2017M611322  and Grant  2018T110247 , in part by the  Chinese Scholarship Council  under Grant  201706170165 , in part by the  NSFC  under Grant  61572048  and Grant  71601106 , and in part by the  Hong Kong ITF  under Grant  ITS/391/15FX.
Proteinogenic and non-proteinogenic amino acids, fatty acids or glycans are some of the main building blocks of nonribsosomal peptides (NRPs) and as such may give insight into the origin, biosynthesis and bioactivities of their constitutive peptides. Hence, the structural representation of NRPs using monomers provides a biologically interesting skeleton of these secondary metabolites. Databases dedicated to NRPs such as Norine, already integrate monomer-based annotations in order to facilitate the development of structural analysis tools. In this paper, we present rBAN (retrobiosynthetic analysis of nonribosomal peptides), a new computational tool designed to predict the monomeric graph of NRPs from their atomic structure in SMILES format. This prediction is achieved through the "in silico" fragmentation of a chemical structure and matching the resulting fragments against the monomers of Norine for identification.
Structures containing monomers not yet recorded in Norine, are processed in a "discovery mode" that uses the RESTful service from PubChem to search the unidentified substructures and suggest new monomers. rBAN was integrated in a pipeline for the curation of Norine data in which it was used to check the correspondence between the monomeric graphs annotated in Norine and SMILES-predicted graphs. The process concluded with the validation of the 97. 26% of the records in Norine, a two-fold extension of its SMILES data and the introduction of 11 new monomers suggested in the discovery mode. The accuracy, robustness and high-performance of rBAN were demonstrated in benchmarking it against other tools with the same functionality: Smiles2Monomers and GRAPE.
This approach is efficient with regular peptides, but not for NRPs. Other methods such as RECAP (Retrosynthetic Combinatorial Analysis Procedure)  [7] , BRICS (Breaking retrosynthetically interesting chemical substructures)  [8]  or molBLOCKS  [9]  use fragmentation rules to obtain drug-like chemical entities. However, these methods are focused on the discovery of structural motifs for drug design and they make no attempt to annotate the target compounds by identifying the resulting fragments. Moreover, their fragmentation rules are derived from common chemical reactions, lacking specificity for particular compounds such as NRPs. In recent years, two new tools specifically designed to target NRPs have been published. The first one, Smiles-2Monomers (s2m)  [10]  maps the monomers of a database within an atomic structure and selects the best combination (tiling) that covers the whole molecule with nonoverlapping monomers.
This approach is algorithmically elegant but computationally expensive. As a result, the best tiling is obtained as an approximate solution and the optimal mapping is not always found, sometimes leading to uncovered regions in the molecule. A second solution is implemented in GRAPE (Generalized Retro-biosynthetic Assembly Prediction Engine)  [2]  as the theoretical deconstruction of NRPs and Polyketides (PKs) by applying specific retro-biosynthetic reactions. The obtained fragments are then matched against a monomer library integrated in the software. A sequence of monomers is given as a result, but the original monomer linkages are lost. Both, GRAPE and s2m rely on their monomer database, which is a limitation for the analysis of peptides containing new monomers. Part of the interest in developing retro-biosynthesis tools arises from the benefit of a monomeric representation.
Chemical structure databases dedicate an important part of their resources in data curation, analysis and visualization. The complex structure of NRPs often results in too dense and unclear atomic representations. A monomeric format, as with peptide sequence annotation, reduces the complexity of the layout providing the same information in a more intelligible way and facilitates the implementation of substructure and similarity search algorithms  [11, 12]. Furthermore, this format is biologically meaningful as the monomers provide direct insights into the peptide activity and origin  [11, 13, 14]. These substructures bring essential information to understand the biosynthesis of the peptide and, given their bioactivities, they are interesting data for structure-based drug design studies. The convenience of the monomeric method is reflected in the emergence of new monomer-based notation formats.
Examples of that are the recent languages named HELM (Hierarchical Editing Language for Macromolecules)  [15, 16]  and SCSR (Self-Contained Sequence Representation)  [17] , which provide concise annotation of complex biopolymers in a component-based approach. Some databases devoted to bioactive peptides have also chosen this format to represent their data. This is the case of Norine  [18, 19] , which is entirely dedicated to NRPs and uses monomer graphs for structure depiction and analysis. Indeed, all the structural analysis tools integrated in Norine are monomer-based  [10] [11] [12] 14] , proving the advantages of the approach. Another example is the BIRD (Biologically Interesting molecule Reference Dictionary)  [20]  project from PDB (Protein Data Bank)  [21]. Here, the peptide-like inhibitor and antibiotic molecules are represented as polymers with sequence information or as single components.
BIRD is the result of a remediation work in which part of the PDB entries were reviewed in order to improve their representation and facilitate their identification and analysis. This kind of processes require a long and tedious effort that could be accelerated using bioinformatics tools. Hence, the usage of retro-biosynthesis software is decisive to improve these curation tasks by providing automatic annotation and assuring conciseness between the atomic and monomeric annotations. Additionally, the "in silico" retro-biosynthesis can also be applied to validate already annotated entries by checking the correspondence between the existing and the predicted annotations. A practice that would also spot potentially erroneous entries. In this article, we introduce rBAN, a new tool simulating the retro-biosynthesis of NRPs.
The main strategy of the software is to perform the fragmentation of a molecule by breaking it through a set of pattern bonds and matching the resulting fragments to a monomer database (Fig. 1 ). The matching process was specifically designed to allow tautomer's identification, a feature that was already presented in the s2m tool and named light matching. However, the two approaches are slightly different: the light matching of s2m omits all the implicit hydrogens and bond orders to match the monomer, while rBAN only omits the position of the double/triple bonds, making the method more restrictive and decreasing the likelihood of obtaining false positives. rBAN also introduces the "discovery mode" option that is applied when a monomer cannot be matched in the custom database. In this mode, missing substructure(s) can be automatically searched in PubChem  [22]  to suggest a new monomer.
This feature reduces the dependence to the database, providing more flexibility than the retro-biosynthetic approaches previously presented. Finally, the results are presented in a directed graph format that includes the bond types linking the monomers. To our knowledge, no other tool provides the bond type annotation though it can be highly relevant for its integration into structural analysis pipelines. rBAN is presented in two formats, as an executable jar and as a web application, the latter being a simplified version of the software. We used rBAN Fig. 1  Example of Vancomycin processing. A First, the primary bonds mapping searches the most common bonds between NRP monomers within the molecule. This process results in the mapping of two pairs of adjacent bonds that cannot be targeted simultaneously since it would isolate some atoms.
To avoid that all the possible combinations only including one of the neighboring bonds are computed. B Then, rBAN retrieves the substructures resulting from each combination and it matches them against the monomer database. A coverage score is given to each combination based on the number of atoms that could be annotated. C In this case, any of the results has a full coverage, so the algorithm proceeds to the secondary bonds search of the structure with the highest score. D The breakage of a carbon-carbon bond results in the full mapping of the peptide for the curation of the Norine database and benchmarked it against s2m and GRAPE.
NRPs monomer data Norine is dedicated to NRPs and was used to retrieve the monomer dataset in order to guarantee consistency between the target compounds and their building blocks. This dataset consists of 534 manually-annotated monomers extracted from the compositions of the NRPs in the database. Hence, the dataset is limited to the monomers present in Norine peptides and it may not be sufficient when used for the identification of fragments of new NRPs. To solve this issue, we developed an algorithm that suggests new monomers by adding modifications to the existing ones. In order to add a biological value to the predicted structures, the modifications were selected in accordance to some of the enzymatic reactions occurring in the NRP biosynthesis  [24, 25]  (see Additional file 1: Table  S1 ).
Fragmentation and identification The bonds mapped in the primary search are used as breaking points to obtain the fragments of the molecule. This is done using a breadth-first search algorithm to iterate through the chemical graph and compute the resulting fragments from those breakages. This action is performed for each permutation of bonds pro-vided, producing several sets of fragments that will be matched against the monomer database. Prior to this matching, the fragments are slightly modified in order to compute their expected structure outside the molecule -when not linked-thereby generating structures equivalent to those stored in the monomer database. The modifications applied are in accordance with the linkage patterns observed for each type of bond. For instance, a hydroxyl group is added to the formyl-ended fragment derived from a peptide bond breakage in order to obtain the "original" carboxyl-terminus structure of the monomer (see Additional file 1: Table  S2 ).
Once these modifications are applied, the monomers are matched against the database in order to identify them. Two different matching attempts are sequentially executed: the strict and the light matching. The strict matching will be only successful if the graph of the fragment is identical to the graph from the database. It checks the atom connectivities, the atom types and the bond orders. If a structure cannot be "strictly" matched, rBAN proceeds to light matching, which allows changes in the position of the double/triple bonds facilitating tautomer identification. Failure to match fragments can be due to the fragmentation of inner bonds in a monomer. Hence, when a fragment is not identified, the algorithm repeats the matching process by removing each of its linking bonds consecutively (Fig.
After the secondary bond search, the fragmentation and identification step is repeated. If the full score is still not reached and the monomer discovery mode is activated, rBAN moves to the next step. 4. Monomer discovery The unidentified substructures may represent missing monomers in the database. In these cases, the CDK library is used to generate the SMILES of the unknown chemical structure that serves as a parameter for an automatic PubChem search. The substructures successfully identified are annotated using their PubChem name and suggested in the results as new monomers for the Norine database. The information is presented in a JSON file where the compounds containing the suggested monomer are also listed. Graphical results are also provided. For each new monomer, rBAN creates a folder with the depictions of the peptides where the substructure occurs.
Norine Database Curation and Extension In Norine, the SMILES (atomic structure) and the monomer graphs (monomeric structure) are sometimes extracted from different resources. To guarantee the conciseness between the two representations and thereby validating the SMILES from Norine, rBAN was run to compare the SMILES-predicted monomeric graph with the Norine annotated graph. When the theoretical and the predicted graphs are identical, then the result is considered as correct and the corresponding SMILES is validated. From the 256 peptides that are described in SMILES, rBAN could validate 249 (97. 26%) (Fig. 5a1 ). The non-validated peptides were manually inspected and errors in their SMILES were identified. Hence, the lack of validation was attributed to wrong input data and not to a wrong mapping of the software.
In fact, the software helped to spot these wrong SMILES that were later corrected/removed from the database. An example is Enniatin F, whose monomeric annotation did not match the structure given by the SMILES (Fig. 5b ). As already mentioned, in the previous version of Norine only 256 entries (21. 56% of the total) contained the structural information in the SMILES format. In order to increase this count, we used the PubChem PUG-REST Service to perform automatic searches, retrieve the missing SMILES and validate them using rBAN. The only available parameters for the PubChem searches were the name of the compound, which lacks specificity, and the PubChem link provided by Norine, that is rarely present and occasionally wrong. Hence, the validation step becomes essential to reduce the uncertainty of the search and provide more reliable results.