Celine Vens
email: celine.vens@cs.kuleuven.be

Marie-No Ëlle Rosso

Etienne G J Danchin

Identifying Discriminative Classification Based Motifs in Biological Sequences

Motivation: Identification of conserved motifs in biological sequences is crucial to unveil common shared functions. Many tools exist for motif identification, including some that allow degenerate positions with multiple possible nucleotides or amino acids. Most efficient methods available today search conserved motifs in a set of sequences, but do not check for their specificity regarding to a set of negative sequences. Results: We present a tool to identify degenerate motifs, based on a given classification of amino acids according to their physicochemical properties. It returns the top K motifs that are most frequent in a positive set of sequences involved in a biological process of interest, and absent from a negative set. Thus, our method discovers discriminative motifs in biological sequences that may be used to identify new sequences involved in the same process. We used this tool to identify candidate effector proteins secreted into plant tissues by the root knot nematode Meloidogyne incognita. Our tool identified a series of motifs specifically present in a positive set of known effectors while totally absent from a negative set of evolutionarily conserved housekeeping proteins. Scanning the proteome of M. incognita, we detected 2,579 proteins that contain these specific motifs and can be considered as new putative effectors.

INTRODUCTION

Conserved motifs in biological sequences reflect functionally important shared features. In genome sequences, conserved motifs can point to promoters or regulatory elements, regions of splice junctions between protein-coding exons or regions affecting the shape of the chromatin. In protein sequences, such conserved motifs can highlight signals that are important for controlling the cellular localization (e.g. nucleus, cytoplasm, extracellular compartment), regions shared between proteins that interact with a same partner or regions important for the biochemical function itself. * to whom correspondence should be addressed Physico-chemical properties and three-dimensional structures of proteins are more conserved than the suite of amino-acids itself. Thus, at a given position in a protein sequence, different amino-acids may have similar structural or physico-chemical roles. Degenerate motifs allowing multiple possible amino-acids at one position are necessary to comply with this variability. Several methods allow for discovery of degenerate motifs [START_REF] Bailey | Fitting a mixture model by expectation maximization to discover motifs in biopolymers[END_REF][START_REF] Ji | An efficient technique for mining approximately frequent substring patterns[END_REF], but few of them take into account similarity in terms of physico-chemical properties of amino acids at a given position [START_REF] Jonassen | Efficient discovery of conserved patterns using a pattern graph[END_REF][START_REF] Rigoutsos | Combinatorial pattern discovery in biological sequences: the TEIRESIAS algorithm[END_REF].

When the purpose of the obtained motifs is to scan large datasets (e.g. genomes, proteomes) in order to find new sequences potentially involved in the same biological process, another relevant point in the motif discovery is the specificity of the identified motifs regarding the biological process. Some systems make use of statistics to attach a measure of significance to each of the discovered patterns, as deduced from a model based on the input sequences or a public sequence database [START_REF] Bailey | Fitting a mixture model by expectation maximization to discover motifs in biopolymers[END_REF][START_REF] Jonassen | Efficient discovery of conserved patterns using a pattern graph[END_REF][START_REF] Rigoutsos | Combinatorial pattern discovery in biological sequences: the TEIRESIAS algorithm[END_REF]. For many biological applications, however, a negative set of sequences not involved in the process of interest can be compiled, and this set can be used as a more direct way to evaluate the relevance of the motifs. While several motif discovery processes take into consideration a negative sequence set [START_REF] Redhead | Discriminative motif discovery in DNA and protein sequences using the DEME algorithm[END_REF][START_REF] Bailey | The value of positionspecic priors in motif discovery using MEME[END_REF], this set is often used to guide the search towards motifs over-represented in the positive sequences, rather than discriminating motifs.

In this article, we propose a method that identifies motifs consisting of specific amino acids and physico-chemical properties, that can be used as discriminators to identify new sequences involved in a biological process of interest. To our knowledge, no motif discovery method exists that combines these two features. Our method outputs the top K motifs that are most frequent in a positive set of proteins and are absent from a negative set of proteins.

We applied this method to find motifs in root-knot nematode effectors. Root-knot nematodes are the most damaging plantparasitic animals to the agriculture worldwide, causing billions of euro losses every year [START_REF] Agrios | Plant pathology[END_REF]. They have sophisticated interactions with plants that include penetration of root tissue and establishment of a feeding site. A set of effector proteins that are secreted by the nematode into plant tissue is believed to be crucial for these processes. Most known effectors to date are expressed in Table 1. [START_REF] Koolman | Colour Atlas of Biochemistry[END_REF] nematode secretory glands and delivered to plant tissue through a syringe-like stylet. With the availability of two annotated genome sequences for root knot nematodes [START_REF] Abad | Genome sequence of the metazoan plant-parasitic nematode Meloidogyne incognita[END_REF][START_REF] Opperman | Sequence and genetic map of Meloidogyne hapla: A compact nematode genome for plant parasitism[END_REF], identifying the whole set of candidate secreted effectors can now be envisioned. Although many effectors possess a signal peptide for secretion, others clearly present in secretory glands and/or nematode secretions have no predicted signal peptide [START_REF] Bellafiore | Direct identification of the Meloidogyne incognita secretome reveals proteins with host cell reprogramming potential[END_REF][START_REF] Jaubert | A polygalacturonase of animal origin isolated from the root-knot nematode Meloidogyne incognita[END_REF]. Similarly, many rootknot nematode proteins bearing a signal peptide are not delivered to the plant but have conserved functions in different species. Hence, the presence of a signal peptide can not be used as a discriminator to identify new effectors, and no reliable motif to predict secretion of a nematode protein in plants is currently available. We constructed a positive set of proteins known to be secreted by root-knot nematodes into plant tissue and a negative set of evolutionarily conserved proteins, in order to identify specific motifs in positive proteins. Using these datasets, our method identified a set of effector-specific motifs at the N-terminal region of the positive proteins.

METHODS

Classification schemes

Several amino acid classifications group amino acids according to their physico-chemical properties. In this work, we consider two classification schemes. The first one was proposed by [START_REF] Koolman | Colour Atlas of Biochemistry[END_REF]. It contains 7 non-overlapping properties, see Table 1. The second one is RasMol's classification [START_REF] Sayle | RasMol: Biomolecular graphics for all[END_REF], which is much larger, see Table 2. It contains 15 classes1 , with a lot of overlap. We can view the classification schemes as directed acyclic graphs (DAGs) representing the superclass relationship. In its simplest way, the DAG contains two levels: the classes and the amino acids. However, a closer look at the latter classification scheme can introduce more structure and levels. For instance, all basic amino acids are charged and large, and all charged amino acids are polar and surface.

Formal Task Description

We define the task of identifying the top K discriminative protein motifs with amino acid properties as follows:

Given: (1) a set of positive proteins P and a set of negative proteins N , (2) a parameter K, and (3) a set of amino acid properties C and a partial order (structured as a DAG) defined on the union of C and the amino acid alphabet A. For all c 1 , c 2 ∈ C ∪ A: c 1 c 2 if and only if there is a directed path from c 1 to c 2 in the DAG. [START_REF] Sayle | RasMol: Biomolecular graphics for all[END_REF].

Property

Amino acids

acidic D,E acyclic A,R,N,D,C,E,Q,G,I,L,K,M,S,T,V aliphatic A,G,I,L,V aromatic H,F,W,Y basic R,H,K buried A,C,I,L,M,F,W,V charged D,E,R,H,K cyclic H,F,P,W,Y hydrophobic A,G,I,L,M,F,P,W,Y,V large R,E,Q,H,I,L,K,M,F,W,Y medium N,D,C,P,T,V neutral A,N,C,Q,G,I,L,M,F,P,S,T,W,Y,V polar R,N,D,C,E,Q,H,K,S,T small A,G,S surface R,N,D,E,Q,G,H,K,P,S,T,Y
Find: the set of K motifs, using symbols in C ∪ A, that are maximally frequent in P and are absent from (or infrequent in, see Section 2.3.2) N .

Algorithm

The algorithm we propose is based on the well-known candidate generation principle, introduced in sequential pattern mining by the AprioriAll algorithm [START_REF] Agrawal | Mining sequential patterns[END_REF]. At each iteration, a set of candidate patterns is generated, whose frequency is tested. In order to search for discriminative patterns, we change the basic algorithm, such that it essentially looks for those patterns that are frequent in the positive sequences, and meanwhile tests if they are absent from the negative sequences. In order to include physico-chemical properties of the amino acid residues, we extend the candidate generation step. In the next sections, we describe the different steps of the algorithm.

Candidate generation.

In order to perform a complete and efficient search, it is important that each relevant candidate is generated, and that no candidate is generated more than once. To achieve this, most candidate generation algorithms structure the search space as a lattice representing a general-to-specific structure. Generating candidates then comes down to traversing the lattice, thereby pruning as much as possible.

We follow the same approach and consider a pattern <p 1 , p 2 , p 3 , ..., pn> more general than another pattern <q 1 , q 2 , q 3 , ..., qm>, if and only if n ≤ m and for each pair (p i , q i ) it holds that p i q i . Our candidate generation method traverses the lattice from general to specific, which is done by starting with an artificial root element that denotes the empty pattern, and at each step performing two basic operations to generate minimally specialized new candidates given a pattern: (1) add a top-level element of the DAG (extension), and (2) minimally specialize an element of the pattern (specialization).

In order to ensure that no pattern is considered more than once, we only add elements to the end of the pattern, and only specialize the last element in the pattern. We transform the DAG into a tree in a preprocessing step, such that only one path leads to each amino acid. This is trivially fulfilled for the Koolman and Rohm classification. A possible spanning tree for the hierarchy by Sayle and Milner-White is shown in Fig. 1. The specialization operator is performed by replacing the last element in the pattern by each of its children in this tree. The candidate generation process is illustrated in Figure 2. [START_REF] Sayle | RasMol: Biomolecular graphics for all[END_REF] and the spanning tree of Fig. 1.

Finding the top K motifs.

We introduce two parameters, F P and F N , which denote the minimal frequency threshold for the positive sequences, and the maximal frequency threshold for the negative sequences, respectively. By default, F N is set to zero, and motifs are searched that are absent from the negative set. However, since for some applications, constructing a pure negative set can be difficult, setting F N to a higher value can be useful. The parameter F P defines the threshold above which motifs are retained. Initially it is set to one or to a user defined value, and it increases throughout the execution of the algorithm:

• Initially, after finding K motifs, F P is updated to the minimum of the frequencies of those K motifs in the positive sequences.

• In later stages, if a valid motif is found, it is inserted into the current list of motifs, which is sorted according to their frequency in the positive sequences. If the first K motifs have a frequency higher than F P , then F P is updated to the minimum of these K frequencies.

It is possible that more than K motifs have a frequency above F P at the end.

In this case, one can either randomly pick motifs with frequency F P until K motifs are obtained, or one can output all of them. We opted for the latter approach, so that the user has maximal control over the output.

Candidate pruning and testing.

In order to conduct the search efficiently, the algorithm exploits the anti-monotonicity properties of the frequency constraints. This results in the following rules (f req(X, Y ) returns the number of proteins in set Y that contain the motif X):

• If a pattern M has f req(M, P ) ≤ F P , then we should not consider new candidates C that are more specific than M , since they will have f req(C, P ) ≤ F P , and thus can be discarded.

• If a pattern M has f req(M, N ) ≤ F N , then all new candidates C that are more specific than M will have f req(C, N ) ≤ F N , hence we do not need to count their frequency in the negative set.

When checking a candidate's frequency in the positive set, we make the following two observations. First, we only have to check the frequency of a candidate in case all the candidate's parents in the lattice have passed the minimal frequency threshold F P . Second, it is not necessary to check the complete set of positive sequences, it suffices to check the sequences in which the parents are present. Therefore, we adopt a vertical id-list dataset format [START_REF] Zaki | Efficient enumeration of frequent sequences[END_REF], where we associate to each pattern a list of (positive) sequence IDs in which it occurs. Before testing the frequency of a candidate, we check whether its parents are frequent, and if yes, intersect their sequence ID lists. Only the sequences in the intersection are checked for presence of the pattern. If the pattern passes the minimal frequency constraint, we store it together with the sequences in which it occurs.

When a candidate has been found frequent in the positive set, we test its frequency in the negative set. As mentioned above, if a candidate's parent was infrequent in the negative set, we can output this candidate as a valid motif without any testing. In the other case, we iterate over the negatives, counting hits, and stop searching if the maximal frequency F N is reached. Note that, if the maximal frequency condition is not met, we still have to keep the candidate for further processing, because the maximal frequency condition can become true for any of the new candidates generated from it.

Organization of the search.

The search space lattice can be traversed using several search strategies, a.o. depth-first and breadth-first search. We opt for the former, since it requires less main memory: it only needs to keep sequence id lists for candidates along a single path2 . This implies that pruning (checking whether the parents are frequent and intersecting their sequence id lists) can not be performed using all parents of a candidate. Therefore, we perform pruning only using the minimal generalizations of the last element of the pattern as parents (removing the last element if it corresponds to the highest level in the DAG).

In order to perform pruning correctly, we have to make sure that all considered parents have been tested before a pattern is tested, i.e. the spanning tree of the amino acids and their properties has to be constructed in a way that, in depth-first traversal, all DAG parents of a node are visited before the node itself. The tree shown in Figure 1 fulfills this constraint.

Implementation.

We provide a Perl implementation of the proposed algorithm, called MERCI (Motif -EmeRging and with Classes -Identification), at http://dtai.cs.kuleuven.be/ml/systems/merci. Pseudo code is given in Supplementary Table S1. Counting frequencies is done by Perl's pattern matching operator, using regular expressions to represent classes. The implementation provides the following additional features:

• The user is not restricted to use one of the classifications discussed here, but can define his own classification scheme of amino acid properties.

• There is an option to find gapped motifs. The algorithm is easily extended to include gaps by splitting the extension operator into two basic operations: (1) add a top-level candidate to the end of the pattern, and (2) add a gap followed by a top-level candidate to the end of the pattern. The program supports gaps of variable length, i.e., the user provides a maximal gap length L, and a gap symbol then denotes any number of amino acids between 0 and L. The maximal number of gap symbols is also set by the user.

• The program includes a searching tool, which can be used to locate the discovered motifs' occurrences in any set of sequences.

M. incognita dataset

We first describe how the positive and negative protein sets were constructed. Statistics about the resulting sets are given in Table 3. Then we explain how the resulting motifs are evaluated.

Positive set.

We constructed a positive set with proteins that are known to be secreted or likely to be secreted by the nematode into plant root tissue [START_REF] Bellafiore | Direct identification of the Meloidogyne incognita secretome reveals proteins with host cell reprogramming potential[END_REF][START_REF] Ding | Molecular cloning and characterisation of a venom allergen AG5-like cDNA from Meloidogyne incognita[END_REF][START_REF] Dubreuil | Transcriptome analysis of root-knot nematode functions induced in the early stages of parasitism[END_REF][START_REF] Huang | A profile of putative parasitism genes expressed in the esophageal gland cells of the root-knot nematode M. incognita[END_REF][START_REF] Wang | Molecular cloning and analysis of a new venom allergen-like protein gene from the root-knot nematode Meloidogyne incognita[END_REF] expression in subventral and/or dorsal secretory glands has been shown, 38 proteins that have been identified in the secretome of root-knot nematodes, and 3 translated EST contigs identified by mass-spectrometry in nematode secretions. The resulting 100 sequences were scanned with SignalP 3.0 [START_REF] Emanuelsson | Locating proteins in the cell using TargetP, SignalP and related tools[END_REF] for presence of a potential signal peptide. The criterion used was detection of a signal peptide with either one of the two methods (artificial neural networks or hidden Markov models) integrated in SignalP. In total, 57 sequences have a predicted signal peptide.

Negative set.

As negative set, we used a series of proteins encoded by single-copy genes widely conserved throughout evolution. Such proteins are very unlikely to be secreted by plant-parasitic nematodes in plants as they are highly conserved in non-parasitic species. To identify these proteins we ran an all versus all comparison of 7 proteomes (Meloidogyne incognita, Meloidogyne hapla, Brugia malayi, Pristionchus pacificus, Caenorhabditis elegans, Caenorhabditis briggsae, and Drosophila melanogaster) using OrthoMCL [START_REF] Li | OrthoMCL: identification of ortholog groups for eukaryotic genomes[END_REF]. We identified 459 groups of conserved proteins present as a single copy in all of the seven different proteomes. We retrieved the corresponding proteins in M. incognita and checked for the presence of a signal peptide using SignalP. We found that 43 out of these 459 proteins bear a predicted signal peptide.

Presence of proteins with a signal peptide in the negative set avoids biasing for motifs indicating the presence of a signal peptide.

Evaluating motifs.

The identified motifs were scanned against the proteome of M. incognita [START_REF] Abad | Genome sequence of the metazoan plant-parasitic nematode Meloidogyne incognita[END_REF], consisting of 20,359 proteins. Moreover, the genome of M. incognita is known to encode a repertoire of plant cell wall-degrading proteins. Among these proteins, Cellulases [START_REF] Béra-Maillet | Biochemical characterization of MI-ENG1, a family 5 endoglucanase secreted by the root-knot nematode Meloidogyne incognita[END_REF][START_REF] Ledger | Characterization of a new beta-1,4-endoglucanase gene from the root-knot nematode Meloidogyne incognita and evolutionary scheme for phytonematode family 5 glycosyl hydrolases[END_REF][START_REF] Rosso | Isolation of a cDNA encoding a beta-1,4endoglucanase in the root-knot nematode Meloidogyne incognita and expression analysis during plant parasitism[END_REF], Xylanases [START_REF] Mitreva-Dautova | A symbiont-independent endo-1,4beta-xylanase from the plant-parasitic nematode Meloidogyne incognita[END_REF], Polygalacturonases [START_REF] Jaubert | A polygalacturonase of animal origin isolated from the root-knot nematode Meloidogyne incognita[END_REF], and Pectate lyases [START_REF] Huang | Developmental expression and molecular analysis of two Meloidogyne incognita pectate lyase genes[END_REF] have been shown to be expressed in M. incognita secretory glands. A total of 16 full length proteins bearing a signal peptide and corresponding to these cell wall-degrading enzymes were identified from the genome annotation and from the literature. Half of them were initially included in the positive set, the rest can be used as a positive control.

DISCUSSION

Finding proteins secreted into plant tissues by M. incognita

Using the datasets described in Section 2.4, we have identified motifs that are specific to the positive proteins, i.e., we searched for motifs that are absent from the negative set by setting FN to zero3 . In a first set of experiments, we searched for the top 5 motifs, without considering physico-chemical properties. Disabling the use of gaps resulted in the motifs shown in Table 4 (top). We can make two observations from this result. First, the result contains more than 5 motifs, since there are multiple motifs with the cutoff frequency of 5 (see Section 2.3.2). Second, we notice several motifs that are very similar. More precisely, motif <TLLIIS> is present together with its two parent motifs <TLLII> and <LLIIS>, the latter being the most frequent motif in the result. Many pattern discovery algorithms restrict their output to a set of closed patterns, i.e, patterns that do not have any specializations with the same frequency, and would thus discard <TLLII>. Instead, in this work we output the complete set of top K motifs. The reason is that our motifs can be used as discriminators to identify unknown positive sequences. Depending on the application, one might be more interested in maximizing precision (the proportion of positive predictions that are correct), in which case one would prefer to use the most specific motifs, or in maximizing recall (also called sensitivity, the proportion of positive sequences that are correctly predicted), in which case one would use the most general motifs.

When enabling the use of a gap position (see Table 4, middle), with a maximal gap length of 5, we see that the <LLIIS> motif, which was the most frequent pattern in the previous experiment, can be extended to the left and to the right without decreasing the frequency. Note that the FP threshold has changed from 5 to 7.

In a second set of experiments, we allowed physico-chemical properties in the motifs, starting with the simple [START_REF] Koolman | Colour Atlas of Biochemistry[END_REF] classification. Table 4 (lower part) shows the results, only the results without gaps are shown. Again, we see the <LLIIS> motif, this time together with a number of degenerate variants.

Closer inspection of the <LLIIS> motif and its variants showed that they always occur near the start of the protein sequences. This is consistent with most reported cases in the literature, which state that the signals that control compartment of destination of proteins are often positioned at their N-terminal region. Therefore, in the next experiment, we searched for motifs specifically in this region. We only considered the 30 first positions in this analysis, both for positive and negative sequences. As motifs controlling protein localization are usually short, we set a maximal motif length of 15, and disabled gaps. Without classification, the motif with the maximal frequency is <LIIS> (note the slight difference with the previous <LLIIS>), which occurs in 10 positive sequences. When using the more complex RasMol [START_REF] Sayle | RasMol: Biomolecular graphics for all[END_REF] classification, the maximal motif frequency obtained is 38 (see Table 5 for an example). When reporting the top 100 motifs, 97 motifs have a frequency of at least 35, with a total coverage of 68 positive proteins. Taking a closer look at the coverage, we observed several things. First, some sequences are covered by almost all motifs, meaning that there is a lot of overlap between the motifs. Second, we see that the identified motifs are preferentially found in positive proteins bearing a signal-peptide (SP). Since SPs are present in the negative set, and none of the negatives is covered, these motifs do not indicate the SP itself, but a pattern within the SP that is probably related to secretion in plants. We therefore focused our analysis on the subset of motifs that cover as many as possible of the 57 SP-bearing positive proteins, and none of the non-SP-bearing positives. This subset still contains 66 motifs, covering all but one of the SP-bearing positives. To reduce this number, we applied a heuristic set covering algorithm4 to find a small subset of motifs with the same coverage as the 66 motifs. This procedure resulted in a subset of 4 motifs, shown in Table 5. Scanning the complete proteome of M. incognita, we found that the 4 motifs cover 2,579 proteins (12% of the genome). A total of 2,073 of these proteins (80.3%) are predicted to have an SP, while only 17% (3,487 out of 20,359) of the M. incognita proteins have a predicted SP. Interestingly, if we only consider the proteins that are covered by at least 2 motifs, then 1106 out of 1162 (95%) have an SP. The 4 motifs cover 7 out of the 8 cell wall degrading proteins from the evaluation set. Additionally, using the OrthoMCL analysis performed to construct the set of negatives (see Section 2.4.2), we noticed that 1,817 of the 2,579 proteins are parasite specific, i.e., they do not have orthologs in C. elegans, C. briggsae, D. melanogaster, and P. pacificus. Given that the complete proteome contains 12,234 such proteins, the identification of this subset forms an important contribution to the pipeline of experiments necessary to identify the whole set of candidate effectors. It also introduces the open question of how these motifs in the signal peptide regulate secretion in plants.

Comment

Related Work

A large body of literature in the area of motif discovery exists. Here, we focus on systems that learn discriminative and/or degenerate motifs among biological or other sequences.

A lot of research has been carried out in frequent or discriminative substring mining. Most string mining approaches make use of sequences it covers, where each sequence is scored by the inverse of the number of motifs present in the sequence. This ensures that sequences that are covered by few motifs have a high score. In case of multiple motifs with the highest score, the one with the shortest length is taken. efficient data structures to represent the string data set [START_REF] Fischer | Optimal string mining under frequency constraints[END_REF][START_REF] Weese | Efficient string mining under constraints via the deferred frequency index[END_REF], and avoid the candidate generation approach. However, these techniques are limited to finding motifs defined over the same alphabet as the sequences. Some form of degenerate motifs can be obtained by searching for so-called approximate frequent motifs [START_REF] Ji | An efficient technique for mining approximately frequent substring patterns[END_REF][START_REF] Zhu | Efficient discovery of frequent approximate sequential patterns[END_REF], meaning that some mismatches are allowed when counting the frequency of a motif.

In the area of mining frequent sequential patterns, often used in marketing applications where patterns are searched in ordered lists of transactions, an algorithm is proposed that can integrate user-defined taxonomies in the patterns. GSP [START_REF] Srikant | Mining sequential patterns: Generalizations and performance improvements[END_REF] is a candidate generation algorithm, where candidates are generated by joining frequent sequences of the previous level, pruning away sequences that have a non-frequent subsequence. In order to incorporate taxonomies, each data sequence is replaced by an extended sequence, by adding all ancestor items to each transaction. It does not exploit the generalization structure inherent to the search space and does not find discriminative patterns.

Two other pattern discovery approaches allow the user to provide sets of amino acids, which are considered equivalent. However, they do not search for discriminative motifs. Teiresias [START_REF] Rigoutsos | Combinatorial pattern discovery in biological sequences: the TEIRESIAS algorithm[END_REF] uses a convolution technique to generate new motifs from two smaller motifs. It returns the set of closed patterns that are frequent in a (positive) set of sequences. The amino acid sets are introduced without any modification to the algorithm, i.e. no generalization relation is exploited. The Pratt algorithm [START_REF] Jonassen | Efficient discovery of conserved patterns using a pattern graph[END_REF] uses the concept of a pattern graph to guide the search, and uses a mix of specialization and generalization operators to generate candidates. In a first stage, it searches motifs consisting of specific amino acids, and in an optional refinement stage, these motifs are made more general by replacing amino acids by the amino acid sets. However, it can operate in an exhaustive manner as well.

Another set of related systems is based on probabilistic models. These systems return the discovered motifs as position-specific weight matrices, which specify a score for each residue/position pair. This results in degenerate motifs by enumerating possible alternative residues for each position, in contrast to describing possible alternatives, as in our approach. The enumeration does not take into account any classification. Example systems that find discriminative motifs are DEME [START_REF] Redhead | Discriminative motif discovery in DNA and protein sequences using the DEME algorithm[END_REF], which uses a combination of global and local search to find a single best motif, and the widely used MEME software [START_REF] Bailey | Fitting a mixture model by expectation maximization to discover motifs in biopolymers[END_REF], which uses an Expectation Maximization algorithm, and was recently extended to incorporate negative sequences as input [START_REF] Bailey | The value of positionspecic priors in motif discovery using MEME[END_REF]. However, these algorithms find motifs that are overrepresented in the positive and underrepresented in the negative set; it is not possible to require total absence from the negatives.

Finally, we mention two logic based methods. Warmr [START_REF] King | Warmr: a data mining tool for chemical data[END_REF] is an inductive logic programming system searching frequent patterns. It can take background knowledge as input, that could be used to represent the DAG. However, the system does not find discriminative patterns and, since it was not specifically designed for sequences, requires complex data formatting and language bias descriptions from the user. MineSeqlog [START_REF] Lee | Constraint based mining of first order sequences in SeqLog[END_REF]) is a system for mining discriminative logical sequences. It finds motifs by applying a frequent subsequence mining algorithm twice: once to find the set of most specific patterns that are frequent in the positive sequences, and once to find the most specific patterns that are frequent in the negative sequences. The resulting patterns are those that are more general than the former set and more specific than the latter set. The double application of the frequent pattern miner results in a less efficient approach.

Comparison

We have compared the output of MERCI to four methods from the related work section, that also output degenerate motifs. We applied each method to identify motifs corresponding as much as possible to a common set-up: we used the amino acid properties based on the [START_REF] Koolman | Colour Atlas of Biochemistry[END_REF] classification, allowed at most 1 gap of maximal length 2, required a minimal occurrence in the positives of 10% and absence from the negative set. We looked for the 10 best motifs with these constraints. Parameters that are not discussed were left to their default value. The systems MERCI, Pratt, and DEME were installed and run locally, thus we can also compare their running times (run on an Intel Q9400 2.66GHz processor).

MERCI.

Using MERCI with the above settings, we found 3 motifs, see Table 6. These are the only motifs (with a single gap) that occur in at least 10 positive sequences, and do not occur in any negatives, and hence can be used as a reference. The running time of MERCI was 119 seconds.

Teiresias.

As Teiresias can not take a negative set as input, we only used the positive sequences. The maximum gap length of 2 was simulated by setting parameters L = 2 and W = 4. We used the seq version, and applied equivalence based pattern discovery, with the equivalence sets based on the [START_REF] Koolman | Colour Atlas of Biochemistry[END_REF] classification. Even though Teiresias only reports closed patterns, the result set contains 328,135 motifs. Many of the reported motifs are overly general, e.g. <aliphatic x(1) x(1) aliphatic> (where x(1) denotes a fixed gap of one position), which occurs in all positive sequences, but also in all negative sequences. Calculating a significance score could not be performed within the execution time limit that comes with the web version of Teiresias. Surprisingly, the three motifs found by MERCI are not in Teiresias's output list.

The reason is that MERCI uses variable length gaps, while Teiresias does not. For instance, the second MERCI motif occurs 3 times with a gap length of 0, 5 times with a gap length of 1, and 2 times with a gap length of 2. Thus, Teiresias would need 3 motifs to represent this motif, and these motifs would have a frequency of 3, 5, and 2.

Pratt.

Pratt also has a single input set of proteins. We set the maximal gap length to 2 and allowed a single variable length gap. We required Pratt to perform exhaustive search, in order to maximize the output similarity to MERCI, which also performs an exhaustive search. Pratt scores patterns based on information content. We considered the 10 best patterns, and counted their frequency in the negative sequences. Only half of the patterns are absent from the negative sequences, they are shown in Table 7, and are very similar to the patterns found by MERCI. The reason why there are more patterns and they have a larger frequency is that Pratt also introduces fixed length gaps, e.g. x(2), and their number can not be restricted by the user. The running time required by Pratt was 2,566 seconds, which is more than 20 times slower than MERCI.

MEME.

The web version of the MEME software does allow to give a negative sequence set as input. However, in contrast to the previous systems, MEME does not allow the use of a specific classification scheme, nor does it use gaps. We used the zoops (zero or one per sequence) motif distribution, set the motif width between 2 and 50, and let MEME search for 10 motifs. In the result, 3 motifs have an e-value less than 1. The top scoring motif is very similar to our LLIIS-type motifs. The corresponding motif logo is shown in Figure 3. This motif was input to the corresponding motif occurrence locator program FIMO to search for occurrences in both positive and negative sequence sets. Using the default significance threshold, the motif was found in 32 positive sequences, but also in 36 negative sequences. We conclude that, while MEME allows negative sequences, it should not be used to search for discriminating motifs. In fact, MEME and MERCI have different target applications. While MERCI searches for motifs that can be used directly as a discriminator when classifying new sequences, MEME searches for motifs that describe a set of sequences. For instance, if the application is to find motifs shared by orthologous proteins, then it can help to include a negative set to guide the search towards significant motifs, while it is allowed that some negative sequences also contain the motif.

Comment

3.3.5 DEME. DEME reports a single motif, with a width given by the user. Again, gaps are not supported, and no classification scheme can be specified. We have searched for a motif of length 6, 8, and 10, respectively. The consensus sequences, together with their frequencies (as calculated by applying a threshold of 0.5 on the resulting probabilities, see [START_REF] Redhead | Discriminative motif discovery in DNA and protein sequences using the DEME algorithm[END_REF]) are given in Table 8. The running times required to obtain these motifs were 972, 1,032, and 1,069 seconds, respectively, resulting in a total running time that is 25 times as high as MERCI's running time. DEME finds motifs that are highly frequent in the positive set, and infrequent in the negative set, and therefore gives more useful results for our task than MEME. However, the motifs are still present in the negative sequences, and we believe the fixed motif width is an important drawback.

CONCLUSION

We propose an algorithm for the de-novo identification of protein motifs specific to a set of proteins. The motifs are not restricted to a sequence of specific amino acids, but can involve physico-chemical amino acid properties. The algorithm combines a variety of existing and new algorithmic contributions into a practical tool, that is freely available, and is able to include user defined amino acid properties. We provide additional software to scan sequence databases for the occurrence of the identified motifs. To our knowledge, no method is currently available to identify discriminative motifs that are degenerated according to a classification scheme.

Our tool was used to discover motifs specific to root-knot nematode proteins that are secreted into plant tissues. We showed that by allowing properties in the motifs, we are able to find motifs with a higher frequency in a positive set of proteins, while still being absent from a negative set. Using a set of 4 identified motifs as discriminators, we detected a total of 2,579 proteins in the proteome of M. incognita that can be considered as new putative effectors.

We have compared the motifs discovered by our tool to the result of four other tools that find degenerate motifs. We conclude that our tool is the only one that finds a set of motifs using predefined amino acid classes, that is completely absent from the negative set.

While we have focused on finding protein motifs, the tool can be used on any kind of sequence dataset, with any kind of research question for which a positive and negative set can be defined.

Fig. 1 .

 1 Fig. 1. Spanning tree for the classification of Sayle and Milner-White (1995).

[

Fig. 2 .

 2 Fig. 2. Candidate generation using the amino acid classification of Sayle and Milner-White (1995) and the spanning tree of Fig. 1.

  citer ce document : Vens, C., Rosso, M.-N., Danchin, E. (2011). Identifying discriminative classification-based motifs in biological sequences. Bioinformatics, 27 (9), 1231-1238. , DOI : 10.1093/bioinformatics/btr110 E Version définitive du manuscrit publié dans / Final version of the manuscript published in : Bioinformatics, 2011, vol.27, no.9, DOI: 10.1093/bioinformatics/btr110 Manuscrit d'auteur / Author manuscript Manuscrit d'auteur / Author manuscript Manuscrit d'auteur / Author manuscript Identifying Discriminative Classification Based Motifs Table 4. Motifs found in the secreted proteins. The symbol x(M, N ) denotes a gap of minimal length M and maximal length N . The last column denotes the frequency of the motifs in the positive proteins. I S aliphatic aliphatic> 9 and Rohm <L L aliphatic I neutral aliphatic aliphatic> 9 (no gaps) <L I I S aliphatic aliphatic> 8 <L L I I S> 8 <L aliphatic I I S> 8

Fig. 3 .

 3 Fig. 3. Top motif found by MEME.

  amino acid classification.

	Property	Amino acids	Property Amino acids
	aliphatic	A,G,I,L,V	neutral	S,T,N,Q
	sulfur containing C,M	acidic	D,E
	aromatic	F,Y,W	basic	R,H,K
	cyclic	P

Table 2 .

 2 RasMol's classification of amino acids

Table 3 .

 3 . The data consists of 59 proteins whose Version définitive du manuscrit publié dans / Final version of the manuscript published in :Bioinformatics, 2011, vol.27, no.9, DOI: 10.1093/bioinformatics/btr110 M. incognita protein set statistics.

		Vens et al
	Manuscrit d'auteur / Author manuscript	Positive set Negative set 100 459 Shortest/longest sequence length (residues) 43/902 Number of sequences 57/2106 Average sequence length (residues) 270.3 438.8 Sequences with signal peptide 57 43
	Manuscrit d'auteur / Author manuscript
	Manuscrit d'auteur / Author manuscript

Comment citer ce document : Vens, C., Rosso, M.-N., Danchin, E. (2011). Identifying discriminative classification-based motifs in biological sequences. Bioinformatics, 27 (9), 1231-1238. , DOI : 10.1093/bioinformatics/btr110 E

Table 5 .

 5 Comment citer ce document : Vens, C., Rosso, M.-N., Danchin, E. (2011). Identifying discriminative classification-based motifs in biological sequences. Bioinformatics, 27 (9), 1231-1238. , DOI : 10.1093/bioinformatics/btr110EVersion définitive du manuscrit publié dans / Final version of the manuscript published in :Bioinformatics, 2011, vol.27, no.9, DOI: 10.1093/bioinformatics/btr110 Motifs at N-terminal using RasMol's classification. The last column denotes the frequency of the motifs in the positive proteins.

		Vens et al
	Manuscrit d'auteur / Author manuscript	Motif
	Manuscrit d'auteur / Author manuscript
	Manuscrit d'auteur / Author manuscript

Table 6 .

 6 Motifs found using MERCI.

	Motif	freq(Motif,P)
	<L L aliph I S x(0,2) aliph aliph>	10
	<L L aliph aliph neutral aliph x(0,2) A>	10
	<L aliph aliph aliph neutral L x(0,2) aliph aliph>	10

Table 7 .

 7 Motifs found using Pratt.

	Motif	freq(Motif,P)
	<L L aliph aliph neutr aliph aliph x(0,2) aliph x(2) E>	12
	<L L aliph aliph neutr aliph x(0,2) aliph aliph x(2) E>	12
	<L L x(1) I S x(1) aliph x(0,2) aliph x(2) E>	10
	<L L aliph x(1) neutr aliph aliph x(0,2) aliph x(1) neutr E>	10
	<L aliph aliph aliph x(1) aliph I x(0,2) aliph x(1) neutr E>	10

Table 8 .

 8 Motifs found using DEME.

	Motif (consensus)	freq(Motif,P) freq(Motif,N)
	<K G E G D A>	38	3
	<L F I I S L I G>	54	2
	<L L H I S L I A P N>	59	2

We have discarded the classes positive and negative, since they are equivalent to acidic and basic. We also changed the classification of H: we only classify it as basic, instead of both as basic and neutral.

The number of motifs that are frequent in the positive set can be very large, especially when using amino acid properties. Therefore, memory requirements can be an issue in breadth-first search.

In this discussion, we focus on the motifs found by MERCI. For more information about running times, refer to Supplementary Section S2.

Initially none of the sequences is covered, and we iteratively add a motif with maximal score, until the maximal coverage is obtained. The score of a motif is defined as the sum of the sequence scores of the not-yet-covered

ACKNOWLEDGEMENT

The authors would like to thank Hendrik Blockeel and Siegfried Nijssen for making valuable suggestions w.r.t. the algorithm.

Funding: This work was supported by the Research Foundation, Flanders (FWO-Vlaanderen) through a postdoctoral grant to C.V.


Agnieszka K Szczepankowska

Eric Prestel

Mahendra Mariadassou

Jacek K Bardowski

Elena Bidnenko
email: elena.bidnenko@jouy.inra.fr

Phylogenetic and Complementation Analysis of a Single-Stranded DNA Binding Protein Family from Lactococcal Phages Indicates a Non-Bacterial Origin

Background:

The single-stranded-nucleic acid binding (SSB) protein superfamily includes proteins encoded by different organisms from Bacteria and their phages to Eukaryotes. SSB proteins share common structural characteristics and have been suggested to descend from an ancestor polypeptide. However, as other proteins involved in DNA replication, bacterial SSB proteins are clearly different from those found in Archaea and Eukaryotes. It was proposed that the corresponding genes in the phage genomes were transferred from the bacterial hosts. Recently new SSB proteins encoded by the virulent lactococcal bacteriophages (Orf14 bIL67 -like proteins) have been identified and characterized structurally and biochemically.

Methodology/Principal Findings: This study focused on the determination of phylogenetic relationships between Orf14 bIL67 -like proteins and other SSBs. We have performed a large scale phylogenetic analysis and pairwise sequence comparisons of SSB proteins from different phyla. The results show that, in remarkable contrast to other phage SSBs, the Orf14 bIL67 -like proteins form a distinct, self-contained and well supported phylogenetic group connected to the archaeal SSBs. Functional studies demonstrated that, despite the structural and amino acid sequence differences from bacterial SSBs, Orf14 bIL67 protein complements the conditional lethal ssb-1 mutation of Escherichia coli.

Conclusions/Significance: Here we identified for the first time a group of phages encoded SSBs which are clearly distinct from their bacterial counterparts. All methods supported the recognition of these phage proteins as a new family within the SSB superfamily. Our findings suggest that unlike other phages, the virulent lactococcal phages carry ssb genes that were not acquired from their hosts, but transferred from an archaeal genome. This represents a unique example of a horizontal gene transfer between Archaea and bacterial phages.

Introduction

Single-strand-nucleic acid binding (SSB) proteins have been identified in all domains of life (Eukaryotes, Archaea, Bacteria) and viruses. Proteins belonging to the SSB superfamily are involved in diverse aspects of DNA metabolism [START_REF] Meyer | An Escherichia coli mutant defective in single-strand binding protein is defective in DNA replication[END_REF][START_REF] Wold | Replication protein A: a heterotrimeric, single stranded DNAbinding protein required for eukaryotic DNA metabolism[END_REF]. They assure elimination of secondary structures and protection of ssDNA from nucleolitic degradation, but also coordinate the action of different proteins involved in genome maintenance machinery [START_REF] Alani | Characterization of DNA-binding and strand-exchange stimulation properties of y-RPA, a yeast single-strand-DNA-binding protein[END_REF][START_REF] Lecointe | Anticipating chromosomal fork arrest: SSB targets repair DNA helicases to active forks[END_REF][START_REF] Shereda | SSB as an organizer/mobilizer of genome maintenance complexes[END_REF]. Despite their amino acid sequence diversity, SSB proteins share common characteristics at the structural level. The most important is the presence of a specific ssDNA-binding OB-fold (Oligonucleotide/ Oligosaccharide Binding fold) domain, which constitutes the main core of the protein [START_REF] Murzin | OB (oligonucleotide/oligosaccharide binding)-fold: common structural and functional solution for non-homologous sequences[END_REF]. The OB-fold consists of a mixed b-barrel structure which, in contrast to the additional non-conserved structures present in the ssDNA-binding proteins, shows high structural stability and evolutionary conservation [START_REF] Arcus | OB-fold domains: a snapshot of the evolution of sequence, structure and function[END_REF][START_REF] Guardino | Relative stabilities of conserved and non-conserved structures in the OB-fold superfamily[END_REF]. Amino acids in the OB-fold are directly involved in binding of the protein monomer to DNA [START_REF] Raghunathan | Structure of the DNA binding domain of E. coli bound to ssDNA[END_REF][START_REF] Bochkarev | Structure of the single-stranded DNA-binding domain of replication protein A bound to DNA[END_REF][START_REF] Kerr | Insights into ssDNA recognition by the OB fold from a structural and thermodynamic study of Sulfolobus SSB protein[END_REF]. Most bacterial SSBs are homotetramers with a single OB-fold in each polypeptide [START_REF] De Vries | The singlestranded-DNA-binding proteins (SSB) of Proteus mirabilis and Serratia marcescens[END_REF][START_REF] Raghunathan | Crystal structure of the homo-tetrameric DNA binding domain of Escherichia coli single-stranded DNA-binding protein determined by multiwavelength x-ray diffraction on the selenomethionyl protein at 2.9-A resolution[END_REF]. Eukaryotic ssDNA-binding replication protein A (RPA) is composed of three subunits (RPA70, RPA32 and RPA14) that form a heterotrimeric SSB with six OB-folds [START_REF] Wold | Replication protein A: a heterotrimeric, single stranded DNAbinding protein required for eukaryotic DNA metabolism[END_REF][START_REF] Wold | Replication protein A: a heterotrimeric, single-stranded DNAbinding protein required for eukaryotic DNA metabolism[END_REF][START_REF] Wold | Purification and characterization of replication protein A, a cellular protein required for in vitro replication of simian virus 40 DNA[END_REF]. SSBs encoded by Euryarchaeotes are more similar to their eukaryotic analogues than to eubacterial SSBs. Some Crenarchaeotes harbor a single gene encoding a single OB-fold SSB, structurally similar to bacterial SSBs [START_REF] Che ´din | Novel homolog of replication protein A in archaea: implications for the evolution of ssDNA-binding proteins[END_REF][START_REF] Kelly | Identification and characterization of a single-stranded DNA-binding protein from the archaeon Methanococcus jannaschii[END_REF][START_REF] Wadsworth | Identification and properties of the crenarchaeal single-stranded DNA binding protein from Sulfolobus solfataricus[END_REF][START_REF] Haseltine | A distinctive single-stranded DNAbinding protein from the archeon Sulfolobus solfataricus[END_REF]. Genes encoding for SSB proteins have also been found in numerous bacteriophage (phage) genomes. The characterized phage SSBs include those of coli-phages T7, N4 and P1, as well as those encoded by other phages, e.g. Bacillus Ø29-like phages [START_REF] Kim | Bacteriophage T7 gene 2.5 protein: an essential protein for DNA replication[END_REF][START_REF] Hollis | Structure of the gene 2.5 protein, a single-stranded DNA binding protein encoded by bacteriophage T7[END_REF][START_REF] Choi | Identification, cloning and characterization of the bacteriophage N4 gene encoding the single-stranded DNA-binding protein[END_REF][START_REF] Lehnherr | Identification and characterization of the single-stranded DNA-binding protein of bacteriophage P1[END_REF][START_REF] Bendtsen | Phylogenetic and functional analysis of the bacteriophage P1 single-stranded DNA-binding protein[END_REF][START_REF] Gasco ´n | Structural and functional comparative study of the complexes formed by viral w29, Nf and GA-1 SSB proteins with DNA[END_REF]. Phage-encoded SSB proteins have various roles, depending on the phage life cycle. For some phages, specific SSBs are involved in DNA replication and, in some cases are essential for phage development [START_REF] Kim | Bacteriophage T7 gene 2.5 protein: an essential protein for DNA replication[END_REF][START_REF] Gasco ´n | Structural and functional comparative study of the complexes formed by viral w29, Nf and GA-1 SSB proteins with DNA[END_REF][START_REF] Xu | DNA-binding properties of T4 UvsY recombination mediator protein: polynucleotide wrapping promotes highaffinity binding to single-stranded DNA[END_REF]. Phylogenetic analysis of a number of bacterial and phage SSB proteins indicates that there have been frequent horizontal transfers from bacterial hosts to the genomes of their phages [START_REF] Moreira | Multiple independent horizontal transfers of informational genes from bacteria to plasmids and phages: implications for the origin of bacterial replication machinery[END_REF]. The bacterial origin of the phage ssb genes is easily recognized despite the high evolution rate of phages [START_REF] Bendtsen | Phylogenetic and functional analysis of the bacteriophage P1 single-stranded DNA-binding protein[END_REF][START_REF] Moreira | Multiple independent horizontal transfers of informational genes from bacteria to plasmids and phages: implications for the origin of bacterial replication machinery[END_REF]. Moreover, some phage SSBs are interchangeable with their bacterial analogs in vivo and in vitro [START_REF] Lehnherr | Identification and characterization of the single-stranded DNA-binding protein of bacteriophage P1[END_REF][START_REF] Nakai | The effect of the T7 and Escherichia coli DNAbinding proteins at the replication fork of bacteriophage T7[END_REF].

We previously characterized a novel SSB protein (Orf14 bIL67 ) encoded by the virulent phage bIL67 infecting Lactococcus lactis, a Gram-positive bacterium used by the dairy industry [START_REF] Szczepanska | A distinct single-stranded DNA-binding protein encoded by the Lactococcus lactis bacteriophage bIL67[END_REF]. Threedimensional modeling in silico revealed a putative OB-fold domain in the Orf14 bIL67 structure. The ssDNA-binding character of the Orf14 bIL67 protein and the role of particular amino acid residues in the OB-fold domain were confirmed through electrophoretic mobility shift assays. We proposed that Orf14 bIL67 is a member of a new SSB family comprising homologous gene products identified in virulent Siphoviridae lactococcal phages from 936-and c2-groups [START_REF] Szczepanska | A distinct single-stranded DNA-binding protein encoded by the Lactococcus lactis bacteriophage bIL67[END_REF][START_REF] Deveau | Biodiversity and classification of lactococcal phages[END_REF]. This hypothesis was further supported by recent establishment of crystal structure of the second SSB protein from this group, Orf34 p2 , encoded by 936-like phage p2 [START_REF] Scaltriti | Structure and function of phage p2 Orf34 p2 , a new type of single-stranded DNA binding protein[END_REF].

Here we performed phylogenetic analyses which suggested that the Orf14 bIL67 -like proteins constitute a separate group on the basis of their evolutionary descent. In spite of their phylogenetic distance they are able to functionally complement a conditional E. coli ssb-1 (ts) mutation.

Results

Cluster analysis of the SSB proteins

Proteins of the Orf14 bIL67 SSB family, unlike SSBs encoded by other phages specific for Lactobacillales, show no sequence similarity to SSBs from their bacterial hosts [START_REF] Szczepanska | A distinct single-stranded DNA-binding protein encoded by the Lactococcus lactis bacteriophage bIL67[END_REF][START_REF] Scaltriti | Structure and function of phage p2 Orf34 p2 , a new type of single-stranded DNA binding protein[END_REF]. This raises a question about the relationships between Orf14 bIL67 -like proteins and other SSBs encoded by lactic acid bacteria and their phages.

We first built a dataset including 729 sequences of putative SSBs encoded by bacterial, archaeal, phage, eukaryotic nuclear and mitochondrial genomes (Material and Methods). The sequences from the SSB dataset were compared all-against-all with BLAST, to find clusters of similar sequences and visualize their sequence relationships, as implemented in the CLANS (CLuster ANalysis of Sequences) program [START_REF] Frickey | CLANS: a Java application for visualizing protein families based on pairwise similarity[END_REF]. CLANS allows classification of huge amount of unaligned protein sequences: highly similar sequences are clustered together and connected proportionally to their pairwise p-value (Materials and Methods).

CLANS identified 10 well-defined families (clans) of ssDNAbinding proteins (Figure 1). These clans correspond to the SSB proteins encoded by Gram-positive and Gram-negative bacteria, mitochondrial SSBs, SSB and RPA proteins encoded by Archaea and RPA proteins encoded by eukaryotes respectively. Two clans of the bacterial SSBs (Gram-negative and Gram-positive bacteria) also include phage encoded SSB proteins and are the most compact ones indicating a high level of sequence conservation.

Interestingly, none of the previously identified Orf14 bIL67 -like proteins were detected within the bacterial clans. Clustering revealed these proteins as a distinct well-defined clan with an evolutionary link to SSBs of Gram-positive bacteria and ssDNAbinding proteins of Archaea, as indicated by the relative positions of these clans. In addition to 11 previously identified Orf14 bIL67 -like proteins encoded by lactococcal phages p2, bIL66M1, sk1, bIL170, jj50, P008, bIBB29, 712, c2, bIL67 and P335 (see Material and Methods for accession numbers) this clan includes 7 new members. These new members are encoded by virulent lactococcal phages SL4, SB13, SB14, CB19 and CB20, the lactic acid bacterium Oenococcus oeni AWRIB429 429 and prophage ''2'' of L. lactis subsp. cremoris SK11 (Materials and Methods). The gene encoding the putative SSB protein of O. oeni AWRIB429 429 maps to a 1382 bp DNA segment which is an integral part of the genome shotgun sequence. The DNA sequence along the entire length of this fragment shares up to 92% identity with DNA of lactococcal 936-like phages (Figure S1). So it is an insertion of the phage DNA representing a prophage-like element. Therefore, the new SSB clan proposed here consists exclusively of the proteins from lactococcal bacteriophages.

To assess whether the findings obtained by CLANS remain valid when using the sequences of characteristic ssDNA-binding OB-fold domains common in all SSB and RPA proteins, instead of complete protein sequences, we built a second dataset, containing only the OB-fold domains from the previous 729 proteins (Materials and Methods). The CLANS analysis of this trimmed dataset gives the same results as the analysis of complete sequences: the Orf14 bIL67 OB-fold domain clan is again well separated from other OB-fold domain clans, and still connected to the bacterial and archaeal SSBs (Figure S2). Thus, CLANS analysis, performed on both full length proteins and conserved OB-fold domains only, provide evidence that Orf14 bIL67 -like proteins are clearly distinct from bacterial and archaeal SSBs, as well as from eukaryotic and archaeal RPA proteins.

Phylogenetic analysis of the Orf14 bIL67 SSB protein family

The recognition of the Orf14 bIL67 -like proteins as a separated SSB family, distinct from bacterial SSBs, but connected to archaeal SSBs, is intriguing. This prompted us to perform phylogenetic analyses of the Orf14 bIL67 family to gain insight into the evolutionary links relating these proteins to other families of SSBs.

A representative and balanced sample of 78 ssDNA-binding protein sequences from the 10 identified families was used to construct phylogenetic trees (Materials and Methods). The trees were built on OB-fold multiple sequence alignment using the Maximum Likelihood (ML) and Neighbour Joining (NJ) methods (Materials and Methods). The ML tree shows a clear separation of SSB proteins into several major lineages on the basis of their OBfold domains alignment: Orf14 bIL67 -like SSBs, bacterial SSBs, archaeal SSBs, archeal RPAs and eukaryotic RPAs (Figure 2). These results are consistent with those obtained by CLANS (Figure 1 and Figure S2). All bacterial SSBs falls within the single branch, which as described earlier, is divided into two clades: Gram-positive and Gram-negative bacteria [START_REF] Lindner | Differential expression of two paralogous genes of Bacillus subtilis encoding singlestranded DNA binding protein[END_REF]. As expected, the mitochondrial SSBs fall within the same branch, in agreement with the apparent eubacterial origin of the mitochondrial genome [START_REF] Gray | The origin and early evolution of mitochondria[END_REF]. The majority of the phage-encoded SSBs are present in one or other of the bacterial clade according to their host range and evolutional origin, as reported previously for some of them [START_REF] Bendtsen | Phylogenetic and functional analysis of the bacteriophage P1 single-stranded DNA-binding protein[END_REF][START_REF] Moreira | Multiple independent horizontal transfers of informational genes from bacteria to plasmids and phages: implications for the origin of bacterial replication machinery[END_REF].

As revealed by CLANS, Orf14 bIL67 -like proteins form a distant clade (Figure 2). They are well separated (bootstrap .95) from bacterial SSBs and affiliate to archaeal SSBs. The exact position of Orf14 bIL67 -like SSBs within archaeal proteins is not precise as the resolution of the archaeal/Orf14 bIL67 -like SSBs branching is poor (Figure 2). The Orf14 bIL67 -like SSBs in turn are divided in three groups. The largest monophyletic group is formed by 14 SSBs encoded by 936-like phages. The second and third groups are constituted by SSBs encoded by two c2-like lactococcal phages (c2 and bIL67) and two P335-like phages (L. lactis SK11 prophage ''2'' and phage P335) (Materials and Methods). It is remarkable, that all P335 phages (at least 28 genomes are available in public databases), except the two described above, encode SSB proteins homologous to the L. lactis SSB that explain their position within the bacterial clade designated by CLANS and phylogenetic analysis. Thus, the overwhelming majority (16 out of 18) of proteins forming the distinct Orf14 bIL67 -like SSB branch are encoded by virulent lactococcal phages from 936-and c2-like phage species.

Phylogenetic trees are notoriously difficult to infer from short divergent sequences, explaining the weak support of certain branches. It is thus necessary to check whether Orf14 bIL67 -like SSBs still stand out as a well supported clade when changing inference parameters. Our results show that the coherence and distinctive features of Orf14 bIL67 -like SSBs are remarkably robust: these proteins form a self-contained clade with high bootstrap values (.95), no matter what evolution model and/or number of rate categories are used (Materials and Methods). We checked for consistency that a similar topology with similar bootstrap values is found both in the NJ tree (Figure S3) and when using different alignment software (Material and Methods, Figure S4).

The separation of Orf14 bIL67 -like SSBs from the bacterial SSBs could be due to the classical phenomenon of long-branch attraction [START_REF] Bergsten | A review of long-branch attraction[END_REF]. However, the longest branches in the tree are those leading to Orf14 bIL67 -like and to fungal SSBs (approximately 1.99 and 1.65), so we would expect the long-branch attraction to group Orf14 biL67 -like and fungal branches together, but they appear to be reasonably separated (with bootstrap values around 70%). Interestingly, the long-branch problem is mitigated for the tree reconstructed with known structure information (Figure 2 and Figure S4).

The terminal branches of the Orf14 biL67 -like SSB clade are short (,0.1). This is in agreement with the high level of amino acid (aa) conservation within the clade: up to 53% of aa similarity and 35% of aa identity between SSBs from 936 and c2 phage species and up to 97% of aa identity between SSBs from the same phage species. We searched for Orf14 bIL67 homologous proteins using iterative sequence profile searches with the PSI-BLAST program, with inclusion thresholds of 0.005 (the default) and 0.05 (Materials and Methods). In both cases, convergence occurred after two iterations, and PSI-BLAST identified only 18 homologous proteins: exactly those found in the Orf14 bIL67 family.

Thus, phylogenetic analyses strongly supports the results of CLANS pairwise sequence comparison and shows that the Orf14 bIL67 -like proteins form a family which is clearly distinct from bacterial, archaeal and eukaryotic ssDNA-binding proteins. Both methods stress relationships between Orf14 bIL67 -like and archaeal proteins.

Expression of Orf14 bIL67 improves the growth of the E. coli ssb-1 (ts) mutant

The distinctive features of Orf14 bIL67 -like proteins raise questions about their functionality in bacterial cells. To examine whether Orf14 bIL67 in vivo shares common properties with the representative bacterial EcoSSB protein we used a conditional E. coli ssb-1 (ts) KLC789 mutant strain [START_REF] Chase | Amplification of ssb-1 mutant single-stranded DNA-binding protein in Escherichia coli[END_REF]. We tested whether the activity of Orf14 bIL67 restored growth of the ssb-1 mutant strain at non-permissive temperature. The E. coli KLC789 cells carrying the recombinant plasmid with the orf14 bIL67 gene cloned under the control of inducible promoter were grown at the permissive temperature of 30uC and at non-permissive temperature, 38uC (Materials and Methods). At 30uC, KLC789 (pUC19:orf14 bIL67 ) cells formed colonies of normal morphology, whereas the KLC789 (pUC19) control strain formed small colonies with dry colony morphology (Figure 3A). Plating of the KLC789 (pUC19:orf14-bIL67 ) culture at 38uC resulted in the formation of small colonies, whereas KLC789 (pUC19) did not grow at all (data not shown).

The second test was performed by growing E. coli KLC789 cells in LB broth either continuously at 30uC (Figure 3B) or by shifting the temperature to 38uC after 6 hours at 30uC (Figure 3B and Materials and Methods). The presence of the orf14 bIL67 gene in trans improved growth at 30uC (Figure 3B). The temperature shift from 30uC to 38uC resulted in growth defect of the E. coli KLC789 (pUC19) control strain, whereas the presence of the orf14 bIL67 gene allowed continued cell growth under the same conditions (Figure 3C).

To confirm that the improvement of cellular growth was due to the activity of the Orf14 bIL67 protein, we performed a complementation test using the mutated orf14 bIL67 genes [START_REF] Szczepanska | A distinct single-stranded DNA-binding protein encoded by the Lactococcus lactis bacteriophage bIL67[END_REF]. The orf14 bIL67 /D51A gene codes for a protein somewhat affected in its ssDNA-binding activity, this construct improved the growth of KLC789 at 38uC, albeit to a lesser extent than the wild type gene (Figure 3C). In contrast, the presence of pUC19:orf14 bIL67 /Y70A, coding for a mutant protein unable to bind ssDNA, did not positively affect the growth of E. coli KLC789 cells in nonpermissive conditions (Figure 3C).

To support these results we assessed the affinity of the purified Orf14 bIL67 protein for ssDNA at 30uC and 38uC. We used electrophoretic mobility-shift assays with a radioactively labelled single-stranded 80-mer oligonucleotide of random sequence (Materials and Methods). There was no significant difference in the ssDNA-binding pattern of Orf14 bIL67 at the two temperatures tested (Figure 3D). This indicates that the Orf14 bIL67 protein binds to ssDNA with a similar affinity at 30uC and 38uC. Therefore, the ability of strain KLC789 (pUC19:orf14 bIL67 ) to form only pinpoint colonies at 38uC and partial improvement of KLC789 cell growth by orf14 bIL67 at this temperature is not crucially due to temperature sensitivity of Orf14 bIL67 ssDNA-binding activity.

Thus, the phage bIL67 orf14 bIL67 gene is able to complement the conditional ts mutation in the strain KLC789, E. coli ssb-1 at 38uC. This complementation was not observed with ssDNA-binding deficient mutant, indicating that it required the ssDNA-binding activity of the Orf14 bIL67 protein.

Discussion

SSB proteins are conserved throughout all kingdoms of life. It was suggested that prokaryotic, archaeal and eukaryotic SSBs have all descended from a common ancestor polypeptide with a single OB-fold via gene duplication and recombination events [START_REF] Kerr | Insights into ssDNA recognition by the OB fold from a structural and thermodynamic study of Sulfolobus SSB protein[END_REF][START_REF] Che ´din | Novel homolog of replication protein A in archaea: implications for the evolution of ssDNA-binding proteins[END_REF][START_REF] Phlipova | A hierarchy of SSB protomers in replication protein A[END_REF][START_REF] Robbins | The euryarchaeota, nature's medium for engineering of single-stranded DNA-binding proteins[END_REF]. Nevertheless, bacterial SSB proteins, like other proteins involved in DNA replication, are clearly different from those found in Archaea and Eukaryotes [START_REF] Leipe | Did DNA replication evolve twice independently?[END_REF][START_REF] Tye | Insights into DNA replication from the third domain of life[END_REF][START_REF] Griraldo | Common domains in the initiators of DNA replication in Bacteria, Archaea and Eukarya: combined structural, functional and phylogenetic perspectives[END_REF]. Phylogenetic trees built previously with limited numbers of ssDNA-binding proteins show two essential features of SSB superfamily : i) bacterial and mitochondrial SSBs are separated from the archaeal SSBs/eukaryotic RPAs, ii) phage and bacterial SSBs do not form monophyletic groups and are intermixed with each other [START_REF] Moreira | Multiple independent horizontal transfers of informational genes from bacteria to plasmids and phages: implications for the origin of bacterial replication machinery[END_REF][START_REF] Lindner | Differential expression of two paralogous genes of Bacillus subtilis encoding singlestranded DNA binding protein[END_REF][START_REF] Theobald | Divergent evolution within protein superfolds inferred from profile-based phylogenetics[END_REF]. Thus, phylogenetic analysis supports the hypothesis that the ssDNA-binding protein superfamily was derived from a common ancestral domain present in the genome of an organism at the very base of the evolutionary tree, while phage ssb genes were transferred from the genomes of their hosts [START_REF] Arcus | OB-fold domains: a snapshot of the evolution of sequence, structure and function[END_REF][START_REF] Guardino | Relative stabilities of conserved and non-conserved structures in the OB-fold superfamily[END_REF][START_REF] Moreira | Multiple independent horizontal transfers of informational genes from bacteria to plasmids and phages: implications for the origin of bacterial replication machinery[END_REF]. (pUC19:orf14 bIL67 ) (&), KLC789 (pUC19:orf14 bIL67 /D51A) ( N ) and KLC789 (pUC19:orf14 bIL67 /Y70A) (m) strains were grown for 6 h at 30uC and then shifted to 38uC in a Bioscreen C apparatus (LabSystems), under continuous monitoring of OD 600 . The curves are generated from the means of four to six independent experiments; standard deviations were #10% (not shown). D: Binding of purified Orf14 bIL67 to ssDNA at 30uC and 38uC. A series of concentrations (marked at the top) of the protein were incubated with 0.5 nM of an 80-mer oligonucleotide at two different temperatures (30uC or 38uC) prior to loading on the gel. Asterisks (*) mark the nucleoprotein complexes. The arrow indicates the position of free ssDNA. doi:10.1371/journal.pone.0026942.g003

Here we demonstrate for the first time that SSBs encoded by the well-defined group of lactococcal phages form a clearly isolated protein family. Phylogenetic analyses of the OB-fold domains distinguished the Orf14 bIL67 protein family as a distinct clade of the domain tree, in remarkable contrast to those of other phage SSBs. The position of the Orf14 bIL67 branch in the phylogenetic tree is consistent with a particular ssDNA-binding OB-fold domain of these proteins which shares some features with both archaeal and bacterial OB-folds. We performed multiple sequence alignment of OB-fold domains of Orf14 bIL67 and Orf34 p2 proteins with the domains of representative bacterial, archaeal and eukaryotic ssDNA-binding proteins using tree different methods (Materials and Methods). The sequences were aligned on the basis of sequence similarities detected previously between archaeal and eukaryotic OB-folds [START_REF] Haseltine | A distinctive single-stranded DNAbinding protein from the archeon Sulfolobus solfataricus[END_REF]. All methods revealed that at the sequence level phage proteins are more similar to archaeal SSBs than to bacterial SSBs. This correspond to the structural similarity between phage and archaeal OB-folds (Figure 4A,B). Within conserved or similar residues between at least one phage and archaeal SSBs, several have been proposed to play a role in ssDNA binding of the phage Orf34 p2 SSB: R15, K21, K24 and K68 [START_REF] Scaltriti | Structure and function of phage p2 Orf34 p2 , a new type of single-stranded DNA binding protein[END_REF]. The conserved V17 residue has been shown to be involved in ssDNA binding of the phage Orf14 bIL67 SSB [START_REF] Szczepanska | A distinct single-stranded DNA-binding protein encoded by the Lactococcus lactis bacteriophage bIL67[END_REF].

Thus, although we cannot point explicitly to the origin of Orf14 bIL67 -like SSBs and their propagation pathways, some elements of the evolutionary history of Orf14 bIL67 -like SSBs can be reasonably suggested. The largest group of Orf14 bIL67 SSB proteins is formed by proteins encoded by virulent lactococcal phages of the 936 species suggesting that the ssb gene was initially acquired by a 936-like phage or its ancestor. The presence of Orf14 bIL67 ssb genes in the genomes of temperate lactococcal phages is not surprising, as recombination events causing gene transfer play important role in the evolution of both temperate and virulent lactococcal phages [START_REF] Bidnenko | Phage operon involved in sensitivity to the Lactococcus lactis abortive infection mechanism AbiD1[END_REF][START_REF] Durmaz | Genetic analysis of chromosomal regions of Lactococcus lactis acquired by recombinant lytic phages[END_REF][START_REF] Labrie | Abortive infections mechanisms and prophage sequences significantly influence the genetic make-up of emerging lytic lactococcal phages[END_REF]. The restricted distribution of Orf14 bIL67 ssb genes in P335-like phage genomes suggests a more recent acquisition via horizontal gene transfer from virulent phages. This is in agreement with the commonly accepted view that recent horizontal gene transfers tend to involve closely related organisms and ancient events involved transfer between more distant organisms [START_REF] Ochman | Lateral gene transfer and the nature of bacterial innovation[END_REF][START_REF] Koonin | Genomics of bacteria and archaea: the emerging dynamic view of the prokaryotic world[END_REF][START_REF] Boto | Horizontal gene transfer in evolution: facts and challenges[END_REF]. A similar scenario cannot be proposed with confidence for ssb genes of c2-like phages because the appropriate amount of sequence data is not currently available. Homologous recombination between 936-and c2-like virulent phages is not expected to be frequent, although these phages are able to infect the same host. Nevertheless, the presence in the phylogenetic tree of the SSBs encoded by two c2-like phages may suggest a gene transfer between 936-and c2-like phages.

Here we show that unlike other phages, the virulent lactococcal phages carry ssb genes that were not acquired from their bacterial hosts. The emergence of the phage SSBs among the archaeal ones suggests an archaeal origin of their ssb gene. This indicates a unique case of horizontal gene transfer between Archaea and virulent bacterial phages. The coexistence between diverse archaeal and lactic acid bacteria populations in different types of fermentation processes is well documented [START_REF] Chang | Analysis of yeast and archaeal population dynamics in kimchi using denaturing gradient gel electrophoresis[END_REF][START_REF] Roh | Investigation of archaeal and bacterial diversity in fermented seafood using barcoded pyrosequencing[END_REF][START_REF] Abriouel | Culture-independent study of the diversity of microbial populations in brines during fermentation of naturally-fermented Alorena green table olives[END_REF]. This could facilitate some gene exchange between these organisms, their viruses and phages. Although phages are known to play a key role in horizontal gene transfer in Bacteria, until now there has been no evidence of their participation in gene transfer between Bacteria and Archaea and any bacterial phage was shown to infect Archaea [START_REF] Gill | The proportional lack of archaeal pathogens: Do viruses/phages hold the key?[END_REF].

The precise role of the Orf14 bIL67 -like SSBs in phage development is not yet established. However, it was stressed that the ssb genes are adjacent to the genes encoding the single-strand annealing proteins and most likely involved in phage-promoted DNA recombination [START_REF] Szczepanska | A distinct single-stranded DNA-binding protein encoded by the Lactococcus lactis bacteriophage bIL67[END_REF][START_REF] Scaltriti | Structure and function of phage p2 Orf34 p2 , a new type of single-stranded DNA binding protein[END_REF]. Elucidation of the role of these proteins in phage development is currently in progress. Here we confirmed the biological functionality of the Orf14 bIL67 protein in vivo by complementation of the E. coli ssb-1 mutant. Overexpression of highly homologous SSB proteins from different bacteria and coli-phage P1 and distinct SSB protein from S. solfataricus can complement the lethal phenotype of the ssb-1 mutation [START_REF] Haseltine | A distinctive single-stranded DNAbinding protein from the archeon Sulfolobus solfataricus[END_REF][START_REF] Gasco ´n | Structural and functional comparative study of the complexes formed by viral w29, Nf and GA-1 SSB proteins with DNA[END_REF][START_REF] De Vries | Cloning and sequencing of the Proteus mirabilis gene for a single-stranded DNA-binding protein (SSB) and complementation of Escherichia coli ssb point and deletion mutations[END_REF][START_REF] Chilukuri | Isolation and characterization of the gene encoding single-stranded-DNA-binding protein (SSB) from four marine Shewanella strains that differ in their temperature and pressure optima for growth[END_REF]. The crenarchaeal and E. coli proteins show moderate similarity over the N-terminal part, but share a flexible C-terminal tail involved in protein-protein interaction [START_REF] Kerr | Insights into ssDNA recognition by the OB fold from a structural and thermodynamic study of Sulfolobus SSB protein[END_REF][START_REF] Haseltine | A distinctive single-stranded DNAbinding protein from the archeon Sulfolobus solfataricus[END_REF]. For Orf14 bIL67 , specific complementation was not anticipated, due to amino acid sequence differences from EcoSSB, and the divergent structural characteristics including important differences in the C-terminal part of the proteins [START_REF] Szczepanska | A distinct single-stranded DNA-binding protein encoded by the Lactococcus lactis bacteriophage bIL67[END_REF][START_REF] Scaltriti | Structure and function of phage p2 Orf34 p2 , a new type of single-stranded DNA binding protein[END_REF]. These features were expected to assure nonspecific binding of phage SSB to ssDNA, but prevent Orf14 bIL67 from specific protein-protein interactions important for different aspects of DNA metabolism. Indeed, the growth of E. coli ssb-1 (ts) KLC789 at a non-permissive temperature was improved by expression of Orf14 bIL67 , but not entirely restored. This suggests that the phage bIL67 SSB protein is functional in E. coli in vivo, but it is most probably unable to fully fulfill the varied functions of the EcoSSB protein. It would be also interesting to investigate the functional similarities between Orf14 bIL67 -like SSBs and their archaeal counterparts.

The results presented here explore the unique features of the Orf14 bIL67 -like SSB proteins and their differences from other phage and bacterial SSBs. It strongly supports the hypothesis that the Orf14 bIL67 -like SSBs of lactococcal phages constitute a new protein family within the SSB superfamily. These proteins are encoded by genes which according to presented phylogeny-based analysis were acquired from archaeal origin and adapted to phage multiplication in the bacterial host. This indicates that bacterial phages can also contribute to the horizontal gene transfer between Bacteria and Archaea.

Materials and Methods

Data collection, phylogenetic and sequence analysis

SSB sequences were retrieved from GenBank (http://www. ncbi.nlm.nih.gov) by running BLAST searches using reference SSB sequences from Bacteria, Archaea, Eukaryotes and phages (AAC43153 for E.coli SSB; NP_391512 for B. subtilis, AAK06288 for L. lactis, AAK42515 for S. solfataricus SSB; MJ1159 for Methanococcus jannachii RPA; 6319321 for Saccharomyces cerevisiae RPA70; 1350579 for Homo sapiens RPA70; AAQ14098 for phage P1 SSB, NP_041970 for phage T7 gp2.5, AAR14301 for phage p2 SSB and AAA74351 for phage bIL67 SSB). The resulting SSB dataset included 729 sequences (Table S1). To build the OB-fold SSB dataset all sequences were trimmed to contain only the OBfold domain. Homology searches were carried out using the PSI-BLAST program [START_REF] Altschul | Gapped BLAST and Psi-BLAST: a new generation of protein database search programs[END_REF]. Sequences alignment was performed on 78 sequences sharing no more than 85% identity while preserving the original balance between the 10 protein subfamilies. Sequences were aligned with Clustal X 2.0 (default settings) and MUSCLE (default settings) and then manually refined using Bioedit V7 [START_REF] Thompson | The CLUSTAL_X windows interface: flexible strategies for multiple sequence alignment aided by quality analysis tools[END_REF][START_REF] Edgar | MUSCLE: multiple sequence alignment with high accuracy and high throughput[END_REF][START_REF] Hall | BioEdit: a user-friendly biological sequence alignment editor and analysis program for Windows 95/98/NT[END_REF]. To account for protein structure, sequences were aligned using the ''accurate'' mode of T-coffee (Figure S5). This mode searches each sequence against the PDB and when a high quality match is found uses structure information instead of just sequence information to align sequences [START_REF] Notredame | T-Coffee: A novel method for multiple sequence alignments[END_REF]. Multiple sequence alignments of OB-fold domains of Orf14 bIL67 and Orf34 p2 proteins with the domains of representative bacterial (E. coli, L. lactis), archaeal (S. solfataricus A. pernix, M. jannachii) and eukaryotic (S. cerevisiae, H. sapiens) ssDNA-binding proteins were performed using alignment software ClustalX, Muscle and Mafft available in Bioinformatics platform of Max Planck Institute for Developmental Biology (http://toolkit.tuebingen.mpg.de/sections/alignment).

Cluster Analysis of Sequences (CLANS) was used to identify subfamilies of closely related SSB sequences and elucidate the relationships between and within the ssDNA-binding protein subfamilies [START_REF] Frickey | CLANS: a Java application for visualizing protein families based on pairwise similarity[END_REF]. CLANS is a Java utility based on the Fruchterman-Reingold graph layout algorithm. It runs BLAST on given sequences, all-against-all, and clusters them in 3D according to their similarity. A 2D-representation was obtained by seeding sequences randomly in the arbitrary distance space.

Accession numbers of p2, bIL66M1, sk1, bIL170, jj50, P008, bIBB29, 712, c2, bIL67, P335, SL4, SB13, SB14, CB19 and CB20 phage genomes are GQ979703, AY249139, AF011378, AF009630, DQ227764, DQ054536, EU221285, DQ227763, L48605, L33769, DQ838728 and FJ848881 -FJ848885. Accession number of Oenococcus oeni AWRIB429 429 and prophage ''2'' of L. lactis subsp. cremoris SK11 are ACSE00000000.1 (contig 50, accession number ACSE01000050.1) and CP000425.

We employed both Neighbour Joining (NJ) and Maximum Likelihood (ML) methods in our phylogenetic analyses. MEGA V4 was used for NJ analyses with 100 bootstrap replicates [START_REF] Tamura | MEGA4: Molecular Evolutionary Genetics Analysis (MEGA) software version 4.0[END_REF]. PhyML v3.0 was used for ML analyses with 200 bootstrap replicates [START_REF] Guindon | A simple, fast, and accurate algorithm to estimate large phylogenies by Maximum Likelihood[END_REF]. For ML and NJ analyses, we used a smaller alignment made of 78 OB-fold domains from a representative sample of the 10 subfamilies identified by CLANS. The sequences were chosen so that two sequences have no more than 85% identity. We then selected a model of sequence evolution (LG+G+F) from aligned sequences using ProtTest V2.4 [START_REF] Abascal | ProtTest: selection of best-fit models of protein evolution[END_REF]. Rather than using the default settings (BIONJ starting tree, discrete gamma with four rate categories, NNI moves) and following the guidelines in the operating manual for PhyML v3.0, we used SPR moves with ten starting trees for a more thorough exploration of the tree space (options -alpha e -search BEST -rand_start -n_rand_starts 10 of PhyML).

Bacterial strains and growth conditions

The E. coli strains used in study were TG1 [supE D(hsdM-mcrB) (r k 2 m k 2 McrB 2 ) thi D lac-proAB] F9(traD36 lacI q lacZ DM15 proA + B + ) and the thermosensitive ssb-1 KLC789 mutant (F 2 , metA7, rha8, thyA36, amp50, deoC2, ssb-1) [START_REF] Chase | Amplification of ssb-1 mutant single-stranded DNA-binding protein in Escherichia coli[END_REF]. Strains were grown on LB medium: -strain TG1 at 37uC, and strain KLC789 at 30uC or 38uC. When necessary, ampicillin (100 mg ml 21 ), IPTG (0.25 or 0.5 mM) and X-gal (50 mg ml 21 ) were added to the medium.

Molecular manipulations and DNA sequencing

DNA manipulations, cloning procedures and transformation of E. coli cells were performed as described elsewhere [START_REF] Sambrook | Molecular Cloning: A Laboratory Manual[END_REF]. Digestions with restriction enzymes (New England Biolabs) were done as recommended by the supplier. Cycle extension reactions were used for DNA sequencing with specific primers, Taq polymerase and fluorescent dye-coupled dideoxynucleotides (Applied Biosystems) on a 370A DNA Sequencer (Applied Biosystems).

In vivo complementation

The orf14 bIL67 wild and mutant genes that encode Orf14 bIL67 / Y70A and Orf14 bIL67 /D51A were amplified with oligonucleotides: 59-CGGGATCCTTAGAATGGTAATG-39, 59-GCTCT-AGAAATAATTTTGTTTAAC-39 using as template pTYB recombinant plasmids constructed previously [START_REF] Szczepanska | A distinct single-stranded DNA-binding protein encoded by the Lactococcus lactis bacteriophage bIL67[END_REF]. BamHI and XbaI restriction sites, indicated in bold, were used to insert the PCR products into pUC19 (New England Biolabs). The resulting constructs were used to transform E. coli TG1 cells. After confirming the sequence of the inserted DNA fragments, the recombinant plasmids were introduced into strain KLC789 carrying the ssb-1 allele. Ten independent clones of each KLC789 (pUC19), KLC789 (pUC19:orf14 bIL67 ), KLC789 (pU-C19:orf14 bIL67 /D51A) and KLC789 (pUC19:orf14 bIL67 /Y70A) were grown in 500 ml of LB supplemented with ampicillin at 30uC or 38uC in a Bioscreen C apparatus (LabSystems), with continuous monitoring of OD 600 . For plating experiment E. coli KLC789 cells were transformed with pUC19 or pUC19:orf14 bIL67 plasmid DNA as described elsewhere [START_REF] Sambrook | Molecular Cloning: A Laboratory Manual[END_REF]. Single transformant of each strain was than propagated in LB broth at 30uC for 6 hours, adequate dilutions were plated onto the LB agar plates in the presence of 0.25 mM of IPTG and incubated at 30uC for 18 hours.

Electrophoretic mobility-shift assay (EMSA)

Orf14 bIL67 protein was overproduced and purified using the IMPACT-CN purification system (New England Biolabs) as described previously [START_REF] Szczepanska | A distinct single-stranded DNA-binding protein encoded by the Lactococcus lactis bacteriophage bIL67[END_REF]. Binding of the Orf14 bIL67 to DNA was evaluated by electrophoretic mobility-shift assays (EMSA) with an 80-mer oligonucleotide (Genosys, Sigma): 59-TTTGTCG-GTACTTTATATTCTCTTATTACTGGCTCGAAAATGCC-TCTGCCTAAATTACATGTTGGCGTTGTTAAATATGGGG-G -39 (random wM13-derived sequence) with a 32 P-cdATP (3000 Ci mmol 21 ) labelled 59. Binding reactions (20 ml) were carried out in binding buffer (20 mM Tris-HCl, 25 mM KCl, 1 mM EDTA, 1 mM DTT, 2.5% glycerol, 0.3 mg ml 21 BSA, pH 7.5) by mixing a fixed amount (0.5 nM) of the radioactively labelled oligonucleotide with each of a series of concentrations of the protein (up to 100 nM). The samples were incubated for 10 min at 30uC or 38uC and run on a non-denaturing 5% polyacrylamide gel ran for 2 hours at 200 V in 0.256TBE buffer at 4uC. The gel was dried under vacuum and the binding pattern was determined by autoradiography using a PhosphoImager. Figure S2 Cluster map of the ssDNA-binding protein superfamily. The complete sequence dataset for SSB proteins containing only the OB-fold domain was clustered using CLANS (Materials and Methods). A 2D representation was obtained by seeding sequences randomly in the arbitrary distance space. In the network, each dot represents a single protein. Sequences of phages encoding Orf14 bIL67 -like SSBs proteins are shown in red. Other colours: purple -Crenarchaea , blue -Euryarchaea, maroon -Eukaryotes, dark blue -mitochondria, black -Gram-negative bacteria, green -Gram-positive bacteria. (PDF)

Supporting Information

Figure S3 Unrooted Neighbour Joining (NJ) phylogenetic tree of the ssDNA-binding proteins. The SSB phylogeny was reconstructed from OB-fold multiple alignment of 78 ssDNAbinding protein sequences that was generated using the Clustal X 2.0 (Materials and Methods). Bootstrap support values are shown. Sequences of phages encoding Orf14 bIL67 -like SSBs proteins are shown in red. Other colours: purple -Crenarchaea , blue -Euryarchaea, maroon -Eukaryotes, dark blue -mitochondria, black -Gram-negative bacteria, green -Gram-positive bacteria, and olive -phages. (PDF)

Figure S4 Maximum Likelihood (ML) phylogenetic trees of the ssDNA-binding proteins. The SSB phylogenies were reconstructed from OB-fold multiple alignments of 78 ssDNA-binding protein sequences that were generated using MUSCLE (A) and Clustal X 2.0 (B) (Materials and Methods). The trees are rooted arbitrary. Bootstrap support values .50% are shown. The tip labels correspond to sequence gi numbers. Sequences of phages encoding Orf14 bIL67 -like SSBs proteins are shown in red. Other colours: purple -Crenarchaea , blue -Euryarchaea, maroon -Eukaryotes, dark blue -mitochondria, black -Gram-negative bacteria, green -Gram-positive bacteria, and olive -phages. Branches differing between each tree and the tree represented in Fig. 2 are colored in gray. (PDF)

Figure S5 OB-fold multiple sequence alignment. A representative and balanced sample of 78 ssDNA-binding protein sequences from the 10 identified families were aligned with ''accurate'' mode of T-coffee [START_REF] Notredame | T-Coffee: A novel method for multiple sequence alignments[END_REF]. Boxes are color-coded according to the chemical nature of the conserved amino acid residues. (PNG) Table S1 Data set of the ssDNA-binding proteins. SSB sequences were retrieved from GenBank (http://www.ncbi.nlm. nih.gov/) by running BLAST searches using reference SSB sequences from Bacteria, Archaea, Eukaryotes and phages (Materials and Methods). The resulting SSB dataset included 729 sequences. (XLSX)

Figure 1 .

 1 Figure 1. Cluster map of the ssDNA-binding protein superfamily. The complete sequence dataset for SSB proteins was clustered using CLANS, which classified all ssDNA-binding proteins into 10 subfamilies containing related proteins. CLANS runs BLAST on given sequences and clusters them in 3D according to their all-against-all pairwise similarity. A 2D representation was obtained by seeding sequences randomly in the arbitrary distance space. Protein subfamilies containing members with known structures are indicated with asterisk. In the network, each dot represents a single protein. Sequences of phages encoding Orf14 bIL67 -like SSBs proteins are shown in red. Other colours: purple -Crenarchaea , blue -Euryarchaea, maroon -Eukaryotes, dark blue -mitochondria, black -Gram-negative bacteria, green -Gram-positive bacteria. doi:10.1371/journal.pone.0026942.g001

Figure 2 .

 2 Figure 2. Unrooted Maximum Likelihood phylogenetic tree of the ssDNA-binding proteins. The SSB phylogeny was reconstructed using PhyML from multiple alignments that were generated using the ''accurate'' mode of T-coffee (Materials and Methods). Bootstrap support values are shown. Sequences of phages encoding Orf14 bIL67 -like SSBs proteins are shown in red. Other colours: purple -Crenarchaea , blue -Euryarchaea, maroon -Eukaryotes, dark blue -mitochondria, black -Gram-negative bacteria, green -Gram-positive bacteria, and olive -phages. doi:10.1371/journal.pone.0026942.g002

Figure 3 .

 3 Figure3. Rescue of the E. coli ssb-1 mutant strain KLC789 by the orf14 bIL67 . A: Colony morphology of KLC789 (pUC19) and KLC789 (pUC19:orf14 bIL67 ) strains on an LB agar plates in the presence of 0.25 mM of IPTG after 18 hours of incubation at 30uC. B: KLC789 (pUC19) (%) and KLC789 (pUC19:orf14 bIL67 ) (&) strains were grown in LB broth at 30uC in the presence of 0.25 mM of IPTG. C: KLC789 (pUC19) (%), KLC789

Figure 4 .

 4 Figure 4. Alignment of ssDNA-binding OB-fold domains of Orf14 bIL67 -like, prokaryotic, archaeal and eukaryotic proteins. A: Important elements of the secondary structure of phage p2, S. solfataricus, H.sapiens and E. coli ssDNA-binding proteins. strands are colored in blue, loops are colored in red. Structural data are available in Protein Data Bank (PDB identifiers for p2, S. solfataricus, H.sapiens and E. coli ssDNA-binding proteins are 2WKC, 1O7I, 1JMC and 1SRU respectively). B: Bacteriophage sequences (accession numbers: AAR14301 for phage p2 SSB and AAA74351 for phage bIL67 SSB) aligned with the ssDNA-binding OB-fold domains of S. solfataricus SSB (accession number: AAK42515.1), A. pernix SSB (accession number: BAA80315), M. jannachii RPA (accession number: MJ1159), E. coli SSB (accession number: AAC43153), L. lactis SSB (accession number: AAK06288), S. cerevisiae RPA70 (accession number: CAA42420.1), H. sapiens RPA70 (accession number: AAS94324.1). Conserved residues are shaded grey and identical residues are shaded black. doi:10.1371/journal.pone.0026942.g004

Figure

  Figure S1 Gene context analysis of the DNA fragments in O. oeni AWRIB429 429 genome shotgun sequence. The conserved gene clusters in Oenococcus oeni AWRIB429 429 and lactococcal phage genomes were detected using Gene Context Analysis in the Integrated Microbial Genomes (IMG) data management system (http://img.jgi.doe.gov/). Five upper lines represent O. oeni AWRIB429 429 contigs from whole genome shortgun sequence. Four lower lines represent early genome regions from representative L. lactis 936-like phages. Genes encoding homologous proteins (from 77% to 98% aa identity) are marked by the same color. Genes encoding Orf14 bIL67 -like SSBs proteins are shown in red. Accession numbers of O. oeni and phage sequences are indicated above each line. (TIF)

PLoS ONE | www.plosone.org

November 2011 | Volume 6 | Issue 11 | e26942

Acknowledgments

We would like to thank Dr C. A. Haseltine for providing the E. coli ssb-1 strain KLC789. We are grateful to Dr P. Nicolas, Dr V. Bidnenko and Dr M. Mangan for critical reading of the manuscript.

This work was supported by the joint research project between Institut National de la Recherche Agronomique (INRA), France, and the Ministry of Science and Higher Education (MSHE), Poland [number INRA/26/2008]. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.

Author Contributions