dataesr/scientific-paragraphs-categorization huggingface dataset:
Impact of CG Initialization and Multi-Column Generation per Sub-Problem In this section, we analyze the results considering the standard Algorithm 5 with an exact resolution of sub-problems and generating one or several columns per sub-problem. The second variant is implemented by using the populate mode of Cplex with OPL; we note that it is possible to use all the columns with a negative reduced cost found using callbacks, which is not available with OPL but is now available in some MILP modeling interfaces and libraries such as PythonMIP or Julia JUMP. The generation of several columns is used at most for the five first iterations, and the remaining iterations are processed with the standard Algorithm 5 with at most one column generated per sub-problem. The maximal size of the population of Cplex is set to ten: at most, 10 new columns are added in the RMP.
Instance Characteristics, Benchmarks and Analysis Methodology 6. 1. 1. Instance Characteristics Instances were generated for this study; these instances are available online: https: //github. com/ndupin/SiteDepTRPTW (accessed on 25 October 2021). Instances are named gotic_a_b_c_exd. txt where a ∈ {3, 5, 8, 10, 15, 20} is the number of technicians, b ∈ {1, 3, 5, 10, 20} is the number of skill types, c ∈ {10, 20, 40, 50, 80, 100} is the number of jobs to plan and d ∈ [.
Dataset sc max with minimal speed (d ∈ [[1, 8]]) and maximal number of competences c max ; • Dataset Sc max with maximal speed (d ∈ [[11, 18]]) and maximal number of competences c max ; • Dataset s1 with minimal speed (d ∈ [[1, 8]]) and no skill constraint (c = 1); • Dataset S1 with maximal speed (d ∈ [[11, 18]]) and no skill constraint (c = 1).
6. 1. 1 Instance Characteristics, Benchmarks and Analysis Methodology 6. 1. 1. Instance Characteristics Instances were generated for this study; these instances are available online: https: //github. com/ndupin/SiteDepTRPTW (accessed on 25 October 2021). Instances are named gotic_a_b_c_exd. txt where a ∈ {3, 5, 8, 10, 15, 20} is the number of technicians, b ∈ {1, 3, 5, 10, 20} is the number of skill types, c ∈ {10, 20, 40, 50, 80, 100} is the number of jobs to plan and d ∈ [.
• Dataset sc max with minimal speed (d ∈ [[1, 8]]) and maximal number of competences c max ; • Dataset Sc max with maximal speed (d ∈ [[11, 18]]) and maximal number of competences c max ; • Dataset s1 with minimal speed (d ∈ [[1, 8]]) and no skill constraint (c = 1); • Dataset S1 with maximal speed (d ∈ [[11, 18]]) and no skill constraint (c = 1).
Dataset sc max (the Most Constrained Instances) Fail BKS Mean σ min Q1 Med Q3 Max LocalSolver 30 s LocalSolver 60 s LocalSolver 300 s LocalSolver 600 s LocalSolver 900 s 2 2 2 2 1 0 0 0 0 1 13. 68% 11. 24% 5. 36% 3. 89% 2. 99% 9. 93% 9. 61% 5. 78% 2. 63% 2. 37% 2. 43% 2. 31% 1. 30% 0. 70% 0. 00% 6. 47% 3. 76% 1. 96% 1. 91% 1. 68% 10. 78% 6. 99% 3. 35% 3. 35% 2. 49% 19. 09% 19. 03% 6. 96% 5. 06% 2. 95% 35. 86% 32. 18% 24. 52% 8. 76% 8. 26% RMP_INT_HEUR LAG_HEUR LAG_RINS LAG_RINS+VND 0 0 0 0 6 7 8 15 1. 09% 0. 81% 0. 19% 0. 08% 1. 32% 1. 10% 0. 29% 0. 27% 0. 00% 0. 00% 0. 00% 0. 00% 0. 00% 0. 00% 0. 00% 0. 00% 0. 50% 0. 43% 0. 08% 0. 00% 1. 82% 1. 07% 0. 29% 0. 00% 3. 66% 3. 66% 1. 12% 1. 12% 5 job,nbTec+VND 5 job,timeJob+VND 10 job,nbTec+VND 10 job,timeJob+VND init0+VND 0 0 0 0 0 3 2 1 0 2 2.
91% 3. 60% 3. 34% 4. 71% 5. 91% 2. 84% 3. 59% 3. 17% 3. 57% 6. 04% 0. 00% 0. 00% 0. 00% 0. 09% 0. 00% 0. 49% 0. 70% 1. 24% 2. 33% 1. 11% 2. 10% 2. 66% 2. 84% 4. 13% 4. 44% 4. 71% 5. 56% 4. 43% 7. 03% 10. 46% 9. 23% 14. 32% 13. 53% 11. 67% 20. 91% Multi-start VND 0 4 1. 71% 2. 33% 0. 00% 0. 11% 0. 66% 2. 49% 9. 23% For dataset sc max Fail BKS Mean σ min Q1 Med Q3 Max LocalSolver 30 s LocalSolver 60 s LocalSolver 300 s LocalSolver 600 s LocalSolver 900 s 0 0 0 0 0 0 0 3 5 5 7. 91% 5. 02% 1. 85% 1. 20% 0. 91% 5. 36% 3. 06% 1. 63% 1. 45% 1. 09% 1. 32% 0. 79% 0. 00% 0. 00% 0. 00% 4. 97% 2. 94% 0. 56% 0. 03% 0. 03% 7. 05% 4. 80% 1. 30% 0. 77% 0. 51% 8. 56% 6. 55% 2. 98% 1. 77% 1. 24% 24. 33% 13. 50% 4. 62% 4. 62% 3. 63% RMP_INT_HEUR LAG_HEUR LAG_RINS LAG_RINS+VND 0 0 0 0 5 7 9 16 1. 31% 0. 87% 0.
For Dataset S1 (the Less Constrained Instances) Fail BKS Mean σ min Q1 Med Q3 Max LocalSolver 30 s LocalSolver 60 s LocalSolver 300 s LocalSolver 600 s LocalSolver 900 s 0 0 0 0 0 0 0 3 6 8 7. 78% 6. 35% 2. 42% 1. 71% 0. 83% 5. 03% 4. 67% 3. 05% 2. 59% 1. 19% 2. 56% 0. 83% 0. 00% 0. 00% 0. 00% 3. 44% 2. 97% 0. 13% 0. 00% 0. 00% 6. 65% 5. 24% 0. 69% 0. 32% 0. 13% 11. 21% 7. 46% 4. 62% 1. 56% 1. 46% 19. 30% 15. 81% 9. 10% 7. 52% 3. 72% RMP_INT_HEUR LAG_HEUR LAG_RINS LAG_RINS+VND 0 0 0 0 3 5 11 16 0. 86% 0. 35% 0. 17% 0. 07% 0. 80% 0. 41% 0. 31% 0. 21% 0. 00% 0. 00% 0. 00% 0. 00% 0. 16% 0. 02% 0. 00% 0. 00% 0. 79% 0. 17% 0. 00% 0. 00% 1. 29% 0. 67% 0. 13% 0. 00% 2. 21% 1. 36% 0. 86% 0. 86% 5 job,nbTec+VND 5 job,timeJob+VND 10 job,nbTec+VND init0+VND 0 0 0 0 9 9 8 11 0. 67% 0. 67% 0. 99% 0. 68% 0.
Third-generation sequencing technologies allow to sequence long reads of tens of kbp, that are expected to solve various problems. However, they display high error rates, currently capped around 10%. Self-correction is thus regularly used in long reads analysis projects. We introduce CONSENT, a new self-correction method that relies both on multiple sequence alignment and local de Bruijn graphs. To ensure scalability, multiple sequence alignment computation benefits from a new and efficient segmentation strategy, allowing a massive speedup. CONSENT compares well to the state-of-the-art, and performs better on real Oxford Nanopore data. Specifically, CONSENT is the only method that efficiently scales to ultra-long reads, and allows to process a full human dataset, containing reads reaching up to 1.
5 Mbp, in 10 days. Moreover, our experiments show that error correction with CONSENT improves the quality of Flye assemblies. Additionally, CONSENT implements a polishing feature, allowing to correct raw assemblies. Our experiments show that CONSENT is 2-38x times faster than other polishing tools, while providing comparable results. Furthermore, we show that, on a human dataset, assembling the raw data and polishing the assembly is less resource consuming than correcting and then assembling the reads, while providing better results. CONSENT is available at https ://githu b. com/moris pi/CONSE NT. Third-generation sequencing technologies Pacific Biosciences (PacBio) and Oxford Nanopore Technologies (ONT) have become widely used since their inception in 2011. In contrast to second-generation technologies, producing reads reaching lengths of a few hundreds base pairs, they allow the sequencing of much longer reads (10 kbp on average 1 , and up to > 1 million bps 2 ).
Our experiments show that CONSENT compares well to the latest state-of-the-art self-correction methods, and outperforms them on real ONT datasets. In particular, they show that CONSENT is the only method able to efficiently scale to ONT ultra-long reads, allowing to perform correction of a full human dataset, containing reads reaching up to 1. 5 Mbp in 10 days. Additionally, CONSENT is also able to polish assemblies generated from raw long reads. Our experiment on a full human dataset shows that assembling the raw data and polishing the assembly is less resource consuming than correcting and then assembling the data, while offering better results. Our experiments also show that CONSENT outperforms state-of-the-art assembly polishing tools in terms of resource consumption, while providing comparable results.
www. nature. com/scientificreports/ Datasets. For our experiments, we used simulated PacBio long reads, as well as real PacBio and ONT long reads. PacBio simulated reads were generated with SimLoRD, using the previously mentioned parameters. We generated two datasets with a 12% error rate for E. coli, S. cerevisiae and C. elegans: one with a 30x coverage, and one with a 60x coverage, corresponding to typical sequencing depths in current long reads experiments. As for the real data, we used a 89x coverage dataset from S. cerevisiae, a 63x coverage dataset from D. melanogaster, and a 29x coverage from H. sapiens chr 1, containing ultra-long reads, reaching lengths up to 340 kbp. Human data were sequenced by 2 ] and are publicly available with accession number PRJEB23027 (release 4). D. melanogaster data are publicly available with accession number SRX3676783.
Real S. cerevisiae data are publicly available with accession number SRR9617898. Further details for all the datasets are given in Supplementary Table  S1. We used the reference genomes K-12 substr. MG1655 for E. coli, S288C for S. cerevisiae, Bristol N2 for C. elegans, BDGP Release 6 for D. melanogaster, and GRCh38 for H. sapiens. Further details on the reference sequences are given in Supplementary Table  S2. Comparison on simulated data. To precisely assess the accuracy of the different correction methods, we first tested them on the simulated PacBio datasets. ELECTOR was used to evaluate the correction accuracy of each method. Correction statistics of all the aforementioned tools on the different datasets, along with their runtime and memory consumption, are given in Table  1. For methods having distinct, easily identifiable, steps for overlapping and correction (i.
e. Daccord, MECAT and CONSENT), we additionally report runtime and memory consumption of these two processes apart. We ran all the correction experiments on a computer equipped with 16 2. 39 GHz cores and 32 GB of RAM. All tools were thus run with 16 threads. Daccord clearly performed the best in terms of number of bases and quality, outperforming all the other methods on the E. coli and the S. cerevisiae datasets. However, the overlapping step, relying on actual alignment of the long reads against each other, consumed high amounts of memory, 3x to 11x more than CONSENT or MECAT mapping strategies. As a result, Daccord could not scale to the C. elegans datasets, DALIGNER reporting an error upon start, even when run on a cluster node equipped with 128 GB of RAM. On the contrary, Canu displayed the highest error rates on all the datasets, except on the C.
elegans dataset with a 30x coverage, but consumed relatively stable, low amounts of memory. In particular, on the two C. elegans datasets, it displayed the lowest memory consumption among all the other methods. MECAT performed the best in terms of runtime, outperforming all the other tools on all the datasets. Its overlapping strategy was also highly efficient, and displayed the lowest memory consumption among all the other strategies, on all the datasets. However, compared to Minimap2 (the overlapping strategy adopted in CONSENT) MECAT's overlapping strategy displayed higher runtimes, although it remained faster than Daccord's DALIGNER. Minimap2's memory consumption, however, was larger than that of MECAT's overlapping strategy, on all the datasets. The memory consumption of Minimap2 can nonetheless easily be reduced, at the expense of a slightly larger runtime, by decreasing the size of the index used for computing the overlaps, which CONSENT sets to 1 Gbp by default.
Compared to both FLAS and CONSENT, MECAT displayed lower number of bases on all the datasets. As for FLAS, this can be explained by the fact that it is a MECAT wrapper, allowing to retrieve additional overlaps, and thus correct a greater number long reads. As a result, since it relies on MECAT's error correction strategy, FLAS displayed highly similar memory consumption. Runtime was however higher, due to the additional steps allowing to retrieve supplementary overlaps, and to the resulting higher number of reads to correct. Numbers of bases and error rates of FLAS and CONSENT were highly similar on all the datasets, varying by 0. 12% at most, on the S. cerevisiae dataset with a 30x coverage. CONSENT was also faster than FLAS on the E. coli and S. cerevisiae datasets. However, on the C. elegans datasets, CONSENT displayed slightly higher runtimes.
As for the memory consumption of the error correction step, CONSENT was less efficient than MECAT on most datasets. This can be explained by the fact that CONSENT loads the correction jobs into a queue of default size 100,000. This queue thus loads the necessary data for 100,000 correction tasks into memory at once. We then iteratively allocate new tasks to threads as they become available. Reducing the size of this queue would allow CONSENT to consume less memory, at the expense of a slightly higher runtime, since the queue would have to be repopulated more often. Comparison on real data. We then evaluated the different correction methods on a real PacBio S. cerevisiae dataset, as well as on larger, real ONT datasets from D. melanogaster and H. sapiens (chr 1). For these datasets, we not only evaluate how well the corrected long reads realign to the reference genome, but also how well they assemble.
For the alignment assessment, we report how many reads were corrected, their total number of bases, their N50, the proportion of corrected reads that could be aligned, the average identity of the alignments, as well as the genome coverage, that is, the percentage of bases of the reference genome to which at least a nucleotide aligned. For the assembly assessment, we report the overall number of contigs, the number of contigs that could be aligned, the NGA50 and NGA75, and, once again, the genome coverage. We obtained alignment statistics using ELECTOR's second module, which performs alignment to the reference genome with Minimap2. We performed assemblies using Minimap2 and Miniasm  27. Moreover, for the H. sapiens (chr 1) dataset, we performed additional assembly experiments using the more modern and sophisticated assembler Flye  28.
Assembly statistics were obtained with QUAST-LG  29. Results are given in Table  2  for the alignment assessment, and in Table  3  for the assembly assessment. Runtimes and memory consumption of the different methods are also given in Table  2. As for the simulated data, we report runtime and memory consumption of the overlapping and correction steps apart, when possible. We ran all the correction experiments on a cluster node equipped with 28 2. 39 GHz cores and 128 GB of RAM. All tools were thus run with 28 threads. On these three datasets, Daccord failed to run, as DALIGNER could not perform alignment, for the same reason as for the simulated C. elegans datasets. For all the datasets, CONSENT corrected the largest number of reads, output the largest number of bases, and reached the largest genome coverage.
On the S. cerevisiae dataset, CONSENT reached slightly lower alignment identity than the other tools. However, on the two more complex ONT datasets, CONSENT displayed the highest alignment identity. Additionally, the N50 of CONSENT was the highest on the S. cerevisiae dataset, and was higher than that of all the others methods, except Canu, on the two ONT datasets. When it comes to runtime and memory consumption, MECAT outperformed all the other methods, as in the experiments on simulated data. However, it is worth noting that the runtime was comparable to other methods, and that CONSENT was the second fasted tool after MECAT on the two ONT datasets. Finally, MECAT reached the highest proportion of aligned reads, on all datasets, although CONSENT was close, since only 0. 24-1. 21% fewer reads could be aligned.
Moreover, on the H. sapiens (chr 1) dataset, CONSENT and Canu were the only tools able to deal with ultralong reads. Indeed, other methods reported errors when attempting to correct the original dataset. As a result, Table  1. Metrics output by ELECTOR on the simulated PacBio datasets. Daccord results are missing for the two C. elegans datasets, as DALIGNER failed to perform alignment, reporting an error upon start, even when ran on a cluster node with 28 2. 4 GHz cores and 128 GB of RAM. Recall and precision are not reported for original reads, since they cannot be computed from uncorrected reads. Best results for each metric is highlighted in bold. in order to allow these methods to perform correction, we had to manually remove the reads longer than 50 kbp. There were 1,824 such reads, accounting for a total number of 135,364,312 bp.
However, even if it managed to scale to the correction of ultra-long reads, Canu was almost seven times slower than CONSENT, making CONSENT the only tool to efficiently scale to ultra-long reads. On the S. cerevisiae dataset, the assembly yielded from FLAS corrected reads outperformed all the other assemblies in terms of number of contigs. Oppositely, the assembly yielded from CONSENT corrected reads displayed the largest number of contigs. It also displayed more errors per 100 kbp and a slightly higher number of misassemblies compared to other assemblies. Canu corrected reads yielded the assembly covering the largest proportion of the reference genome, whereas MECAT corrected reads yielded the assembly displaying the lowest number of misassemblies and errors per 100 kbp. However, all assemblies were comparable in terms of NGA50 and NGA75, and CONSENT even outperformed MECAT in terms of NGA75.
On the D. melanogaster dataset, the assembly yielded from CONSENT corrected reads outperformed all the other assemblies in terms of number of contigs, NGA50, NGA75, as well as error rate per 100 kbp. In particular, the NGA50 of the CONSENT assembly was 2. 1-6. 8 times larger than that of other assemblies. The assembly yielded from Canu corrected reads outperformed all the other assemblies in terms of genome coverage, but was composed of the highest number of contigs, after the assembly obtained from the raw reads. However, the genome coverage of the CONSENT assembly was slightly larger than that of FLAS and MECAT. Finally, in terms of misassemblies, the assembly generated from MECAT corrected reads outperformed the other assemblies, although they all remained comparable on this metric. On the H.
sapiens (chr 1) dataset, the assembly obtained from CONSENT corrected reads once again outperformed all the other assemblies in terms of number of contigs, NGA50, and NGA75. In particular, the NGA50 of the CONSENT assembly was almost 1. 6-4. 3 times larger than that of other assemblies. However, 12 contigs of the CONSENT assembly could not be aligned to the reference. As a result, compared to the assemblies obtained from FLAS and MECAT corrected reads, the assembly yielded from the CONSENT corrected reads covered 2. 6% less of the reference sequence, and displayed a higher error rate per 100 kbp. These unaligned contigs and differences could likely be reduced by further adapting both CONSENT and Miniasm parameters. Moreover, the assembly yielded from CONSENT corrected reads displayed a slightly higher number of misassemblies, although it remained comparable to that of other assemblies.
On this metric, the assembly generated from MECAT corrected reads once again slightly outperformed other assemblies. In addition, as we previously mentioned, we also performed additional assembly experiments using the more modern and sophisticated assembler Flye on the H. sapiens (chr 1) dataset. Here, the assembly yielded from CONSENT corrected reads displayed the smallest number of contigs, and the lowest number of errors per 100 Table  2. Statistics of the real long reads, before and after correction with the different methods. Best results for each metric is highlighted in bold. 1  Reads longer than 50 kbp were filtered out, as ultra-long reads caused the programs to stop with an error. There were 1824 such reads in the original dataset, accounting for a total number of 135,364,312 bp.
2  Daccord could not be run on these two datasets, due to errors reported by DALIGNER. kbp. Its number of misassemblies was also smaller than that of all other assemblies, except the one generated from Canu corrected reads. Morever, the proportion of aligned contigs and the genome coverage were highly similar for all assemblies. Interestingly, only the assembly generated from CONSENT corrected reads allowed to reach larger NGA50 and NGA75 than the assembly generated from the raw reads. Compared to other correction tools, CONSENT is the only method allowing to enhance the quality of the Flye assembly in such a way. Indeed, all the other assemblies, despite displaying a smaller number of contigs than the assembly generated from raw reads, reached smaller NGA50 and NGA75. These results thus underline the fact that Flye can benefit from CONSENT correction to generate higher quality assemblies.
Assembly polishing. As an additional feature, CONSENT also allows to perform assembly polishing. The process is pretty straightforward. Indeed, instead of computing overlaps between the long reads, as presented in the previous sections, overlaps are simply computed between the assembled contigs and the long reads used for the assembly. The rest of the pipeline remains the same. We present assembly polishing results on the simulated E. coli, S. cerevisiae, and C. elegans datasets with a 60x coverage, as well as on the real S. cerevisiae, D. melanogaster and H. sapiens (chr 1) datasets. We compare CONSENT to RACON  30  , a state-of-the-art assembly polishing method. Results are presented in Table  4. We ran all the polishing experiments on a cluster node equipped with 28 2. 39 GHz cores and 128 GB of RAM.
All tools were thus run with 28 threads. Moreover, we only compare the runtimes of the actual polishing steps of the tools. Thus, the runtime of Minimap2, and the runtime of CONSENT pre-processing steps (sorting and reformatting the overlaps file) are not taken into account in the comparisons. Although these pre-processing steps can be slow for large datasets and large overlaps files, and are not required by RACON, we would like to underline that they allow to avoid the burden of loading the full overlaps file into memory, as required by RACON. The benefits of these pre-processing steps can be confirmed by comparing the memory consumption of CONSENT and RACON, as commented below. Moreover, to further emphasize the interest of these pre-processing steps, additional experiments on another human dataset (accession number NA12878, release 6), which are not presented here, have shown RACON could require more than 2 TB of RAM, while CONSENT displayed a peak of 39 GB.
These results show that CONSENT outperformed RACON in terms of quality of the results, especially dealing better with errors, and thus greatly reducing the error rate per 100 kbp, on the E. coli, S. cerevisiae, and C. elegans datasets. RACON outperformed CONSENT in terms of NGA50, NGA75, genome coverage, and number of misassemblies, but the two methods were highly comparable on these three datasets. Oppositely, RACON Table  3. Statistics of the assemblies generated from the raw and corrected real long reads. Best results for each metric is highlighted in bold. 1  As previously mentioned, Daccord results on the three datasets are absent, since it could not be run. 2 For the assembly of the original reads on the H. sapiens (chr 1) dataset, QUAST-LG did not provide a metric for the NGA75. outperformed CONSENT in terms of errors per 100 kbp on the S.
Dataset For the larger, eukaryotic D. melanogaster dataset, RACON outperformed CONSENT in terms of number of errors per 100 kbp, and genome coverage, but the NGA50, NGA75 of the two methods remained comparable. On the H. sapiens (chr 1) dataset, RACON once again outperformed CONSENT in terms of error rate and genome coverage, and also displayed larger NGA50 and NGA75. However, polishing the assembly with CONSENT allowed to align a greater proportion of contigs, compared to both the raw and the RACON polished assembly. On these two datasets, RACON slightly outperformed CONSENT in terms of number of misassemblies, although the two methods remained highly comparable. 2Additionally, on all the datasets, the polishing step of CONSENT was 3x to 38x faster than RACON, and also consumed up to four times less memory, thanks to its pre-processing steps.