dataesr/scientific-paragraphs-categorization huggingface dataset:
Concerning running time, each facet needs at most m flips to generate all its children in the spanning tree. Since a flip can be performed in O(mn) time (by Proposition 3. 9), the running time per facet of the greedy flip algorithm is still in O(m 2 n). We have implemented the greedy flip algorithm using the mathematical software Sage [S + 12] as part of a project 3  on implementing subword complexes. We have seen that these two algorithms for generating facets have the same theoretical complexity, namely O(m 2 n) per facet. To compare their experimental running time, we have constructed the k-cluster complex of type A n for increasing values of k and n. Its facets correspond to the k-triangulations of the (n + 2k + 1)-gon (see Example 3. 4 and  [CLS11]  for the definition of multicluster complexes in any finite type).
Acknowledgments We are very grateful to the two anonymous referees for their detailed reading of several versions of the manuscript, and for many valuable comments and suggestions, both on the content and on the presentation. Their suggestions led us to the current version of Proposition 5. 2, to correct a serious mistake in a previous version, and to improve several arguments in various proofs. V. P. thanks  M. Pocchiola  for introducing him to the greedy flip algorithm on pseudotriangulations and for uncountable inspiring discussions on the subject. We thank  M. Kallipoliti  and  H. Mühle  for mentioning our construction in [KM12]. Finally, we thank the  Sage and Sage-Combinat  development teams for making available this powerful mathematics software.
iLOVECLIM version 1. 0 iLOVECLIM is a coupled climate model of intermediate complexity. It is a code fork of the LOVECLIM1. 2 climate model  (Goosse et al. , 2010) , of which it retains only some of the physical climate components: the atmosphere (ECBilt), the ocean (CLIO) and the vegetation (VECODE) modules. It is thus a direct descendant of the ECBilt-CLIO-VECODEcoupled model that has successfully simulated a wide range of different climates from the last glacial maximum  (Roche et al. , 2007)  to the future  (Driesschaert et al. , 2007)  through the Holocene  (Renssen et al. , 2005 (Renssen et al. , , 2009) )  and the last millennia  (Goosse et al. , 2005). Details on the recent developments included in the present version and on its difference to the previous ones can be found in  Goosse et al.
The latter computes two PFTs (trees and grass) and a dummy type (bare soil). The vegetation model is resolved on the atmospheric grid (hence at T21 resolution) and allows the fractional allocation of PFTs in the same grid cell to account for the small spatial scale needed by vegetation. An iceberg trajectory module is also implemented  (Jongma et al. , 2009)  but is not activated in the present study. The different modules exchange heat, stress and water. It should be noted that precipitation correction is needed to avoid the overestimation of precipitation over the Arctic and the North Atlantic in ECBilt. Removed precipitation is then applied homogeneously in the North Pacific for water conservation purposes. For the sake of clarity, we note that the LOVECLIM1. 2, as described in  Goosse et al.
Simulated temperature fields Temperature is an important governing factor for the surface mass balance of the ice sheet. In the CTRL configuration, iLOVECLIM does not exhibit a coherent, systematic bias over the whole Greenland area (Fig. 14a  and b ). The mean annual temperatures are generally within ±2 • C of the climatological value, except for specific regions. Those include regions with high topography over a small spatial extent (overestimation of temperature by 5 • C in southern Greenland) and the sides of the ice sheet where the altitude varies a lot over a short distance (underestimation of 5 • C on the western and eastern flanks). Yet, taking into account that the climatology consists of present-day data and that it was probably about 2 • C colder during the pre-industrial times that we are simulating  (Kobashi et al.
Acknowledgements. This work is a contribution to the  INSU/LEFE/EVE  " RISCC " project. D. M. Roche  is supported by  INSU-CNRS  and  NWO  under project number n •  864. 09. 013. C. Dumas  and  S. Charbit  are supported by  CEA  ( Commissariat à l'Énergie Atomique et aux Énergies Alternatives ). M. Bügelmayer is supported by  NWO  under project number no  864. 09. 013. C. Ritz  is supported by  INSU-CNRS. We thank  Jeremy Fyke  and an anonymous reviewer for comments and suggestions that led to the substantial improvement of an earlier version of the manuscript. Edited by: I. Rutt The publication of this article is financed by  CNRS-INSU.
Motivation: Among challenges that hamper reaping the benefits of genome assembly are both unfinished assemblies and the ensuing experimental costs. First, numerous software solutions for genome de novo assembly are available, each having its advantages and drawbacks, without clear guidelines as to how to choose among them. Second, these solutions produce draft assemblies that often require a resource intensive finishing phase. Methods: In this paper we address these two aspects by developing Mix , a tool that mixes two or more draft assemblies, without relying on a reference genome and having the goal to reduce contig fragmentation and thus speed-up genome finishing. The proposed algorithm builds an extension graph where vertices represent extremities of contigs and edges represent existing alignments between these extremities.
Several software packages were developed in order to capitalize on different advantages of existing assemblers. Among these tools are GAM  [7] , minimus2  [8] , MAIA  [9] , Reconciliator  [10] , Zorro  [11]  and GAM-NGS  [12]. MAIA relies on a finished reference in order to guide the contig integration process; it is available as a MATLAB package. Zorro proceeds by masking the repeated regions known to cause problems during assembly. The minimus2 pipeline uses nucmer  [13]  to compute overlaps between contigs. GAM-NGS, Reconciliator and Zorro rely on reads in addition to assemblies for the merging process. Even when there is no clearly defined reference assembly, some tools still treat the two input assemblies differently; when referring to such setup we will use the term of asymmetry. Graph Accordance Assembly tool GAA  [14]  was developed in order to improve global assembly quality starting from two assemblies, one being the target and the other being the query.
Mycoplasma are a genus of mollicutes that are a class of wall-less bacteria. Consequently, the most pertinent evaluation of assembly tools' performance is against bacterial benchmarks. A recent thorough evaluation of both assemblers and assembly merging tools has been done by Magoc and co-authors and provides a benchmark of 12 bacterial datasets called GAGE-B  [15]. Most interestingly, at the end of their manuscript the authors mention that "over a large number of computational experiments, most combinations of assemblers, k-mer values, and merging algorithms did not produce improvements, and often produced inferior assemblies to the best individual assembly", with one exception where GAA produced superior results. Thus, GAA was chosen to be tested along with assembly tools in present work.
A very recent application GAM-NGS  [12]  attempts to merge two different assemblies by avoiding a mutual alignment step and mapping the raw reads on the two assemblies instead. The merging is based on the construction of a graph where the number of reads mapped on different regions is used to weight the edges and determine the correctness of merging two regions. An asymmetry is introduced between the two assemblies, one called the master and the other the slave, master assembly driving the merging process. Even if no clear assembly improvement is reported in the paper, since GAM-NGS was not included in the GAGE-B study, we have included it in our own benchmarking. In the current manuscript we describe Mix a finishing algorithm that generates an assembly starting from different genome assemblies with the main objective of reducing contig fragmentation and maximizing the cumulative contig length.
We address this question for the case where no reference genome is available and no asymmetry is introduced in dealing with assemblies, case not previously considered in literature. Moreover, we do not restrict ourselves to using only two assemblies. To address the excessive fragmentation, we propose a solution based on the maximal path problem in order to extend the contig length. To do this, we build a extension graph that connects contigs by their mutual alignments and is used to mix contigs when appropriate. We evaluate our Mix algorithm on GAGE-B benchmark and apply it to novel NGS data for 10 genomes from bacteria belonging to the genus Mycoplasma. We show that contrary to other tools that merge different assemblies, Mix clearly provides an advantage in terms of genome fragmentation while preserving the original assemblies characteristics in terms of missing bases and misassemblies.
A third, more robust, statistics is derived from the conservation of gene products. These last two statistics can be measured only if a fully assembled and annotated reference genomes is provided. In total 1171 different assemblies were produced by crossing each species, master and slave assembler datasets (for GAM and GAA) and all possible pairs of assemblers for Mix. All original assemblies were downloaded from the GAGE-B website, they consist of contigs assemblies and correspond to HiSeq libraries, with the exception of B. cereus for which we used assemblies based on MiSeq libraries in order to match the GAGE-B setup. Only 13 species/merger/assemblers combination are missing from the full factorial setup. Figure  3  reports the NA50 distributions per species and assembly merger contrasted with single (unmerged) assemblies.
Notably for B. cereus, for which the authors of GAGE-B already reported some improvement over single assemblies when using GAA, we manage with GAM or Mix to improve even more. The best Mix assembly for B. cereus stitches 90 contigs from MaSuRCA and 105 from SOAP into 47 contigs (including 4 extension paths), improving the NA50 score by 97%(NA50 of 487kb). For five out of six species, one of the top 5 assemblies generated by Mix is better than the best GAA, GAM and single assemblies. In particular, Mix significantly improves statistics measuring fragmentation of assemblies (for complete results, see results and figures available at https://github. com/cbib/MIX), as well as alignments of contigs. Similar plots and tabular data for other QUAST statistics are available on the accompanying MIX website.
2. ABySS consistently produced assemblies with the fewest errors and had the second best N50. 3. MIRA produced a large corrected N50 with errors occurring mostly in smaller contigs. Moreover, MIRA and ABySS rely on different algorithmic methods (overlap/layout/consensus and deBruijn graph construction, respectively). Two other considerations were taken into the account for the Mycoplasma case-study. First, ABySS was specifically developed for very short reads, which is the case for our application (see Table  1 ). Second, MIRA aims at combining reads from different sequencing technologies, which is the case for the Mycoplasma data (Illumina and 454). We have added the CLC Assembly Cell (based on the deBruijn graph), a commercial solution that was not part of the GAGE-B evaluation, but shows high N50 statistics.
For the number of contigs, the lower the better. For the other three statistics, the higher the better. goal has been previously explored by a number of papers, and in particular by the authors of GAA  [14]  and GAM-NGS  [12]. A recent GAGE-B evaluation for bacterial genomes of assemblers and assembly mergers concluded that the latter did not provide any advantage and even sometimes worsened the results. GAM-NGS was not included in that study. In current work we have described Mix , the first truly reference-free assembly merger. Our solution is based on solving the Maximal Independent Longest Path Set problem, known to be NP-hard, but tractable for this particular application and problem sizes. Evaluating Mix on the GAGE-B bacterial dataset, we show that our approach consistently lowers genome fragmentation without compromising biological relevance (ex.
HS is supported by an  ERASysBio+ EU ERA-NET Plus scheme in FP7  (project  LymphoSys ). Genome sequencing was done by the  Genoscope  ( Centre National de Séquençage, Evry, France ). Computer resources for assembly were provided by the computing facilities  MCIA (Mésocentre de Calcul Intensif Aquitain) of the Université de Bordeaux  and of the  Université de Pau et des Pays de l'Adour. This article has been published as part of  BMC Bioinformatics Volume 14 Supplement 15 , 2013: Proceedings from the  Eleventh Annual Research in Computational Molecular Biology (RECOMB) Satellite Workshop on Comparative Genomics. The full contents of the supplement are available online at http://www. biomedcentral. com/bmcbioinformatics/supplements/ 14/S15.
SIFT therefore requires to take intermediary poses to reconstruct the structure, which finally isn't making the use of SIFT faster than A SIFT. However, existing reconstruction programs like RGBDSLAM use a parallel version of SIFT called SIFT GPU using the Nvidia CUDA technology which considerably reduce its computation time. (Our team is currently interested in parallelizing A SIFT in the same way). We decided to keep only 3 correspondences that we judged good enough. (Red points on Fig. 5 ) We eventually implemented a way for the program to automatically keep 3 points that were clearly not collinear:  Among the correspondence points, we randomly choose 3 points. If they are almost collinear, we discard one point and randomly pick another one, and check again if they are almost colinear until they are not.
Here, we design a novel and integrated strategy to analyze reads when a reference genome is available. Our approach extracts information solely from the genome and read sequences, and is independent of any annotation; we implemented it in a program named CRAC. The rationale behind it is that an integrated analysis avoids recomputation, minimizes false inferences, and provides precise information on the biological events carried by a read. A peculiarity of CRAC is that it can deliver computational predictions for point mutations, indels, sequence errors, normal and chimeric splice junctions, in a single run. CRAC is compared with state-of-the-art tools for mapping (BWA, SOAP2, Bowtie, and GASSST)  [9] [10] [11] [12] [13] , and both normal (GSNAP, TopHat, and MapSplice)  [3, 14, 15]  and chimeric (TopHat-fusion)  [16]  splice junction predictions.
The results show the relevance of the approach in terms of efficiency, sensitivity, and precision (which is also termed specificity in the literature). We also provide true assessments of the sensitivity of each method by analyzing complex simulated data. Availability: CRAC is distributed under the GPL-compliant CeCILL-V2 license and is available as source code archive or a ready-to-install Linux package from the CRAC project website  [17]  or the ATGC bioinformatics platform  [18]. It includes two programs: crac-index to generate the index of the genome, and crac for analyzing the reads.
Results We evaluated CRAC for mapping reads, predicting candidate SNVs, indels, splice junctions, and chimeric junctions, and compared it to other tools. Simulated data are needed to compute exact sensitivity and accuracy levels, while real data enable us to study predictions with biologically validated RNAs. For simulating RNA-seq, we first altered a reference genome with random substitutions, indels, and translocations to derive a mutated genome, then reads were sequenced in silico using FluxSimulator  [22] , the annotated RefSeq transcripts, and a realistic distribution of random expression levels (Additional file 2). As read lengths will increase, we used two simulated datasets to assess different strategies: one (hs75) with a typical read length of 75, another (hs200) with reads of 200 nt representing the future.
For instance with indels, GSNAP yields 65% and 83% sensitivity on insertions and deletions respectively, Bowtie2 yields 70% sensitvity for both insertions and deletions, while the other tools remain below 30%. BWA, GASSST, Bowtie, and SOAP2 output continuous alignments for 9% to 19% of spliced reads, and Bow-tie2 up to 35%. Although their output locations are considered correct, for they are in one exon, their alignments are not. Such reads are considered as mapped and thus not reanalyzed by tools like TopHat or MapSplice in a search for splice junctions, which may lead to missing junctions. Analyzing longer reads (200 nt) is another challenge: the probabilities for a read to carry one or several differences (compared to the reference) are higher. In this dataset, 36% of the reads cover a splice junction, and 50% carry an error.
Compared to the 75 nt data, while their precision remains >99%, BWA, GASSST, Bowtie, Bowtie2, SOAP2, and GSNAP, have lower sensitivity (approximately 10 points less for BWA-SW, GASSST, and GSNAP, 14 for Bowtie2, and 20 for Bowtie). Only CRAC remains as precise and gains 1. 5 points in sensitivity (Table  1 ). The detail by category confirms this situation (Figure  2 ), showing CRAC is better than current tools. CRAC's k-mer profiling approach can accurately handle reads altered by distinct categories of biological events, and importantly adapts well to longer reads. The same analyses have been performed on Drosophila datasets and these show that all tools perform better, but the differences between tools remain (Additional file 3). The run times and memory usage of all tools are given in Additional file 3, Table  S3.
Predicting distinct categories of biological events Mapping is not a goal per se, but only a step in the analysis; the goal of read analysis is to detect candidate biological events of distinct categories (SNVs, indels, and splice and chimeric junctions) from the reads. The question is: if, for example, there is an SNV or splice junction that has been sequenced, can it be predicted and not buried under a multitude of false positives (FPs)? Here, sensitivity and precision are relative to the number of events, not to the number of reads covering them. We assessed CRAC's prediction ability and compared it to splice junction prediction tools on our simulated datasets. Figure  3  gives CRAC's precision and sensitivity for each category of events and for sequencing error detection. For SNVs and indels (<15 nt), CRAC achieves a sensitivity in the range [60,65]% and a precision in the range [96.
41%). With 200 nt reads, tools based on k-mer matching, that is CRAC and MapSplice, improve their sensitivity (6. 5 and 5 points respectively), while mapping-based approaches (GSNAP and TopHat) lose, respectively, 12 and 30 points in sensitivity, and TopHat2 gains 6. 4 points in sensitivity. With long reads, CRAC has the second best sensitivity and the best precision (>99%). It also exhibits a better capacity than MapSplice to detect junctions covered by few reads: 15,357 vs 13,101 correct junctions sequenced in ≤4 reads. A comparison using chimeric RNAs shows that CRAC already has an acceptable balance between sensitivity and precision with 75 nt reads (53% and 93%, respectively), while the sensitivities of TopHat-fusion and MapSplice remain below 32% (Table  3 ). With 200 nt The figure shows the mapping by event category on simulated RNA-seq against the human genome on datasets with short and long reads (left 42M, 75 nt; right 48M, 200 nt) for seven different mapping tools: Bowtie, Bowtie2, BWA/BWA-SW, CRAC, GASSST, GSNAP, and SOAP2.
Splice junction prediction To evaluate CRAC's ability to detect splice junctions in real RNA-seq data, we compared it to state-of-the-art tools (TopHat, GSNAP, and MapSplice) on a dataset of 75 million stranded 100 nt reads (ERR030856; see Additional file 4 Table  S1 ). Splice junctions were searched for using each tool and then compared to human RefSeq transcripts. Each found junction consists of a pair of genomic positions (that is, the exons 3' end and 5' start) and we considered that it matches a RefSeq junction if the positions were equal within a 3 nt tolerance. Found junctions were partitioned into known, new, and other junctions (KJs, NJs, and OJs, respectively). Known junctions are those already seen in a RefSeq RNA, new ones involve RefSeq exons but in a combination that has not yet been observed in RefSeq, while the remaining junctions go into  the class other.
The corresponding figures are 47% and 47% for GSNAP, 49% and 50% for MapSplice, 51% and 44% for TopHat. The percentages of OJs and NJs confirmed by mRNAs are >13% for CRAC and <8% for all other tools (excepted for OJs with TopHat, which was 17%, the same as CRAC). If we consider all junctions, 93% of CRAC junctions align entirely to an EST with a good hit. Whatever the class of the junctions, CRAC predicts more unreported junctions that are confirmed by mRNAs or ESTs than the other tools. This corroborates the precision rates obtained by these tools on simulated data. Regarding expressed transcripts, all tools detect >18,000 transcripts and agree on 17,131 of them (Additional file 4 Figure  S1 ). GSNAP and CRAC agree on 97% (19,431) of CRAC's detected transcripts, expressed in 15,589 distinct genes, which represents 87% of the 17,843 multi-exon RefSeq genes.
For the four uncertain cases, the k-mer support over the junction break equals one, meaning that only one read matches the junction exactly; hence CRAC identifies a chimeric junction, but classifies them as uncertain candidates TopHat-fusion reports approximately 200 times more raw candidates than CRAC; this ratio increases after filtering. Comparison with the set of validated chRNAs by Edgren et al. [27]  shows that both the filtered and unfiltered predictions of CRAC and TopHat-fusion include respectively 20 and 21 true chRNAs and they agree for 17 of them. (Undetermined file). Three out of four are nevertheless detected by TopHat-fusion, but with two or one spanning reads (2,1,1) and few supporting pairs (6,5,0), thereby corroborating CRAC's view and confirming these are expressed at very low levels in this dataset.
Discussion CRAC is a multi-purpose tool for analyzing RNA-seq data. In a single run it can predict sequencing errors, small mutations, and normal and chimeric splice junctions (collectively termed events). CRAC is not a pipeline, but a single program that can replace a combination of Bowtie, SAMtools, and TopHat/TopHat-fusion, and can be viewed as an effort to simplify NGS analysis. CRAC is not simply a mapper, since it uses local coverage information (in the support profile) before computing the genomic position of a read. In contrast to the current paradigm, mapping and post inferences are not disjoint steps in CRAC. Instead, it implements a novel, integrated approach that draws inferences by simultaneously analyzing both the genomic locations and the support of all k-mers along the read.
A more complex drawback of k-mer profiling is when two events are located <k positions apart on the genome (see the BCAS4-BCAS3 chimera); again such cases even with a high support are not fully resolved and end up in the BioUndetermined file. A post-processing of reads in this file, for example by an alignment program, could clearly save such cases. Obviously, such cases are rare, and we keep this as future work. As briefly mentioned, k-mer profiling also detects when reads span a repeat border region, which should help in inferring the locations of mobile genetic elements, duplications, or copy number variations; this suggests further developments and CRAC's usefulness for analyzing genomic data. Determining the correct genomic location of reads is crucial information for any NGS data analysis and especially for cataloging all transcripts of a cell with RNAseq.