Danny Hermelin
email: hermelin@mpi-inf.mpg.de

Romeo Rizzi
email: rrizzi@dimi.uniud.it

Stéphane Vialette
email: vialette@univ-mlv.fr

Algorithmic Aspects of the Intersection and Overlap Numbers of a Graph

The intersection number of a graph G is the minimum size of a ground set S such that G is an intersection graph of some family of subsets F ⊆ 2 S . The overlap number of G is defined similarly, except that G is required to be an overlap graph of F. Computing the overlap number of a graph has been stated as an open problem in [B. Rosgen and L. Stewart, The overlap number of a graph, (2010), Submitted, (20 pages, 2 figures,

Introduction

An intersection graph is a graph that represents the pattern of intersections of a family of sets. Any undirected graph G may be represented as an intersection graph: For each vertex of G, form a set consisting of the edges incident to this vertex; then two such sets have a nonempty intersection if and only if the corresponding vertices share an edge. Erdős, Goodman, and Pósa [START_REF] Erdős | The intersection of a graph by set intersections[END_REF] provided a construction that is more efficient in which the total number of set elements is at most n 2 /4, where n is the number of vertices in the graph. Many important graph families can be described as intersection graphs of more restricted types of set families, in particular sets corresponding to geometric objects. Examples of such graph classes are interval graphs (intersection graphs of intervals on the real line), circle graphs (intersection graphs of chords in a circle), unit disc graphs (intersection graphs of unit discs in the plane), and string graphs (intersection graphs of simple curves in the plane).

The intersection number of a graph G, denoted i(G), is defined to be the minimum cardinality of a (ground) set S such that G is an intersection graph of a family of subsets F ⊆ 2 S of S. In [START_REF] Erdős | The intersection of a graph by set intersections[END_REF], it was shown that i(G) also equals the minimum number of complete subgraphs needed to cover the edges of G. This latter number is known as the edge-clique cover number of G, and is denoted θ(G). (The best general reference is [START_REF] Mckee | Topics in intersection graph theory[END_REF].) Computing θ(G) (and hence i(G)) is NP-hard [START_REF] Kou | Covering graphs by cliques with regard to keyword conflicts and intersection graphs[END_REF][START_REF] Orlin | Contentment in graph theory: Covering graphs with cliques[END_REF], even when restricted to planar graphs [START_REF] Chang | On the tree-degree of graphs[END_REF] or graphs with maximum degree 6 [START_REF] Hoover | Complexity of graph covering problems for graphs of low degree[END_REF]. It is polynomial-time solvable for chordal graphs [START_REF] Ma | Clique covering of chordal graphs[END_REF], graphs with maximum degree 5 [START_REF] Hoover | Complexity of graph covering problems for graphs of low degree[END_REF], line graphs [START_REF] Orlin | Contentment in graph theory: Covering graphs with cliques[END_REF], and circular-arc graphs [START_REF] Hsu | Linear time algorithms on circular-arc graphs[END_REF]. By way of contrast, it is not approximable within ratio n ε for some ε > 0 unless P = NP [START_REF] Lund | The approximation of maximum subgraph problems[END_REF], and so far nothing better than a polynomial ratio of O(n 2 (log log n) 2 (log n) 3 ) is known [START_REF] Ausiello | Complexity and Approximation: Combinatorial optimization problems and their approximability properties[END_REF]. As for its parameterized complexity, computing θ(G) is fixed-parameter tractable under the standard parameterization [START_REF] Gramm | Data reduction and exact algorithms for clique cover[END_REF]. Guillaume and Latapy [START_REF] Guillaume | Bipartite structure of all complex networks[END_REF] argue that computing θ(G) is very widely applicable to discover underlying structure in complex real-world networks, while [START_REF] Nor | Mod/resc parsimony inference[END_REF] give a bioinformatic application for this problem.

The overlap model for graph representations arose much later and is not as well studied [START_REF] Cranston | Overlap number of graphs[END_REF]. The overlap graph of a family of sets F = {S 1 , S 2 , . . . , S n }, denoted O(F), is the graph having F as vertex set with S i adjacent to S j if and only if S i and S j intersect and neither set is contained in the other, i.e., S i ∩ S j = ∅, S i \ S j = ∅, and S j \ S i = ∅. Notice that some graph classes can play it both ways: A graph is an intersection graph of chords in a circle (i.e., a circle graph) if and only if it is has an overlap representation using intervals on a line. The overlap number of a graph G, denoted ϕ(G), is the minimum size of the ground set in any overlap representation of G. Extending an overlap representation and finding a minimum overlap representation with limited containment have been shown to be NP-hard problems [START_REF] Rosgen | The overlap number of a graph[END_REF]. However, the general problem of computing the overlap number of a graph has been stated as an open problem in [START_REF] Rosgen | The overlap number of a graph[END_REF] and [START_REF] Cranston | Overlap number of graphs[END_REF]. The following upper bounds for the overlap number of a n-vertex graph are known [START_REF] Rosgen | Set representations of graphs[END_REF][START_REF] Rosgen | The overlap number of a graph[END_REF]: n + 1 for trees, 2n for chordal graphs, 10 3 n -6 for planar graphs, and n 2 /4 + n for general graphs. It was also observed that the overlap number of K n is the minimum such that a -set contains n pairwise incomparable sets, that the overlap number of C n is n -1, and that the overlap number of any caterpillar with at least 2 vertices if the number of vertices in the longest path. In [START_REF] Cranston | Overlap number of graphs[END_REF], it is shown among other results that an optimal overlap representation of a tree can be produced in linear-time, and its size is the number of vertices in the largest subtree in which the neighbor of any leaf has degree 2.

The results in this paper are of twofold. In the first part of the paper, we consider the Intersection Number and Overlap Number problems, the optimization problems that ask to determine the intersection and overlap number, respectively, of a given input graph. We show that both problems are APX-hard. While for Intersection Number this was already known for general graphs [START_REF] Lund | The approximation of maximum subgraph problems[END_REF], our result proves this is the case also for graphs of maximum degree 7. Moreover, this result is used to show the APX-hardness of Overlap Number. In the second part of the paper, we show that for any intersection graph class G, i.e., any graph class defined by specifying the allowed intersection model, the recognition problem associated with G is linear-time solvable when restricted to graphs with bounded fixed intersection or overlap number.

Notations

Let G be a graph. We write V(G) for the set of vertices and E(G) for the set of edges of G. An adjacent vertex of a vertex u in a graph is a vertex that is connected to u by an edge. The neighborhood of a vertex u, denoted N G (u) or (when the graph is unambiguous) N (u), is the set of adjacent vertices to u. We let N [v] denote the set {v} ∪ N (v). The degree of a vertex u ∈ V(G), denoted d(u), is the number of vertices adjacent to u. The maximum degree of G, denoted by ∆(G), is the maximum degree of its vertices. A biconnected graph is a connected graph that is not broken into disconnected pieces by deleting any single vertex (and its incident edges). An edge-clique cover of G is any family

E = {Q 1 , Q 2 , . . . , Q k } of complete subgraphs of G such that every edge of G is in at least one of Q 1 , Q 2 , . . . , Q k .
The minimum cardinality of an edge-clique cover of G is denoted θ(G), and we write Edge-Clique Cover for the combinatorial problem of computing θ(G).

The Cartesian product G × H of graphs G and H is the graph such that the vertex set of G × H is the Cartesian product V(G) × V(H), and any two vertices

(u, u ) and (v, v ) are adjacent in G × H if and only if either u = v and u is adjacent with v in H, or u = v and u is adjacent with v in G. A column of G × H is the set of vertices {(u, u ) : u ∈ V(G)} for some vertex u ∈ V(H), and a row of G × H is the set of vertices {(u, u ) : u ∈ V(H)} for some vertex u ∈ V(G).
Observe that each row induces a copy of H, and each column induces a copy of G (see Figure 1). This terminology is consistent with a representation of G × H by the points of the |V(G)| × |V(H)| grid. (See Figure 1 for an illustration.)

× = Fig. 1.
The cartesian products of two graphs.

Hardness of approximating i(G)

Since i(G) = θ(G) [START_REF] Erdős | The intersection of a graph by set intersections[END_REF], we prove hardness of approximation for bounded degree graphs in terms of edge-clique covers. Notice that this result will be the main ingredient of upcoming Proposition 2.

Proposition 1. Edge-Clique Cover is APX-hard for biconnected graphs with maximum degree 7.

Proof. The reduction is from Vertex Cover in cubic graphs, which is known to be APX-hard [START_REF] Papadimitriou | Optimization, approximation and complexity classes[END_REF][START_REF] Alimonti | Some APX-completeness results for cubic graphs[END_REF]. Let G be a cubic n-vertex graph. We construct a new graph H as follows. We represent each vertex u ∈ V(G) by a triangle T u with vertices u 0 , u 1 and u 2 in the new graph H. These n triangles are all vertex disjoint in H, and each of them can offer a different edge for three connections. Let us be more specific. For each vertex u ∈ V(G) with incident edges e u [0], e u [START_REF] Alimonti | Some APX-completeness results for cubic graphs[END_REF] and e u [START_REF] Ausiello | Complexity and Approximation: Combinatorial optimization problems and their approximability properties[END_REF] (the order is arbitrary), the edge represent an edge {u, v} ∈ E(G) in H, where {u i , u i+1 (mod 3) }, 0 ≤ i ≤ 2, is the edge of the triangle T u devoted to representing {u, v}, and {v j , v j+1 (mod 3) }, 0 ≤ j ≤ 2, is the edge of the triangle T v devoted to representing {u, v}, we introduce two new vertices A u,v and B u,v and the 6 edges {A u,v , u i }, {A u,v , v j }, {B u,v , u i+1 (mod 3) }, {B u,v , v j+1 (mod 3) }, and {u i , v j }. What is left is to add m non-incident edges to H (one additional edge for each edge of G): For each edge {u, v} ∈ E(G) in H, where {u i , u i+1 (mod 3) }, 0 ≤ i ≤ 2, is the edge of the triangle T u devoted to representing {u, v}, and {v j , v j+1 (mod 3) }, 0 ≤ j ≤ 2, is the edge of the triangle T v devoted to representing {u, v}, we add the edge {u i , v j+1 (mod 3) } or {u i+1 (mod 3) , v j } (the choice is made so that these m additional edges form a matching). We refer the reader to Figure 2 for an illustration. Clearly |V(H)| = 9 2 n and |E(H)| = 27 2 n. Moreover, it follows from the construction that H is a biconnected graph with maximum degree 7.

{u i , u i+1 (mod 3) } ∈ T u , 0 ≤ i ≤ 2, is devoted to the edge e u [i] ∈ E(G). Now, to
We claim that G has a vertex cover of size k if and only if θ(H) ≤ k + 3m, where m = 3 2 n is the number of edges of G. Suppose G has a vertex cover V ⊆ V(G) of size k. Construct an edge-clique cover E of H as follows. For each u ∈ V , add T u to E. For each edge {u, v} ∈ E(G), let {u i , u i+1 (mod 3) }, i ∈ {0, 1, 2}, be the edge of triangle T u devoted to representing edge {u, v}, and {v j , v j+1 (mod 3) }, j ∈ {0, 1, 2}, be the edge of triangle T v devoted to representing edge {u, v}. Without loss of generality, assume {u i , v j+1 (mod 3) } ∈ E(H). Add the two cliques {u i , v j , A u,v } and {u i+1 (mod 3) , v j+1 (mod 3) , B u,v } to E. Furthermore, if u ∈ V , add the clique {u i , v j , v j+1 (mod 3) } to E, and {u i , u i+1 (mod 3) , v j+1 (mod 3) } otherwise. Since V is a vertex cover of G, it follows that E is an edge-clique cover of H of cardinality k + 3m.

For the reverse direction, let E be an edge-clique cover of H. Let {u, v} be any edge of G, and let {u i , u i+1 (mod 3) }, i ∈ {0, 1, 2}, be the edge of triangle T u devoted to representing edge {u, v}, and {v j , v j+1 (mod 3) }, j ∈ {0, 1, 2}, be the edge of triangle T v devoted to representing edge {u, v}. Without loss of generality, assume {u i , v j+1 (mod 3) } ∈ E(H). If we let H u,v stand for be the subgraph of H induced by the subset {u i , u i+1 (mod 3) , A u,v , B u,v , v j , v j+1 (mod 3) }, we make the easy observations (see Figure 2) that (i) 4 cliques are needed to cover the edges of H u,v , and (ii) 3 cliques are needed to cover the edges of H u,v if {u i , u i+1 (mod 3) } or {v j , v j+1 (mod 3) } (possibly both) is removed. Therefore, |E| = 3m + k for some non-negative integer k ≤ m. But each triangle T w , w ∈ V(G), can be covered by 1 clique, and hence there is no loss of generality in assuming k ≤ n. Furthermore, there is no loss go generality in assuming that E satisfies the following property: for every edge {u, v} ∈ E(G), either T u or T v (possibly both) is in E. Let V ⊆ V(G) be the subset defined as follows:

u ∈ V if T u ∈ E. According to the above, if |E| = 3m + k for some non-negative integer k ≤ n, then |V | = k is a vertex cover of G.

Hardness of approximating ϕ(G)

This section is devoted to proving that there exists a constant c > 1 such that computing the overlap number of a graph is hard to approximate to within c.

Proposition 2. Overlap Number is APX-hard.
Proof. According to Proposition 1, there exists a constant c > 0 such that θ(G) cannot be approximated to within c (unless P = NP). We shall prove that a √ capproximation algorithm for Overlap Number would yield a c-approximation algorithm for Edge-Clique Cover

Let G be a n-vertex graph with maximum degree 7 for which we are asked to c-approximate θ(G). Without loss of generality, we assume that G has no isolated vertices and is biconnected (see Proposition 1). Let m be the smallest integer such that m ≥ n and m m-1 < c, and let K m be the complete graph on m vertices. Let H = K m × G be the Cartesian product of K m by G. For the sake of simplicity, write V(K m ) = {u 1 , u 2 , . . . , u m } and V(G) = {v 1 , v 2 , . . . , v n }. We have divided the proof into a sequence of claims.

Claim 1. ϕ(H) ≤ n + m θ(G).

Proof (Of Claim 1). Let k = θ(G) and let E = {Q 1 , Q 2 , . . . , Q k } be a size-k edgeclique cover of G. To every node (u i , v j ) ∈ V(H), we associate the set S (u i ,v j ) defined as follows:

S (u i ,v j ) = {v j } ∪ {(u i , p) : v j ∈ Q p }. Consider the family F = {S (u i ,v j ) : (u i , v j ) ∈ V(H)} defined over the ground set X = (u i ,v j )∈V(H) S (u i ,v j ) = V(G) ∪ (V(K m ) × [k]),
where [k] is the set of the first k integers {1, 2, . . . , k}. Notice that |X| = n + km. We prove that O(F) and H are isomorphic graphs, thereby proving the claim. Indeed, let S (u i ,v j ) and S (ur,vs) be two subsets of F. We need to consider 3 cases.

-If u i = u r and v j = v s , then (u i , v j ) and (u r , v s ) are not adjacent vertices in H.

It can be easily verified that S (u i ,v j ) and S (ur,vs) are disjoint subsets, and hence S (u i ,v j ) and S (ur,vs) are not adjacent vertices in O(F). -If u i = u r and v j = v s , then (u i , v j ) and (u r , v s ) are adjacent vertices in H since K m is a clique. Firstly, v j ∈ S (u i ,v j ) and v j ∈ S (ur,vs) since v j = v s , and hence S (u i ,v j ) ∩S (ur,vs) = ∅. Secondly, both v j ∈ S (u i ,v j ) \S (ur,vs) and v s ∈ S (ur,vs) \S (u i ,v j ) are non-empty (i.e., the two sets have some private element) since u i = u r and v j is not an isolated vertex of G. Therefore, S (u i ,v j ) and S (ur,vs) overlap, and hence S (u i ,v j ) and S (ur,vs) are adjacent vertices in O(F). -If u i = u r and v j = v s , then (u i , v j ) and (u r , v s ) are adjacent vertices in H if and only if {v i , v j } ∈ E(G). We have v j ∈ S (u i ,v j ) \ S (ur,vs) and v s ∈ S (ur,vs) \ S (u i ,v j ) (i.e., the two sets have some private element) Therefore, the two sets overlap if and only if v j and v j belong to a same Q p for some 1 ≤ p ≤ k, which amounts to saying that {v i , v j } ∈ E(G). Hence, S (u i ,v j ) and S (ur,vs) are adjacent vertices in O(F) if and only if {v i , v j } ∈ E(G).

For the reverse direction, we need the following technical claim that deals with containment in overlap representations of H.

Claim 2. Let (F = {S (u i ,v j ) : (u i , v j ) ∈ V(H)}, X) be an overlap representation of H.
If S (ur,vs) ⊂ S (u i ,v j ) for some vertices (u i , v j ) and (u r , v s ) of H, then S (up,vq) ⊂ S (u i ,v j ) for every vertex (u p , v q ) of H which is not adjacent to vertex (u i , v j ).

Proof (Of claim 2). First, if S (ur,vs) ⊂ S (u i ,v j ) then vertices (u r , v s ) and (u i , v j ) are not adjacent in H since (F, X) is an overlap representation of H. Now, let (u p , v q ) be any vertex of H distinct from (u r , v s ) that is not adjacent to (u i , v j ). Also, let H be the graph obtained from H by deleting every vertex in the close neighborhood of vertex (u i , v j ). Notice that, since (u r , v s ) and (u p , v q ) are not adjacent to (u i , v j ) in H, they are both vertices of H . We claim that there exists a path between vertices (u r , v s ) and (u p , v q ) in H . Indeed, since G is biconnected there exists a path in G between vertices v s and v q that does not go through vertex v j , and hence there exists a path in H between vertices (u r , v s ) and (u r , v q ). If u r = u p we are done. Otherwise, since each column of H is a clique then the two vertices (u r , v q ) and (u p , v q ) are connected by an edge in H .

To prove the claim it is now enough to show that S (up,vq) ⊂ S (u i ,v j ) for any vertex (u p , v q ) of H that is adjacent to (u r , v s ) but not to (u i , v j ). The proof follows from an easy contradiction. Suppose S (up,vq) ⊂ S (u i ,v j ) . Since S (up,vq) = ∅ (H does not contain any isolated vertex), then there exists x ∈ X such that x ∈ S (up,vq) and x / ∈ S (u i ,v j ) , and hence S (up,vq) \ S (u i ,v j ) = ∅. Furthermore, (u p , v q ) and (u r , v s ) are adjacent vertices in H, and hence (since S (up,vq) and S (ur,vs) have to overlap) there exist x , x ∈ X such that (i) x ∈ S (up,vq) and x ∈ S (ur,vs) , and (ii) x / ∈ S (up,vq) and x ∈ S (ur,vs) . But S (ur,vs) ⊂ S (u i ,v j ) , and hence x ∈ S (u i ,v j ) and x ∈ S (u i ,v j ) . Then it follows that S (u i ,v j ) \ S (up,vq) = ∅ and S (up,vq) ∩ S (u i ,v j ) = ∅, and hence S (up,vq) and S (u i ,v j ) overlap. This is the sought contradiction since this would result in (u p , v q ) and (u i , v j ) being adjacent in H.

We are now ready for the reverse direction of the reduction.

Claim 3. θ(G) ≤ ϕ(H)-n-1 m-1 + 7.
Proof (Of claim 3). Let (F = {S (u i ,v j ) : (u i , v j ) ∈ V(H)}, X) be an overlap representation of H. Suppose that there exists some subset S (u i ,v j ) ∈ F that strictly contains at least one set of F. Then, according to Claim 2, S (u i ,v j ) contains all subsets S (ur,vs) ∈ F such that u i = u r and v j = v s (i.e., S (u i ,v j ) contains all those subsets of F that are associated to vertices of H that are not in the same row nor column of vertex (u i , v j )). Furthermore, if there exist subsets S (ur,vs) , S (up,vq) ∈ F distinct from S (u i ,v j ) such that S (ur,vs) ⊂ S (up,vq) , then u i = u p or v j = v q (i.e., vertex (u p , v q ) is on the same row or on the same column of vertex (u i , u j )). Indeed, assuming u i = u p and v j = v q , Claim 2 would yield to S (u i ,v j ) ⊂ S (up,vq) and S (u i ,v j ) ⊂ S (up,vq) , a contradiction. Now, let H be the graph obtained from H by deleting all vertices (u r , v s ) such that u r = u i or v s = v j (i.e., deleting all vertices that are in the same row or column of vertex (u i , v j )). Also, let F ⊆ F be those subsets of F that correspond to vertices of H , and X ⊆ X be the union of the subsets in F (X is the ground set of F ). Notice that F is an overlap representation of H where no subset being a subset of another, and that |X | ≤ |S (u i ,v j ) | since every subset of F is strictly contained in S (u i ,v j ) . Moreover, if we let G stand for the graph obtained from G by deleting vertex v j we have H = K m-1 × G . We now claim that θ(G ) ≤ |X|-n-1 m-1 . Indeed, consider the "edge-multi-coloring" procedure of H defined by assigning to every edge e = {(u r , v s ), (u p , v q )} of H the "colors" col(e) = S (ur,vs) ∩ S (up,vq) . Since F is an overlap representation of H , it follows that at least one color is assigned to every edge of H . Furthermore, since no subset being a subset of another in F , it follows that for every color c, {e ∈ E(H ) : c ∈ col(e)} induces a clique in G , and hence H can be covered with at most |X| cliques. But the maximal cliques of H are either columns (there are n -1 of these and at least n -1 vertical edges must have received a different color), or are contained in a single row and correspond to maximal clique of G. Therefore, m -1 disjoint copies of G can be covered with at most |X| -n -1 cliques.

This proves θ(G ) ≤ |X|-n-1 m-1 . What is left is to prove θ(G) ≤ ϕ(H) -n -1 m -1 + 7. This follows from θ(G ) ≤ |X|-n-1 m-1
and θ(G) ≤ θ(G ) + ∆(G).

Suppose, aiming at a contradiction, that there exists a √ c-approximation algorithm B for Edge-Clique Cover. Then, we have B(H) ≤ √ c ϕ(H). Combining this inequality with Claim 1 yield B(H) ≤ √ c (n+m θ(G)). We now apply the constructive proof of Claim 3 to obtain an approximate A(G) of θ(G). We have

A(G) ≤ B(H) -n -1 m -1 + 7 = B(H) m -1 - n + 1 m -1 + 7 ≤ √ c (n + m θ(G)) m -1 - n + 1 m -1 + 7 ≤ n √ c m -1 + ( √ c ) 2 θ(G) m -1 - n + 1 m -1 + 7 ≤ ( √ c ) 2 θ(G) + n √ c m -1 - n + 1 m -1 + 7 = c θ(G) + O(1).
The constant makes no problem since θ(G) is bound to grow with n since we assume ∆(G) is bounded.

Recognizing graphs with fixed intersection or overlap number

A central algorithmic problem corresponding to an intersection (resp. overlap) graph class G is the so called G-Recognition problem: Given a graph G, is G ∈ G? In this section, we show that this problem is linear-time solvable for graphs with fixed intersection or overlap numbers.

Proposition 3. Let G be any intersection (resp. overlap) graph class, and let k ∈ N.

The G-Recognition problem can be solved in linear-time when restricted to graphs with intersection (resp. overlap) number at most k.

For ease of presentation, we will prove this result for graphs with fixed intersection numbers. The proof for overlap numbers is along the same lines. The proof of proposition 3 heavily relies on the notion of well quasi orders. A quasi order (i.e., a binary reflexive transitive relation) is a well quasi order (or wqo for short) if it does not contain infinitely descending sequences nor infinite antichains. For example, the standard order ≤ of the natural numbers N is a well quasi order. Another less obvious example is given by considering vectors in N d . For two vectors -→

x ∈ N K 1 and - → y ∈ N K 2 , let us write - → x ≤ - → y if K 1 ≤ K 2 and
x i ≤ y i for all i ∈ {1, . . . , K 1 }.

The following lemma follows directly from a classical result known in the literature as Higman's Lemma [START_REF] Higman | Ordering by divisibility in abstract algebras[END_REF].

Lemma 1. The set N K is well quasi ordered by ≤ for any fixed K ∈ N.

A characteristic vector of a graph G is a vector -→ c ∈ N K such that there exists According to the above definition, a graph G of dimension K may have several characteristic vectors -→ c ∈ N K . However, all of these must be isomorphic. We say that two characteristic vectors -→ c , -→ d ∈ N K are isomorphic if there is a permutation π ∈ S K such that c i = d π(i) for all i ∈ {1, 2, . . . , K}. It is not difficult to see that two graphs are isomorphic if and only if they both have the same dimension K, and any pair of characteristic vectors of dimensions K for these graphs are isomorphic. The immediately implies the following lemma whose proof is omitted. We next show two applications of Lemma 3. The first application allows us to show that graphs of bounded intersection number are wqo by the induced subgraph order.

Fig. 2 .

 2 Fig. 2. The three edge-gadgets used in the proof of Proposition 1 for vertex u ∈ V(G) with edges eu[0] = {u, v}, eu[1] = {u, w}, and eu[2] = {u, x}.

a partitioning {V 1 ,

 1 V 2 , . . . , V k } of V(G) satisfying the two following properties for each i ∈ {1, 2, . . . , K}: (i) |V i | = c i , and (ii) N [u] = N [v] for all u, v ∈ V i . Define the dimension of a graph G to be the minimum number K such that G has a characteristic vector of dimension K. Lemma 2. A graph G with i(G) ≤ k has dimension at most K = 2 k .Proof. Since i(G) ≤ k, G has a representation F with | F | ≤ k, which implies that there are at most 2 k distinct sets in F. Since vertices of G corresponding to identical sets in F have identical neighborhoods, the lemma follows.

Lemma 3 .

 3 A graph H is an induced subgraph of a graph G if and only if H has a characteristic vector -→ c (H) with -→ c (H) ≤ -→ c (G) for some characteristic vector -→ c (G)of G of size K, where K is the dimension of G.

 Lemma 4.Let k ∈ N. The set of all graphs G with i(G) ≤ k is wqo by the induced subgraph order.

Proof. Let G denote the set of all finite graphs G with i(G) ≤ k. Clearly there are no infinite descending sequences in G w.r.t. the induced subgraph order, and so to prove the lemma it suffices to show that there are also no infinite antichains in G. Consider a infinite subset of graphs G ⊆ G, and let -→ C (G ) denote a set of characteristic vectors of minimum dimension for each graph in G . By Lemma 2 all vectors in -→ C (G ) have dimension at most K = 2 k , and so Lemma 1 implies that -→ C (G ) is wqo by ≤. But then G cannot be an antichain w.r.t. to the induced subgraph order according to Lemma 3.

Induced Subgraph problem asks to determine given a pair of input graph H and G whether H is an induced subgraph of G. The second application of Lemma 3 is that Induced Subgraph can be solved in linear-time when restricted to graphs of bounded intersection number. Lemma 5. Let k ∈ N. There is a linear time algorithm for Induced Subgraph when restricted to graphs H and G with intersection number at most k.

Proof. Let N H and N G denote the total number of vertices and edges in H and G, respectively, and let K H and K G respectively denote the dimensions of H and G. By Lemma 2 we have K H , K G ≤ 2 k . We first compute a characteristic vector -→ c (H) ∈ N K H for H, and a characteristic vector


Amar Riba

Noureddine Bouras

Salim Mokrane

Florence Mathieu

Ahmed Lebrihi

Nasserdine Sabaou
email: sabaou@yahoo.fr

Aspergillus section Flavi and aflatoxins in Algerian wheat and derived products

Wheat and its derivatives are a very important staple food for North African populations. The aim of this study was to analyze populations of Aspergillus section Flavi from local wheat based on aflatoxins (AFs), cyclopiazonic acid (CPA) and sclerotia production, and also to evaluate AFs-contaminated wheat collected from two different climatic regions in Algeria. A total of 108 samples of wheat were collected during the following phases: pre-harvest, storage in silos and after processing. The results revealed that among the Aspergillus species isolated, those belonging to section Flavi were predominant. Of the 150 strains of Aspergillus section Flavi isolated, 144 were identified as Aspergillus flavus and 6 as Aspergillus tamarii. We showed that 72% and 10% of the A. flavus strains produced AFs and CPA, respectively. Among the 150 strains tested, 60 produced amounts of AFB1 ranging from 12.1 to 234.6 lg/g of CYA medium. Also, we showed that most strains produced large sclerotia. AFB1was detected by HPLC in 56.6% of the wheat samples and derived products (flour, semolina and bran) with contamination levels ranging from 0.13 to 37.42 lg/kg.

Introduction

Contamination of food and feed with mycotoxins represents a high risk for human and animal health. Mycotoxins can cause acute or chronic intoxication and damage to humans and animals after ingestion of contaminated food and feed [START_REF] Moss | Mode of formation of ochratoxin A[END_REF]. Furthermore, mycotoxins are responsible for generating huge economic losses in the producing countries [START_REF] Bhat | Mycotoxin food safety risks in developing countries. Food Safety in Food Security and Food Trade. Vision 2020 for[END_REF]. [START_REF] Pittet | Natural occurrence of mycotoxins in food and feeds -an updated review[END_REF] reported that 25-40% of cereals consumed in the world are contaminated by these toxic compounds. Mycotoxins are secondary metabolites produced by some species of mold genera such as Aspergillus, Penicillium and Fusarium, which enter the food chain in the field, during storage, or later, under favorable conditions of temperature and humidity.

Aflatoxins (AFs) are the most potent natural carcinogens known (JECFA, 1997), affecting animal species, including humans. Four aflatoxins are commonly produced in foods, aflatoxins B1, B2, G1 and G2. These mycotoxins are produced by Aspergillus flavus, Aspergillus parasiticus, Aspergillus nomius, Aspergillus pseudotamarii, Aspergillus bombycis, Aspergillus toxicarius, Aspergillus minisclerotigenes, Aspergillus parvisclerotigenus and Aspergillus arachidicola in Aspergillus section Flavi [START_REF] Samson | Old and new concepts of species differentiation in Aspergillus[END_REF][START_REF] Pildain | Two novel aflatoxin-producing Aspergillus species from Argentinean peanuts[END_REF]. The most important aflatoxin producers from a public health point of view are A. flavus and A. parasiticus. Aflatoxin B1 (AFB1) is often found at the highest concentrations in contaminated food and feed. The most pronounced contamination has been encountered in corn, peanuts, cottonseed and other grain crops [START_REF] Gourama | Aspergillus flavus and Aspergillus parasiticus, aflatoxigenic fungi of concern in foods and feed -a review[END_REF].

In North African countries, the foods most susceptible to aflatoxin contamination are locally produced or imported cereals such as wheat. This crop is a staple in dry Mediterranean regions of North Africa, where its consumption in the form of couscous, pasta, macaroni, spaghetti, bread, and frik is a cultural tradition. The mycobiota of wheat and wheat products was found to be dominated by Aspergillus section Nigri and Flavi species [START_REF] Riba | Mycoflora and ochratoxin A producing strains of Aspergillus in Algerian wheat[END_REF]. However, up to now, there has been no systematic study on contamination by AF producing species either on the levels of AFs in wheat consumed in Algeria or on its derivatives. Therefore, the aim of our study was to identify and screen Aspergillus section Flavi isolates for AFs and CPA production, and to evaluate the rates of contamination with aflatoxins in wheat destined for human consumption.

Abbreviations: AFs, aflatoxins; AFB1, aflatoxin B1; AFPA, Aspergillus flavus parasiticus agar; CAM, coconut agar medium; CPA, cyclopiazonic acid; CYA, Czapek yeast extract agar; CZ, Czapek-Dox agar; DRBC, dichloran rose-bengal chloramphenicol agar; HPLC, high performance liquid chromatography; TLC, thin layer chromatography; MEA, malt extract agar; PDA, potato dextrose agar.

Materials and methods

Study area

The samples were collected from Mitidja and Sétif, two representative regions of the climate of different wheat-producing regions of Algeria. In addition, more than 80% of Algerian wheat is produced in these two areas. Because of its proximity to the Mediterranean sea, Mitidja (latitude, 36°43 0 N; longitude 4,°03 0 E; altitude, 200 m) has a high mean annual rainfall (700 mm). By contrast, Sétif (latitude, 36°11'N; longitude, 5°25 0 E; altitude, 1081 m) has a much lower mean rainfall (400 mm). These two regions are characterized by a sub-humid and a semi-arid climate, respectively. All together, 108 samples of wheat and its derived products, destined for human consumption, were collected from these two regions: during the seasons of 2004 (85 samples) and 2006 (23 samples).

Sample collection

The samples were collected during the following phases of production: pre-harvest (field samples), storage in silos and during processing (in the form of unclean and clean wheat, flour, semolina and bran). The sample collection data are summarized in Table 1.

For the field (pre-harvest) wheat (variety Waha), 27 (seven samples from Mitidja region and 20 samples from Sétif region) and 23 samples (13 samples from Mitidja region and 10 samples from Sétif region) were collected at the maturity stage in July 2004 and July 2006, respectively. The samples were collected along the diagonals of six 1-hectare parcels. Each sample was composed of 40-50 ears, randomly collected from four to five sampling points which were approximately 15-20 m apart.

Thirty-four samples of durum wheat (varieties Waha and Vitron) were collected from silos. In February 2005, 10 and 14 samples of durum wheat were collected after 6 months of storage in silos from Mitidja and Sétif, respectively. Ten samples of wheat stored in silos for 12 months were collected from Mitidja in September 2004. The stored wheat was harvested by combine harvester in many local fields in July 2004. For each sample, a sub-sample of 300-400 g was taken through the ''trench-type" silo in a transect at three levels (low, middle and high) and combined to give a sample of about 1 kg per bin (cylindrical bins of corrugated metal).

From flour and semolina mills, 24 samples (12 per mill) were collected during the mills' routine intake sampling procedure. From each mill, three samples of 1 kg each were taken at four levels along the production chain: soft wheat (variety HD1220), durum wheat (variety Waha) stored for 9 months in mill bins, clean wheat and products (flour, semolina and bran). The cleaning of wheat consists of eliminating impurities from the grain, hydrothermal treatment and grain sorting. At the moment of collection, the moisture content of durum wheat and soft wheat grain stored in a silo was 12% w/w, whereas that of the clean wheat, flour and semolina ranged from 13% to 14% w/w.

After collection in paper bags, the samples were ground to a fine powder using a Waring Blendor at high speed for a short period to avoid overheating of the samples. Aliquots of 100-200 g were used for the analysis of mycoflora, and the remaining was stored at À20 °C for the aflatoxins analysis.

Reagents

All reagents (potassium chloride, phosphoric acid, hydrochloric acid, ammonium hydroxide, b-cyclodextrin) were of PA grade. All organic solvents (methanol, acetonitrile, 2-propanol, n-hexane, chloroform and ethyl-acetate) were of HPLC grade. Deionized water was used for the preparation of all aqueous solutions and for HPLC. Standard toxins, aflatoxins (AFs) and cyclopiazonic acid (CPA) and Ehrlich's reagent (1 g of 4-dimethyl-aminobenzaldehyde in 75 ml ethanol and 25 ml concentrated HCl) were supplied by Sigma chemicals (France). All other solvents and reagents were of analytical grade purchased from Merck, Germany.

Fungal isolates and culture conditions

Dilution plating was used as the enumeration technique [START_REF] Pitt | Fungi and Food Spoilage[END_REF]. Ten grams of each sample were added to 90 ml of 0.1% peptone dissolved in water. This mixture was then shaken on a rotary shaker for approximately 15 min and diluted 10 2 , 10 3 and 10 4 fold. Aliquots consisting of 0.1 ml of each dilution were spread (in triplicate) on the surface of the Dichloran Rose-Bengal Chloramphenicol Agar medium (DRBC; [START_REF] King | Dichloran-rose bengal medium for enumeration and isolation of molds from foods[END_REF] which was composed of: glucose 10 g/L; peptone 5 g/L; K 2 HPO 4 1 g/L; MgSO 4 Á7H 2 O 0.5 g/L; agar 15 g/L; Rose Bengal 25 mg/L; dichloran (2,6 dichloro-4-nitroaniline) 2 mg/L and chloramphenicol 100 mg/L. All Petri-dishes were incubated for 3-7 days at 28 °C in the dark and under normal atmosphere. One of the three sets of dilutions averaging between 10 and 60 colonies per Petri-dish was selected for enumeration. The results were expressed as average cfu/g. Stock cultures were maintained on PDA tubes and then stored at 4 °C for subsequent characterization and taxonomic identification procedures.

Table 1 Distribution of Aspergillus

Morphological characterization of the isolates

The colonies of Aspergillus section Flavi from each PDA tube were sub-cultured on 9 cm diameter Petri dishes containing 20 ml of Malt Extract Agar (MEA) and Czapek-Dox agar (CZ) (per liter): sucrose 30 g, K 2 HPO 4 1 g, NaNO 3 2 g, KCl 0.5 g, MgSO 4 Á7H 2 O 0.5 g, FeSO 4 Á7H 2 O 0.01 g, ZnSO 4 Á7H 2 O 0.01 g, CuSO 4 Á5H 2 O 0.005 g and Agar 20 g). Cultures were incubated for 7 days, in the dark, at 25 °C and then analyzed for colony color, presence and size of sclerotia, head seriation and conidial morphology. For micromorphological observations, the isolates were examined under the microscope (10Â, 40Â and 1000Â magnification). Identification was performed according to the taxonomic keys and guides available for the Aspergillus genus [START_REF] Pitt | Fungi and Food Spoilage[END_REF][START_REF] Klich | Identification of common Aspergillus species[END_REF]. All isolates were also cultured on Aspergillus flavus parasiticus Agar (AFPA) for 3-5 days at 25 °C, in the dark, to confirm group identification by colony reverse color. All isolates were also cultured on CZ at 42 °C, and colony diameters were measured after 7 days of incubation [START_REF] Ehrlich | Aflatoxin producing Aspergillus species from Thailand[END_REF].

2.6. Mycotoxigenic ability of the isolates 2.6.1. Aflatoxins detection 2.6.1.1. Detection by fluorescence on coconut agar medium. A preliminary screen for aflatoxin production was performed on the basis of emission of blue fluorescence after UV light excitation at 365 nm after growth of the isolates on Coconut Agar Medium (CAM) supplemented with 0.3% b-cyclodextrin [START_REF] Davis | Improved method of screening for aflatoxin with a coconut agar medium[END_REF][START_REF] Fente | New additive for culture media for rapid identification of aflatoxin-producing Aspergillus strains[END_REF]. One hundred grams of shredded coconut was homogenized for 5 min with 300 ml of hot distilled water. The homogenate was filtered through four layers of cheesecloth, and the clear filtrate was adjusted to pH 7.0 with 2 N NaOH. Agar was added (20 g/l), and the mixture was sterilized by autoclaving at 120 °C for 15 min. The isolates were inoculated by the application of a mass of conidia to the central point on a 60 mm diameter Petri dish containing 10 ml of CAM. The cultures were incubated at 28 °C for a period of 7 days, and for the appearance of colonies with brilliant orange-yellow reverse coloration under daylight and blue fluorescence under long wavelength (365 nm) UV light was periodically verified. A blank consisting of sterilized, non-inoculated CAM medium, incubated under the same conditions, was used as control.

2.6.1.2. Detection by TLC. Thin layer chromatography (TLC) was used as a screening method to identify the positive samples essentially as described by [START_REF] Calvo | VeA is required for toxin and sclerotial production in Aspergillus parasiticus[END_REF]. For this, four cores (16-mm diameter) corresponding to 2 g of fungal biomass were collected from each replicate of CAM cultures and placed in a 50-ml Falcon tube. AFs were extracted from these samples by adding 5 ml of chloroform three consecutive times. Extracts were allowed to dry and then re-suspended in 500 ll of chloroform. A volume of 15 ll of each extract was applied on a silica gel G 60 plate (20 Â 20 cm, 0.25 mm thick, Merck 5721, Germany), along with standard AFs mixture (containing AFB1 and AFG1 at 0.5 lg/ml each and AFB2 and AFG2 at 0.15 lg/ml each). The plates were developed in a benzene/glacial acetic acid (95:5, v/v) solvent system. After development, the plates were dried and observed under short (254 nm) and long wavelengths (365 nm). The detection limit was 0.05 lg/g for all the AFs. The AFs were detected as an intense blue and green fluorescence spot for AFB and AFG, respectively, with the R f values of 0.8, 0.6, 0.5 and 0.4 for AFB1, AFB2, AFG1 and AFG2, respectively. 2.6.1.3. Detection by HPLC. High performance liquid chromatography (HPLC) was used to confirm the identity of the AFs and to quantify them. AFs production by isolated fungal strains was determined using HPLC following the methodology described by [START_REF] Bragulat | An easy screening method for fungi producing ochratoxin A in pure culture[END_REF]. After 7 days of growth of isolates on Czapek yeast extract agar (CYA) at 28 °C, three agar plugs (10 mm in diameter) were removed, with a cork borer, from the central area of each colony. Plugs were weighted and introduced into 3 ml vials and extracted with 1 ml of methanol for 1 h. The extracts were centrifuged at 13,000 rpm for 10 min at 4 °C and filtered through a 0.45 lm hydrophilic PVDF filter (Millipore).

The presence of aflatoxins was detected by high performance liquid chromatography (HPLC) using a post-column derivatization electrochemically generated bromine (Kobra cell) and a fluorescence detector (Spectra physic 2000) (k = 362 nm excitation, k = 435 nm emission). The HPLC column used was a reverse phase RP C18 ProntoSil analytical column (250 Â 4 mm, 3 lm particle size) preceded by a C18 pre-column (Ultrasep 10 Â 4 mm) and the flow rate was 0.5 ml/min. For post-column derivatization, 119 mg potassium bromide and 350 ll of 4 M nitric acid were added to 1 l of the mobile phase (20:20:60 (v/v) acetonitrile/methanol/ water), as suggested in the Kobra cell instruction manual. The system was run isocratically, with a flow rate of 0.5 ml/min; the elution times for AFB1, AFB2, AFG1 and AFG2 were 30.2, 24.1, 22.5 and 21.4 min, respectively. The chromatograms were analyzed with Class-LC10 software version 1.6 (Shimadzu). The limit of detection was 0.005 lg/kg for AFB1 and AFG1, and 0.02 lg/kg for AFB2 and AFG2.

Cyclopiazonic acid detection

The isolates were tested for cyclopiazonic acid (CPA) production on CYA medium following the method described by [START_REF] Pildain | Analysis of population structure of Aspergillus flavus from peanut based on vegetative compatibility, geographic origin: mycotoxin and sclerotia production[END_REF]. All strains were inoculated on 90 cm diameter Petri dishes and incubated at 28 °C. After 10 days, 2 g of fungal biomass was extracted by adding 5 ml of chloroform, three consecutive times. Extracts were allowed to dry and then re-suspended in 500 ll of methanol, and filtered through a 0.45 lm hydrophilic PVDF filter (Millipore).

Crude extract samples were applied to TLC on silica gel plates as above. To determine the detection limit, a series of different concentrations (0.5, 1, 10, 25 and 50 lg/ml) of CPA dissolved in methanol was prepared and a volume of 20 ll of each was applied to a silica gel TLC. Twenty microliter of standard and each extract (re-dissolved in 500 ll of methanol) were applied to a silica gel TLC plate, which was previously impregnated with a solution of oxalic acid (2% in methanol) for 2 min and dried. The plates were run in the same direction with ethyl acetate/2propanol/ammonium hydroxide (40:30:20, v/v) [START_REF] Fernandez Pinto | Natural cooccurrence of aflatoxin and cyclopiazonic acid in peanuts grown in Argentina[END_REF]. After pulverization of the plates with Ehrlich's reagent, the CPA was detected under daylight as an intense purple spot with an R f of 0.5. The detection limit of the TLC technique was 1 lg/g.

Analysis of AFs in wheat and wheat products

Extraction of AFs

The extraction of AFs from wheat samples was performed according to El Adlouni et al. (2006). Briefly, 20 g of fine powdered samples were added to 20 ml of 4% potassium chloride solution acidified to pH 1.5 with sulfuric acid. The mixture was homogenized and extracted with 180 ml acetonitrile on an orbital shaker for 20 min, and filtered through No. 4 Whatman paper.

Purification of the extract

The n-hexane (100 ml) was added to the filtrate and shaken for 1 min. After separation, the upper phase (n-hexane) was discarded. To the lower phases, 50 ml deionized water and 100 ml chloroform were added. The mixture was shaken for 10 min. After separation, the lower phase (chloroform) was collected. The upper phase was re-extracted three times with 20 ml of chloroform using the above conditions. To the pooled chloroform extracts, 50 ml of 5% sodium bicarbonate was added and shaken for 10 min. The upper phase (bicarbonate) was collected, acidified to pH 1.5 with concentrated hydrochloric acid and allowed to stand about 20 min. The acidified solution was extracted three times with chloroform (100, 50 and 50 ml). The pooled chloroform phases were evaporated to near dryness under vacuum using a rotary evaporator placed in a 40 °C water bath. The extract was re-suspended in 1 ml of methanol, sonicated and filtered through a 0.2 lm Minisart cartridge (Sartorius AG Goettingen, Germany). The analysis was performed using the method previously described (Section 2.6.1.).

Determination of the rate of AFB1 recovery

The rate of AFB1 recovery was determined by spiking an AFB1-free sample (50 g of ground wheat) with an equivalent of 0.5, 5.0, 10 and 20 lg/kg of AFB1, from a 10 lg/ml stock solution of AFB1 dissolved in methanol. Spiking was carried out in triplicates and a single analysis of a blank sample was also carried out. After allowing the methanol solvent to evaporate overnight, AFB1 was extracted as described above. The percentage of AFB1 recovery was calculated and taken into account for the determination of AFB1 levels in analyzed samples.

Results

Distribution of isolates of Aspergillus section Flavi

The fungal strains isolated from 108 samples (pre-harvest, in a state of storage and from flour and semolina mills) collected in 2004 and 2006 are shown in Table 1. The results revealed the dominance of Aspergillus species from all the samples analyzed with the mean percentage of 64.5%. Regarding Aspergillus section Flavi isolation, the mean percentage found was 22.5% of the total Aspergillus and 15.1% of the total fungi. The other species isolated belonged to the Aspergillus section Nigri, Circumdati and Terrei. Colonization of wheat by species belonging to Aspergillus section Flavi was higher in stored samples (26%, 26.2% and 28.7%) compared to the field samples (5%, 5.1%, 6.8% and 18.5%). The soft and durum wheat from mills contained levels of these species ranging from 3.4% to 23.8% with a mean of 13.6% of the total fungi. These species were isolated at a low frequency from wheat products (flour, semolina and bran).

Identification of strains of Aspergillus section Flavi

Among the total strains of Aspergillus section Flavi isolated from wheat and its derivatives (flour, semolina and bran), 150 were chosen for their AFs, CPA production and sclerotia characterization.

Aspergillus strains belonging to the section Flavi were identified preliminarily at the species level, based on morphological characteristics (mainly colony color on Czapek-Dox agar and conidia morphology). Of the 150 strains of Aspergillus section Flavi collected from wheat, 144 were identified as presumptive A. flavus and 6 as Aspergillus tamarii. The 144 isolates of A. flavus displayed typical morphological features of yellow-green colonies with smooth to finely rough globose conidia. The reverse sides of colonies of A. flavus strains were of a bright orange color on Aspergillus flavus parasiticus agar (AFPA) plates and could grow at 42 °C. By contrast, the 6 isolates identified as A. tamarii were of brown-to-dark-brown color and produced rough conidia. Moreover, colonies of A. tamarii could not grow at 42 °C.

Aflatoxin production by isolates of Aspergillus section Flavi

The capacity for producing AFs was determined for 150 isolates collected in 2004 and 2006 from wheat and its derivatives. Initially, aflatoxin production was screened on Coconut Agar Medium (CAM), and the results showed that 45 isolates (30%) were aflatoxigenic. HPLC analysis revealed that among the 150 strains tested, 108 (72%) were AFB1 producers. The results concerning the per-centage of AFB1-producing ability of Aspergillus section Flavi strains on CYA medium are shown in Table 2.

Isolates of Aspergillus section Flavi were randomly classified into five groups according to their capacity for producing AFB1, which ranged from 0.02 to 234 lg/g of medium (Table 2). Twenty-three isolates (15%) presented high aflatoxigenic capacity with mean levels of AFB1 ranging from 103 to 234.6 lg/g, and 37 (25%) were moderately aflatoxigenic (12.1-95.7 lg/g of medium) as demonstrated by HPLC analysis. Furthermore, we observed that a total of 40 strains (27%) were able to produce small quantities of AFB1 in the 0.02-0.09 lg/g range. Similarly, we observed that the high producers of AFB1 (greater than 100 lg/g) were also AFB2 producers (4-125 lg/g). However, none of the 42 isolates (28%) produced AFB1 at the detectable limit (5 lg/g) and no AFG production was detected in any of the 150 isolates analyzed.

Identification of chemotypes in Aspergillus section Flavi

Based on mycotoxin production patterns (AFB1, AFG and CPA) and formation of sclerotia, the 150 strains were classified into eight chemotypes (Table 3). Chemotype I was represented by 45 isolates (30%) non-producing of any mycotoxins or sclerotia; chemotype II was represented by 45 isolates (30%), which produced only AFB1; chemotype III was represented by 30 isolates (20%), which only present sclerotia; chemotype IV was represented by 15 isolates (10%), which produced both AFB1 and sclerotia; chemotype V was represented by six isolates, which were able to produce AFB1, CPA and sclerotia, including one isolate which produced small sclerotia (<400 lm); chemotype VI was represented by three isolates, which produced both AFB1 and CPA; chemotype VII was represented by four isolates, which were able to produce only CPA; and chemotype VIII was represented by only two isolates, which produced CPA and sclerotia.

Aflatoxin content in wheat and wheat products

The incidence and level of AFB1 contamination in pre-harvest and stored wheat are summarized in Table 4. AFB1 was detected in 30 of the 53 samples examined (or an incidence of 56.6%). The incidence of contamination in 2004 and 2006 was 53.3% and 60.9%, respectively, with concentrations ranging from 0.13 to 37.42 lg/kg. The high level of AFB1 (37.4 lg/kg) was found in sample wheat stored for 12 months. In the processing chain, AFB1was detected only in bran of flour mill (3.37 lg/kg) and semolina (1.18 lg/kg). Of the 53 samples analyzed, five (9.4%) were above the legal limit established by EU regulations (5 lg/kg) (European commission, 2006) and two samples were above the legal limit as recognized in Algeria (10 lg/kg) (FAO, 2004).

Discussion

Wheat is one of the world's most important food crops. Foods made from wheat and its derivatives are a major part of a diet for over a third of the world's people. In Algeria, climatic conditions characterized by high humidity and temperature and inadequate storage practices contribute to the potential for significant exposure of the Algerian population to AFs. In our previous study [START_REF] Riba | Mycoflora and ochratoxin A producing strains of Aspergillus in Algerian wheat[END_REF], species of Fusarium, Penicillium, Alternaria and Mucor and especially Aspergillus (belonging to section Flavi and Nigri) were the major fungal species most commonly isolated from Algerian wheat. The presently available data confirm that the genus Aspergillus displays a worldwide distribution, particularly in subtropical and warm temperate regions such as North Africa [START_REF] Hocking | Mycotoxigenic fungi[END_REF]. Among all the strains screened, we could not find any AFG producer. This observation suggests the absence of AFG-producing species (A. parasiticus, A. nomius, A. bombycis, A. toxicarius, and A. arachidicola) in the analyzed samples. On the other hand, [START_REF] Ehrlich | Aflatoxin producing Aspergillus species from Thailand[END_REF] reported that A. pseudotamarii is characterized by a brown to dark-brown color, and is not able to grow at 42 °C. However, our results showed that all the AF-producers have yellowgreen colonies and are able to grow at 42 °C. This observation suggests the absence of this species in our samples. In our study, the one strain producing small sclerotia produce only AFB and CPA. This strain does not obviously belong to A. minisclerotigenes or to A. parvisclerotigenus, which produce both AFB and AFG [START_REF] Pildain | Two novel aflatoxin-producing Aspergillus species from Argentinean peanuts[END_REF]. Thus, we can conclude that A. flavus is the only aflatoxigenic fungus in Algerian wheat. It is known that A. flavus strains are commonly associated with warmer geographical regions. Indeed, several studies reported the predominance of this species in wheat samples originating from Argentina [START_REF] Vaamonde | Variability of aflatoxin and cyclopiazonic acid production by Aspergillus section Flavi from different substrates in Argentina[END_REF], Australia [START_REF] Berghofer | Microbiology of wheat and flour milling in Australia[END_REF]), Egypt (Abdel Hafez et al., 1990;[START_REF] Mazen | Survey of the mycoflora of Egyptian wheat grain and their lemmae and paleae[END_REF], Iran [START_REF] Ghiasian | Mycoflora of Iranian maize harvested in the main production areas in[END_REF], and Turkey [START_REF] Baydar | Aflatoxin and ochratoxin in various types of commonly consumed retail ground samples in Ankara, Turkey[END_REF]. In addition, although aflatoxin-production ability has been detected in a variety of species of the Aspergillus genus, inside and outside the Flavi section, A. flavus and A. parasiticus remain the most important and representative AF-producers occurring naturally in food commodities.

Of the 150 strains examined, 108 (72%) produced AFB1 in amounts ranging from 0.02 to 234.6 lg/g of CYA medium. The percentage of aflatoxigenic strains of A. flavus has been shown to vary with the nature of substrate, and environmental factors [START_REF] Horn | Ecology and population biology of aflatoxigenic fungi in soil[END_REF][START_REF] Klich | Environmental and developmental factors influencing aflatoxin production by Aspergillus flavus and Aspergillus parasiticus[END_REF]. For example, the incidence of aflatoxigenic A. flavus strains was higher in peanuts (69%) than in wheat (13%) [START_REF] Vaamonde | Variability of aflatoxin and cyclopiazonic acid production by Aspergillus section Flavi from different substrates in Argentina[END_REF]. In addition, among Aspergillus isolates, there is great variation in aflatoxin production especially within the most common aflatoxin-producing species, A. flavus [START_REF] Abbas | Relationships between aflatoxin production and sclerotia formation among isolates of Aspergillus section Flavi from the Mississippi Delta[END_REF]. Our strains were classified into eight different chemotypes, based on patterns of mycotoxin (AFB1, AFG and CPA) and sclerotial production. The results obtained demonstrate a great variability in the AFB and CPA-producing potential of A. flavus. According to [START_REF] Pitt | A descriptive model of mold growth and aflatoxin formation as affected by environmental conditions[END_REF], A. flavus isolates produce AFB1 and AFB2, CPA alone, AFB1, AFB2 and CPA or neither. Our results showed that only 10% of isolates are able to produce CPA. We observed that only 9 isolates (6%) of A. flavus were able to simultaneously produce AFB1 and CPA. In contrast, [START_REF] Frisvad | Taxonomic comparison of three different groups of aflatoxin producers and a new efficient producer of aflatoxin B1, sterigmatocystin and 3-omethylsterigmatocyst in: Aspergillus rambellii sp. nov[END_REF] reported that production of CPA is correlated with AFB1 production. [START_REF] Giorni | Studies on Aspergillus section Flavi isolated from maize in northern Italy[END_REF] showed that 70% of A. flavus isolated from Italian maize are producers of AFs, and that half of them are CPA producers.

Our results showed that only 21 aflatoxigenic strains (14%) are able to produce sclerotia (chemotypes IV and V). Several authors suggested that the size and formation of sclerotia are correlated to the aflatoxigenicity of isolates [START_REF] Cotty | Virulence and cultural characteristics of two Aspergillus flavus strains pathogenic on cotton[END_REF][START_REF] Criseo | Differentiation of aflatoxin-producing and non-producing strains of Aspergillus flavus group[END_REF]. It is currently known that all S-type strains, with small sclerotia (<400 lm in diameter) are aflatoxigenic. However, L-type strains, with larger sclerotia (>400 lm in diameter), usually include both aflatoxigenic and non-aflatoxigenic strains. Many authors reported that the S-type strains are rarely isolated [START_REF] Vaamonde | Variability of aflatoxin and cyclopiazonic acid production by Aspergillus section Flavi from different substrates in Argentina[END_REF][START_REF] Barros | Aspergillus flavus population isolated from soil of Argentina's peanut-growing region. Sclerotia production and toxigenic profile[END_REF][START_REF] Giorni | Studies on Aspergillus section Flavi isolated from maize in northern Italy[END_REF] and are usually obtained from geographical regions characterized by high temperatures and low rainfall [START_REF] Cardwell | Distribution of Aspergillus section Flavi among field soils from the four agroecological zones of the Republic of Benin West Africa[END_REF].

Of the 53 samples of wheat and wheat products analyzed, 57.1% were contaminated by AFB1 and two samples were not safe for human consumption according to the national limits (10 lg/kg). Our results are in line with those reported by [START_REF] Perenzin | Frumento tenero biologico: Risultati agronomici equalitativi[END_REF] who found that 62% of wheat samples collected from experimental field plots in northern Italy (Lombardy) were contaminated by aflatoxins. In contrast, [START_REF] Jiménez | Occurrence of Toxigenic Fungi and Mycotoxins in Agricultural Commodities in Spain[END_REF] reported that although aflatoxigenic fungi were found at high levels in wheat, no aflatoxins were found in 165 samples collected from markets in Spain. Although the number of samples analyzed was limited, our results revealed a relatively high contamination of wheat grain comparing to wheat products. Therefore, it can be hypothesized that during processing, the quantity of mycotoxins is reduced as observed for the species belonging to Aspergillus section Flavi. [START_REF] Zinedine | Presence of aflatoxin M1 in pasteurized milk from Morocco[END_REF] reported that the incidence of AFB1 in wheat flour commercialized in Morocco was about 17.6%, and that levels of contamination ranged from 0.03 to 0.15 lg/kg. According to [START_REF] Behfar | Determination of aflatoxin (B1, B2, G1, G2) levels in wheat flour[END_REF], none of 32 wheat flour samples was contaminated by aflatoxins. Some food processing methods have been shown to result in reduction or elimination of aflatoxins [START_REF] Murphy | Food mycotoxins, an update[END_REF]). These results reveal the widespread occurrence of aflatoxigenic strains of A. flavus in Algeria, and highlight the importance of the post-harvest care of grains. Thus, whenever there is a problem in the storage or in the processing of wheat and wheat-based feeds that allows fungal growth, the risk of mycotoxin contamination should be taken into account. More investigations on levels of AFs in different food products are necessary to provide data on the exposure of the Algerian population to AFs.

  and A. flavus isolated from samples of pre-harvest and stored wheat and its derivatives collected in 2004 and 2006detected. SD: standard deviation. a Wheat grains freshly harvested in July 2004 and 2006. b Wheat grains stored for 6 months in a silo (2004 harvest). c Wheat grains stored for 12 months in a silo (2004 harvest). e Calculated as a percentage of the total fungi. d Calculated as a percentage of the total Aspergillus.

Table 2

 2 Occurrence and AFB1-producing ability of 150 isolates of Aspergillus section Flavi isolated from samples of pre-harvest, stored wheat and its derivatives collected in2004 and 2006.

	AFB1 (lg/g) a	No. of strains	Percentage (%)
	<0.005	42	28
	0.005-0.1	40	27
	0.11-10.0	8	5
	10.1-100	37	25
	>100	23	15
	a The amounts of AFB1 were calculated after 7 days of growth on CYA at 28 °C
	and analyzed by HPLC.

Table 3

 3 Chemotype patterns of Aspergillus section Flavi strains on aflatoxins, cyclopiazonic acid and sclerotia producing ability.

	Chemotype	Mycotoxins		Sclerotia	No. of	Percentage (%) b
						strains
		AFB1	AFGI	CPA
	I	À	À	À	À	45	30
	II	+	À	À	À	45	30
	III	À	À	À	+	30	20
	IV	+	À	À	+	15	10
	V	+	À	+	+ a	6	4
	VI	+	À	+	À	3	2
	VII	À	À	+	À	4	2.7
	VIII	À	À	+	+	2	1.3
	AFB1: aflatoxin B1; AFG1: aflatoxin G1; CPA: cyclopiazonic acid.
	a Only one strain (chemotype V) was able to produce the S-type sclerotia.
	b Percentage of the 150 isolates.

Table 4

 4 Incidence and range of AFB1 level in samples of pre-harvest and stored wheat collected from the Mitidja and Sétif regions (Algeria) in2004 and 2006.

	Samples origin	Mitidja region				Sétif region
	Samples source	Field		Stored wheat		Field		Stored wheat
	Season	2004	2006	Silo 1	Silo 2	2004	2006	Silo 3
	Number of samples analyzed	3	13	6 a	5 a	2 b	10	6 a
	Number of positive samples	2	8	5	4	1	6	2
	Amount of AFB1 in positive samples (lg/kg)	1.35; 3.41	0.22-13.96	0.31-4.62	1.69-37.42	0.87	0.21-7.0	0.13; 0.44

a Each sample represents one bin of silo. b Each sample represents the 10 pooled sub-samples collected in one land parcel.

Conflict of Interest

The authors declare that there are no conflicts of interest.


Slim Smaoui

Lobna Elleuch

Wacim Bejar

Ines Karray-Rebai

Imen Ayadi

Bassem Jaouadi

Florence Mathieu

Hichem Chouayekh

Samir Bejar

Lotfi Mellouli
email: lotfi.mallouli@cbs.rnrt.tn

Inhibition of Fungi and Gram-Negative Bacteria by Bacteriocin BacTN635 Produced by Lactobacillus plantarum sp. TN635

Keywords: Lactobacillus plantarum sp, TN635, Identification, BacTN635, Purification, Broad inhibitory spectrum

The aim of this study was to evaluate 54 lactic acid bacteria (LAB) strains isolated from meat, fermented vegetables and dairy products for their capacity to produce antimicrobial activities against several bacteria and fungi. The strain designed TN635 has been selected for advanced studies. The supernatant culture of this strain inhibits the growth of all tested pathogenic including the four Gram-negative bacteria (Salmonella enterica ATCC43972, Pseudomonas aeruginosa ATCC 49189, Hafnia sp. and Serratia sp.) and the pathogenic fungus Candida tropicalis R2 CIP203. Based on the nucleotide sequence of the 16S rRNA gene of the strain TN635 (1,540 pb accession no FN252881) and the phylogenetic analysis, we propose the assignment of our new isolate bacterium as Lactobacillus plantarum sp. TN635 strain. Its antimicrobial compound was determined as a proteinaceous substance, stable to heat and to treatment with surfactants and organic solvents. Highest antimicrobial activity was found between pH 3 and 11 with an optimum at pH=7. The BacTN635 was purified to homogeneity by a four-step protocol involving ammonium sulfate precipitation, centrifugal microconcentrators with a 10-kDa membrane cutoff, gel filtration Sephadex G-25, and C18 reverse-phase HPLC. SDS-PAGE analysis of the purified BacTN635, revealed a single band with an estimated molecular mass of approximately 4 kDa. The maximum bacteriocin production (5,000 AU/ml) was recorded after a 16-h incubation in Man, Rogosa, and Sharpe (MRS) medium at 30°C. The mode of

Introduction

During the last two decades, with the misuse use of existing antibiotics in human and veterinary medicine and in agriculture, the effectiveness of currently available antibiotics is decreasing due to the increasing number of resistant pathogenic strains. This is presently an urgent focus of research and it becomes inevitable to discover new antimicrobial agents for combating such a problem. Numerous antibacterial agents are now being considered, such as bacteriophage [1], probiotic bacteria [2], antimicrobial peptides [3], and bacteriocins [4]. Bacteriocins are ribosomally synthesized peptides with a narrower spectrum of antimicrobial activity than most antibiotics [START_REF] Brooks | Adelberg's medical microbiology[END_REF]. Their antimicrobial activity has been found more effective against closely related strains [START_REF] Settanni | [END_REF]. Actually, attention is turning to the potential application of bacteriocins in the protection of human health [START_REF] Nawaz | African[END_REF], in agriculture [8], and in food preservation [9]. Although bacteriocins are produced by many Gram-positive and Gram-negative bacteria, those produced by lactic acid bacteria (LAB) are of particular interest because they are known as "good bacteria" and can be used as natural preservatives in food industry [10]. During the last few years, a large number of new LAB bacteriocins have been identified and characterized. However, only few have been described to possess activities against Gram-negative bacteria, e.g., plantaricin 35d produced by Lactobacillus plantarum [11], bacteriocin ST34BR produced by L. lactis subsp. Lactis [12], bacteriocins ST26MS and ST28MS produced by L. plantarum [13] and bacteriocin AMA-K produced by L. plantarum AMA-K [14].

During our search program for bioactive compounds from LAB, a new bacterium called TN635 was selected. This paper describes the selection, identification, and phylogenetic determination of this bacterium. The purification and the characterization of a bacteriocinlike substance called BacTN635, from the supernatant culture of this new strain are also reported.

Materials and Methods

Bacterial Strains and Plasmids

The TN635 strain was selected as a producer of potent antimicrobial activities and was used as the source of chromosomal DNA to amplify the 16S rRNA gene. E. coli TOP10 (Invitrogen), F-mcrA Δ(mrr-hsdRMS-mcrBC) φ 80lacZΔM15 ΔlacX74 deoR recA1 araD139 Δ(ara-leu)7697 galU galK rpsL endA1 nupG, and E. coli DH5α [15] were used as host strains. Bacterial strains: Gram-positive bacteria (Micrococcus luteus LB 14110, Staphylococcus aureus ATCC 6538, Listeria ivanovii BUG 496, Enterococcus faecalis JH 2-2 and Enterococcus faecium ENSAIA 631), Gram-negative bacteria (Escherichia coli ATCC 8739, Salmonella enterica ATCC43972, Pseudomonas aeruginosa ATCC 49189, Hafnia sp. and Serratia sp.), and lactic acid bacteria: (Lactobacillus casei DSM 20011, Lactobacillus sakei 2525, Lactobacillus delbrueckii DSM 20081, Lactococcus lactis ATCC 11454 and Lactococcus lactis subsp. cremoris DSM 11603) were used as indicator microorganisms for the antibacterial activity assays. Antifungal activity was determined against the Fusarium sp. and Candida tropicalis R2 CIP203.

pIJ2925 [16] derivative of pUC18 and pCR-Blunt vector (Invitrogen) Col E1 origin (pUC-derived) Kn R were used as the cloning vectors. pSS1, derivative of pCR-Blunt vector carrying a 1,540-bp DNA fragment corresponding to the whole 16S rRNA gene of the TN635 strain (this work).

Culture Conditions

E. coli DH5α was grown on Luria Bertani (LB) plates supplemented with ampicillin (50 μg/ml) and 5-bromo-4-chloro-3-indolyl-β-D-galactopyranoside (40 μg/ml) when appropriate [START_REF] Sambrook | Molecular cloning: a laboratory manual[END_REF]. Transformation of E. coli DH5α with pIJ2925 derivatives was carried out according to Hanahan [15]. Growth and transformation of TOP10 E. coli strain with the pCR-Blunt vector derivative were carried out according to the manufacturer's instructions (Invitrogen). For determination of antibacterial activities, indicator microorganisms were grown overnight in LB medium in aerobic conditions at 30°C for Lb. casei DSM 20011, Lb. sakei 2525, Lc. lactis ATCC 11454, Lc. lactis subsp. cremoris DSM 11603, L. ivanovii BUG 496, S. enterica ATCC43972, P. aeruginosa ATCC 49189, and M. luteus LB 14110, in aerobic conditions at 37°C for E. coli ATCC 8739 and S. aureus ATCC 6538, in anaerobic conditions at 30°C for E. faecalis JH 2-2, E. faecium ENSAIA 631, Hafnia sp and Serratia sp, and in anaerobic conditions at 37°C for Lb. delbrueckii DSM 20081. For antifungal activities determination, Fusarium sp. was grown in potato dextrose agar (PDA) for 7 days at 30°C. Spores were collected in sterile distilled water and then concentrated to produce a suspension with approximately 10 4 spores/ml. C. tropicalis R2 CIP203 was grown in YP10 medium (10 g/l yeast extract, 10 g/l peptone, 100 g/l glucose, 15 ml of 2 g/ l adenine solution) at 30°C for 24 h in an orbital incubator with shaking at 200 rpm. The TN635 strain was maintained as frozen stocks at -80°C in Man, Rogosa, and Sharpe (MRS) broth containing 20% (v/v) glycerol. Before experimental use, the cultures were propagated twice in MRS medium at 30°C for 12 h and the transfer inoculum was 1% (v/v).

DNA Isolation and Manipulation

Total DNA preparation from TN635 strain was carried out according to the method of Leenhouts et al. [START_REF] Leenhouts | [END_REF] with slight modifications as described by Lee et al. [19]. Small-scale plasmid preparations from E. coli were performed as described by Sambrook et al. [START_REF] Sambrook | Molecular cloning: a laboratory manual[END_REF]. Digestion with restriction endonucleases, separation of DNA fragments by agarose gels electrophoresis, dephosphorylation with alkaline calf intestinal phosphatase, ligation of DNA fragments, and transformation of E. coli were performed according to Sambrook et al. [START_REF] Sambrook | Molecular cloning: a laboratory manual[END_REF].

PCR Amplification of the 16S rRNA Gene of TN635 Strain PCR amplification of the 16S rRNA gene of TN635 strain was performed using two specific primers P1: 5′-AGAGTTTGATCCTGGCTCAG-3′ and P2: 5′-ATGGCTCAGGAC GAACGCT-3′. Approximately 200 ng genomic template DNA was used with 150 pmol of each primer per 50 μl reaction volume. Amplification was performed in an automated thermocycler (Perkin Elmer) using 1 U Pfu DNA polymerase (Stratagene) according to the following amplification profile: 94°C (3 min) followed by 40 cycles of denaturation at 94°C (30 s), annealing at 60°C (1 min), and extension at 72°C (3 min).

DNA Sequencing and Analysis

Nucleotide sequence of the whole 16S rRNA gene of TN635 strain was determined on both strands by an automated 3100 Genetic Analyser (Applied Biosystems) using specific primers. Homology search was performed using Blast Search algorithm. The nucleotide sequence of the whole 16S rRNA gene (1,540 pb) of TN635 strain has been assigned GenBank (EMBL) under accession number FN252881. Multiple sequence alignment was carried out using CLUSTAL W [20] at the European Bioinformatics Institute website (http://www.ebi.ac.uk/clustalw/). Phylogenetic analyses were performed using programs from the PHYLIP package [START_REF] Felsenstein | PHYLIP-Phylogeny Inference Package, version 3.2[END_REF] and phylogenetic tree was constructed by the neighborjoining (NJ) algorithm [22] using Kimura ten-parameter distance. The robustness of the inferred tree was evaluated by bootstrap (100 replications).

Antimicrobial Activities Determination

The ability of TN635 strain to produce diffusible metabolites was tested by the agar well diffusion assay [23]. The diameters of the inhibition zones were measured. The bacteriocin samples to be spotted were serially diluted twofold, and the reciprocal of the highest inhibitory dilution was used to calculate the arbitrary activity units (AU) per milliliter. The un-inoculated media were also tested for inhibitory zones as a control.

Effect of Different Treatments on the Antimicrobial Activity of the TN635 Strain

The indicator strains used in these experiments were: L. ivanovii BUG 496, S. enterica ATCC43972, S. aureus ATCC 6538, E. faecalis JH 2-2 and E. faecium ENSAIA 631, and the pathogenic fungus C. tropicalis R2 CIP203. All determinations were carried out simultaneously three times under the same conditions. For each determination, control tests were realized without the corresponding treatment.

Effect of Temperature and Stability at Different pH

Cultures of the TN635 strain in MRS broth under anaerobic condition were maintained at different temperatures (25,30,37, and 45°C). The growth was followed by measuring the optical density (OD) at 600 nm. Sensitivity to heat of antimicrobial compounds was investigated by treating the 16-h culture supernatant of the TN635 strain growing at 30°C in water bath at 45, 70, 85, and 100°C for 90 min and 2 h and by autoclaving (20 min at 121°C). In order to determine the sensitivity of the bacteriocin to pH, the supernatant of the TN635 strain culture (30°C, 16 h incubation) was adjusted to pH levels ranging from 1 to 14 (intervals of 1.0) with sterile 1 N HCl or 1 N NaOH and kept at 4°C for 6 h. The treated supernatants were adjusted to pH 7.0 and tested for their antimicrobial activities as previously described.

Sensitivity to Different Enzymes and Surfactants

In order to determine the biological nature of the antimicrobial activity produced by the strain TN635, 1 ml of the cell-free supernatant was incubated for 3 h at 37°C in the presence of 1 mg/ml catalase (Boehringer). The untreated bacteriocin-containing cell-free supernatant served as control. Sensitivity to proteolytic, lipolytic and α-amylase enzymes of antimicrobial compounds was investigated by the addition of Trypsin, pronase E (Sigma), Proteinase K (Boehringer), lipase A (Sigma) and α-amylase (Sigma) at final concentration of 1 mg/ml to the culture supernatants of the TN635 strain (30°C, 16 h). The samples were incubated for 2 h at 37°C and immediately after, the residual activity was determined as described above. The surfactants used were Tween 20, Tween 80, urea, Triton X-100, sodium dodecyl sulfate (SDS), ethylenediaminetetraacetic acid (EDTA), and phenylmethanesulfonylfluoride (PMSF) which were added to the culture supernatants of the TN635 strain (30°C, 16 h) at a final concentration of 1% (v/v) and incubated at 30°C for 2 h. Surfactants at 1% in MRS broth were used as controls. All surfactants were prepared at 10% in water and filter-sterilized before use.

Effect of Organic Solvents

The culture supernatants of the TN635 strain (30°C, 16 h) were mixed with various organic solvents (ethyl acetate, isopropanol and methanol) at a final concentration of 50% (v/v). After incubation for 1 h at room temperature, the organic solvent was evaporated in a vacuum concentrator and the residual antimicrobial activity was determined.

Bacteriocin Purification, Molecular Weight Determination, and Zymogram Analysis

Strain TN635 was inoculated (1% v/v) into 900 ml (Duran bottles, containing 900 ml of MRS broth), and incubated without agitation at 30°C until early stationary phase (16 h) corresponding to maximum bacteriocin production. For bacteriocin purification, proteins of the crude supernatant fluid (CSF) were precipitated with 40, 60, and 80% saturated ammonium sulfate, gradually added by slow stirring during 4 h at 4°C. After centrifugation at 9,000×g for 30 min at 4°C, the precipitate was suspended in 10 ml of 20 mmol/l sodium phosphate buffer (pH 7.0) and desalted in centrifugal microconcentrators (Amicon, Inc.) with a 10-kDa membrane cutoff. The resulting solution (3.5 ml) was loaded on a column (70× 1.5 cm) of gel filtration Sephadex G-25 equilibrated with 20 mmol/l sodium phosphate buffer (pH 7). Elution of proteins was performed with the same buffer at 30 ml/h; 140 fractions (F1-F140) with 5 ml each were eluted from the Sephadex G-25 column and collected automatically. These 140 fractions detected using absorption measurements at 280 nm were fractioned into six samples (S1-S6): S1 (F1-F40), S2 (F41-F70), S3 (F71-F76), S4 (F77-F81), S5 (F82-F93), and S6 (F94-F140). The antimicrobial activity of the different collected fractions was tested using L. ivanovii BUG 496, S. enterica ATCC43972, and C. tropicalis R2 CIP203 as an indicator strains. The active fraction was then applied to a second round of purification by a reverse-phase HPLC method using a C18 column (300×4.6 mm) at a flow rate of 0.5 ml/min. Bacteriocin was eluted from the column with two mobile phases: A (99.9% water, 0.1% trifluoroacetic acid "TFA") and B (99.9% acetonitrile, 0.1% TFA); from 0 to 5 min (90% A, 10% B), from 5 to 30 min (50% A, 50% B), from 30 to 35 min (20% A, 80% B), from 35 to 50 min (10% A, 90% B) and from 50 to 60 min (90% A, 10% B). Proteins were monitored at 280 nm. The pooled biological active fraction obtained from HPLC elution was concentrated and stored at -20°C. The estimated molecular weight of the purified bacteriocin was determined by SDS-PAGE according to Laemmli [24] with 20% acrylamide gel. Protein concentration was measured using BSA as reference as described by Bradford [25]. The used protein marker is from BioLabs with a broad range of 2-212 kDa. To determine the apparent molecular mass of the bacteriocin, the gel was cut into two vertical parts after SDS-PAGE. The part of the gel containing the sample and the protein marker was stained with 0.25% Coomassie brilliant blue R-250 (BioRad), while the remaining part, containing only the sample, was washed in 10 mmol/l phosphate buffer (pH 7) for 4 h, then fixed and used for direct detection of antimicrobial activity by overlaying with LB soft agar containing 100 μl of a 5 h culture of L. ivanovii BUG 496.

Mode of Action of BacTN635

For this realization, we have used two indicator microorganisms: L. ivanovii BUG 496 and C. tropicalis R2 CIP203. Partially-purified BacTN635 (the fraction obtained from gel filtration chromatography and freeze-dried) at 400 AU/ml, was added to 200 ml LB culture of L. ivanovii BUG 496 and 200 ml YP10 of C. tropicalis R2 CIP203 at in early exponential phase (10 7 colony-forming units (CFU)/ml). The two indicator microorganisms growing in LB (L. ivanovii BUG 496) and YP10 (C. tropicalis R2 CIP203) in the absence of bacteriocin were used as controls. Changes in the turbidity of the cultures were recorded at an O.D. of the 600 nm and the number of CFU was determined by plaiting the samples on LB or YP10 agar.

Results and Discussion

Screening of LAB Strains Producing Bacteriocin

During previous works (data not shown), a collection of 54 LAB strains were isolated from several isolates (meat, fermented vegetables, and dairy products). We have tested these bacteria for their capacity to produce antimicrobial activities against the following indicator microorganisms: Lb. casei DSM 20011, L. ivanovii BUG 496, S. enterica ATCC43972, Fusarium sp., and C. tropicalis R2 CIP203. As shown in Table 1, different profiles of inhibition were observed. Nine strains (TN600, TN606, TN615, TN618, TN623, TN627, TN635, TN644, and TN653) were characterized by the broad-spectrum inhibition. These nine isolates were tested for their capacity to inhibit the growth of other microorganisms (Table 2). The largest spectrum of inhibition was showed by TN635 strain which inhibited all used indicator microorganisms. Moreover, the active molecule(s) of the TN635 strain presents the highest inhibitory effect against all tested microorganisms including the pathogenic Gram-positive bacteria (L. ivanovii BUG 496, S. aureus ATCC 6538, E. faecalis JH 2-2 and E. faecium ENSAIA 631), the four pathogenic Gram-negative bacteria (S. enterica ATCC43972, P. aeruginosa ATCC 49189, Hafnia sp. and Serratia sp.), and the pathogenic fungus C. tropicalis R2 CIP203. Since bacteriocins often have a narrow killing spectrum and inhibit only bacteria closely related to those from which they have been formed, bacteriocins from Gram-positive bacteria are generally not effective against Gramnegative bacteria and have no effect with yeasts and fungi [26,27]. The search for new bacteriocins with a wider spectrum of activity which can be used in human health, agriculture, and the food industry is being studied by several research groups. According to its large inhibitory spectrum, our finding, BacTN635 of the new isolated TN635 strain, may be of applied interest as food preservation and/or in the protection of human health.

Identification and Phylogenetic Analysis of TN635 Strain

Using the two specific primers: forward P1: 5′-AGAGTTTGATCCTGGCTCAG-3′ and reverse P2: 5′-ATGGCTCAGGACGAACGCT-3′ and the TN635 strain genomic DNA as template, we have amplified by PCR a DNA fragment having an expected size of approximately 1,500 pb. After purification, this DNA fragment was cloned in the pGEM-T Easy vector, yielding the pSS1 plasmid. Total nucleotide sequence of 1,540 pb (accession number FN252881) of the whole 16S rRNA gene of strain TN635 was determined in both strands. The alignment of this sequence through matching with reported 16S rRNA gene sequences in gene bank shows high similarity (97-99%) to the Lactobacillus 16S rRNA genes. The organism most similar to the new isolate TN635 strain was L. plantarum NRIC 0383 (Fig. 1). Based on the nucleotide sequence of the 16S rRNA gene of the TN635 strain and the phylogenetic analysis, we propose the assignment of our new isolate bacterium as L. plantarum sp. TN635 strain.

Growth and Bacteriocin Production

To test the effect of incubation temperature on cell growth and antimicrobial activity production, cultures of the L. plantarum sp. TN635 strain in MRS broth under anaerobic conditions were maintained at different temperatures (25, 30, 37, and 45°C). The growth was followed by measuring the OD at 600 nm and the antimicrobial activity was determined against the three indicator microorganisms: L. ivanovii BUG 496, S. enterica ATCC43972, and C. tropicalis R2 CIP203. Aliquots were withdrawn at 3 h time intervals. Obtained results show that the secretion of biological activity is correlated with biomass production. Highest growth and antimicrobial activity were obtained at 30°C (Fig. 2). We can deduce that the extracellularly antimicrobial activity was produced in the logarithmic growth phase and the production profile was a typical growth associated patter. The maximum antimicrobial activity was detected 16 h after incubation. This activity remains stable between 13 and 20 h and then gradually decreased. Enzymatic tests showed that the antimicrobial activity against the three tested indicator microorganisms, L. ivanovii BUG 496, S. enterica ATCC43972, and C. tropicalis R2 CIP203, of the supernatant culture of the L. plantarum sp. TN635 strain was not affected by the addition of catalase, indicating that the observed growth inhibition was not due to hydrogen peroxide production. In contrast, treatment with the proteolytic enzymes (Trypsin, pronase E, and Proteinase K) caused complete inactivation of the antimicrobial compounds, which therefore identified them as proteinaceous substances. The sensitivity of the inhibitory compounds to heat treatment showed that inhibitory activity was not significantly altered by boiling for 90 min showing that the antagonistic activity of the culture supernatant is heat-resistant. The activity of the sample was insensitive to lipase and αamylase, which eliminates the possibility that synthesized active compounds are included in the group of complex biologically active substances containing a lipid or carbohydrate component [28]. Concerning the sensitivity to pH, the supernatant culture of the Lb. plantarum sp. TN635 (30°C, 16 h incubation) was adjusted to pH levels ranging from 1 to 14 (intervals of 1.0). The obtained results show that bacteriocin activity was highest when the pH of the supernatant was between 3 and 11, with an optimum at pH 7. About 50% activity was maintained at pH 12 and was completely inactivated above pH 12. Exposure to surfactants caused about 15% inactivation of the antimicrobial activity for the SDS agent and about 40% for the other tested surfactants (Tween 20, Tween 80, Triton X-100, Urea, EDTA, and PMSF). Concerning the treatment with organic solvents (ethyl acetate, methanol, and isopropanol), no significant alteration of the BacTN635 activity was observed. BacTN635 was purified to homogeneity from a cell-free culture supernatant of Lb. plantarum sp. TN635 strain by a four-step protocol. Maximum antimicrobial activity was obtained when the cell-free culture supernatant was precipitated with 80% ammonium sulfate. One hundred forty fractions (F1-F140) with 5 ml each were eluted from a Sephadex G-25 column. These 140 fractions detected using absorption measurements at 280 nm were fractioned into six samples (S1-S6). After concentration, the antagonistic activity of each sample was essayed using L. ivanovii BUG 496, S. enterica ATCC43972, and C. tropicalis R2 CIP203 as indicator microorganisms. Only sample S5 (F82-F93) possesses inhibitory activity against the three tested cells (Fig. 3). Sample S5 was then applied to another round of purification using the HPLC technique. Three well-defined 4). Only the fraction of the peak P3 possesses an antimicrobial activity against the three tested microorganisms mentioned above and no activity has been observed for the two other fractions. The yield, activity, and purification fold of the BacTN635 of the four various purification steps were summarized in Table 3. SDS-PAGE analysis of the purified BacTN635, revealed a single band with an estimated molecular mass of approximately 4 kDa indicating that this bacteriocin had been purified to (Fig. 5a). Antibacterial activity determination against L. ivanovii BUG 496 strain, reveals a growth inhibitory zone at the same position than that visualized in the stained gel (Fig. 5b). During the last few years, a large number of new bacteriocins produced by LAB bacteria have been identified and characterized. However, a few bacteriocins produced by this species have been reported to be active against Gramnegative bacteria and particularly against fungi. Most of the described bacteriocins as antifungal agents from Lactobacillus are organic compounds or diketopiperazine derivatives with low molecular mass, lower than 1 kDa [29]. Too rare are the bacteriocins described from LAB bacteria with a molecular mass higher than 1 kDa and having antifungal activities [30]. The addition of partial purified BacTN635 (the fraction obtained from gel filtration chromatography and freeze-dried) at 400 AU/ml, to cells of L. ivanovii BUG 496 (3 h old) and C. tropicalis R2 CIP203 (10 h old) in their early logarithmic growth phase, resulted in a rapid decrease in the number of L. ivanovii BUG 496 viable cells (from 10 7 CFU/ml to less than 10 CFU/ml) over a period of 5 h (Fig. 6a). The optical density readings of this indicator microorganism remained constant since the addition of the BacTN635 (Fig. 6a).

These results indicate that the studied bacteriocin exhibits bactericidal effect against L. ivanovii BUG 496 strain. Concerning the C. tropicalis R2 CIP203, the optical density readings were very similar in presence and absence of BacTN635 (Fig. 6b). However, we notice an increase of the number of viable cells grown in the absence of the bacteriocin at Fig. 6 The effect of BacTN635 on the growth of L. ivanovii BUG 496. Optical density at 600 nm in absence (▲) and in presence (■) of BacTN635. Viable cell counts (CFU/ml) in absence (♦) and in presence (■) of BacTN635 (a). The effect of BacTN635 on the growth of C. tropicalis R2 CIP203. Optical density at 600 nm in absence (♦) and in presence (▲) of BacTN635. Viable cell counts (CFU/ml) in absence (□) and in presence (■) of BacTN635 (b) 40 h of growth (Fig. 6b). These data indicate that BacTN635 acts with a fungistatic effect against C. tropicalis R2 CIP203.

Conclusions

A new LAB strain has been selected for its antimicrobial activity against pathogenic Gramnegative bacteria and fungi. Based on the analysis of the nucleotide sequence (1,540 pb) of the whole 16S rRNA gene (accession no: FN252881) and the phylogenetic study, we propose the assignment of our new isolate bacterium as Lb. plantarum sp. TN635 strain.

The antimicrobial compound of this strain was determined as a proteinaceous substance.

The maximum bacteriocin-like substance (BacTN635) production (5,000 AU/ml) was recorded after a 16-h incubation in MRS medium at 30°C. BacTN635 was stable to heat and to treatment with surfactants and organic solvents. Highest antimicrobial activity was found between pH 3 and 11 with an optimum at pH=7. The purified BacTN635, revealed a single band with an estimated molecular mass of approximately 4 kDa. BacTN635 produced by Lb. plantarum sp. TN635 strain, may possess potential practical applications, since it was able to inhibit important Gram-negative pathogenic bacteria such as (S. enterica ATCC43972, P. aeruginosa ATCC 49189, Hafnia sp., and Serratia sp.) and pathogenic fungi such as C. tropicalis R2 CIP203. S. enterica is an important cause of human salmonellosis and food-poisoning associated with consumption of contaminated chicken eggs and poultry products [START_REF] Erich | Antimicrobial food additives, characteristics, uses, effects[END_REF]. P. aeruginosa is an opportunistic pathogen of humans. It causes urinary tract infections, respiratory system infections, gastrointestinal infections, and a variety of systemic infections, particularly in patients with severe burns and in cancer and AIDS patients who are immunosuppressed [START_REF] Wiblin | Nosocomial pneumonia[END_REF]. Serratia and Hafnia sp. are usually found in the intestinal tract. These pathogenic bacteria cause s wide variety of infections primarily pneumonia, wound, and urinary tract infections. Moreover, it should be noted that the number of patients with fungal infections has been rising in recent years. In addition to the species Candida albicans and Candida stellatoidea, C. tropicalis is one of the significant pathogenic yeasts in humans belonging to the genus Candida [START_REF] Kobayashi | [END_REF].

Fig. 1

 1 Fig. 1 Phylogenetic trees derived from 16S rDNA sequence of L. plantarum sp. TN635 strain. All the sequences used here were from LAB type strains

Fig. 2

 2 Fig. 2 BacTN635 production during growth of L. plantarum TN635 in MRS broth at 30°C. (filled square) Optical density at 600 nm; activities of BacTN635 against C. tropicalis R2 CIP203 (filled upright triangle); against S. enterica ATCC43972 (filled circle), and against L. ivanovii BUG 496 (filled diamond) were measured by diameter (mm) of zone of inhibition

Fig. 3 Fig. 4

 34 Fig. 3 Purification of BacTN635 by cation-exchange chromatography using Sephadex G-25 monitoring by absorbance at 280 nm (filled square)

Fig. 5

 5 Fig. 5 Electrophoretic and zymogram analyses of the purified BacTN635. Coomassie brilliant blue R-250 stained SDS-PAGE gel. Lane 1 molecular mass markers; lane 2 purified BacTN635 (a). Portion of the renaturated SDS-PAGE, overlaid with LB soft agar containing L. ivanovii BUG 496 (b)

Table 1

 1 Inhibitory spectrum (zone of inhibition/mm) of the isolated 54 LAB (TN600-TN653) against Lb. casei DSM 20011, L. ivanovii BUG 496, S. enterica ATCC43972, Fusarium.sp, and C. tropicalis R2 CIP203: L (listeria); Lb (Lactobacillus); C (Candida).

	Isolates	Indicator microorganisms
		Lb. casei	L. ivanovii	S. enterica	Fusarium sp.	C. tropicalis
		DSM 20011	BUG 496	ATCC43972		R2 CIP203
	TN600	6	12	22	14	8
	TN601	-	7	-	-	-
	TN602	-	-	-	-	-
	TN603	8	-	-	-	6
	TN604	-	-	-	8	8
	TN605	10	16	7	7	-
	TN606	7	18	16	16	9
	TN607	6	5	-	-	-
	TN608	8	8	8	-	-
	TN609	9	-	7	8	-
	TN610	-	13	15	-	-
	TN611	-	-	-	-	-
	TN612	-	-	-	-	-
	TN613	9	17	10	-	8
	TN614	-	6	7	8	15
	TN615	7	6	18	19	5
	TN616	8	-	-	16	-
	TN617	-	-	-	18	-
	TN618	8	14	16	18	9
	TN619	8	7	-	10	-
	TN620	7	16	-	-	-
	TN621	6	-	-	20	-
	TN622	-	7	5	-	6
	TN623	7	20	18	17	19
	TN624	8	8	7	7	-
	TN625	7	6	17	-	-
	TN626	-	-	-	-	-
	TN627	8	9	12	14	10
	TN628	-	-	6	16	-
	TN629	7	-	-	6	-
	TN630	9	9	-	6	6
	TN631	-	18	17	9	-
	TN632	-	8	8	-	-
	TN633	9	-	-	-	7
	TN634	6	-	7	7	-
	TN635	9	22	21	23	21
	TN636	9	6	-	7	-
	TN637	8	7	-	15	-
	TN638	7	-	7	16	-
	TN639	-	7	7	18

Table 1 (

 1 continued).

	Isolates	Indicator microorganisms
		Lb. casei	L. ivanovii	S. enterica	Fusarium sp.	C. tropicalis
		DSM 20011	BUG 496	ATCC43972		R2 CIP203
	TN640	7	7	8	6	-
	TN641	-	16	17	-	15
	TN642	6	-	-	16	-
	TN643	-	6	7	17	6
	TN644	7	16	6	22	6
	TN645	6	7	8	-	-
	TN646	-	-	-	18	7
	TN647	7	-	6	8	-
	TN648	8	8	-	18	-
	TN649	-	-	8	16	6
	TN650	-	16	-	17	17
	TN651	6	-	7	7	6
	TN652	-	8	-	12	7
	TN653	7	16	17	18	8

Table 2

 2

	Indicator strains	TN600 TN606 TN615 TN618 TN623 TN627 TN635 TN644 TN653
	Gram-positive bacteria
	M. luteus LB 14110	23	14	6	14	14	6	23	14	11
	S. aureus ATCC 6538	12	15	16	14	9	16	22	21	8
	L. ivanovii BUG 496	12	18	6	16	20	9	22	16	16
	E. faecalis JH 2-2	6	18	8	-	15	16	22	7	8
	E. faecium ENSAIA 631	6	14	7	-	14	14	21	8	6
	Gram-negative bacteria
	E. coli ATCC 8739	5	22	13	15	15	23	22	13	22
	S. enterica ATCC43972	22	16	18	16	18	12	21	6	17
	P. aeruginosa ATCC 49189	22	16	6	9	14	9	22	8	9
	Hafnia sp.	5	15	6	13	24	6	24	5	7
	Serratia sp.	12	6	12	15	21	7	23	8	9
	LAB
	Lb. Casei DSM 20011	6	7	7	8	7	8	9	7	7
	Lb. delbrueckii DSM 20081	-	6	8	-	-	9	9	6	-
	Lb. Sakei 2525	-	6	7	-	7	6	9	-	-
	Lc. lactis ATCC 11454	-	-	6	5	6	7	9	-	9
	Lc. lactis cremoris DSM 11603 -	-	5	7	7	9	8	-	8
	Fungi
	Fusarium sp.	14	16	19	18	17	14	23	22	18
	C. tropicalis R2 CIP203	8	9	5	9	19	10	21	6	8

Inhibitory spectrum (zone of inhibition/mm) of TN600, TN606, TN615, TN618, TN623, TN627, TN635, TN 644 and TN653 strains against Gram-positive and Gram-negative bacteria, LAB and fungi: L (listeria); Lb (Lactobacillus); Lc (Lactococcus); C (Candida).

Table 3

 3 Purification of BacTN635 produced by Lactobacillus plantarum sp. TN635 strain.

	Step	Volume	Total activity	Total	Specific activity	Purification	Yield
		(ml)	(AU) a	protein (mg)	(AU/mg)	fold	%
	Culture supernatant	900	45×10 5 2,160	2,083	1	100
	Ammonium sulfate precipitation	50	5.2×10 5	52.5	9,904	4.75	11.55
	Microconcentrators	32	3.32×10 5	23.2	14,310	6.87	7.38
	Gel filtration	3.5	2.25×10 5	1.54	146,104	70.14	5
	HPLC	0.7	1.125×10 5	0.57	197,368	94.75	2.5
	a Antibacterial activity (in arbitrary units [AU]) was assayed by agar well diffusion assay using L. ivanovii
	BUG 496 as an indicator strain

Acknowledgments This work was supported by the Tunisian government (Contract Program CBS-LEMP) and the CMCU project (2006-2008) No 06/S 0901 "MELLOULI/AIGLE". We are grateful to Dr. M. Ferchichi for providing the indicator bacteria.