Laurent Noé
email: laurent.noe@univ-lille1.fr

Donald E K Martin
email: martin@stat.ncsu.edu

A Coverage Criterion for Spaced Seeds and Its Applications to Support Vector Machine String Kernels and k-Mer Distances

Keywords: Spaced seed, Spaced k-mer, Gapped k-mer, Coverage sensitivity, Support Vector Machine, String kernel, Alignment-free distance

Introduction

To detect similarities in bio-sequences, in the so called hit and extend strategy framework, spaced seeds are now a frequently used technique to define the hit [START_REF] Keich | On spaced seeds for similarity search[END_REF]. Several tools have been proposed 1 that use spaced seeds [START_REF] Chen | PerM: efficient mapping of short sequencing reads with periodic full sensitive spaced seeds[END_REF][START_REF] David | SHRiMP2: Sensitive yet practical short read mapping[END_REF][START_REF] Harris | Improved pairwise alignment of genomic DNA[END_REF][START_REF] Homer | BFAST: An alignment tool for large scale genome resequencing[END_REF][START_REF] Ilie | BOND: Basic OligoNucleotide Design[END_REF][START_REF] Szymon | Adaptive seeds tame genomic sequence comparison[END_REF], Li et al., 2004[START_REF] Hao Lin | ZOOM! Zillions Of Oligos Mapped[END_REF][START_REF] Zhou | Spaced seeds for cross-species cDNA-to-genome sequence alignment[END_REF], or to design spaced seeds [START_REF] Buhler | Designing seeds for similarity search in genomic DNA[END_REF][START_REF] Do Duc | AcoSeeD: An ant colony optimization for finding optimal spaced seeds in biological sequence search[END_REF], Ilie et al., 2011[START_REF] Kucherov | A unifying framework for seed sensitivity and its application to subset seeds[END_REF][START_REF] Marschall | Probabilistic arithmetic automata and their applications[END_REF][START_REF] Nuel | Bioinformatics -Trends and Methodologies, chapter Significance Score of Motifs in Biological Sequences[END_REF]. Work related to spaced seeds also includes the lossless filtration problem [START_REF] Battaglia | Masking patterns in sequences: A new class of motif discovery with don't cares[END_REF][START_REF] Břinda | Languages of lossless seeds[END_REF][START_REF] Burkhardt | Better filtering with gapped q-grams[END_REF], Egidi and Manzini, 2014a,b, Farach-Colton et al., 2007[START_REF] Giladi | Error tolerant indexing and alignment of short reads with covering template families[END_REF][START_REF] Kucherov | Roytberg. Multiseed lossless filtration[END_REF][START_REF] Nicolas | Hardness of optimal spaced seed design[END_REF], in the sense that all the alignments of a given set must be detected; the work proposed in this article can be applied to this problem too (section 3.3), but we concentrate on the lossy filtration problem in the sense that we suppose that the alignments are associated with a probabilistic model. We also mention a related work on clump statistics [START_REF] Bassino | Constructions for clumps statistics[END_REF][START_REF] Marschall | Probabilistic arithmetic automata and their applications[END_REF][START_REF] Donald | Distribution of clump statistics for a collection of words[END_REF][START_REF] Régnier | Clump combinatorics, automata, and word asymptotics[END_REF][START_REF] Stefanov | Waiting times for clumps of patterns and for structured motifs in random sequences[END_REF] that is close (but not similar), and that can, in some way, be complementary when both of them are considered in a more general framework.

The organization of the article is as follows. Section 2 gives notation and definitions related to spaced seeds. Section 3 defines the coverage of spaced seeds and proposes the tools used to measure it. Section 4 shows how coverage can be used in two biologically oriented applications : first, when spaced seeds are included within SVM kernels (sub-section 4.1), or when spaced seeds are applied to measure phylogenetic distances (sub-section 4.2). In this last case, we also propose a new distance based on the coverage (subsection 4.2.2) and the substantial improvement achieved. Section 5 provides, at the end, some concluding remarks.

Notation

We suppose here that strings are indexed starting from position number 1. For a given string u, we will use the following notation : u[i] gives the i-th symbol of u, |u| is the length of u, and |u| a is the number of symbol letters a that u contains. Also, d (u) is the prefix of length d of the string u, and (u) d is the suffix of length d of the string u. For two strings u and v, u • v is the concatenated string.

Alignments without gaps (indels) can be modeled by a succession of mismatch or match symbols, and thus be represented as a string x in a binary alphabet {0, 1}. A spaced seed can be represented as a string π, but in a different binary alphabet { * , 1} : 1 indicates a position on the seed π where a match must occur in the alignment x (it is thus called a must match symbol), whereas * indicates a position where a match or a mismatch is allowed (it is thus called a joker symbol). The weight of a seed π (denoted by w) is defined as the number of must match symbols (w = |π| 1 ), whereas the span/length of a seed π (denoted by k) is its full length (k = |π|).

A spaced seed π of length k hits an alignment x of length n starting at position i

(i ∈ [1 . . . n -k + 1]) iff ∀j ∈ [1 . . . k] π[j] = 1 =⇒ x[j + i -1] = 1
The usual requirement for a seed, when used to detect alignments x, is to have at least one hit [START_REF] Keich | On spaced seeds for similarity search[END_REF]) in x, the so called single hit criterion. Several methods are also based on multiple hits, as they require more than one hit to trigger an alignment extension [START_REF] Burkhardt | q-gram based database searching using a suffix array (QUASAR)[END_REF][START_REF] David | SHRiMP2: Sensitive yet practical short read mapping[END_REF][START_REF] Kim | Efficient q-gram filters for finding all ǫ-matches over a given length[END_REF]. In the next section, we extend the way to define criteria based on seed hits by measuring coverage provided by these hits.

3 Definition and computation of the seed coverage

Definition of the coverage

The coverage of a seed π on an alignment x is defined by the number of 1's in the alignment x that are covered by at least one must match symbol of one of the seed's hits [START_REF] Benson | Exact distribution of a spaced seed statistic for DNA homology detection[END_REF], Martin, 2013, Martin and Noé, 2014).

For example, the seed π = 11 * 1 has three hits on the string alignment x = 101111001011111. The coverage provided by these hits (denoted by • symbols below) is 8.

π occ1 1 1 * 1 π occ2 . . . . . . . . . 1 1 * 1 π occ3 . . . . . . . . . . . . 1 1 * 1 x 1 0 1 • 1 • 1 1 • 0 0 1 0 1 • 1 • 1 • 1 • 1 •
The coverage concept can be generalized to multiple seed patterns. For example, the set of seeds

{π 1 , π 2 } = {11 * 1, 1 * 1 * 1}
has six hits on the string alignment x. The coverage provided by these hits is 11.

π 2 occ1 1 * 1 * 1 π 1 occ2 . . . 1
x 1 • 0 1 • 1 • 1 • 1 • 0 0 1 • 0 1 • 1 • 1 • 1 • 1 •

Coverage automaton

Given a seed π or a set of seeds {π 1 , π 2 , . . .} along with an input string x, the aim of the automaton is to compute the coverage of π 1 , π 2 , . . . on x, as defined in section 3.1. To fully compute the coverage, a necessary and sufficient task, typically devoted to an automaton, is to update the coverage each time we concatenate a new symbol to the right of x. For example, for the set of seeds {π 1 , π 2 } = {11 * 1, 1 * 1 * 1} and the string x = 1011110011110, we desire to determine the set of newly covered positions (denoted by two • symbols below) after reading the new symbol 1 to form the extended string x ′ = x • 1, together with their count to update the coverage. We will call this (+2) value the coverage increment.

π 2 occ1 1 * 1 * 1 π 1 occ2 . . . 1 1 * 1 π 1 occ3 . . . . . . . . . . . . . . . 1 1 * 1 x 1 • 0 1 • 1 • 1 • 1 • 0 0 1 • 1 • 1 1 • 0 ↓ π 2 occ1 1 * 1 * 1 π 1 occ2 . . . 1 1 * 1 π 1 occ3 . . . . . . . . . . . . . . . 1 1 * 1 π 2 occ4 . . . . . . . . . . . . . . . . . . 1 * 1 * 1 π 1 occ5 . . . . . . . . . . . . . . . . . . . . . 1 1 * 1 x ′ 1 • 0 1 • 1 • 1 • 1 • 0 0 1 • 1 • 1 • 1 • 0 1 • For a set of seeds {π 1 , π 2 , . . .} with k = max i (|π i |), first notice that a suffix of x of length (at most) k -1
is sufficient to know which proper prefixes of one of the seeds can lead to a new hit : we will call q this suffix.

Moreover, to update the coverage increment, we need to know which 1 symbols inside q have already been covered by previous hits of one of the seeds : this can be done with a binary word c of length |q| associated with q. States of the automaton are thus defined accordingly by a pair q c .

For example, for the set of seeds {π 1 , π 2 } = {11 * 1, 1 * 1 * 1}, the state reached when reading the first string alignment x = 1011110011110 (used in the previous example) is represented by the pair q c = 1

• 11 • 0 and the transition to x ′ = x • 1 can be computed accordingly with the new hits of π 1 and π 2 The new state may be represented by the pair

π 2 occ4 . . . 1 * 1 * 1 π 1 occ5 . . . 1 1 * 1 q → q ′ . . . 1 • 1 • 1 • 0 1 •
q ′ c ′ = 1 • 1 • 01 • with |q ′ | ≤ k -1.
Note that q ′ can even be reduced to a smaller suffix, because no proper prefix of π 1 or π 2 can start with q ′ = 1101, but a prefix of π 2 can match the first proper suffix of q ′ , namely 101, to initiate a hit. Thus

q ′ c ′ = 1 • 1 • 01 • ≡ 1 • 01 •
: this reduction can be done easily using the Fail function of Aho-Corasick algorithm [START_REF] Aho | Efficient string matching: An aid to bibliographic search[END_REF] which is applied in classical seed automata [START_REF] Buhler | Designing seeds for similarity search in genomic DNA[END_REF][START_REF] Kucherov | Subset seed automaton[END_REF], as well as coverage automata [START_REF] Benson | Exact distribution of a spaced seed statistic for DNA homology detection[END_REF]Mak, 2008, Martin andNoé, 2014). We will suppose that we always apply this reduction on all the states q c .

From the point of view of the automaton definition, two finite state machines are possible : Mealy or Moore. Accordingly, the automaton must provide the coverage increment, either on each transition (for the Mealy automaton), or on each state (for the Moore automaton). For example, on the set of seeds {π 1 , π 2 } = {11 * 1, 1 * 1 * 1}, these two representations are illustrated on Figures 1 and2 : due to size, we present here the minimal version for both automata by merging equivalent states. For readability, when some hits occur, we have represented the states q c with their full length matching symbols of length up to k and not k -1 (see for example q c ≡ 1

• 1 • 01 • and q ′ c ′ ≡ 1 • 01
• on the Figures 1 and2). The Mealy automaton is obviously more compact when considering the number of states. On the other hand, it requires one to store an additional value per transition (and also needs more specific algorithms : for example, the Hopcroft minimization algorithm [START_REF] Hopcroft | An n log n algorithm for minimizing the states in a finite automaton[END_REF]) must be adapted to the Mealy case).

Each representation has been independently implemented by one of the authors : the one based on count on transition (Mealy) is implemented in Matlab (see Martin, 2013, Martin andNoé, 2014), and code has been also tested on Octave (Octave community, 2014), whereas the other, mainly for compatibility issues, is based on count on states (Moore), and is generalized for subset seeds (slight extension of spaced seeds) with multiple seeds in mind [START_REF] Kucherov | Subset seed automaton[END_REF]. The "Mealy" Matlab code is available upon request from the second author, and the "Moore" code is included in the C++ Iedera program [START_REF] Kucherov | Roytberg. Iedera subset seed design tool[END_REF] starting from development version 1.06 α7.

Several minimizations of the states (considering both q and c) can be considered during the construction of these automata, but the details are out of scope of this article (see Kucherov et al., 2007, Martin andNoé, 2014). In practice, we use at least two methods to detect coverage strings c that are equivalent, together with the optimisation of [START_REF] Kucherov | Subset seed automaton[END_REF] on strings q to save some memory space before completing the full automaton. Note that this last automaton, once entirely built, can always be fully reduced to its minimal form, for example by applying the classical Hopcroft minimization algorithm [START_REF] Hopcroft | An n log n algorithm for minimizing the states in a finite automaton[END_REF]. Independently, we also mention that it seems difficult, for this special coverage problem, to find an equivalent classical regular expression to help build the automata. Even classical tools (such as grep) have for example equivalent parameters to simulate a single or multiple hit, but no parameter is provided for this coverage problem.

Computation

Given a generative model X for the string x, it is possible to compute the distribution of the coverage values according to a Markov process (Martin, 2013, Martin andNoé, 2014) or any model that can be represented by a non-deterministic probabilistic automaton [START_REF] Kucherov | A unifying framework for seed sensitivity and its application to subset seeds[END_REF][START_REF] Marschall | Probabilistic arithmetic automata and their applications[END_REF], Martin and Noé, 2014[START_REF] Nuel | Pattern Markov chains: optimal Markov chain embedding through deterministic finite automata[END_REF]. We don't consider directly in this article this computation, as the model used in our tests is pure Bernoulli : the computation can thus be performed directly with a simple dynamic programming algorithm on the coverage automaton of section 3.2. We refer to the aforementioned articles for more details on more complex probabilistic models. Independently, we also mention that the work proposed here is applied on the lossy seed framework, in the sense that we consider a probability to hit (or cover) an alignment sequence x generated by a model X .

However, this work is not strictly limited to probabilities, and can be easily extended, for example to the lossless seed framework. In that case, the set of alignments is fixed, for example by giving a fixed length together with a fixed number of errors : the problem is then to always hit (or cover) any of the alignments on this set (so without loss). This last computation can be done easily, simply by replacing the semi-ring used for probabilities by a less conventional tropical semi-ring [START_REF] Mohri | Handbook of Weighted Automata, chapter Weighted Automata Algorithms[END_REF][START_REF] Pin | Tropical semirings[END_REF][START_REF] Simon | Recognizable sets with multiplicities in the tropical semiring[END_REF]) used for match/mismatch scores or mismatch costs. Note also that the simple fact of counting the number of alignments, in alignment classes that have a given percentage of identity (as done in [START_REF] Benson | Exact distribution of a spaced seed statistic for DNA homology detection[END_REF], or a given coverage for a set of seeds, or any combination of these elements, is also possible, by use of a counting semi-ring adapted for this task [START_REF] Huang | Dynamic programming algorithms in semiring and hypergraph frameworks[END_REF].

Experiments

In this section, we consider two biological sequence oriented applications that have recently been proposed to use spaced seeds : SVM classifiers based on spaced string kernels [START_REF] Onodera | The gapped spectrum kernel for support vector machines[END_REF], and alignment-free distance estimators using spaced k-mers [START_REF] Boden | Alignment-free sequence comparison with spaced k-mers[END_REF], Horwege et al., 2014, Leimeister et al., 2014). We show that the coverage sensitivity can be used in both cases to improve the estimators, and thus also be applied to the selection of the best seed patterns on such domains.

Additional data and results, together with scripts used for this section can be found at http://bioinfo.lifl.fr/yass/iedera_coverage/.

Coverage sensitivity and spaced seed string kernels

String kernels [START_REF] Lodhi | Text classification using string kernels[END_REF] are a classical model used for text classification with SVM. They have frequently been applied to biological sequence classification, as k-spectrum kernels [START_REF] Leslie | The spectrum kernel: A string kernel for SVM protein classification[END_REF], mismatch k-spectrum kernels [START_REF] Leslie | Mismatch string kernels for discriminative protein classification[END_REF], string alignment kernels [START_REF] Saigo | Protein homology detection using string alignment kernels[END_REF], profile-based string kernels [START_REF] Kuang | Profile-based string kernels for remote homology detection and motif extraction[END_REF] to cite a few examples.

k-spectrum kernels and its derivatives are mostly used with contiguous seeds : surprisingly, no spaced seeds were designed to comply with this approach. However, it has been experimentally shown by [START_REF] Onodera | The gapped spectrum kernel for support vector machines[END_REF], and during the submission of this work by Ghandi et al. (2014a,b) that spaced seeds help decrease the zero/one misclassification rate in practice, even for the simplest kernels. The main reason of this lack might be the intrinsic difficulty to find a correct estimation criterion for spaced seed patterns, but on the other hand, not so much effort has been made to increase the diversity of criteria used. Most of the proposed algorithms to estimate spaced seed sensitivity concentrate on the single-hit criterion ("at least one hit for a seed/set of seeds"). This criterion makes sense for classical "hit and extend" alignment methods used in bioinformatics, but seems to be too restrictive for spectrum kernels that are supposed to filter the information content based of "several concordant clues".

The multi-hit criterion ("at least t hits for a seed/set of seeds") seems at first more appropriate for this task, but again has never been tried in this field of research. One possible drawback is that it does not distinguish highly overlapped hits of seeds from disjoint ones. Finally, and for the latter reason, we also decided to apply the new coverage criterion ("at least t covered 1-symbols in the alignment, each covered by at least one 1-symbol of a seed hit ") in comparison with the two others.

In the two following subsections, we try to correlate these three criteria with SVM zero/one misclassification rate.

SVM-Benchmark and Protocol

The benchmark used for this test consists of 2208 families extracted from the non-coding RNA database RFAM v11.0 [START_REF] Burge | Rfam 11.0: 10 years of RNA families[END_REF]. It represents up to 65908 sequences per family.

We decided to split each family by randomly picking 50% of its sequences for the SVM learning process and keeping the 50% remaining for the classifier to measure the zero/one misclassification rate. We use the SV M multiclass [START_REF] Joachims | Learning to Classify Text using Support Vector Machines[END_REF] package Version 2.20 (date 14.08.2008) from http://www.cs.cornell.edu/people/tj/svm_light/s with the linear kernel. In each case, single or double seeds of weight 3 and span from 3 to 7 were used as a k-spectrum string kernel.

Seed sensitivity

In parallel, for each single or double seed, we compute its "sensitivity", either using the single hit criterion, the multi-hit criterion, or the coverage criterion. Note that, for the two last criteria, we have the possibility to change the threshold t required to consider a success. We arbitrarily choose to measure these seeds on an i.i.d. alignment model of length 32 (the probability to have a 1-symbol in the alignment has been fixed at 0.7) although experiments show that this does not have much influence on the final results [data not shown].

Figure 3: zero/one misclassification rate vs theoretical sensitivity Examples of comparative plots are given in Figure 3 for multi-hit and coverage-hit : a slight correlation can be seen at first sight. But we can also see that some seeds with repetitive and highly correlated patterns (e.g. 1*1*1), usually bad in theory, are in practice more efficient for the SVM-classifier.

Correlation between zero/one misclassification and the three criteria

Finally, to determine if one of the three estimators was better suited to correlate with this SVM classifier task, we computed the sample Pearson correlation coefficient for each of the three criteria, for each set of seeds : this gives the best correlation between the theoretical seed sensitivity estimated by one of the three estimators with the experimentally measured sensitivity of the SVM classifier of each set of seeds.

For both the multiple hit and coverage criteria, we allowed the threshold parameter t for seed sensitivity to vary (x-axis). These results are illustrated in Figure 4 for single and double seeds. Surprisingly, correlation results for the multi-hit criterion are not good when the number of hits Figure 4: Correlation coefficient between zero/one misclassification rate and theoretical sensitivity required is too large. This must be taken into account when using this criterion because the multi-hit criterion gives correct results for double seeds when the number of hits is for example at 2 . The single-hit criterion gives good results for each set. However combining single and double seeds into one set, and doing the same experiment makes it the worse of the three estimators [data not shown].

A carefully chosen value for the coverage criterion (here between 14 and 16) helps to reach the highest correlation of the three for double seeds. On single seeds, this is difficult to conclude, due to the few seeds of weight 3 that have been tested. Note that we also tried the same experiment for seeds of weight 4 but the dimension used here (4 4 ) makes the classifier more random without a preselection of dimensions [data not shown].

We can first notice that the correlation of the single-hit criterion is more stable than the correlation of the coverage criterion that varies more for lower thresholds. It also seems that the optimal coverage threshold is at some point a surprisingly quite regular and convex function that might be estimated when enough data is available.

Coverage sensitivity and alignment-free distance for sequence comparison

Estimating alignment-free distance is a common method used for sequence comparison in multiple alignment tools guided tree estimation [START_REF] Edgar | MUSCLE: Multiple sequence alignment with high accuracy and high throughput[END_REF] and related phylogenetic tree estimation [START_REF] Liu | Accurate taxonomy assignments from 16S rRNA sequences produced by highly parallel pyrosequencers[END_REF][START_REF] Qi | CVTree: A phylogenetic tree reconstruction tool based on whole genomes[END_REF]. Several distances are based on fixed size k-mers (Simsa et al., 2009, Vinga and[START_REF] Vinga | Alignment-free sequence comparison -a review[END_REF] with possible mismatches allowed [START_REF] Apostolico | Alignment free sequence similarity with bounded Hamming distance[END_REF], or with variable length k-mers : local decoding [START_REF] Didier | Variable length local decoding and alignment-free sequence comparison[END_REF], irredundant common subwords [START_REF] Comin | Alignment-free phylogeny of whole genomes using underlying subwords[END_REF], etc. They are applied on assembled genomes [START_REF] Chor | Genomic DNA k-mer spectra: Models and modalities[END_REF][START_REF] Haubold | Genome comparison without alignment using shortest unique substrings[END_REF], protein classification [START_REF] Pooj | Simple alignment-free methods for protein classification: A case study from G-protein-coupled receptors[END_REF], and even on unassembled genomic data to estimate phylogenies [START_REF] Maurer-Stroh | A simple shortcut to unsupervised alignment-free phylogenetic genome groupings, even from unassembled sequencing reads[END_REF]. We refer to a recent special issue on alignment-free methods for more details [START_REF] Vinga | Editorial: Alignment-free methods in computational biology[END_REF].

Interestingly, it's only in the last year that the use of spaced seeds has been proposed [START_REF] Boden | Alignment-free sequence comparison with spaced k-mers[END_REF], Horwege et al., 2014, Leimeister et al., 2014), with recent applications for specific Next Generation Sequencing tasks, such as multi-clonal clusterization [START_REF] Mathieu | Fast multiclonal clusterization of V(D)J recombinations from high-throughput sequencing[END_REF]. Here again, the lack of seed criteria used in the literature didn't help the selection of good seeds for these tasks.

In subsection 4.2.1, we recall that the "classical" distance can be estimated by multi-hit sensitivity computation which helps in selecting good spaced seeds.

In subsections 4.2.2 and 4.2.3, we also show that coverage sensitivity can be used in a more elaborate distance : this distance can be computed using the Longest Increasing Subsequence (LIS) of the positions of the common hits between gapped k-mers. As LIS can be computed in t • log(t) time, where t is the number of hits, it is thus a reasonable estimator in practice.

Multi-hit experimental support

One common method used to estimate alignment-free distances is based on k-mer frequency : 4 k counts can be first made and used as simple Feature Frequency Profiles (where counts are normalized to relative frequencies for any of the 4 k k-mers), or more elaborate Composition Vectors (where normalization is done with the help of a background model). Distances can then be estimated by several models [START_REF] Vinga | Alignment-free sequence comparison -a review[END_REF] to provide phylogenetic applications with an initial distance matrix. As some of these phylogenetic methods, as Unweighted Pair Group Method with Arithmetic Mean (UPGMA) [START_REF] Michener | A quantitative approach to a problem in classification[END_REF], start by considering small distances, it's important to have the best estimator here, and keep track of common k-mers (or spaced k-mers) and their common locations in the two sequences. One estimator that can help in that task is the number of seed hits obtained : we will call it the multi-hit value.

For our experiment, we use a set of seeds (627 seeds of weight 3 or 4, span up to 7, single seed or double seed patterns), a percentage of identity varying from 20% to 100% by steps of 5% each time, and we generate (for each percentage of identity) 1000 alignments of length 32. We then measure the multi-hit value of each alignment and compare it to the true alignment distance.

It can be shown first (Figure 5 x-axis only) that the correlation coefficient is high (> 0.9 for seeds of weight 3, less otherwise). Provided that we expect to pay a little additional cost, it is possible to improve this result, as shown in the next section.

Coverage experimental support

The distance we propose to measure is based on the number of covered 1-symbols in the alignment, each covered by at least one 1-symbol of a seed hit : we will call it the coverage value. To show how this distance better estimates the true distance (we assume here that the Hamming distance is the true distance), we are repeating the same experiment with both the multi-hit value and the coverage value on the set.

We use the same protocol here : the same set of seeds (627 seeds of weight 3 or 4, span up to 7, single seed or double seed patterns), the same percentage of identity varying from 20% to 100% by steps of 5% each time, and generating for each percentage of identity the same 1000 alignments of length 32 each time, we measure the multi-hit and the coverage values for each simulated alignment. Then, we compared the correlation coefficient for each of these two measures with the true percentage of identity used to simulate the alignment.

The correlation coefficient for all the seeds was 0.88 for the multi-hit value and 0.96 for the coverage value.

We tried to refine this first experiment by separately measuring single seed patterns and double seed patterns and running the same test. For single seed patterns, the correlation was 0.89 and 0.94 respectively, whereas for multiple seed patterns, it was 0.89 and 0.96 respectively. We also tried to measure this correlation for each of the 627 seeds : Figure 5 plots these two correlations (pair of coordinates).

Note first that, as all the points for this plot are on the left-upper region, the true distance is better estimated by the coverage value than by the multi-hit value. We can also notice that double seeds outperform single seeds in both cases, so that multiple seed patterns can help in estimating the distance more accurately than single seed patterns : the gain is even better for the coverage value than for the multi-hit value.

From the point of view of the seed weight and the number of seed patterns used, we can see that using two patterns of weight 4 gives the same correlation coefficient as using one single pattern of weight 3, but only for the coverage value, not for the multi-hit value : this encouraging result may help defend the idea that more patterns of larger weight will help measure a correct distance. Note that this conclusion is quite similar to the one provided ten years ago for detecting alignments [START_REF] Li | PatternHunter II: Highly sensitive and fast homology search[END_REF], which was recently and independently observed in [START_REF] Horwege | Spaced words and kmacs: Fast alignment-free sequence comparison based on inexact word matches[END_REF], [START_REF] Leimeister | Fast alignment-free sequence comparison using spaced-word frequencies[END_REF], but here, as the distance estimation problem is quite different from alignment detection, the seeds designed will probably be completely different from those previously seen.

Figure 5:

! "#$ "%$ # & % ' '
From the point of view of the seed patterns, we can see in Figure 5 that, for single seeds, selection done for both values gives the same optimal seed pattern 11*1 (or its mirror) for weight 3, and the same optimal seed pattern 1*1**11 (or its mirror) for weight 4. The choice for the optimal double seed patterns differs between the multi-hit or coverage values, and this difference is even more marked for seeds of weight 4. However, computing the coverage is more difficult than simply counting common k-mers. We justify in the next part that, given two easily measurable assumptions on the sequences and the k-mer weight, this task can be done efficiently.

Coverage algorithmic point of view

In this part, we briefly describe how coverage can be computed efficiently. Given two sequences s 1 and s 2 of equivalent length, we want to search for the spaced k-mers that are common to s 1 and s 2 . But, more than establishing a frequency profile for these common k-mer codes, the main idea is here to find a set of common k-mers that have the same order of position occurrences on s 1 and s 2 . To do so, one solution is to keep occurrences of any of the 4 k possible k-mers in a reverse list of positions (given one k-mer code, we have two lists of positions where this k-mer occurs, on s 1 or respectively on s 2 ). Keeping the common k-mers of both s 1 and s 2 , sorting their list of pairs of occurrence positions according to the positions of one of the two sequences (for example positions along s 1 ), then applying a LIS (or a windowed LIS if the two sequences are not of similar lengths) on s 2 , provided that spurious k-mers (those occurring randomly) are not frequent, will give a better approximation for the number of true hits, and thus can be used to compute the coverage.

Note first that the LIS can be computed in t • log(t) time [START_REF] Schensted | Longest increasing and decreasing subsequences[END_REF] where t is the number of hits (e.g. pairs of positions for a common k-mer) : this value t, provided that k is well chosen to correctly filter spurious k-mers and there is no composition bias on both sequences, must be either close to |s 1 | and |s 2 | if the s 1 and s 2 sequences are similar (and without self-repetitive bias/low complexity regions), or reasonably low if the sequences are non-similar, but can be otherwise high for low complexity/self-repeating/redundant regions that similarity search tools usually want to avoid.

Note also that, once the common and ordered hits are collected by the LIS procedure, it is possible to compute the coverage using :

• either a masking process using shift-or for collecting the coverage symbols, and then computing the coverage increment (which implies an additional CPU cost if no population count instruction is available),

• or an automaton (an example is provided in Figure 6 for the hits of the seeds {π 1 , π 2 } = {11 * 1, 1 * 1 * 1}) that keeps the last overlapping suffix of the previously encountered hits for any of the seeds. This automaton has an alphabet of size 2 #seeds since we record whether or not there is a seed hit for each seed.

Otherwise, a very similar definition to the coverage automaton holds. Once this automaton is built, it is possible to compute the coverage increment in constant time.

In both cases, gaps (indels) must be taken into consideration because they break, from a dot-plot point of view, diagonals, thus reinitializing the automaton or the coverage mask.

} = {11 * 1, 1 * 1 * 1} 1 • {} 1*1 • • {¹} (+2) *1*1 • • {²} (+2) 1111 •••• {¹,²} (+4) {} {¹} (+3) {²} (+3) {¹,²} (+5) {²} (+1) {¹,²} (+3) *1 • {} 111 ••• {¹} (+2) {} {¹} (+1) {²} {¹,²} (+3) {²} {¹,²} (+1) {} {¹} {} {¹} (+2) {¹,²} (+4) 11*1 •• • {²} (+3) {} {¹} {²} {¹,²} (+2) 11 •• {} {¹} (+1) {¹,²} (+3) {²} (+2) {¹,²} (+2) {²} (+1) {} {¹} (+1)

Concluding Remarks

We have presented how the coverage criterion [START_REF] Benson | Exact distribution of a spaced seed statistic for DNA homology detection[END_REF]Mak, 2008, Martin, 2013) can help in measuring the seed efficiency in two recent problems : a classifier based on spaced k-mers [START_REF] Onodera | The gapped spectrum kernel for support vector machines[END_REF], and a k-mer alignment-free distance estimation [START_REF] Boden | Alignment-free sequence comparison with spaced k-mers[END_REF], Horwege et al., 2014, Leimeister et al., 2014). We have also shown how to extend the second one to be even more sensitive.

The Moore (or Mealy) automaton obtained to measure the coverage criterion is by itself of interest for several reasons : its size seems to be bounded by polynom(w, r) × 3 r even if the bound obtained now is rather limited and exponential (see the Appendix).

For example the coverage automaton size for the PatternHunter 1 seed where the current sizes for Moore and Mealy automata are respectively obtained by the Iedera tool (Kucherov et al., 2014, version 1.06 α7), or by the Matlab code (Martin and Noé, 2014) before minimization by the gap-system FR package [START_REF] Bartholdi | Functionally recursive groups[END_REF]. These sizes can be compared with those of the mere multi-hit automaton :

Moore Mealy

states

Although more than 20 times larger than the equivalent multi-hit automaton, the coverage automaton for multiple seeds is again still usable for dynamic programming computation.

It would be also interesting (but out of the scope of this article) to consider SVM kernels or k-mer distances with subset seed [START_REF] Frith | Improved search heuristics find 20 000 new alignments between human and mouse genomes[END_REF][START_REF] Gambin | Subset seed extension to Protein BLAST[END_REF][START_REF] Kucherov | Subset seed automaton[END_REF][START_REF] Yang | Run probabilities of seed-like patterns and identifying good transition seeds[END_REF] or more general vector seed [START_REF] Brejová | Vector seeds: An extension to spaced seeds[END_REF] techniques. Several string kernels, such as the mismatch string kernel [START_REF] Leslie | Mismatch string kernels for discriminative protein classification[END_REF], use this general concept, but generate full neighborhoods (all the words at a given distance from a given k-mer). Moreover optimal resolution [best seed weight] [START_REF] Simsa | Alignment-free genome comparison with feature frequency profiles (FFP) and optimal resolutions[END_REF] remains an open problem for spaced seeds in both SVM kernels or k-mer distance problems. Note also, if one wants to avoid this optimal resolution question, seed design and increasing weight can be combined (as done in [START_REF] Csűrös | Performing local similarity searches with variable length seeds[END_REF][START_REF] Szymon | Adaptive seeds tame genomic sequence comparison[END_REF], but may not be always directly compatible with the aforementioned cited works on variable k-mers.

A last idea to explore is also to merge the definition of clumps [START_REF] Bassino | Constructions for clumps statistics[END_REF][START_REF] Marschall | Probabilistic arithmetic automata and their applications[END_REF][START_REF] Donald | Distribution of clump statistics for a collection of words[END_REF][START_REF] Régnier | Clump combinatorics, automata, and word asymptotics[END_REF][START_REF] Stefanov | Waiting times for clumps of patterns and for structured motifs in random sequences[END_REF]) with coverage, for example by giving more significance (than a linear weight function) to coverage provided by clumps of hits than coverage provided by isolated hits.

A Seed coverage automaton size

We consider in this part the size of the seed automaton. Given a seed of weight w and r jokers we are particularly interested in a bound for the size of the coverage automaton, as this can provide a limit on memory needed for future analyses.

In this section, we first solve the problem in the special case of a seed of the form 1* r 1, before going to a more general case of a seed of weight w and r jokers, for which we show a more general (but less satisfying) upper bound.

A.1 Seed 1* r 1 coverage automaton size In boxes are set all the seed prefixes q that can be reached for the Moore multi-hit (a) and the Moore coverage (b) automata. Additionally, on the coverage automaton (b), for each prefix q, we have enumerated all the possible coverage strings c that are compatible to form q c states : this is done by substituting any non-covered 1 symbol of q c (but the last) by a possibly covered one 1 The 1* r 1 seed family has already been shown to reach the multi-hit automaton size bound [START_REF] Kucherov | A unifying framework for seed sensitivity and its application to subset seeds[END_REF] : as a nightmare for the classical seed design tools, such seeds are good candidates to start with.

The multi-hit automaton size is, in the general case, of maximal size (w + 1)2 r [START_REF] Buhler | Designing seeds for similarity search in genomic DNA[END_REF][START_REF] Kucherov | A unifying framework for seed sensitivity and its application to subset seeds[END_REF]. Moreover, for seeds of the form 1* r 1, this size cannot be reduced further [START_REF] Kucherov | A unifying framework for seed sensitivity and its application to subset seeds[END_REF] : thus, 1* r 1 always have multi-hit automata of size 3 × 2 r (illustrated in Figure 7 (a) where not all the transitions are shown).

The coverage automaton size for seeds of the form 1* r 1 is respectively 4 × 3 r for the Moore automaton, and 3 × 3 r for the Mealy automaton.

Proof. We concentrate first on the Moore automaton. The set of states for the coverage automaton can be easily deduced from the multi-hit automaton by considering, for each of the multi-hit prefixes q, all the possible coverages c that are compatible with the current prefix to form reachable q c states. Any prefix q may have any of its 1-positions (but the last) covered by a previous hit of a seed if this previous hit ends at this 1-position (illustrated by the dot symbols of Figure 7 (b) to mark 1-positions already covered). Moreover, it must be noticed that coverage of any 1-positions inside q can be chosen independently, by making/disabling a previous hit of a seed using its first 1-position (this position is not shown on the automaton, thus not overlapping the current prefix, and does not have any side effect). Thus all the possible 1-positions (but the last) of a given proper prefix q can be chosen independently with or without coverage. Thus, for any proper prefix q of length l + 1 (0 < l + 1 < k) (q overlaps the first must match symbol, followed by l = 1 . . . r joker symbols of the seed ongoing hit)

1. the very first 1 symbol under a must match symbol can be covered or not (two possibilities :

1 or 1 • ),
2. the next l -1 symbols under joker symbols can be independently chosen as 0 or 1 (three possibilities :

0, 1 or 1 • ),
3. the very last symbol under the last joker symbol can be independently chosen as 0 or 1 (two possibilities).

Note that this 1, as new, cannot be covered by a previous hit.

For a given prefix q with l = 1 . . . r jokers, there are thus 2 × 3 l-1 × 2 = 4 × 3 l-1 possible q c states . Finally, the final states can be seen as prefixes q of length k = r + 2, where the last 1 is always newly covered (one choice : 1

•

), the r jokers can be any of 0, 1 or 1

• (3 choices), and the very first 1 can be previously covered or newly covered (2 choices : 1

• or 1

• when considering the Moore automaton), leading to 3 r × 2 final q c states.

At the end, adding the initial state for q = ǫ, and its next state (for q = "1" corresponding to the first must match position of the seed which cannot be covered), gives :

A.2 Coverage automaton size in the general case

Now consider a seed of span k with r jokers and of weight w (w + r = k). Following the previous section A.1, a similar reasoning gives a bound on the automaton size of 2 w × 3 r for the Moore automaton and of (2 w -1) × 3 r for the Mealy automaton.

Proof. We concentrate first on the Moore automaton. We respectively call r j and w j the number of joker symbols and must match symbols for a given seed prefix of length j (r j = j (π) * , w j = j (π) 1 , r j + w j = j).

We don't necessarily suppose that the seed starts and ends with a must match symbol. We will show that the number of states q c such that |q| and |c| are ≤ j is at most 2 wj × 3 rj , by induction.

• This is first true for j = 0, because the empty state (also called the initial state) q c where |q| = |c| = 0

is the only one that can match the empty seed prefix 0 (π).

• If we suppose that it is true for a given i (#{states q c with |q| = |c| ≤ i} ≤ 2 wi × 3 ri ), it can be now considered for j = i + 1. We split the demonstration for j in two parts :

1. when |q| = |c| ≤ i, by taking the set of the 2 wi × 3 ri possible q c states (induction hypothesis) 2. otherwise, when |q| = |c| = j, by considering and adding to this set the states q c that can be possibly reached. Two cases must then be considered :

(a) if the last symbol π[j] of the seed prefix j (π) is a must match, this symbol can only be compatible with a 1 on q[j] (and this 1 cannot be covered by c[j], as the last one being added).

(b) if the last symbol π[j] of the seed prefix j (π) is a joker, this symbol can be compatible either with a 0 or a 1 on q[j] (which cannot be covered by c[j] too) .

Considering now the prefix i (π) preceding π[j], we can see that :

the w i must match symbols of i (π) are compatible with a 1 or a 1

•

(2 wi possibilities),

the remaining r i jokers of i (π) are compatible with a 0, a 1 or a 1

• (3 ri possibilities).

Combining each of the cases (a) and (b) with the preceding prefix i (π) gives 1 × 2 wi 3 ri states for (a), or 2 × 2 wi 3 ri states for (b), respectively, when |q| = |c| = j.

At the end, because (a) w j = w i + 1 and r j = r i , or (b) w j = w i and r j = r i + 1 otherwise, we can see that summing the number of states when |q| = |c| ≤ i and when |q| = |c| = j gives the expected result 2 wj × 3 rj , for non-final states.

Figure 1 :Figure 2 :

 12 Figure 1: Minimized Mealy coverage automaton (count on transitions) for the seeds {π 1 , π 2 } = {11 * 1, 1 * 1 * 1}

Figure 6 :

 6 Figure 6: Mealy coverage increment automaton for hits of the seeds {π 1 , π 2 } = {11 * 1, 1 * 1 * 1}

Figure 7 :

 7 Figure 7: Moore multi-hit (a) and Moore coverage (b) automata size illustrated for the seed π = 1 * 1.

•

  and, for final states, by considering newly covered positions 1• .

  Such seeds 1* r 1 have thus a Moore coverage automata of size 4 × 3 r .

Acknowledgements D.E.K. Martin was supported in this research by the National Science Foundation under Grant DMS-1107084. L. Noé was supported by a CNRS Mastodons grant, and benefited from a half-time course buyout from the French Institute for Research in Computer Science and Automation (Inria).

Author Disclosure Statement

No competing financial interests exist.

Note that this size cannot be reduced. In other words, given any pair of states qa ca and q b c b on this automaton, and starting (from each of these states) a walk by reading the same (given) string u :

• if q a and q b are different, then it is always possible to find one string u such that only one of the two walks reaches a final state (as done in [START_REF] Kucherov | A unifying framework for seed sensitivity and its application to subset seeds[END_REF].

• otherwise, the coverages c a and c b must be different : it is then always possible to find one string u going to two f inal states that have a different coverage increment for the Moore automaton.

We concentrate now on the Mealy automaton. The main difference with the Moore automaton is that suffixes of full length k (that are final states of the Moore automaton) are not represented because coverage values are set on transitions, and not on states (see [START_REF] Frith | Improved search heuristics find 20 000 new alignments between human and mouse genomes[END_REF].

For the Mealy automaton of Martin and Noé ( 2014), and seeds of the form 1* r 1 (of length k = r + 2 and weight 2 ), there are 2 × 3 l proper prefixes q of length l + 1 (0 ≤ l + 1 < k) :

1. the first symbol must be 1, or 1

2. the next l symbols can be 0, 1 or 1

Adding the initial state, gives :

This bound is reached for the same reasons of non-reducibility (applied on transition labels on Mealy, and not on final state labels as in Moore).

It must be then noticed that, even for final states, new symbols that have just been covered (1

•

) are only replacing the non-covered ones (1) on a subset of the w fully determined positions given by the seed shape that are not yet covered (1

•

): they thus don't modify the recurrence when j = |π| as they simply represent indicators to compute the coverage increment.

We concentrate now on the Mealy automaton. Again, the main difference with the Moore automaton is that suffixes of full length k are not represented because coverage values are set on transitions, but one thing to consider is that the last symbol can be covered on the Mealy automaton (see [START_REF] Frith | Improved search heuristics find 20 000 new alignments between human and mouse genomes[END_REF]. By a similar reasoning, there are thus at most k-1=r+w-1 i=0 3 ri × 2 wi states in the general case, and :

Note that if we suppose that the seed starts with a must match symbol, then this bound can be reduced a little more :

We notice in practice a much smaller size, and we suspect this bound more likely to be a polynom(w, r)×3 r value, instead of exponential both in 2 w and 3 r . In the special case of symmetric seeds, we already have a very simple proof of this polynom(w, r) × 3 r bound. This is interesting, because experimentally, seeds of the form 11 u (*1 u ) r 1 have been shown to give large coverage automata size.

Note even if not satisfying, the general result still improves on the only available "bound" proposed to date (in [START_REF] Benson | Exact distribution of a spaced seed statistic for DNA homology detection[END_REF] that can be estimated to be of order w2 w 4 r .


Mohammad H Afzali
email: mohammad.afzali@univ-tlse2.fr

Philippe Birmes
email: birmes.p@chu-toulouse.fr

Stéphane Vautier
email: vautier@univ-tlse2.fr

EVIDENCE-BASED ORDERING OF SUICIDALITY RESPONSE PROFILES

Keywords: Chronic anxiety, Self-harm, Suicidality assessment, Suicide risk, Suicide attempt

 sample of 39,617

French adults, and (ii) detecting the items, among 20 screening items used for Axis I diagnosis, that are informative for suicidality assessment. Three suicidality levels were identified. Cooccurrence of suicide ideation, self-harm intention, and lifetime suicide attempt forms a high risk condition: 44% of current month suicide, 95% confidence interval = [0.38, 0.50]. All suicidality levels were systematically moderated by chronic anxiety. This symptom should be included in the set of relevant risk factors for suicidality assessment.

Introduction

Suicide is one of the main causes of death around the world [START_REF] Bertolote | Psychiatric Diagnoses and Suicide[END_REF], and the study of suicidal behaviors prevalence as well as suicide risk levels has been a part of several psychopathological surveys with nationally representative samples. Relying on the National Comorbidity Survey database, N = 5,877, [START_REF] Kessler | Prevalence of and risk factors for lifetime suicide attempts in the National Comorbidity Survey[END_REF] report that 4.6% of individuals have made a suicide attempt at least once in their lifetime. L'abate ( 2011) reports that about one-third of individuals who attempted suicide repeated such an attempt within the following year, and about 10% of those who threaten or attempted suicide completed the suicidal act. In the European context, relying on the SMPG1 survey database, [START_REF] Roelandt | La santé mentale en population générale : images et réalités[END_REF] highlight an 8% prevalence of life time suicide attempt and a 0.7% prevalence of suicide attempt with current month in the French general population.

Suicide risk assessment, in psychopathological research, consists in assessing the presence of risk factors through item responses, and the ordering of possible response profiles with respect to the suicidality construct. Thus each response profile is associated with a suicidality level. The ordering is based on a consensual approach: risk factors are selected by experts in the field and the assessment rationale can be summed up by -the more hits in the response profile, the more risky this profile‖. Such a rationale implies that the conjoint contribution of each risk factor to suicidality is not amenable to empirical investigation due to the lack of criterion.

The five-item suicidality module of the Mini International Neuropsychiatric Interview (MINI) has been used to establish risk levels in large samples from nationally representative surveys in France (SMPG database, N = 39,617, Bellamy, Roelandt, Caria, & Kergall, 2005) and in China ( N = 1,757, [START_REF] Chen | Suicide risk in major affective disorder: Results from a national survey in China[END_REF], as well as in clinical samples of various psychopathological characteristics such as epileptic patients [START_REF] Gandy | Rates of DSM-IV mood, anxiety disorders, and suicidality in Australian adult epilepsy outpatients: a comparison of well-controlled versus refractory epilepsy[END_REF], and postpartum women [START_REF] Tavares | Prevalence of suicide risk and comorbidities in postpartum women in Pelotas[END_REF]. The assessment of suicidality through the five suicidality items of MINI is based on a set of conventional rules detailed in the Appendix. For example, if a participant reports to have had a suicide attempt in his lifetime along with suicidal ideation, then he is identified as a high risk person. A methodological consequence of this conventional approach is that the risk levels have no meaning in terms of criterion-related validation. In other words it is not clear that the term ‗risk' refers to risk of what specific outcome.

The large size of the SMPG sample provides the opportunity to complement the conventional approach to suicidality assessment by using available evidence. The present study applies an evidence-based alternative to consensual suicidality assessment, which is based on criterion-related validation. Instead of using all risk factors to assign a suicidality level, one can select a proper criterion from the available descriptors, namely, recent suicide attempt. The proportion of this criterion can be examined conditionally to the response profiles that result from the remaining descriptors.

The terms ‗risk', ‗risk factors', and ‗risk scale' may favor scientific miscommunication if they are used carelessly. Thus, before detailing the research objectives of the present study, it is helpful to clarify their meaning in this paper.

Risk, Risk Factor, and Risk Scale: Theory

In medical and epidemiological literature, the phrase ‗risk of an (undesirable) outcome' (e.g., becoming ill or dying) refers to the outcome probability in a population of individuals who share a given characteristic [START_REF] Kraemer | Coming to terms with the terms of risk[END_REF]. Let us consider the simple case of two conditions resulting from having or not having a characteristic. The presence or the absence of the characteristic raises the issue of whether the outcome probability depends on this characteristic (in which case one says that the characteristic moderates the outcome). If the presence of this characteristic is associated with a higher probability, it is considered a ‗risk factor' in the population.

As [START_REF] Kraemer | Coming to terms with the terms of risk[END_REF] mentioned, the manipulability of the characteristic is necessary for a causal interpretation of a risk factor. Considering the impossibility of manipulating some characteristic (e.g. suffering from a mental disorder), cross-sectional or longitudinal studies use the terms ‗risk' and ‗risk factor' to refer to statistical dependencies between a characteristic and a outcome without assuming causal dependencies.

It is common to consider the probability of an undesirable outcome with respect to more than one risk factor. A widespread intuition consists in assuming risk factors are -additive‖, that is, the more risk factors co-occur, the higher the risk. However, one ignores the -addition formula‖. Specifically, it can be expected that characteristics (or risk factors) are riskier when they co-occur. Thus, it is possible to estimate the outcome probability for each compound condition. In the case of n risk factors, 2 n compound conditions have to be considered. In this perspective, a risk scale results from ordering of different compound conditions with respect to their respective outcome probabilities.

Risk, Risk Factor, and Risk Scale: Methodology

In risk assessment, the only accessible information is the frequency (or, equivalently, the proportion) of outcome in certain conditions. In order to establish a risk factor one has to compare the outcome frequencies in the samples corresponding to these conditions. [START_REF] Cohen | Statistical Power Analysis for the Behavioral Sciencesitle[END_REF] h index of effect size is useful to decide whether the difference should be acknowledged or neglected.

When several risk factors are considered conjointly, in order to constitute a risk scale, one has to consider the outcome frequency with respect to each compound condition of characteristics. For example, four risk factors yield in 2 4 = 16 compound conditions. Furthermore, one aims at finding out an ordering of 16 conditions, relying upon the outcome frequencies in the corresponding samples.

As the liability of frequencies depends on sample sizes, a trade-off has to be found between both the number of conditions that can be distinguished and the sizes of the relevant samples. This issue is critical when the outcome prevalence is low. A possible strategy consists in considering the union of distinct conditions when their respective samples have a small size and exhibit similar outcome frequencies. Of course, the resulting ordering can be revised as far as the survey database can be updated.

Objectives

This study aims at supplementing the current rules of French MINI suicidality module listed in the Appendix, through an evidence-based approach that takes recent suicide attempt as the outcome. Moreover, it examines the relevance of additional characteristics-which are not comprised in the suicidality items. An additional characteristic is considered relevant if it systematically moderates the outcome probability once the suicidality conditions have been taken into account. .

Method

Materials

The SMPG survey [START_REF] Roelandt | La santé mentale en population générale : images et réalités[END_REF] consists of two main interviews. (i) A sociodemographic interview regarding gender, age, marital status, education, professional activity, income level, religious beliefs and practice, immigration, and country of origin. (ii) The 166item version of the French MINI aims at assessing suicidality and the prevalence of psychiatric disorders. [START_REF] Lecrubier | The Mini International Neuropsychiatric Interview (MINI). A short diagnostic structured interview: reliability and validity according to the CIDI[END_REF] The present study focuses on the information provided by the MINI. The MINI was designed as a brief structured interview for 12 Axis I psychiatric disorders with priority given to current diagnosis (161 items), along with five suicidality items. All items are to be answered in a ‗yes' or ‗no' format. Each of the 12 psychiatric disorders is evaluated with screening items.

Negative answers to screening items necessarily rule out the diagnosis. Consequently, complete data is only available for the 20 screening items that are used for the 12 Axis I psychiatric disorders.

Participants

The SMPG survey consisted in interviewing a nationally representative sample of 39,617 respondents in 47 sites in France. In each site, approximately 900 participants were evaluated by nursing students using interviews mentioned above. The sample is composed of 54% women and 46% men, aged 18 and older (M = 45, SD = 18.3).

Analyses

The first part of this study focuses on the information provided by the suicidality items (as detailed in the Appendix). The subsequent part of this study uses the information provided by the 20 mandatory screening items. The current month suicide attempt was chosen as the outcome. Sixteen conditions were defined on the basis of the four remaining suicidality items, and the outcome frequency was computed in each condition. Then, the conditions were ordered on the basis of their frequencies. Given the low prevalence of this outcome, conditions of small sample sizes and similar outcome frequencies were aggregated.

In order to identify moderating additional characteristics, a two-step procedure was implemented. Firstly, the 20 screening items that exhibited an odds ratio higher than 2 were retained as potential moderator-an odds ratio strictly higher than one indicates that the outcome frequency when the characteristic is present is higher than the outcome frequency when the characteristic is absent. Secondly, the outcome frequency in each risk level of resulting suicidality scale was conditioned to the presence/absence of the selected characteristic, in order to detect its potential moderator role. The difference between the resulting frequencies was normalized by using [START_REF] Cohen | Statistical Power Analysis for the Behavioral Sciencesitle[END_REF] h index of effect size. If the presence versus the absence of an additional characteristic changes the outcome frequency systematically, at least with a moderate effect size, this characteristic is considered as relevant.

Results

Overall, the ordering of the suicidality conditions suggested a three-level risk scale with respective frequencies of 44%, 20% and 0.02% of current month suicide attempt. Concerning the 20 additional characteristics (screening items), the data analysis revealed that excessive worry and chronic anxiety, a symptom of generalized anxiety disorder (GAD), is the unique risk factor that systematically moderates the outcome frequency.

Suicidality Items: Risk Scale

A total of 213 respondents reported a current month suicide attempt (0.68% of the total sample, which corresponds to 8.2% of annual suicide attempt rate). Respondents' age ranged between 18 and 68 years (M = 37, SD = 16.2). Fifty four percent of attempters were female.

Table 1 displays the ordered conditions formed with the four suicidality items. Two conditions with the highest frequencies, more than 40%, were aggregated in the high risk level (henceforth R 1 ). Likewise, three conditions presenting frequencies between 10% and 40% were aggregated in the moderate risk level (henceforth R 2 ), and the remaining 11 conditions with less than 10% were grouped in the low risk (henceforth R 3 ). The specific feature of the high risk condition (R 1 ) was the co-occurrence of self-harm desire (C 2 ), suicidal ideation (C 3 ), and lifetime suicide attempt (C 5 ). In the same way, co-occurrence of lifetime suicide attempt (C 5 ), with either self-injury (C 2 ) or suicidal ideation (C 3 ), but not both, specifies moderate risk (R 2 ).

Figure 1 displays the resulting suicidality scale.

Selection of Additional Characteristics

Table 2 shows the 18 additional characteristics with odds ratios higher than 2. Odds ratios ranged between 2.4 and 15.6. Items comprised three depression items, one dysthymia, two maniac episodes in bipolar disorder, two agoraphobia and panic attack, one generalized anxiety, one Post Traumatic Stress Disorder (PTSD), one drug abuse, and seven current psychotic episode items.

Evaluation of the Moderator Role of Additional Characteristics

Given the presence versus the absence of each additional characteristic, each of the three suicidality conditions (R 1 , R 2 , R 3 ) was divided into two sub-conditions. Table 3 displays the observed effect sizes. According to [START_REF] Cohen | Statistical Power Analysis for the Behavioral Sciencesitle[END_REF], effect sizes below 0.20, between 0.20 and 0.80, and over 0.80 are considered as small, moderate and large, respectively. Fifty three out of 54 h indexes fell in the small or moderate ranges and 39 were positive.

The item concerning excessive worry and chronic anxiety, a symptom of GAD, exhibited the highest effect sizes in all conditions (see Figure 2). In other words, the outcome frequencies are systematically changeable according to positive or negative response to the GAD item. In the R 1 condition, the outcome frequency switches from 4% to 46% when one considers the absence or the presence of chronic anxiety. In the R 2 and R 3 conditions, it increases from 3% to 19%, and from 0.01% to 3%, respectively.

Discussion

The literature on suicidality presents a long list of risk factors including socio-economic risk factors, proximal psychopathological risk factors in adults and adolescents, as well as distal risk factors, stressful life events and biological risk factors (for a review see [START_REF] Nock | Suicide and suicidal behavior[END_REF]. The risk levels obtained from taking into account each risk factor separately are not as high as those found by a multi-characteristic approach. Using a single-characteristic approach, [START_REF] Zahl | Repetition of deliberate self-harm and subsequent suicide risk: longterm follow-up study of 11,583 patients[END_REF] found 6.9% of suicide in a sample of 11,583, repeated deliberate selfharmers. [START_REF] Nock | Mental disorders, comorbidity and suicidal behavior: results from the National Comorbidity Survey Replication[END_REF] reported 15.4% of suicide attempts in a sample of 5,962 cases characterized by the presence of any mood disorder in the National Comorbidity Survey replication. The present study shows that 46.4% of individuals in a compound condition-defined by the co-occurrence of suicidal ideation, deliberate self-harm wish, life time suicide attempt, and chronic anxiety-reported a suicide attempt in the current month. This finding highlights the interest of a multi-characteristic approach for identifying high risk conditions. In the same vein, according to [START_REF] Baca-Garcia | Estimating risk for suicide attempt: are we asking the right questions? Passive suicidal ideation as a marker for suicidal behavior[END_REF] in the National Epidemiologic Survey of Alcohol and Related Conditions (NESARC) database, N = 43,093, 30% of 3,077participants characterized by the co-occurrence of desire for death and suicidal ideation reported a suicidal attempt. While the suicide attempt frequency is only 6% within the 542 suicidal ideators without the desire for death. To the best of our knowledge, no previous study on suicidality reports risk conditions as high as 46.4%.

This study, along with previous literature, shows that patients' chronic anxiety is a characteristic to take into account for suicidality assessment. Numerous authors [START_REF] Borges | A risk index for 12-month suicide attempts in the National Comorbidity Survey Replication (NCS-R)[END_REF][START_REF] Fawcett | Treating impulsivity and anxiety in the suicidal patient[END_REF][START_REF] Nock | Prevalence, correlates, and treatment of lifetime suicidal behavior among adolescents: results from the national comorbidity survey replication adolescent supplement[END_REF] consider agitation and poor behavioral control as forms of chronic anxiety, and report them to be the correlates of a suicide attempt among suicidal ideators. These finding are consistent with the detection of chronic anxiety as a characteristic relevant to suicidality in the present study. Future large sample surveys interested in suicidality should include questions concerning chronic anxiety and examine its role in suicide attempts along with the other risk factors.

The risk scale obtained in the present study should be considered taking into account a main limitation. The risk scale cannot be used to estimate the probability that someone will attempt suicide. Even if the criterion had been, for example, suicide attempt after the characterization of individual's condition, the resulting frequencies cannot be individual probabilities (or propensities). To our knowledge, such propensities are not measurable (although one can try to estimate them in the context of therapeutical or prevention decision making).

The current research contributes to clarify terms such as risk, risk factor, and risk scale, and demonstrates a simple methodology of data analysis to establish risk scales on the basis of available evidence in large data samples. Such an approach complements the traditional approach to risk assessment based on expert consensus. Further research could try to discover new characteristics to be added to five aforementioned items, in order to enhance or decrease the outcome frequency. Note. (C 1 ) positive response to the item concerning wish to be dead, (C 2 ) positive response to the item concerning intention towards harm hurt or to injure oneself, (C 3 ) positive response to the item concerning suicidal ideation,(C 5 ) positive response to the item concerning lifetime suicide attempt,(C )negative response to the item, (R1) high risk condition,(R2) moderate risk condition,( R3) low risk condition. Note. h index is negative if the outcome frequency is higher in the negative answer condition.

  and Sheehan et al. (1998) reported a high inter-rater agreement between the diagnosis proposed by MINI and the clinical diagnosis based on the fourth version of Diagnostic and Statistical Manual of Mental Disorders (DSM-IV) or the tenth version of International Statistical Classification of Diseases (ICD-10).

Figure 2 .

 2 Figure 2. Percentage of current month suicide attempt in the presence and in the absence of chronic anxiety with 95% confidence intervals

Table 1

 1 Ordered suicidality conditions and high (R 1 ), moderate (R 2 ), and low (R 3 ) risk aggregated conditions

	Condition	Number of outcome	Sample size of the	Proportion	95% confidence
			condition		interval
	(C 1 ,C 2 ,C 3 ,C 5 )	15	33	0.455	[0.285, 0.634]
	(C 1 ,C 2 ,C 3 ,C 5 )	100	227	0.441	[0.375, 0.508]
	(C 1 ,C 2 ,C 3 ,C 5 )	36	152	0.237	[0.173, 0.314]
	(C 1 ,C 2 , C 3 ,C 5 )	4	25	0.160	[0.053, 0.369]
	(C 1 ,C 2 ,C 3 ,C 5 )	6	51	0.118	[0.049, 0.246]
	(C 1 ,C 2 ,C 3 ,C 5 )	8	141	0.057	[0.027, 0.112]
	(C 1 ,C 2 ,C 3 ,C 5 )	2	39	0.051	[0.009, 0.186]
	(C 1 ,C 2 ,C 3 ,C 5 )	1	33	0.030	[0.002, 0.175]
	(C 1 ,C 2 ,C 3 ,C 5 )	4	170	0.024	[0.008, 0.063]
	(C 1 ,C 2 ,C 3 ,C 5 )	25	1,785	0.013	[0.008, 0.019]
	(C 1 ,C 2 ,C 3 ,C 5 )	4	357	0.011	[0.004, 0.030]
	(C 1 ,C 2 ,C 3 ,C 5 )	1	113	0.009	[0.001, 0.055]
	(C 1 ,C 2 ,C 3 ,C 5 )	1	136	0.007	[0.001, 0.046]
	(C 1 ,C 2 ,C 3 ,C 5 )	1	929	0.001	[0.001, 0.012]
	(C 1 ,C 2 ,C 3 ,C 5 )	5	26,785	0.0001	[0.000, 0.001]
	(C 1 ,C 2 ,C 3 ,C 5 )	0	48	0.000	[0.000, 0.092]
	R 1	115	260	0.442	[0.503, 0.382]
	R 2	46	228	0.202	[0.254, 0.150]
	R 3	52	30,536	0.002	[0.002, 0.001]

Table 3 h

 3 index of the difference between current month suicide attempt percentages given positive or negative answer to the selected screening items

	Item	h (% suicide attempt in ‗item = no' condition, % suicide attempt		h index
			in ‗item = yes' condition)
		R1	R2	R3	Min	Max	Average
	Generalized Anxiety	1.08 (4.3, 46.4)	0.7 (2.9, 18.8)	0.32 (0.0, 3.0)	0.70	1.08	0.32
	Psychotic Disorder 2	0.17 (41.2, 49.5)	0.34 (15.6, 29.7)	0.07 (0.1, 0.5)	0.19	0.34	0.07
	Depression 2	0.26 (35.7, 48.3)	0.03 (19.6, 20.6)	0.12 (0.1, 0.8)	0.13	0.26	0.03
	Psychotic Disorder 6	0.05 (43.6, 46.2)	0.27 (17.8, 29.2)	0.07 (0.1, 0.5)	0.13	0.27	0.05
	Panic Disorder	0.29 (38.1, 52.2)	-0.1 (21.7, 17.6)	0.11 (0.1, 0.8)	0.10	0.29	-0.1
	Maniac Episode 1	0.08 (42.5, 46.5)	0.16 (18, 24.4)	0.06 (0.1, 0.4)	0.10	0.16	0.06
	Depression 1	-0.03 (45.5, 43.8)	0.24 (14.1, 23.3)	0.07 (0.1, 0.5)	0.09	0.24	-0.03
	Psychotic Disorder 3	-0.11 (45.6, 40)	0.27 (17.7, 28.8)	0.08 (0.1, 0.6)	0.08	0.27	-0.11
	Psychotic Disorder 4	0.05 (43.6, 46.2)	0.12 (19.4, 24.3)	0.04 (0.2, 0.4)	0.07	0.12	0.04
	Psychotic Disorder 1	0.12 (42.4, 48.2)	-0.02 (20.1, 19.2)	0.04 (0.1, 0.3)	0.05	0.12	-0.02
	Drug Abuse	-0.02 (44.6, 43.5)	0.09 (19.3, 22.8)	0.02 (0.2, 0.2)	0.03	0.09	-0.02
	Psychotic Disorder 7	-0.07 (44.7, 41.5)	0.03 (19.6, 20.9)	0.11 (0.1, 0.9)	0.03	0.11	-0.07
	Maniac Episode 2	0.09 (41.7, 46)	-0.06 (21.2, 18.7)	0.05 (0.1, 0.4)	0.03	0.09	-0.06
	Depression 3	-0.04 (45.6, 43.5)	-0.01 (20.4, 20)	0.07 (0.1, 0.4)	0.01	0.07	-0.04
	Psychotic Disorder 5	0.26 (43.4, 56.3)	-0.37 (21.5, 8.7)	0.11 (0.1, 0.8)	0.00	0.26	-0.37
	PTSD	0.05 (43, 45.3)	-0.12 (22.5, 17.6)	0.04 (0.1, 0.3)	-0.01	0.05	-0.12
	Agoraphobia	-0.12 (47.2, 41.5)	-0.09 (21.7, 18.2)	0.04 (0.1, 0.3)	-0.06	0.04	-0.12
	Dysthymia	-0.25 (50.9, 38.5)	-0.14 (21.3, 15.8)	0.07 (0.1, 0.4)	-0.11	0.07	-0.25

La Santé Mentale en Population Générale (Mental Health in General Population).

 If all of the items are answered no, then ‗no risk'.

Twenty four out of 32 possible response profiles fulfill more than one risk level. For example, the profile 11101, which means that all items except for C 4 were answered ‗yes', corresponds to the high level, as items C 3 and C 5 are responded ‗yes', and to the low risk level, as items C 1 or C 2 or C 3 are responded ‗yes'. Thus, a meta-rule is needed to choose the unique risk level. This rule could be -if the profile has several risk levels, then choose the highest‖.