Željko Agić
email: zeljko.agic@hum.ku.dk

Anders Johannsen

Barbara Plank

♥ ♣ Héctor Martínez

Natalie Schluter

Anders Søgaard
email: soegaard@hum.ku.dk

Multilingual Projection for Parsing Truly Low-Resource Languages

We propose a novel approach to cross-lingual part-of-speech tagging and dependency parsing for truly low-resource languages. Our annotation projection-based approach yields tagging and parsing models for over 100 languages. All that is needed are freely available parallel texts, and taggers and parsers for resource-rich languages. The empirical evaluation across 30 test languages shows that our method consistently provides top-level accuracies, close to established upper bounds, and outperforms several competitive baselines.

Introduction

State-of-the-art approaches to inducing part-ofspeech (POS) taggers and dependency parsers only scale to a small fraction of the world's ∼6,900 languages. The major bottleneck is the lack of manually annotated resources for the vast majority of these languages, including languages spoken by millions, such as Marathi (73m), Hausa (50m), and Kurdish (30m). Cross-lingual transfer learning-or simply cross-lingual learning-refers to work on using annotated resources in other (source) languages to induce models for such low-resource (target) languages. Even simple cross-lingual learning techniques outperform unsupervised grammar induction by a large margin.

Most work in cross-lingual learning, however, makes assumptions about the availability of linguistic resources that do not hold for the majority of low-resource languages. The best cross-lingual dependency parsing results reported to date were pre-sented by [START_REF] Sadegh | Density-Driven Cross-Lingual Transfer of Dependency Parsers[END_REF]. They use the intersection of languages covered in the Google dependency treebanks project and those contained in the Europarl corpus. Consequently, they only consider closely related Indo-European languages for which high-quality tokenization can be obtained with simple heuristics.

In other words, we argue that recent approaches to cross-lingual POS tagging and dependency parsing are biased toward Indo-European languages, in particular the Germanic and Romance families. The bias is not hard to explain: treebanks, as well as large volumes of parallel data, are readily available for many Germanic and Romance languages. Several factors make cross-lingual learning between these languages easier: (i) We have large volumes of relatively representative, translated texts available for all language pairs; (ii) It is relatively easy to segment and tokenize Germanic and Romance texts; (iii) These languages all have very similar word order, making the alignments much more reliable. Therefore, it is more straightforward to train and evaluate cross-lingual transfer models for these languages.

However, this bias means that we possibly overestimate the potential of cross-lingual learning for truly low-resource languages, i.e., languages with no supporting tools or resources for segmentation, POS tagging, or dependency parsing.

The aim of this work is to experiment with crosslingual learning via annotation projection, making minimal assumptions about the available linguistic resources. We only want to assume what we can in fact assume for truly low-resource languages. Thus, for the target languages, we do not assume the avail-ability of any labeled data, tag dictionaries, typological information, etc. For annotation projection, we need a parallel corpus, and we therefore have to rely on resources such as the Bible (parts of which are available in 1,646 languages), and publications from the Watchtower Society (up to 583 languages). These texts have the advantage of being translated both conservatively and into hundreds of languages (massively multi-parallel). However, the Bible and the Watchtower are religious texts and are more biased than the corpora that have been assumed to be available in most previous work.

In order to induce high-quality cross-lingual transfer models from noisy and very limited data, we exploit the fact that the available resources are massively multi-parallel. We also present a novel multilingual approach to the projection of dependency structures, projecting edge weights (rather than edges) via word alignments from multiple sources (rather than a single source). Our approach enables us to project more information than previous approaches: (i) by postponing dependency tree decoding to after the projection, and (ii) by exploiting multiple information sources.

Our contributions are as follows:

(i) We present the first results on cross-lingual learning of POS taggers and dependency parsers, assuming only linguistic resources that are available for most of the world's written languages, specifically, Bible excerpts and translations of the Watchtower.

(ii) We extend annotation projection of syntactic dependencies across parallel text to the multisource scenario, introducing a new, heuristicsfree projection algorithm that projects weight matrices from multiple sources, rather than dependency trees or individual dependencies from a single source.

(iii) We show that our approach performs significantly better than commonly used heuristics for annotation projection, as well as than delexicalized transfer baselines. Moreover, in comparison to these systems, our approach performs particularly well on truly low-resource non-Indo-European languages.

All code and data are made freely available for general use. 12 Weighted annotation projection Motivation Our approach is based on the general idea of annotation projection [START_REF] Yarowsky | Inducing Multilingual Text Analysis Tools via Robust Projection Across Aligned Corpora[END_REF] using parallel sentences. The goal is to augment an unannotated target sentence with syntactic annotations projected from one or more source sentences through word alignments. The principle is illustrated in Figure 1, where the source languages are German and Croatian, and the target is English.

The simplest case is projecting POS labels, which are observed in the source sentences but unknown in the target language. In order to induce the grammatical category of the target word beginning, we project POS from the aligned words Anfang and početku, both of which are correctly annotated as NOUN. Projected POS labels from several sources might disagree for various reasons, e.g., erroneous source annotations, incorrect word alignments, or legitimate differences in POS between translation equivalents. We resolve such cases by taking a majority vote, weighted by the alignment confidences. By letting several languages vote on the correct tag of each word, our projections become more robust, less sensitive to the noise in our source-side predictions and word alignments.

We can also project syntactic dependencies across word alignments. If (u s , v s ) is a dependency edge in a source sentence, say the ingoing dependency from das to Wort, u s (Wort) is aligned to u t (word), and v s (das) is aligned to v t (the), we can project the dependency such that (u t , v t ) becomes a dependency edge in the target sentence, making the a dependent of word. Obviously, dependency annotation projection is more challenging than projecting POS, as there is a structural constraint: the projected edges must form a dependency tree on the target side. [START_REF] Hwa | Bootstrapping Parsers via Syntactic Projection Across Parallel Texts[END_REF] were the first to consider this problem, applying heuristics to ensure well-formed trees on the target side. The heuristics were not perfect, as they have been shown to result in excessive non-projectivity and the introduction of spurious relations and tokens [START_REF] Tiedemann | Treebank Translation for Cross-Lingual Parser Induction[END_REF][START_REF] Tiedemann | Rediscovering Annotation Projection for Cross-Lingual Parser Induction[END_REF]. These design choices all lead to di-Figure 1: An outline of dependency annotation projection, voting, and decoding in our method, using two sources i (German) and j (Croatian) and a target t (English). Part 1 represents the multi-parallel corpus preprocessing, while parts 2 and 3 relate to our projection method. The graphs are represented as adjacency matrices with column indices encoding dependency heads. We highlight how the weight of target edge (u t = was, v t = beginning) is computed from the two contributing sources. minished parsing quality.

We introduce a heuristics-free projection algorithm. The key difference from most previous work is that we project the whole set of potential syntactic relations with associated weights-rather than binary dependency edges-from a large number of multiple sources. Instead of decoding the best tree on the source side-or for a single source-target sentence pair-we project weights prior to decoding, only decoding the aggregated multi-source weight matrix after the individual projections are done. This means that we do not lose potentially relevant information, but rather project dense information about all candidate edges.

Multi-source sentence graph

We assume the existence of n source languages and a target language t. For each tuple of translations in our multi-parallel corpus, our algorithm projects syntactic annotations from the n source sentences to the target sentence.

Projection happens at the sentence-level, taking a tuple of n annotated sentences and an unannotated sentence as input. We formalize the projection step as label propagation in a graph structure where the words of the target and source sentences are vertices, while edges represent dependency edge candidates between words within a sentence (a parse), as well as similarity relations between words of sentences in different languages (word alignments).

Formally, a projection graph is a graph G = (V, E). All edges are weighted by the function w e : E → R. The vertices can be decomposed into sets

V = V 0 ∪ • • • ∪ V n
, where V i is the set of words in sentence i.

We often need to identify the target sentence V t = V 0 and the source sentences

V s = V 1 ∪ • • • ∪ V n sep-
arately. Edges between V s and V t are the result of word alignments. The alignment subgraph is the bipartite graph A = (V s , V t , E A ), i.e., the subgraph of G induced by all (alignment) edges, E A , connecting V s and V t .

The subgraph induced by the set of vertices V i , written as G[V i ], represents the dependency edge candidates between the words of the sentence i. In general these subgraphs are dense, i.e., they encode weight matrices of edge scores and not just the single best parse. For the source sentences, we assume that the weights are provided by a parser, while the weights for the syntactic relations of the target sentence are unknown.

With the above definitions, the dependency projection problem amounts to assigning weights to the edges of G[V t ] by transferring the syntactic parse graphs G[V 1 ], . . . , G[V n ] from the source languages through the alignments A.

Part-of-speech projection

Our annotation projection for POS tagging is similar to the one proposed by [START_REF] Nivre | Universal Dependencies 1[END_REF]. The algorithm is presented in Algorithm 1. We first introduce a conditional probability distribution p(l|v)

Algorithm 1: Project POS tags Data: A projection graph G = (V s ∪ V t , E); a set of POS labels L; a function p(l|v) assigning probabilities to labels l for word vertices v.

Result: A labeling of V t p ← empty probability table label ← empty label-to-vertex mapping for v t ∈ V t do for l ∈ L do p(l|v t ) ← vs∈Vs p(l|v s )w a (v s , v t ) label(v t ) ← arg max l p(l|v t ) return label Algorithm 2: Project dependencies Data: A projection graph G = (V s ∪ V t , E). Result: A dependency tree covering the target vertices V t . if project from trees then for i=1 to n do G[V i ] ← DMST(G[V i ]) for (u t , v t ) ∈ G[V t ] do w e (u t , v t ) ← -∞ if (•, u t ) or (•, v t ) / ∈ E A then continue w e (u t , v t ) ← n i=1 max us,vs∈V i w e (u s , v s ) w a (u s , u t ) w a (v s , v t ) G[V t ] ← normalize(G[V t ]) return DMST(G[V t ])
over POS tags l ∈ L for each vertex v in the graph. For all source vertices, the probability distributions are obtained by tagging the corresponding sentences in our multilingual corpus with POS taggers, assigning a probability of one to the best tag for each word, and zero for all other tags. For each target token, i.e., each vertex v, the projection works by gathering evidence for each tag from all source tokens aligned to v, weighted by the alignment score:

p(l|v t ) ∝ vs∈Vs p(l|v s ) w a (v s , v t )
The projected tag for a target vertex v t is then arg max l p(l|v t ). When both the alignment weights and the source tag probabilities are in {0, 1}, this reduces to a simple voting scheme that assigns the most frequent POS tag among the aligned words to each target word.

Dependency projection

While in POS projection, we project vertex labels, in dependency projection we project edge scores. Our procedure for dependency annotation projection is given in Algorithm 2. For each source language, we parse the corresponding side of our multi-parallel corpus using a dependency parser trained on the source language treebank. However, instead of decoding to dependency trees, we extract the weights for all potential syntactic relations, importing them into G as edge weights.

The parser we use in our experiments assigns scores w e ∈ R to possible edges. Since the ranges and values of these scores are dependent on the training set size and the number of model updates, we standardize the scores to make them comparable across languages. Standardization centers the scores around zero with a standard deviation of one by subtracting the mean and dividing by the standard deviation. We apply this normalization per sentence.

Scores are then projected from source edges to target edges via word alignments w a ∈ [0, 1]. Instead of voting among the incoming projections from multiple sources, we sum the projected edge scores. Because alignments vary in quality, we scale the score of the projected source edge by the corresponding alignment probability.

A target edge (u t , v t ) ∈ G[V t ] can originate from multiple source edges even from a single source sentence, due to m : n alignments. In such cases, we only project the source edge (u s , v s ) ∈ G[V i>0 ] with the maximum score, provided the words are aligned, i.e., (u s , u t ) and (v s , v t ) ∈ E A .

In the case of a single source sentence pair, the target edge scores are set as follows:

w e (u t , v t ) ← max us,vs∈V i edge w e (u s , v s ) alignment w a (u s , u t ) w a (v s , v t )
We note the distinction between edge weights w e and alignment weights w a . With multiple sources, the target edge scores w e (u t , v t ) are computed as a sum over the individual sources:

n i=1 max us,vs∈V i w e (u s , v s ) w a (u s , u t ) w a (v s , v t )
After projection we have a dense set of weighted edges in the target sentence representing possible syntactic relations. This structure is equivalent to the n × n edge matrix used in ordinary first-order graph-based dependency parsing.

Before decoding, the weights are softmaxnormalized to form a distribution over each possible head decision. The normalization balances out the contributions of the individual head decisions; and in our development setup, we found that omitting this step resulted in a substantial (∼10%) decrease in parsing performance.

We then follow [START_REF] Mcdonald | Online Large-Margin Training of Dependency Parsers[END_REF] in using directed maximum spanning tree (DMST) decoding to identify the best dependency tree in the matrix. We note that DMST decoding on summed projected weight matrices is similar to the idea of re-parsing with DMST decoding of the output on an ensemble of parsers [START_REF] Sagae | Parser Combination by Reparsing[END_REF], which we use as a baseline in our experiments.

Data

Training and test sets

We use source treebanks from the Universal Dependencies (UD) project, version 1.2 [START_REF] Nivre | Universal Dependencies 1[END_REF]. 2 They are harmonized in terms of POS tag inventory (17 tags) and dependency annotation scheme. In our experiments, we use the canonical data splits, and disregard lemmas, morphological features and alternative POS from all treebanks.

Out of the 33 languages currently in UD1.2, we drop languages for which the treebank does not distribute word forms (Japanese), and languages for which we have no parallel unlabeled data (Latin, Ancient Greek, Old Church Slavonic, Irish, Gothic). Languages with more than 60k tokens (in the training data) are considered source languages, the remaining 6 smaller treebanks (Estonian, Greek, Hungarian, Latin, Romanian, Tamil) are strictly considered targets. This results in 22 treebanks for training source taggers and parsers. We use two additional test sets: Quechua and Serbian. The first one does not entirely adhere to UD, but we provide a POS tagset mapping and a few modifications and include it as a test language to deepen the robustness assessment for our approach across language families. The Serbian test set fully conforms to UD, as a fork of the closely related Croatian UD dataset. 3 This results in a total of 30 target languages.

Multi-parallel corpora

We use two sources of massively parallel text. The first is the Edinburgh Bible Corpus (EBC) collected by [START_REF] Christodouloupoulos | A Massively Parallel Corpus: The Bible in 100 Languages[END_REF] containing 100 languages. EBC has either 30k or 10k sentences for each language, depending on whether they are made up of full Bibles or just translations of the New Testament, respectively. We also crawled and scraped the Watchtower Online Library website to collect what we will refer to as the Watchtower Corpus (WTC). 4 The data is from 2002-2016 and the final corpus contains 135 languages with sentences in the range of 26k-145k. While some EBC Bibles are written in dated language, we do not make any modifications to the corpus if the language is also present in WTC. However, as Basque is not represented in WTC, we replace the Basque Bible from 1571 with a contemporary version from 2004, to enable the use of Basque in the parsing experiments. 5EBC and WTC both consist of religious texts, but they are very different in terms of style and content. If we examine Table 1 that shows the most frequent words per corpus, we observe that the English Bible-the King James Version from 1611contains many Old English verb forms ("hath", "giveth"). In contrast, the English Watchtower is written in contemporary English, both in terms of verb inflection ("does", "says") and vocabulary ("today", "human"). WTC also deals with contemporary topics such as blood "transfusion" (36 mentions) and "computer" (42 mentions).

The other languages also show differences in terms of language modernity and dialectal difference between EBC and WTC. While each Bible translation has its individual history, Watchtower transla-EBC: hath, saith, hast, spake, yea, cometh, iniquity, wilt, smote, shew, begat, doth, lo, hearken, thence, verily, neighbour, goeth, shewed, giveth, smite, didst, wherewith, knoweth, night WTC: bible, does, however, says, today, during, show, human, later, important, really, humans, meetings, personal, states, future, fact, relationship, result, attention, someone, century, attitude, article, different tions are commissioned by the same publisher, following established editorial criteria. Thus, we not only expect Watchtower to yield projected treebanks that are closer to contemporary language, but also more reliable alignments. We expect these properties to make WTC a more suitable parallel corpus for our experiments and for bootstrapping treebanks for new languages.

Preprocessing

Segmentation For the multi-parallel corpora, we apply naive sentence splitting using full-stops, question marks and exclamation points of the alphabets from our corpora. We have collected these trigger symbols from the corpora, provided that they appeared as individual tokens at the ends of lines, and belonged to the "Punctuation, Other" Unicode category. After sentence splitting, we use naive whitespace tokenization. 6 We also remove short-vowel diacritics from all corpora written in Arabic script.

We use the same sentence splitting and tokenization for EBC and WTC. This is done regardless of Bibles being distributed in a verse-per-line format, which means verses can be split in more than one sentence. The average sentence length across languages is 18.5 tokens in EBC and 16.7 in WTC.

The UD treebank tokenization differs from the tokenization used for the multi-parallel corpora. The UD dependency annotation is based on syntactic words, and the tokenization guidelines recommend, for example, splitting clitics from verbs, and undoing contractions (Spanish "del" becomes "de el"). These tokens made up of several syntactic words are 6 https://github.com/bplank/ multilingualtokenizer called multiword tokens in the UD convention, and are included in the treebanks but are not integrated in the dependency trees, i.e., only their forming subtokens are assigned a syntactic head. 7 In order to harmonize the tokenization, we eliminate subtokens from the dependency trees, and incorporate the original multiword tokens-which are more likely to be naive raw tokens-in the trees instead. For each multiword token, we provide it with POS and dependency label from the highest subtoken, namely the subtoken that is closest to root. For example, in the case of a verb and its clitics, the chosen subtoken is the verb, and the multiword token is interpreted as a verb. If there are more candidates, we select one through POS ranking.8

Alignment We sentence-and word-align all language pairs in both our multi-parallel corpora. We use hunalign [START_REF] Varga | Parallel Corpora for Medium Density Languages[END_REF] to perform conservative sentence alignment. 9 The selected sentence pairs then enter word alignment. Here, we use two different aligners. The first one is IBM2 fastalign by [START_REF] Dyer | A Simple, Fast, and Effective Reparameterization of IBM Model 2[END_REF], where we adopt the setup of Agić et al. ( 2015) who observe a major advantage in using reverse-mode alignment for POS projection (4-5 accuracy points absolute). 10 In addition, we use the IBM1 aligner efmaral11 by Östling (2015). The intuition behind using IBM1 is that IBM2 introduces a bias toward more closely related languages, and we confirm this intuition through our experiments. We modify both aligners so that they output the alignment probability for each aligned token pair.

Tagging and parsing The source-sides of the two multi-parallel corpora, EBC and WTC, are POStagged by taggers trained on the respective source languages, using TnT [START_REF] Brants | TnT: A Statistical Part-of-Speech Tagger[END_REF]. We parse the corpora using TurboParser [START_REF] André | Turning on the Turbo: Fast Third-Order Non-Projective Turbo Parsers[END_REF]. The parser is used in simple arc-factored mode with pruning. 12 We alter it to output per-sentence arc weight matrices. 13

Experiments

Outline For each sentence in a target language corpus, we retrieve the aligned sentences in the source corpora. Then, for each of these source-target sentence pairs, we project POS tags and dependency edge scores via word alignments, aggregating the contributions of individual sources. Once all contributions are collected, we perform a per-token majority vote on POS tags and DMST decoding on the summed edge scores. This results in a POS-tagged and dependency parsed target sentence ready to contribute in training a tagger and parser.

We remove target language sentences that contain word tokens without POS labels. This may happen due to unaligned sentences and words. We then proceed to train models.

Setup

Each of the experiment steps involves a number of choices that we outline in this section. We also describe the baseline systems and upper bounds.

POS tagging Below, we present results with POS taggers based on annotation projection with both IBM1 and IBM2; cf. Table 3. We train TnT with default settings on the projected annotations. Note that we use the resulting POS taggers in our dependency parsing experiments in order not to have our parsers assume the existence of POS-annotated corpora.

For a more extensive assessment, we refer to the work by [START_REF] Nivre | Universal Dependencies 1[END_REF] who report baseline and upper bounds. In contrast to their work, we consider two different alignment models and use the UD POS tagset (17 tags), in contrast to the 12 tags of [START_REF] Petrov | A Universal Part-of-Speech Tagset[END_REF]. This makes our POS tagging problem slightly more challenging, but our parsing models potentially benefit from the extended tagset. 14Dependency parsing We use arc-factored Tur-boParser for all parsing models, applying the same setup as in preprocessing. There are three sets of models: our systems, baselines, and upper bounds.

Our systems are trained on the projected EBC and WTC texts, while the rest-except system: DCA-PROJ (see below)-are trained on the (delexicalized) source-language treebanks.

To avoid a bias toward languages with big treebanks and to make our experiments tractable, we randomly subsample all training sets to a maximum of 20k sentences. In the multi-source systems, this means a uniform sample from all sources up to 20k sentences. This means our comparison is fair, and that our systems do not have the advantage of more training data over our baselines.

Our systems We report on four different crosslingual systems, alternating the use of word aligners (IBM1, IBM2) and the structures we project, as they can be either (i) arc-factored weight matrices from the parser (GRAPHS) or (ii) the single-best trees provided by the parser after decoding (TREES). See the if-clause in Algorithm 2.

We tune two parameters for these four systems using English as development set, confidence estimation and normalization, and we report the best setups only. For the IBM1-based systems, we use the word alignment probabilities in the arc projection, but we use unit votes in POS voting. The opposite yields the best IBM2 scores: binarizing the alignment scores in dependency projection, while weight-voting the POS tags. We also evaluated a number of different normalization techniques in projection, only to arrive at standardization and softmax as by far the best choices.

Baselines and upper bounds We compare our systems to three competitive baselines, as well as three informed upper bounds or oracles. First, we list our baselines.

DELEX-MS: This is the multi-source direct delexicalized parser transfer baseline of McDonald et al. (2011). 15

DCA-PROJ: This is the direct correspondence assumption (DCA)-based approach to projection, i.e., the de facto standard for projecting dependencies. First introduced by [START_REF] Hwa | Bootstrapping Parsers via Syntactic Projection Across Parallel Texts[END_REF], it was recently elucidated by [START_REF] Tiedemann | Rediscovering Annotation Projection for Cross-Lingual Parser Induction[END_REF], whose implementation we follow here. In contrast to our approach, DCA projects trees on a source-target sentence pair basis, relying on heuristics and spurious nodes or edges to maintain the tree structure. In the setup, we basically plug DCA into our projection-voting pipeline instead of our own method. REPARSE: For this baseline, we parse a target sentence using multiple single-source delexicalized parsers. Then, we collect the output trees in a graph, unit-voting the individual edge weights, and finally using DMST to compute the best dependency tree [START_REF] Sagae | Parser Combination by Reparsing[END_REF]. Now, we explain the three upper bounds: DELEX-SB: This result is using the best singlesource delexicalized system for a given target language following [START_REF] Mcdonald | Universal Dependency Annotation for Multilingual Parsing[END_REF]. We parse a target with multiple single-source delexicalized parsers, and select the best-performing one.

SELF-TRAIN:

For this result we parse the targetlanguage EBC and WTC data, train parsers on the output predictions, and evaluate the resulting parsers on the evaluation data. Note this result is available only for the source languages. Also, note that while we refer to this as self-training, we do not concatenate the EBC/WTC training data with the source treebank data. This upper bound tells us something about the usefulness of the parallel corpus texts.

FULL: Direct in-language supervision, only available for the source languages. We train parsers on the source treebanks, and use them to parse the source test sets.

Evaluation All our datasets-projected, training, and test sets-contain only the following CoNLL-X features: ID, FORM, CPOSTAG, and HEAD. 16For simplicity, we do not predict dependency labels (DEPREL), and we only report unlabeled attachment scores (UAS). The POS taggers are evaluated for accuracy. We use our IBM1 taggers for all the baselines and upper bounds.

Results

Our average results are presented in Figure 2, including broken down by language family, the lan- guages for which we had training data (Sources) and those for which we only had test data (Targets). We see that our systems are substantially better than both multi-source delexicalized transfer, DCA, and reparsing based on delexicalized transfer models. Focusing on our system results, we see that projection with IBM1 leads to better models than projection with IBM2. We also note that our improvements are biggest with non-Indo-European languages. Our IBM1-based parsers top the ones using IBM2 alignment by 6 points UAS on Indo-European languages, while the difference amounts to almost 10 points UAS on non-Indo-European languages (cf. Table 2). This difference in scores exposes a systematic bias towards more closely related languages in work using even more advanced word alignment [START_REF] Tiedemann | Synthetic Treebanking for Cross-Lingual Dependency Parsing[END_REF].

The detailed results using the Watchtower Corpus are listed in Table 3, where we also list the POS tagging accuracies. Note that these are not directly comparable to [START_REF] Nivre | Universal Dependencies 1[END_REF], since they use a more coarse-grained tagset, and the results listed here are using WTC. We list the detailed results with the Bible Corpus online. 17 The tendencies are the same, but the results are slightly lower almost consistently across the board.

Finally, we observe that our results are also better than those that can be obtained using a predictive model to select the best source language for delexi- calized transfer [START_REF] Rosa | KLcpos3: A Language Similarity Measure for Delexicalized Parser Transfer[END_REF]; and better than what can be obtained using an oracle (DELEX-SB) to select the source language. Direct supervision (FULL) upper bound unsurprisingly records the highest scores in the experiment, as it uses biased in-language and in-domain training data. We also experiment with learning curves for direct supervision, with a goal of establishing the amount of manually annotated sentences needed to beat our cross-lingual systems. We find that for most languages this number falls within the range of 100-400 in-domain sentences.

Discussion

Function words In UD, a subset of function words-tags: ADP, AUX, CONJ, SCONJ, DET, PUNCT-have to be leaves in the dependency trees, unless, e.g., they participate in multiword expressions. Our predictions show some violations of this constraint (less than 1% of all words with these POS), but this ratio is similar to the amount of vi-olations found in the test data.

Projectivity The UD treebanks are in general largely projective. Our UD test languages have an average of 89% fully projective sentences. However, with IBM1 for example, we only predict 55% of all sentences to be projective. Regardless of the differences in UAS, we observe a corpus effect in the difference of projectivity of the predictions between using EBC (65%) and WTC (55%). We attribute the higher level of projectivity of EBC-projected treebanks to Bible sentences being shorter.

The least projective predictions are Farsi (17%) and Hindi (19%), for which we also obtain the lowest UASs. This may be a consequence of our naive tokenization, yielding unreliable alignments. However, projectivity correlates more with UAS (ρ = 0.56) than with POS prediction accuracy (ρ = 0.34).

Dependency length

We observe that the average edge length on IBM1 and WTC is of 2.95, while for EBC it is 2.67. The average gold edge length is 3.6-which is significantly higher at p < 0.05 (Student's t-test). However, the variance in gold edge length is about 1.2 times the deviation of predicted edge length. In other words, gold edges are often longer and more far-reaching. This difference indicates our predictions have worse recall for longer dependencies such as subordinate clauses, while being more accurate in local, phrasal contexts.

POS errors Unlike most previous work on crosslingual dependency parsing, and following the notable exception of [START_REF] Mcdonald | Multi-Source Transfer of Delexicalized Dependency Parsers[END_REF], we rely on POS predictions from cross-lingual transfer models. One may hypothesize that there is a significant error propagation from erroneous POS projection. We observe, however, that about 40% of wrong POS predictions are nevertheless assigned the right syntactic head. We argue that the fairly uniform noise on the POS labels helps the parsers regularize over the POS-dependency relations.

Possible improvements We treat POS and syntactic dependencies as two separate annotation layers and project them independently in our approach. Moreover, we project edge scores for dependencies, in contrast to only the single-best source POS tags. [START_REF] Johannsen | Joint Part-of-Speech and Dependency Projection from Multiple Sources[END_REF] introduce an approach to joint projection of POS and dependencies, showing that exploiting the interactions between the two layers yields even better cross-lingual parsers. Their approach also accounts for transferring tag distributions instead of single-best POS tags.

All the parsers in our experiments are restricted to 20k training sentences. EBC and WTC texts offer up to 120k training instances per language. We observe limited benefits of going beyond our training set cap, indicating a more elaborate instance selection-based approach would be more beneficial than just adding more training data.

In our dependency graph projection, we normalize the weights per sentence. For future development, we note that corpus-level normalization might achieve the same balancing effect while still preserving possibly important language-specific signals regarding structural disambiguations.

EBC and WTC constitute a (hopefully small) subset of the publicly available multilingual parallel corpora. The outdated EBC texts can be replaced by newer ones, and the EBC itself replaced or aug-mented by other online sources of Bible translations. Other sources include the UN Declaration of Human Rights, translated to 467 languages,18 and repositories of movie subtitles, software localization files, and various other parallel resources, such as OPUS [START_REF] Tiedemann | Parallel Data, Tools and Interfaces in OPUS[END_REF]. 19 Our approach is languageindependent and would benefit from extension to datasets beyond EBC and WTC.

6 Related work POS tagging While projection annotation of POS labels goes back to Yarowsky's seminal work, [START_REF] Das | Unsupervised Partof-Speech Tagging with Bilingual Graph-Based Projections[END_REF] recently renewed interest in this problem. [START_REF] Das | Unsupervised Partof-Speech Tagging with Bilingual Graph-Based Projections[END_REF] go beyond our approach to POS annotation by combining annotation projection and unsupervised learning techniques, but they restrict themselves to Indo-European languages and a coarser tagset. [START_REF] Li | Wiki-ly Supervised Part-of-Speech Tagging[END_REF] introduce an approach that leverages potentially noisy, but sizeable POS tag dictionaries in the form of Wiktionaries for 9 resource-rich languages. [START_REF] Garrette | Real-World Semi-Supervised Learning of POS-Taggers for Low-Resource Languages[END_REF] also consider the problem of learning POS taggers for truly low-resource languages, but suggest crowdsourcing such POS tag dictionaries.

Finally, [START_REF] Nivre | Universal Dependencies 1[END_REF] were the first to introduce the idea of learning models for more than a dozen truly low-resource languages in one go, and our contribution can be seen as a non-trivial extension of theirs.

Parsing With the exception of [START_REF] Zeman | Cross-Language Parser Adaptation Between Related Languages[END_REF], initial work on cross-lingual dependency parsing focused on annotation projection [START_REF] Hwa | Bootstrapping Parsers via Syntactic Projection Across Parallel Texts[END_REF][START_REF] Spreyer | Training Parsers on Partial Trees: A Cross-Language Comparison[END_REF]. [START_REF] Mcdonald | Multi-Source Transfer of Delexicalized Dependency Parsers[END_REF] and [START_REF] Søgaard | Data Point Selection for Cross-Language Adaptation of Dependency Parsers[END_REF] simultaneously took up the idea of delexicalized transfer after [START_REF] Zeman | Cross-Language Parser Adaptation Between Related Languages[END_REF], but more importantly, they also introduced the idea of multi-source cross-lingual transfer in the context of dependency parsing. [START_REF] Mcdonald | Multi-Source Transfer of Delexicalized Dependency Parsers[END_REF] were the first to combine annotation projection and multi-source transfer, the approach taken in this paper.

Annotation projection has been explored in the context of cross-lingual dependency parsing since [START_REF] Hwa | Bootstrapping Parsers via Syntactic Projection Across Parallel Texts[END_REF]. Notable approaches include the soft projection of reliable dependencies by [START_REF] Li | Soft Cross-lingual Syntax Projection for Dependency Parsing[END_REF], and the work of [START_REF] Ma | Unsupervised Dependency Parsing with Transferring Distribution via Parallel Guidance and Entropy Regularization[END_REF], who make use of the source-side distributions through a training objective function.

Tiedemann and Agić (2016) provide a more detailed overview of model transfer and annotation projection, while introducing a competitive machine translation-based approach to synthesizing dependency treebanks. In their work, we note the IBM4 word alignments favor more closely related languages, and that building machine translation systems requires parallel data in quantities that far surpass EBC and WTC combined.

The best results reported to date were presented by [START_REF] Sadegh | Density-Driven Cross-Lingual Transfer of Dependency Parsers[END_REF]. They use the intersection of languages represented in the Google dependency treebanks project and the languages represented in the Europarl corpus. Consequently, their approach-similar to all the other approaches listed in this section-is potentially biased toward closely related Indo-European languages.

Conclusions

We introduced a novel, yet simple and heuristicsfree, method for inducing POS taggers and dependency parsers for truly low-resource languages. We only assume the availability of a translation of a set of documents that have been translated into many languages. The novelty of our dependency projection method consists in projecting edge scores rather than edges, and specifically in projecting these annotations from multiple sources rather than from only one source. While we built models for more than a hundred languages during our experiments, we evaluated our approach across 30 languages for which we had test data. The results show that our approach is superior to commonly used transfer methods.

Table 1 :

 1 The 25 most frequent words exclusive to the English Bible or Watchtower.

Table 2 :

 2 Overview of the parsing experiment results for the 25 languages in EBC ∩ WTC. We report the best average UAS score per system and language subset. IE: Indo-European languages, †: EBC, : WTC.

				Languages
	Baselines	All	Sources Targets	IE	Non-IE
	DELEX-MS 45.43	45.64	44.59	49.53	34.88 †
	DCA-PROJ 47.87 † 47.05	47.19	51.33 † 40.66 †
	REPARSE 47.79	47.87	47.47	51.34	38.67
	Our systems
	IBM1 GRAPHS 52.82	53.01	52.07	55.44	46.08
	TREES 53.47 IBM2 GRAPHS 46.44 † 46.14 53.49	53.38 44.39	55.91 49.54 † 38.47 † 47.19
	TREES 46.48 † 46.67	45.54	49.58 † 38.93
	Upper bounds
	DELEX-SB 48.52	48.64	48.02	50.91	42.35
	SELF-TRAIN	-	58.38	-	-	-
	FULL	-	72.55	-	-	-

Table 3 :

 3 POS tagging accuracies and UAS parsing scores for the models built using WTC data. The results are split for source and target languages. All baselines and upper bounds use IBM1 POS taggers, while our MULTI-PROJ systems use their respective IBM1 or IBM2 taggers.

	Targets
	Estonian 75.76 68.76	63.43	65.94	51.31	57.58	48.48	58.41	54.34	58.62 no	-	-
	Greek 75.04 63.57	60.86	61.69	50.19	50.06	54.90	52.95	59.29	55.27 no	-	-
	Hungarian 73.70 69.52	47.80	50.84	44.83	45.38	46.66	42.33	49.85	47.62 fi	-	-
	Quechua 19.49 15.19	26.17	25.93	23.15	22.74	21.67	27.48	22.87	24.30 pl	-	-
	Romanian 78.08 74.67	62.08	62.52	52.46	51.95	51.23	54.78	51.01	54.27 id	-	-
	Tamil 44.27 35.23	22.41	22.16	21.61	17.34	34.07	15.98	34.67	37.99 hi	-	-
	Averages
	All 70.56 65.18	51.88	52.51	45.23	45.69	45.34	46.22	47.62	48.43	-	-
	Sources 73.28 68.23	53.2	53.75	46.55	47.08	46.05	47.43	48.28	49.02	58.54 72.55
	Targets 61.06 54.49	47.13	48.18	40.59	40.84	42.84	41.99	45.34	46.35	-	-

Transactions of the Association for Computational Linguistics, vol. 4, pp. 301-312, 2016. Action Editor: Chris Quirk. Submission batch: 1/2016; Revision batch: 4/2016; 5/2016; 7/2016; Published 7/2016. c 2016 Association for Computational Linguistics. Distributed under a CC-BY 4.0 license.

https://bitbucket.org/lowlands/release

http://hdl.handle.net/11234/1-1548

https://github.com/ffnlp/sethr

http://wol.jw.org

http://www.biblija.net/biblija.cgi?l=eu

http://universaldependencies.org/ format.html

https://github.com/coastalcph/ ud-conversion-tools.

Parameters used: utf, bisent, cautious, realign.

Parameters used: d, o, v, r.

Also reverse mode, with default settings, see https:// github.com/robertostling/efmaral.

Parameters used: basic.

Our fork of TurboParser is available from https:// github.com/andersjo/TurboParser.

For example, the AUX vs. VERB distinction from UD POS does not exist the tagset of[START_REF] Petrov | A Universal Part-of-Speech Tagset[END_REF], and neither does NOUN vs. PROPN (proper noun).

Referred to as multi-dir in the original paper.

http://ilk.uvt.nl/conll/#dataformat

https://bitbucket.org/lowlands/release

http://www.ohchr.org/EN/UDHR/Pages/ SearchByLang.aspx

http://opus.lingfil.uu.se/

Acknowledgements We thank the editors and the anonymous reviewers for their valuable comments. This research is funded by the ERC Starting Grant LOWLANDS (#313695).


J.-M Frigerio

F Rimet

A Bouchez

E Chancerel

P Chaumeil

F Salin

S Thérond

M Kahlert

& A Franc

diagno-syst: a tool for accurate inventories in metabarcoding

Metabarcoding on amplicons is rapidly expanding as a method to produce molecular based inventories of microbial communities. Here, we work on freshwater diatoms, which are microalgae possibly inventoried both on a morphological and a molecular basis. We have developed an algorithm, in a program called diagno-syst, based a the notion of informative read, which carries out supervised clustering of reads by mapping them exactly one by one on all reads of a well curated and taxonomically annotated reference database. This program has been run on a HPC (and HTC) infrastructure to address computation load. We compare optical and molecular based inventories on 10 samples from Léman lake, and 30 from Swedish rivers. We track all possibilities of mismatches between both approaches, and compare the results with standard pipelines (with heuristics) like Mothur. We find that the comparison with optics is more accurate when using exact calculations, at the price of a heavier computation load. It is crucial when studying the long tail of biodiversity, which may be overestimated by pipelines or algorithms using heuristics instead (more false positive). This work supports the analysis that these methods will benefit from progress in, first, building an agreement between molecular based and morphological based systematics and, second, having as complete as possible publicly available reference databases.

Introduction

Unexpected diversity of unicellular Eucaryots (nanoplankton) or hydrothermal sediments has been revealed in 2001 by sequencing ribosomal DNA (18S), using BLAST for comparison with databases, and establishing molecular phylogenies of these unexplored worlds, [START_REF] López-García | Unexpected diversity of small eukaryotes in deep-sea antarctic plankton[END_REF][START_REF] López-García | Autochthonous eukaryotic diversity in hydrothermal sediment and experimental microcolonizers at the mid-atlantic ridge[END_REF]. At the same time, unexpected diversity of oceanic picoplankton has been revealed using 18S and phylogenies too [START_REF] Moon Van Der Staay | Oceanic 18S rDNA sequences from picoplankton reveal unsuspected eukaryotic diversity[END_REF].

Since then, exploration of microbial diversity, be it in protists, bacteria or archaea by molecular based tools has exploded, and has become a standard for biodiversity assessments. Soon after, Hebert and coll. launched the barcoding of life for animals [START_REF] Hebert | Biological identifications through DNA barcodes[END_REF], which has been quickly extended to other kingdoms (see e.g. [START_REF] Hollingsworth | A DNA barcode for land plants[END_REF]), and to protists [START_REF] Pawlowski | Protist Working Group: Barcoding eukaryotic richness beyond the animal, plant, and fungal kingdoms[END_REF]. The advance of sequencing technologies, especially NGS, producing first hundreds of thousands of reads with pyrosequencing, then millions with Ilumina, have paved the way for metagenomics, and metabarcoding for biodiversity or biomonitoring studies (see e.g., among many others, [START_REF] Hajibabaei | Environmental barcoding: a next generation sequencing approach for biomnitoring applications using river benthos[END_REF][START_REF] Bik | Sequencing our way towards understanding global eukaryotic biodiversity[END_REF][START_REF] Taberlet | Environmental DNA[END_REF][START_REF] Kermarrec | A next-generation sequencing approach to river biomonitoring using benthic diatoms[END_REF][START_REF] Dafforn | Faster, higher and stronger? the pros and cons of molecular faunal data for assessing ecosystem condition[END_REF][START_REF] Joly | Ecology in the age of DNA barcoding: the resource, the promise and the challenges ahead[END_REF][START_REF] Pawlowski | Next-generation environmental diversity surveys of foraminifera: Preparing the future[END_REF]).

Metabarcoding is expected to yield inventories of species diversity similar to those provided by morphological based methods, if molecular and morphological taxonomies agree. One way for a rigorous verification is by isolating and culturing, and comparing with results of metabarcoding. [START_REF] Pedrós-Alió | Dipping into the rare biosphere[END_REF] cites a well known case of a bacteria in the Mediterranean Sea (Leeuwenhoekiella blandensis), which has been isolated and cultivated but never found in repeated molecular inventories on the same spot. A still more controlled way to estimate the quality of the information given by metabarcoding is to build artificial samples in the laboratory, and run the metabarcoding protocol on these laboratory-assembled communities (see [START_REF] Porazinska | Evaluating high-throughput sequencing as a method for metagenomic analysis of nematode diversity[END_REF] for nematodes, [START_REF] Kermarrec | Next-generation sequencing to inventory taxonomic diversity in eukaryotic communities: a test for freshwater diatoms[END_REF] for diatoms), or in silico experiments (see e.g. [START_REF] Clarke | Environmental metabarcodes for insects: in silico PCR reveals potential for taxonomic bias[END_REF]).

A second way to estimate this quality, on which we will focus here, is by comparing morphological based inventories with molecular based inventories on same natural communities. Such an approach has been used for alveolates in a freshwater lake [START_REF] Medinger | Diversity in a hidden world: potential and limitation of next-generation sequencing for surveys of molecular diversity of eukaryotic microorganisms[END_REF], tintinnids (ciliates, microzooplankton) [START_REF] Bachy | Accuracy of protist diversity assessments: morphology compared with cloning and direct pyrosequencing of 18S rRNA genes and ITS regions using the conspicuous tintinnid ciliates as a case study[END_REF], arthropods and birds [START_REF] Ji | Reliable, verifiable and efficient monitoring of biodiversity via metabarcoding[END_REF], seegrass communities [START_REF] Cowart | Metabarcoding is powerful yet still blind: A comparative analysis of morphological and molecular surveys of seagrass communities[END_REF], freshwater diatoms [START_REF] Zimmerman | Metabarcoding vs. morphological identification to assess diatom diversity in environmental studies[END_REF], the latter insisting on the need to derive tools for assigning a taxon name to a sequence (what will be referred to in the sequel as taxonomic assignment), and estuarine plankton [START_REF] Abad | Is metabarcoding suitable for estuarine plankton monitoring? A comparative study with microscopy[END_REF], where completing the reference database was found to settle most of inconsistencies between both approaches in zooplankton. Such an approach permits to study a still open question: how reliable is metabarcoding for inventorying or unveiling rare species? How to estimate the so called rare biosphere [START_REF] Sogin | Microbial diversity in the deep sea and the underexplored "rare biosphere[END_REF][START_REF]Pedrós-Alió. The rare bacterial biosphere[END_REF][START_REF] Lindeque | Next generation sequencing reveals the hidden diversity of zooplankton assemblages[END_REF][START_REF] Debroas | Evidence for an active rare biosphere within freshwater protists community[END_REF] ? But see [START_REF] Reeder | The "rare biosphere": a reality check[END_REF][START_REF] Kunin | Wrinkles in the rare biosphere: pyrosequencing errors can lead to artificial inflation of diversity estimates[END_REF].

We develop here a data analysis framework without any heuristics, doing exact computations using High Performance Computing techniques, in order to produce as accurate as possible molecular based inventories, quantify the comparison between morphological based and molecular based inventories, facilitate the localization of major sources of errors, and propose some priorities to fix them.

Discrepancies in comparing a morphological based and a molecular based inventory on the same sample can have three origins: (i) inappropriate morphological based inventory (ii) inappropriate molecular based inventory (iii) both inventories are correct but do not give the same information (differences in species delineation between molecular phylogenies and morphological based identification, for example). The latter is crucial, and deserves further research. As an example, accurate comparison between molecular and morphological taxa delineation in angiosperms has been shaped over many decades through collaboration between many teams (see [START_REF] Angiosperm | An update of the Angiosperm Phylogeny Group classification for the orders and families of flowering plants: APG III[END_REF] in 2009, after APG in 1998and APGII in 2003). Such a comparison remains crucial, as a benchmark for ongoing characterization of currently unseen biodiversity in eukaryotic communities. Here, we develop a tool, named diagno-syst, for having an as accurate as possible molecular based inventory, relying on High Performance Computing for handling massive data, without any heuristics to speed up calculation process. We focus on best possible quality for molecular based inventories, assuming that morphological based inventories are correctly evaluated (i.e. we will not discuss here morphological based taxonomy of diatoms).

One of the requirements for metabarcoding is selecting markers which are, as much as possible, universal, resolutive, and technologically easy to work with. Most of this work is inherited from barcoding. A synthesis paper on marker choice for Eukaryotes from CBOL Protist Working Group is [START_REF] Pawlowski | Protist Working Group: Barcoding eukaryotic richness beyond the animal, plant, and fungal kingdoms[END_REF]. In the remaining of this paper, we assume that a marker has been selected. Knowing that, several sources of errors have been recognized in metabarcoding data analysis (see [START_REF] Bachy | Accuracy of protist diversity assessments: morphology compared with cloning and direct pyrosequencing of 18S rRNA genes and ITS regions using the conspicuous tintinnid ciliates as a case study[END_REF] and references therein). There exists several studies or reviews (see e.g. [START_REF] Zinger | Two decades of describing the unseen majority of aquatic microbial diversity[END_REF][START_REF] Bucklin | Metabarcoding of marine zooplankton: prospects, progress and pitfalls[END_REF]) which focus on well known pitfalls and caveats of molecular approaches, but very few on the pitfalls and caveats when using heuristics instead of exact computations because of the size of data sets. We focus here on isolating bioinformatics challenges from biological challenges, by running exact calculation for sequence comparisons, without any heuristics.

A molecular based inventory is built on sequence comparisons between a set of queries and a reference database, often on amplicons. Such a comparison can be made exactly by Needleman-Wunsch algorithm [START_REF] Needleman | A general method applicable to search for similarities in the amino-acid sequence of two proteins[END_REF] for global alignment or Smith-Waterman algorithm [START_REF] Smith | Identification of common molecular subsequences[END_REF] for local alignment. These algorithms are well understood and exact [START_REF] Gusfield | Algorithms on strings, trees, and sequences[END_REF]. They work well on small size data sets as those produced by Sanger technologies. However, they are quadratic in time as scaling with the number of queries × the number of references. BLAST [START_REF] Altschul | Basic local alignment search tool[END_REF] is a well established tool for exploring quickly a huge database of references. We have the opposite in metabarcoding communities of a given group of organisms: the reference database is often of reasonable size (a few thousands specimen), whereas the number of queries to match becomes huge (about 10 5 or even 10 6 ). Moreover, it is known that BLAST can produce bad results [START_REF] Guillou | The Protist Ribosomal Reference database (PR 2 ): a catalog of unicellular eukaryote Small Sub-Unit rRNA sequences with curated taxonomy[END_REF]. Therefore, as in [START_REF] Guillou | The Protist Ribosomal Reference database (PR 2 ): a catalog of unicellular eukaryote Small Sub-Unit rRNA sequences with curated taxonomy[END_REF], we developed specific assignation tools based on local alignment (here, Smith-Waterman score). As being exact is paid by a heavier computation load, we have exploited the fact that this algorithm belongs to the category of massively parallel problem: the 10 5 or 10 6 local alignments of each query with all specimen in the reference database are all independent, and can be run in parallel on different cores of a computer. Hence, we have opted for a massively parallel implementation of exact local alignment, which answers exactly to the raised question of sequence comparison between a reference database and a set of queries.

Material

We have worked on inventories of diatom communities, as diatom species can be identified both optically (by looking at the frustule), and molecularly (many reference sequences for diatom barcodes are available). This enables to test the quality of the dictionary between both approaches.

The starting point for data analysis is a set of several sets: each sample is given as a set of sequences (the reads), and we have a set of samples. We have one reference database, R-Syst::Diatoms [START_REF] Rimet | R-Syst::diatom: An open-access and curated barcode database for diatoms and freshwater monitoring[END_REF], which will be used for all environmental samples. The reference database is given as a set of n specimens. For each specimen, we have a sequence identifier (a code), a sequence (of the same marker with the same primers), and a hierarchical list of names, naming Order, Family, Genus and Species. We have a set of 10 environmental samples from Léman lake, and a second set of 20 environmental samples from Swedish rivers. For each environmental sample, we have an optic inventory, made by a trained diatomist, and a set of reads, which are produced after amplification of a given marker with given primers. An optical inventory has been produced for each environmental sample by counting about 400 diatom valves in a microscope and identifying them via standard diatom literature using CEN (European Standardization Committee) methods [START_REF] Afnor | NF EN 14407 -Qualité de l'eau -Guide pour l'identification et le dénombrement des échantillons de diatomées benthiques de rivières et de lacs[END_REF][START_REF] Afnor | NF T90 354 -Qualité de l'eau -Échantillonnage, traitement et analyse de diatomées benthiques en cours d'eau et canaux[END_REF].

Environmental samples

Two datasets were analyzed: one from Léman lake, and one from Sweden. The Léman lake dataset contains one site sampled at ten different dates (about one month between two sampling campaigns). The Swedish dataset contains data of 13 streams and one lake distributed over the whole country, six of the streams sampled in two subsequent years. The streams covered different ecological regions and stream types, including lowland agricultural streams common also in Central Europe, small boreal streams and mountain streams with no forest cover in the catchment. In this way, we could test if the reference data base of diatoms developed to match Léman Lake communities can be used also for other regions of the world. We expected more problems when using it for Swedish data.

Reference database: names

The taxonomic names selected in this study are those selected in Thonon Reference Database, R-Syst::Diatoms, which has been built first at Thonon (Thonon Culture Collection, TCC, see www.inra.fr/carrtel-collection), and complemented by careful curation of freshwater diatom sequences in NCBI [START_REF] Kermarrec | Next-generation sequencing to inventory taxonomic diversity in eukaryotic communities: a test for freshwater diatoms[END_REF]. The privileged taxonomic level is the species level. Names in the reference database are as much as possible accepted authored names. However, in several circumstances, a discrepancy between molecular based species delineation by phylogenies and morphological based species delineation have been acknowledged. In such a case, a compromise has been made (e.g. Fragilaria group) in order to have the best agreement between morphological based and molecular based taxonomic identification of specimen in the reference database. It is not the purpose of this paper to discuss diatom systematics, and the current state of the art, even if acknowledged as perfectible, is taken for granted and accepted.

Any accepted evolution or change in diatom's systematics can be taken into account in a further step just by changing the accepted names. Taxa in this study should be considered as operational taxonomic units as close as possible to species level and accepted species names, knowing that some discrepancies still exist in the current state of the art. For sake of simplicity, they will be referred to as species in the sequel of this paper.

Reference database: sequences

Marker choice: Before the bloom of barcoding, molecular taxonomy of plankton has been studied using 18S as a marker. Over the subsequent years, several hypervariable regions of 18S have been progressively selected in scientific community to study plankton, and more generally protists, i.e. unicellular eukaryots (see [START_REF] Pawlowski | Protist Working Group: Barcoding eukaryotic richness beyond the animal, plant, and fungal kingdoms[END_REF][START_REF] Bucklin | Metabarcoding of marine zooplankton: prospects, progress and pitfalls[END_REF][START_REF] Tanabe | Comparative study of the validity of three regions of the 18S-rRNA gene for massively parallel sequencing-based monitoring of the planktonic eukaryote community[END_REF]). A second criteria for a marker choice is the availability of a well curated database. PR 2 (see [START_REF] Guillou | The Protist Ribosomal Reference database (PR 2 ): a catalog of unicellular eukaryote Small Sub-Unit rRNA sequences with curated taxonomy[END_REF] and http://ssu-rrna.org/) has been designed specifically for marine plankton. [START_REF] Kermarrec | Next-generation sequencing to inventory taxonomic diversity in eukaryotic communities: a test for freshwater diatoms[END_REF] have compared rbcL, 18S and CO1 for freshwater diatoms, the three of them being acknowledged as potential barcodes for diatoms, making a balance between resolution and richness of existing database. They have shown that rbcL was more resolutive than 18S, and that public information was available for both of them. Hence, a choice has been made to work with rbcL, and to complete the existing database. Subsequently, an inner marker has been selected, of 312 bp long to comply with technological requirements of NGS sequencing facilities, which could not provide ≥ 500bp long reads as Sanger technology could. For amplifying this region, the primer pair Diat_rbcL_708F [START_REF] Stoof-Leichsenring | Hidden diversity in diatoms of kenyan lake naivasha: a genetic approach detects temporal variation[END_REF] and R3 [START_REF] Bruder | Molecular assessment of phylogenetic relationships in selected species/genera in the naviculoid diatoms (Bacillariophyta). I. The genus Placoneis[END_REF] was used directly for samples from Léman lake, and was modified for the Swedish samples as follow: forward primer combine an equimolar mix of Diat_rbcL_708F_1 (AGGT-GAAGTAAAAGGTTCWTACTTAAA), Diat_rbcL_708F_2 (AGGTGAAGT-TAAAGGTTCWTAYTTAAA) and Diat_rbcL_708F_3 (AGGTGAAACTAAAG-GTTCWTACTTAAA); reverse primer combine an equimolar mix of R3_1 (CCTTC-TAATTTACCWACWACTG) and R3_2 (CCTTCTAATTTACCWACAACAG). The resolution of the selected short barcode has been checked, and the drop from full rbcL fragment, even if noticeable, was found to be non significant.

Methods

For each set of samples (Léman lake and Swedish rivers), the work has been processed along a sequence of three steps

• have an optical based inventory

• build a molecular based inventory

• identify and classify mismatches between both.

Methods for each of these steps are given in what follows, with a focus on molecular based inventories and classification of mismatches.

Let us note that an output of a Proton sequencer for an environmental sample typically counts about 10 5 reads, of 312bp long each. Here, instead of using heuristics to speed up the analysis, we have kept on the choice to use exact algorithm, which scale linearly with the number of reads. We have designed as well automatic procedures to handle a large number of environmental samples, i.e. data flows between different steps in calculation. Therefore, we have used a High Performance Computing Center for intensive computing (IDRIS, see http://www.idris.fr/eng/), and iRODS as a file manager for managing data flows.

Molecular based inventories: data analysis

The algorithms used for taxonomic annotation of queries knowing a reference database (supervised clustering) are given here. The motivations for such a choice, i.e. the notion of informative read and sliding barcoding gap, which distinguish these algorithms from, say, those encapsulated in Mothur, are presented in the discussion section (section 5.1).

Notations: Let us give some notations. The set of references is denoted R. Each reference is a 312bp long sequence, with little variations in length, with an identifier, and a taxonomic annotation (species, genus, family). There is a set of queries per environmental sample i, denoted Q i . Each query is a 312bp long sequence, with some variatons in length, with an identifier. The number of references is denoted |R|, and the number of queries in sample i is denoted |Q i |. We have for this study |R| = 1446. The barcode gap is denoted α, and maximum barcode gap θ.

Distance between sequences:

We have implemented in C the Smith-Waterman algorithm [START_REF] Smith | Identification of common molecular subsequences[END_REF] producing a score of local alignment between two sequences. Let (q, r) be a pair query × reference. Let sw(q, r) be the Smith-Waterman score between the query and the reference. Then sw(q, r) is the highest sore of global alignment between a substring α ⊂ q and a substring β ⊂ r over all pairs (α, β) (see [START_REF] Gusfield | Algorithms on strings, trees, and sequences[END_REF]). Selected costs are +1 for a match, and -1 for a gap (for one base) or a substitution. This can easily be extended to more diverse evolution models. The score has been translated into a distance as follows: let ℓ(q) be the length of the query, ℓ(r) be the length of the reference. Then

d(q, r) = min{ℓ(r), ℓ(q)} -sw(q, r) 2 (1)
The program computing d(q, r) from q and r as inputs is called disseq.

Step 1:

Step 1 is to compute d(q, r) for any pair (q, r) ∈ Q × R. This has been done by a double loop. This is the intensive part of the computation. Step 2: A barcoding gap α being selected, step 2 is to derive the neighborhood of any query q ∈ Q as the set N α (q) of all sequences in R such that d(q, r) ≤ α

N α (q) = {r ∈ R : d(q, r) ≤ α} (2)
Step 3: This step is assigning a name, or not, to a query, knowing its neighborhood in R. A query q is called informative if all the references r ∈ N α (q) belong to the same taxon. A query can be informative for the genus, but not for the species. Hence, a small program has been written (in python) which implements the following procedure:

Algorithm 1 pseudocode for taxonomic assignation through informative reads: tax annot = informative(q,α)

1: input: q ∈ Q {query} 2: input α {barcoding gap} 3: get N α (q) 4: if N α (q) == ∅ then 5:
tax annot ← 'unknown' 6: else 7:

T ← list of taxa in N α (q) 8:

|T | ← number of taxa in T end if 14: end if 15: return tax annot Then, procedure tax annot = informative(q,α) has three possible outcomes:

• unknown if the query is too far from the reference database

• ambiguous if there are several references in the neighborhood of q, but of different taxa

• a taxon if all the references in the neighborhood of q belong to the same taxon

Step 4: Programme informative is run as a loop over all reads q ∈ Q i . For 2.10 5 queries, it takes less than 30 seconds in python on an standerd laptop with Linux Ubuntu. If there are n queries, this gives a vector of strings v of length n.

Step 4 simply is to produce a table which counts the number n i of occurrences of item i (where i can be unknown, ambiguous or any taxon for which at least a read is informative). This step is called diagno syst(tax annot).

Step for q ∈ Q do

6: v[q] ← informative(q, α) 7:
end for 8:

x α ← diagno syst(v) 9: end for 10: return X = [x 0 | . . . |x θ ]
Notes: First, We have not looked at an optimization of calculation time here, but have focused on exact calculation. For example, [START_REF] Liu | CUDASW++: optimizing Smith-Waterman sequence database searches for CUDA-enabled graphics processing units[END_REF] have proposed CUD-ASW++, an optimization of SW algorithm for or CUDA-enabled GPUs. See for example [START_REF] Okada | Accelerating the Smith-Waterman algorithm with interpair pruning and band optimization for the allpairs comparison of base sequences[END_REF] for recent background. Second, we have filtered the set Q by keeping queries with a length 300 ≤ ℓ(q) ≤ 315, as we wish a high homology between the query and some references. About one half of the queries only have been kept with this filter for each environmental sample. Third, in the discussion section, we will compare the inventories produced this way with inventories produced with Mothur [START_REF] Schloss | Hollister. Introducing mothur: Open-source, platformindependent, community-supported software for describing and comparing microbial communities[END_REF].

Classification of mismatches

Detecting and quantifying eventual problems was done by directly comparing the abundance of taxa in the molecular inventory and the optical inventory. Abundances were divided into low abundance and high abundance. Low abundance in the optical inventories was defined as ≤ 1% relative abundance of a taxon, high abundance was ≥ 1%. In the molecular inventories, low abundance was defined as a low number of amplicon reads ≤ 1000, high abundance then was defined as ≥ 1000 reads. Comparison was then done between the abundance of a taxon in the optical inventory and the abundance of reads for each barcoding gap. Hence, each taxon encountered in at least one of the inventories has been allocated a category per inventory

• ∅: absent • ℓ: low abundance • A: high abundance.
For example, a taxon absent in optics and present in low abundance in molecular inventories will be tagged (∅, ℓ). In an ideal case, both the list of species and their abundance would match exactly between both methods (only (ℓ, ℓ) or (A, A). In practice, this is not the case.

The mismatches have been studied, and allocated to the following possible causes (first code for optics, second for molecular):

• (∅, ℓ):
the optical inventory could be made down to genus only; hence, the taxon was not identified to species and could therefore not be addressed to one of the species sequences of the molecular database: code e

the species has been detected with large gap (≥ 15), hence is likely a match on another nearby species: code i there exists a discrepancy between DNA based classification and morphological based classification: code a the species is rare, has been detected in molecular inventory, but not in optical: code b

• (∅, A): All codes a, e, i can explain such a discrepancy as well (as in (∅, ℓ)) when the reads assigned to a given taxon are abundant too. This is however not the case for code b (rare species) where the reads cannot be abundant. Hence, code e cannot be found in such a situation.

• (ℓ, A) or (A, ℓ): It is highly likely that there has been an amplification problem: code g

• (ℓ, ∅)
as a symmetry to (∅, ℓ), there exists a discrepancy between DNA based classification and morphological based classification: code a the barcode of corresponding species, as as well as of nearby species, is absent from reference database: code c

the optics has probably lead to count dead frustules: code f

• (A, ∅):
as in the case (ℓ, ∅), situations described by code a or c are possible code f , however, is unlikely,

The key for possible misclassification causes is given in table 1.

The classification of mismatches par sample according to these codes has been done with expertise of diatomists who have done the optical inventories.

Results

There are three results per set of sample (Léman lake and Swedish rivers):

• the optical inventories

• the molecular based inventories

• the likely causes for mismatch between both Optical inventories are given in file Léman optics.txt for Léman lake and Sweden optics.txt for Swedish rivers. An example of molecular based inventory with the number of informative reads per gap (see methods) is given in file L6.txt. Mismatch classification are given in tables 2 for Léman lake and table 3 for Swedish rivers.

Discussion

Molecular based inventories

Similarity based data retrieval: The pipeline presented here for supervised clustering can be summarized as a two steps process for each query: (i) a search for neighbors in the reference database, (ii) a post-processing of this set. The search can be processed either by BLAST, or here by exact local alignment scores. We have selected the latter because it is easily parallelizable. The key point is on post-processing. The question of allocating a query to a reference, knowing a reference database and a distance, has been thoroughly studied in many areas under the name of similarity search, or similarity based data retrieval (see e.g. [START_REF] Pestov | On the geometry of similarity search: dimensionality curse and concentration of measure[END_REF]). The model behind taxonomic assignment is the model behind barcoding: there exists a barcoding gap α such that if two sequences x, y are at a distance d(x, y) < α, they belong to the same taxon, whereas if they are at a distance d(x, y) > α, they belong to different taxa. We discuss here how to assign a name knowing a gap (notion of informative read), and how to extend the procedure to a set of barcoding gaps (notion of sliding barcoding gap).

Notion of informative read:

The notion of informative read is at the basis of our assignment pipeline, and is developed here. For a given barcoding gap α, the neighborhood of a query is retrieved as the set of references at distance d ≤ α. If all belong to same taxon in reference database, this taxon is assigned to the query. If not, the annotation is called ambiguous. If the neighborhood is the empty set, the annotation is unknown. Let us illustrate this on the example given in figure 1. Let us have two different taxa shown here with blue dots, called here taxon 1 and taxon 2. Each taxon is a clique, as they have been derived by a mixture of morphological and molecular based basis. Let us have two queries, one green one, and one red one. There are edges between each query and all references at distance less that the barcoding gap α whatever their taxon. Both edges from green query are towards nodes in taxon 1. Hence the read is informative and the label taxon 1 can be assigned to it. On the contrary, one edge from red query is towards taxon 1 and one is towards taxon 2. Then, red query is not informative, and assignment is ambiguous.

Sliding barcoding gap:

The barcoding gap is a value such that two reads separated by a distance larger than the gap are expected to belong to different taxa, and to the same taxon if their distance is smaller than the gap. The gap depends on the taxonomic level. It is commonly accepted that an homology of 97% or more is relevant for assignation at species level. As the marker used here is 312 bp long, this leads to a gap of 9 bp (either mismatch or unitary indel). However, it is commonly accepted as well that the barcoding gap may depend on the clade, and is not uniform. Hence, we have implemented the procedure deciding whether a read is informative, or not, and the taxonomic assignment if it is informative for a range of barcoding gaps between gap = 0 (the more stringent choice) to gap = 20, as it is not expected to have distances larger than 20 bp (less than 93% of homology) within the same species. This procedure has been run for all reads. This means that we have produced an array with N rows if the sample is made of N reads, and 21 columns, one column for each barcoding gap between 0 and 20. At row i and column α, we have either a taxon if read i is informative for gap α, or the character ambiguous or unknown.

Then, for each gap α with 0 ≤ α ≤ 20, and for each taxon t in the reference database, we have computed the number n(t, α) of reads which are informative with taxon t at barcoding gap α. Interestingly, for a given taxon t, the curve plotting the number n(t, α) of informative reads in the sample hitting a given taxon as a function of the barcoding gap α is often, but not always, unimodal. This means that this number can increase or decrease when the gap decreases.

It is likely that it increases for small values because the neighborhood (the set of specimen at distance equal to or less than the gap) increases and specimens in it belong to the same taxon, and decreases for larger values because for some reads the neighborhood becomes taxonomically heterogeneous when the distance increases. This phenomenon is driven by the shape of the reference database, and is under study with tools from multivariate analysis or machine learning. An example of such a phenomenon for one read is given in figure 2. It can be shown that if a read is informative for a given species at a given gap, it cannot be informative for another species at a different gap. The advantage of such an assignment procedure is that it permits assignment without a selection of a unique barcoding gap: it is an adaptive procedure, without a model for barcoding gap (either constant or clade dependent).

Classification of mismatches

Interpretation of the results: The fraction of perfect matches between morphological based and molecular based inventories is of 14 % for Léman lake, and 7 % for Swedish rivers. This could appear as desperately low. The main causes for mismatches are

• for Léman lake: case b (rare species not recognized in optics) for 41 %, then c (absence of barcode in R-Syst) for 17 %, i (likely match on a nearby species) for 14 %, and a (mismatch between molecular based and morphological based taxonomy) for 11 %.

• for Swedish rivers: a (mismatch between molecular based and morphological based taxonomy) for 26 %, c (absence of barcode in R-Syst) for 24 %, then b (rare species not recognized in optics) for 13 %, i (likely match on a nearby species) for 9 % and e (optical inventory at genus level only) for 8 %

All others causes can be considered as negligible (less than 5 %). It appears that the main sources of mismatches are not due to the lack of resolution of molecular marker or accuracy of the pipeline, but to taxonomical and technical difficulties, which can be arranged in three categories:

• a still ongoing mismatch for some groups or clades between morphological based and molecular based taxonomy (case a)

• a difficulty in optics to accurately detect rare species (case b)

• the incompleteness of the reference data base (cases c and i), preventing an accurate molecular based inventory.

Hence, the conditions for a molecular based inventory in metabarcoding to be accurate are that (i) there is an agreement between morphological based and molecular based systematics and (ii) the reference molecular database encompasses the whole diversity of the sampled communities. If those conditions are fulfilled, there is a slight advantage for molecular based inventories which could be more accurate for detecting rare species.

Incompleteness of the reference database: Regarding the Swedish dataset, about 50% of all taxa found in the optical inventory were not present in the reference database, so were impossible to find by the NGS method. Checking the different streams, we found that many of the diatom species dominating the streams of the boreal region are not present in database and that taxa from acid streams are especially missing. Examples of Swedens most frequent taxa missing from the reference database are Brachysira neoexilis Lange-Bertalot, Eunotia incisa W. Smith & W. Gregory and Eunotia implicata Nörpel, Lange-Bertalot & Alles. Additionally, taxa from high mountain regions are missing as well. Best represented are typical agricultural streams from the non-boreal region of Sweden, ecologically most similar to Central Europe. On the contrary, 17% only of taxa found optically in Léman lake are absent in the reference database. They are therefore impossible to detect in the molecular inventories. It is the case for taxa such as species of the Encyonopsis genus or Calonei bacillum, Navicula radiosafallax, N. utermoehlii, Nitzschia lacuum. There are also several species of the Achnanthidium genus (A. catenatum, A. eutrophilum) which were not detected in the molecular inventory but were observed in microscopy for the same reason. This is in line with recent works of [START_REF] Abad | Is metabarcoding suitable for estuarine plankton monitoring? A comparative study with microscopy[END_REF] which ranked completeness/incompleteness of reference database as first among causes for mismatch between optical and molecular based inventories.

Discrepancy between molecular based and morphological based taxonomy: Such a discrepancy is a major limit for building an agreement between classical optical inventories and metabarcoding. A most prominent example for this category of problems is the genus Fragilaria, recorded as a problem in all but four of the 20 samples of the Swedish dataset. Even if a number of recent publications are trying to unravel the taxonomy of this genus, its identification and separation between species are far from clear. Identification literature gives often no clear limits between species, some features are only visible in electronic microscopy, and most of all, different references are often giving different characters for the different species (see e.g. the case of F.gracilis Østrup, which is very common in Fennoscandia, but not so much in Central Europe, where it often is identified as F. rumpens (Kützing) Lange-Bertalot instead). This leads to problems when trying to separate these species in optical inventories, and also especially when giving a name to a species in a reference database leading in turn to problems when comparing optical and molecular inventories to each other. In some circumstances, we can today not even say which of the given names in an inventory are correct, but have to go back and harmonize the way of identifying species. There is as well a need to make close studies of molecular and optical characters of taxa which were until now considered as a species, and study the accuracy of separations to closely related species. If none can be found, it may lead to pool species in order to enable clear identifications. Other taxon complexes suffer of similar problems, represented in the Swedish dataset by for example Achnanthidium minutissimum and related species, Nitzschia palea and related species, Navicula cryptocephala and N. cryptotenella and related species, Eolimnia minima and related species, certain Gomphonema species, the genera Staurosira, Ulna, Encyonema Cymbella, Mayamaea, Amphora, and Planothidium.

Comparison with existing pipelines

Mismatches between optical based and molecular based inventories can come from biases in one of the inventory (or both ...), as well as disagreements between morphology based and molecular based systematics. Hence, we have tried to minimize the possible biases due to the computing phase in building a molecular based inventory. Therefore, we have favored exact calculations, i.e. calculation of all local alignments between queries and references. We have compared our inventories with the ones issued on same datasets with standard tools, here Mothur [START_REF] Schloss | Hollister. Introducing mothur: Open-source, platformindependent, community-supported software for describing and comparing microbial communities[END_REF].

Comparison with Mothur: methods Mothur requires that the reference database is aligned, whereas diagno-syst does not. For each query, mothur searches the read in reference database closer to the query (the best hit), makes a local alignment between both, and provides some information on the of the alignment. When the quality of the alignment is considered as sufficient (some threshold have to be defined for that), next step is to accept the alignment as good, look at the identity of the aligned reference, look at its name, and transfer it to the query, considered as an element of the inventory. Different tools can be selected as options, as kmers, suffix tree or BLAST for searching closest reference, and global or local alignment for the quality of the alignment.

We have selected a search with kmers, and local alignment with gotoh. We have been stringent with the quality of the alignment (300 aligned bp or more among 312 bp). Beyond the necessity to have an aligned reference database, and use of heuristics by mothur, the main difference between mothur and diagno-syst is a taxonomic annotation from the best hit by mothur, and by an informative read by diagno-syst. Diagno-syst is more stringent, in the sense that, for a given gap, it requires that all neighbors in reference database at distance less than the gap belong to the same taxon. Then the name is transferred. It is therefore expected that Mothur has more false positive, and diagno-syst more false negative.

Comparison with Mothur: an example A comparison between both inventories has been made for each sample of swedish rivers and Léman lake, and results for one sample (UR 775, Swedish rivers) are presented here as an example. The comparison is given in file UR 757 compare.txt. The sample is oligotrophic and neutral, and from the pristine mountains. [START_REF] Angiosperm | An update of the Angiosperm Phylogeny Group classification for the orders and families of flowering plants: APG III[END_REF]

Conclusions

We have designed and run a new pipeline, called diagno-syst for molecular based inventories in metabarcoding. We have produced a pipeline which enables an industrialization of production of such inventories. It relies on computing exact distances, without heuristics, between each read of an environmental sample and each sequence of a reference database. Such distances are then used to build molecular based inventories on environmental samples. We have compared the results of inventories of freshwater benthic diatom communities with optical based inventories on two contrasted sets of environmental samples: 10 samples from Léman lake, and 20 samples from Swedish rivers. All samples have been inventoried optically, and with metabarcoding, with a same protocol, and using a reference database specifically designed for freshwater diatoms (R-Syst::diatoms, see [START_REF] Rimet | R-Syst::diatom: An open-access and curated barcode database for diatoms and freshwater monitoring[END_REF]). We have compared the outputs of our pipeline with the standard existing one for metabarcoding inventories in microbial communities: Mothur. We have found that our pipeline is more stringent: both recovered species which had been recognized optically, but they differed in the number and types of false positive: more positive, and sometimes taxonomically more distant from what could be expected, with Mothur. The higher quality and accuracy of diagno-syst inventories is paid by a longer computation time, which is reasonable with parallelization (which has been implemented).

We have studied a main question: is it possible to quantify the fraction of match/mismatch between both ways of performing an inventory on a same sample, split according to potential causes? We have been interested in answering to two further questions: first, a focus on rare species, by definition difficult to detect, but a key component of biodiversity, and, second, having two contrasted datasets handled with the same protocol permits to have an idea of the dependence of the result on regional idiosyncrasies.

In both datasets, the largest causes of mismatches between molecular and optical dataset were a -Discrepancy between DNA-data and classical taxonomy, b -rare species, c -no barcode in R-Syst and i -species detected for gaps ≥ 15. However, we found that the plausible main causes of discrepancies are different for datasets: In Léman lake, most mismatches were caused by taxa that were found by metabarcoding but not in microscope. This category was interpreted as rare species, which simply had been overlooked in the microscope, as only 400 valves are too be counted. As our knowledge of diatoms benthic communities in Léman lake is fairly good, it is possible to state in most of cases that those species actually have been found earlier in the frequent and long-term monitoring of this lake. So we can assert with high confidence that the NGS method is correct here, and that the NGS method is better in finding rare taxa. On the other hand, in the Swedish dataset most mismatches were caused by (i) a discrepancy between DNA-based and classical taxonomy and (ii) by optical taxa missing in the reference database. Furthermore, a comparison between Mothur and diagno-syst showed that the long tail of rare species or genera provided by Mothur is not fully trustable: it is probably over-estimated. Most of these discrepancies are due to an underrepresentation of boreal taxa in the reference database.

As a consequence, much effort still has to be put into (i) implementation of exact calculations (sequence comparisons) for comparing queries with a reference database in order to minimize an overestimation of the long tail of diversity, (ii) diatom taxonomy, to unravel DNA based and optical based species delineation, and (iii) completing reference databased with more species from underrepresented regions. References have been categorized by a mixture of molecular and morphological based assignment. Hence they are depicted as (nearly) cliques. There is an edge between a query and a reference when the distance between them is less than α.

Acknowledgements

Green query is an informative read, because both edges lead to the same taxon, whereas red query is ambiguous, as both edges lead to two different taxa. See text for details. n = 0 (unknown) 1 ≤ n ≤ 5 n > 5 (ambiguous) Figure 2: The red dot is a read. The blue dots and green dots are two species in the reference database, respectively. Black quarter of circle represent areas at distance equal to the radius of the circle. For small distances, the query has no it (n = 0). The status is unknown. For some region, the read can have between 1 and 5 hits of references belonging all to species blue (1 ≤ n ≤ 5).The status is informative for species blue. Beyond a given radius, the read has more than 5 hits (n > 5), but on references belonging to either blue or green species. The status is ambiguous.

9 :

 9 if |T | == 1 then 10: tax annot ← the unique taxon in T 11: else 12: tax annot ← 'ambiguous' 13:

Figure 1 :

 1 Figure 1: Blue dots are references. Green and red dots represent two queries.References have been categorized by a mixture of molecular and morphological based assignment. Hence they are depicted as (nearly) cliques. There is an edge between a query and a reference when the distance between them is less than α. Green query is an informative read, because both edges lead to the same taxon, whereas red query is ambiguous, as both edges lead to two different taxa. See text for details.

  It has been run both on Babel and Turing. Babel is a BlueGene P (IBM) located at Idris in Saclay. It offers massive parallelization, fully adapted to the computation of large matrices of pairwise distances. Its characteristics are: 40,960 cores PowerPC 450, 20 To of memory, 139 Tflop/s peak power, and 800 To of memory on disks. Turing is a BlueGene Q (IBM) located at IDRIS too. Its architecture is made of 6 racks, of 1024 nodes each, and 16 cores per node, hence 98 304 cores. We have used Turing with up to 214 = 16384 cores (one rack). Its peak power is 1,258 Pflop/s. Their main advantage (apart from massive parallelization) is a low energy consumption: 300 kW, at a cost of lower frequency in cores, but larger number of cores. Such an architecture is particularly suitable for massive embarassingly parallel jobs. The loop for computing all pairwise distances has been run with Message Passing Interface (MPI) programming, by a dedicated program called mpi-disseq, written in C and MPI for this purpose. The program has been tested first on Avakas (Mésocentre de Calcul Intensif Aquitain, 264 computing nodes, 12 cotes each) and then ported to Babel and Turing. The program scales perfectly.

  5: Step 4 is run for any barconding gap α ∈ {0, θ}. Steps 3, 4 and 5 have been associated into a single program called diagno syst loop, and reads Algorithm 2 pseudocode for diagno syst loop

1: input: Q 2: input θ 3: for α ∈ 0, . . . , θ do 4: v ← [.] 5:

  species have been recognized by optics, 69 with diagno-syst, and 134 with Mothur. 10 false positive have been produced by diagno-syst, and 34 by Mothur. It has been more difficult to quantify the amount of false-negatives, as into the category "taxonomical/barcoding problems": they might have been hit but as a closely related taxon. Another possibility is that there is a mismatch between optical and molecular based species delineation, like for Cocconeis placentula. Hence, we have counted the taxa that diagno-syst and Mothur found and were absent from optical inventory, and assessed which were probably (e.g. earlier found) or likely (i.e. oligotrophic, clean-water taxa) in the sample. This represents 13 species (out of 24 false positive) for diagno-syst, and 25 (out of 89) for Mothur. This shows that diagno-syst inventories are closer to optical based inventories than mothur inventories. This is probably due to the fact that, in order to be quick, mothur runs one local alignment only, and diagno-syst, in order to be more exact, runs them all (in this early version). Mothur assignment relies on the alignment with the best hit only, whereas diagno-syst relies on the alignment with all reference reads in a given neighborhood, and hence is more stringent.Comparison with Mothur at genus level: This can be checked by a comparison between both approaches at the genus level, where taxonpic discrepancies between different approaches are less developed. The result is given in table UR 757 compare genera.txt. Looking at it indicates in nice global correlation (better seen on a log-log scale), but a few important discrepancies. A major one is for genus Cymbella, and all the other ones are in a long tail of rare genera, found by Mothur and not by diagno-syst Placoneis, Craticula, Acanthoceras, Fallacia, .... This comparison between Mothur and diagno-syst has to be studied further and in more details.

:

  It is a pleasure to acknowledge a definite input of Yec'han Laizet (BioGeCo) for an earlier version of pipeline diagno syst, several discussions on metabarcoding of protists with D. Debroas, the earlier work of and discussions with Lenaïg Kermarrec as PhD student on metabarcoding in Carrtel with tight collaborations with BioGeCo. This work has been supported by ONEMA project "Developpement d'outils de bio-indication phytobenthos et macroinvertébrés benthiques pour les cours d'eau de Mayotte" given to AB, project e-Biothon given to AF, DARI project "biodiversiton" i2015037360 in 2015 and 2016 for access to National Computing center IDRIS, given to AF, and a one year CDD given by CEBA (Centre d'étude de la biodiversité amazonienne) ANR Project to AF, which supported an earlier version of diagno-syst. The Swedish contribution to this study was jointly funded by The Swedish Agency for Marine and Water Management, SwAM, and the Environmental Monitoring and Assessment (Fortlöpande miljöanalys (Foma) och miljöövervakning) research program at the Swedish University of Agricultural Sciences.

	7 Tables
	code meaning
	a	Discrepancy between DNA-data and classical taxonomy
	b	rare species
	c	no barcode in R-Syst
	e	Genus level in optics only
	f	If barcode in R-Syst: no DNA, dead frustule
	g	amplification problem
	h	other reasons
	i	species detected for gaps ≥ 15
	k	ok

Table 1 :

 1 Coding of the possible reasons for discrepancy between optical based and molecular based inventories

		a	b	c e	f g h	i	k
	L1	12	27	11 0	3 0 0	5 10
	L2	7	25	12 0	1 0 0	6 11
	L3	12	26	9 0	1 0 0	5	8
	L4	6	38	11 0	2 0 0	9	8
	L5	7	27	10 0	1 0 0 10	8
	L6	7	27	12 0	1 0 0 12	9
	L7	6	27	11 0	3 0 0 11 11
	L8	7	25	8 0	2 0 0 10	6
	L9	5	18	16 0	4 0 1	9 11
	L10	8	33	15 0	2 0 1 15 10
	Sum	77 273 115 0 20 0 2 92 92
	(%, rounded) 11	41	17 0	3 0 0 14 14

Table 2 :

 2 Counting the number of species per sample (in row) and per possible cause of discrepency (in columns) for 10 samples of Léman lake. See table1for the meaning of the codes.

		a	b	c	e f	g	h	i	k
	UR 787	20	5	9	3 0	2	4	7	3
	UR 36	32	15	9	9 0	0	7	8	3
	UR 775	24	11	25	5 0	2	3	4	3
	UR 1	30	12	20	7 0	1	6	7	6
	UR 38	29	9	31	8 0	5	4	8	2
	UR 789	30	10	28	5 0	3	3	6	1
	UR SAP45A	7	5	27	5 0	2	1	3	1
	UR 764	6	2	14	3 0	0	4	4	5
	UR 39	29	17	25	4 0	1	5	7 11
	UR 790	30	21	30	6 0	1	4	10 13
	UR 803	23	1	8	3 2	1	4	11	2
	UR 27	35	11	16	6 0	0	3	4	4
	UR 771	6	3	12	3 0	0	3	1	2
	UR 785	25	20	23	5 0	4	4	9	5
	UR SAM36A	8	6	6	5 1	6	0	2	5
	UR 756	6	2	7	2 0	2	2	3	1
	UR 53	4	5	8	4 0	1	3	5	2
	UR 766	26	12	4	8 1	3	2	1	9
	UR 26	34	14	17	11 1	2	6	21 14
	UR 757	29	5	17	9 2	7	2	12	4
	sum	433 186 336 111 7 43 70 133 96
	(%, rounded)	30	13	24	8 0	3	5	9	7

Table 3 :

 3 Counting the number of species per sample (in row) and per possible cause of discrepancy (in columns) for 20 samples of swedish rivers. See table1for the meaning of the codes.