Jean-Daniel Boissonnat

Kunal Dutta

Arijit Ghosh

Sudeshna Kolay

Tight Kernels for Covering with Points and Polynomials

Keywords: 1998 ACM Subject Classification F.2.2 Nonnumerical Algorithms and Problems Incidence Geometry, Tight Kernel Lower bounds, Hyperplanes, Bounded degree polynomials Digital Object Identifier 10.4230/LIPIcs.xxx.yyy.p

The Point Hyperplane Cover problem in R d takes as input a set of n points in R d and a positive integer k. The objective is to cover all the given points with a set of at most k hyperplanes. The D-Polynomial Points Cover problem in R d takes as input a family F of D-degree polynomials from a vector space R in R d , and determines whether there is a set of at most k points in R d that hit all the polynomials in F. Here, a point p is said to hit a polynomial f if f (p) = 0. For both problems, we exhibit tight kernels where k is the parameter. We also exhibit a tight kernel for the Projective Point Hyperplane Cover problem, where the hyperplanes that are allowed to cover the points must all contain a fixed point, and the fixed point cannot be included in the solution set of points.

Introduction

A set system is a tuple (U, F) where U is a universe of n elements and F is a family of m subsets of U . A set system is also referred to as a hypergraph, with the elements in the universe U named as vertices and the subsets in F named as hyperedges. A hyperedge is said to cover a vertex if the vertex belongs to the hyperedge. Similarly a subfamily F of hyperedges is said to cover a subset V of vertices if for each vertex v ∈ V there is a hyperedge h ∈ F such that h covers v. A vertex is said to hit a hyperedge if the vertex belongs to the hyperedge, and a subset V of vertices is said to hit a subfamily F of hyperedges if for each hyperedge h ∈ F there is a vertex v ∈ V that belongs to h. The Set Cover and Hitting Set problems are two of the most well-studied problems in computer science. For the Set Cover problem, the input is a set system (U, F) and a positive integer k. The objective is to determine whether there is a subfamily F ⊆ F with at most k subsets, such that F covers all the elements in U . Such a family F is referred to as a solution family or a covering family. The Hitting Set problem can be thought of as a dual problem. Here, the input is the same as in Set Cover. However, now the objective is to determine whether there is a subset S ⊆ U of size at most k, such that for each hyperedge h ∈ F h ∩ S = ∅. Such a set S is referred to as a solution set.

These problems are part of the original 21 problems NP-complete problems posed by Richard Karp [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. However, the numerous applications for these problems inspires researchers to design algorithms to find solutions with reasonable efficiency, for different measures of efficiency. For Set Cover, the best approximation factor is O(log n) [START_REF] Vijay | Approximation algorithms[END_REF]. It was shown in [START_REF] Dinur | Analytical approach to parallel repetition[END_REF] that log n is the best possible approximation factor unless P=NP. Since Hitting Set is just a reformulation of the Set Cover problem, the same approximation factors hold. The d-Hitting Set problem, where the size of each subset in F is exactly d, is known to be APX-hard [START_REF] Alimonti | Some apx-completeness results for cubic graphs[END_REF], consequent to results obtained for the special case of the Vertex Cover problem where d = 2.

Set Cover and Hitting Set have been studied in parameterized complexity. In parameterized complexity, we say that a problem is fixed parameter tractable (FPT) with respect to a parameter k, if there is an algorithm that takes an instance of size n of the problem, and solves the problem in f (k).n O (1) time, where f is a computable function. For a brief introduction to parameterized complexity please refer to the Preliminaries. For further details please refer to [START_REF] Downey | Parameterized Complexity[END_REF][START_REF] Flum | Parameterized Complexity Theory[END_REF][START_REF] Cygan | Parameterized algorithms[END_REF]. The d-Hitting Set problem, parameterized by the solution size k, is known to be FPT, with a tight O(k d )-sized kernel [START_REF] Dell | Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses[END_REF] under standard complexity theoretic assumptions. In this paper, unless otherwise mentioned, all variants of Hitting Set and Set Cover are parameterized by k. The Set Cover and the general Hitting Set problems are W [START_REF] Alimonti | Some apx-completeness results for cubic graphs[END_REF]-hard, and are not expected to be FPT.

Interestingly, the instances of many real world applications of these two notoriously hard problems have inherent structure in them. With the hope of designing efficient algorithms for such instances by exploiting their structural information, numerous variants of Set Cover and Hitting Set have been studied. A very natural extension in this field of study is to assume geometric structure on the instances. In recent years, there has been a lot of attention to study geometric variants of both the problems.

The Point Line Cover is a example of a geometric variant of Set Cover. Here the universe is a set of points in R 2 and the the hyperedges are the maximal sets of collinear points in the input. Point Line Cover is known to be FPT [START_REF] Langerman | Covering things with things[END_REF]. Kratsch et. al. showed in [START_REF] Kratsch | Point line cover: the easy kernel is essentially tight[END_REF] that the problem has a tight polynomial kernel with O(k 2 ) points. In [START_REF] Afshani | Applications of Incidence Bounds in Point Covering Problems[END_REF], several generalizations of the Point Line Cover problem were studied -the universe is a set of points in a Euclidean space and the family of hyperedges are geometric structures like hyperplanes, spheres, curves, etc. Geometric variants of Set Cover have been studied in [START_REF] Ashok | Unique covering problems with geometric sets[END_REF][START_REF] Ashok | Multivariate complexity analysis of geometric red blue set cover[END_REF].

The results in [START_REF] Kratsch | Point line cover: the easy kernel is essentially tight[END_REF] also imply parameterized results for Line Point Cover, where the universe is a set of lines in R 2 and the objective is to find at most k points in R 2 to hit the universe of lines. This problem is FPT and has a tight kernel with O(k 2 ) lines. Other geometric variants of the Hitting Set problem has been studied in parameterized complexity [START_REF] Dom | Parameterized complexity of stabbing rectangles and squares in the plane[END_REF][START_REF] Giannopoulos | Parameterized complexity of geometric problems[END_REF][START_REF] Heggernes | Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization[END_REF]. Bringmann et al. [START_REF] Bringmann | Hitting set for hypergraphs of low vc-dimension[END_REF] studied the problem for set systems with bounded VC dimensions. They showed that there are set systems with VC dimension as low as 2, where both the Hitting Set, and consequently the Set Cover problem are W [START_REF] Afshani | Applications of Incidence Bounds in Point Covering Problems[END_REF]-hard. This gives an interesting dichotomy, since they also show that when the VC dimension of the set system is 1, then the Hitting Set problem is in P.

In this paper, we consider two parameterized variants.

Input: A set F of n D-degree polynomials from a specified vector space R of D-degree polynomials in R d , a positive integer k. Question: Is there a set S of points in R d such that for each polynomial f ∈ F, there is a point p ∈ S with f (p) = 0?

Please refer to the Preliminaries for the definition of a D-degree polynomials. Both the problems are NP-hard, because of the NP-hardness of Point Line Cover [START_REF] Megiddo | On the complexity of locating linear facilities in the plane[END_REF]. Parameterized by k, we study the parameterized complexity of these problems.

Our results

Extending the results of Kratsch et. al. [START_REF] Kratsch | Point line cover: the easy kernel is essentially tight[END_REF], we show that Point Hyperplane Cover and Projective Point Hyperplane Cover in R d have tight polynomial kernels with O(k d ) and O(k d-1 ) points, respectively. The highlight of this proof, given any positive integer n, is the construction of a set P of n points in R d in general position such that the family of hyperplanes, defined by any d points from P, do not have too many hyperplanes intersecting at a point outside P. This is crucial for a many-one reduction from d-Hitting Set, that results in lower bounds on the size as well as the number of points in a kernel under complexity theoretic assumptions.

Our main contribution is to show tight polynomial bounds for kernel sizes for D-Polynomial Point Cover in R t , for a large family of vector spaces R of D-degree polynomials. For more details on the characterization of R, please see the Preliminaries. The vector space of hyperplanes, spheres and ellipses are among natural vector spaces of polynomials that are covered by this characterization. Therefore, our techniques provide a general framework for proving tight kernels for covering problems, as one can get a tight bound for many families directly.

Our proof strategy is to use the Veronese mapping to transform the space of points and polynomials to a higher dimensional space, where the polynomials transform into hyperplanes and point-polynomial incidences are preserved. The upper bound on the kernel size comes directly from the Veronese mapping. For the lower bound, we show that points in general position with respect to polynomials transform to an equal-sized set of points in general position with respect to hyperplanes in the image space. Using this fact, we construct hard instances of D-Polynomial Point Cover.

Note that the results of Point Hyperplane Cover imply that Hyperplane Point Cover in R d also has a tight kernel with Ω(k d ) hyperplanes. Similarly, we can show that Projective Hyperplane Point Cover has a tight kernel with Ω(k d-1 ) hyperplanes.

Due to paucity of space, we have moved some of the proofs to the Appendix.

] := {f (X 1 , . . . , X d ) ∈ R[X 1 , X 2 , . . . , X d ] | deg(f ) ≤ D}. Observe that Poly D [X 1 , . . . , X d ]
is a vector space over R with the following monomials as the basis

X i1 1 . . . X i d d | 0 ≤ d j=1 i j ≤ D and X i1 1 . . . X i d d | 0 ≤ d j=1 i d ≤ D = D+d D .
For ease of notation, we define the vector X = (X 1 , . . . , X d ).

Given a polynomial f and a point p, the point hits the polynomial if f (p) = 0. In the same situation, the polynomial is said to cover the point. Definition 1. A vector space R of polynomials in R d are said to be α-good if for any positive integers b, m the following conditions hold: 1. In O(1) time we can compute a set of b points in R d such that the set is in general position with respect to R.

2. Given a d-dimensional m × • • • × m grid in R d , each polynomial in R contains at most m d-α
vertices of the grid, where α > 0.

Hyperplanes, spheres, ellipses and many other natural vector spaces of polynomials are α-good.

General position in Geometry. An i-flat in R d is the affine hull of i+1 affinely independent points. The dimension of a (possibly infinite) set of points P, denoted as dim(P), is the minimum i such that the entire set P is contained in an i-flat of R d [START_REF] Langerman | Covering things with things[END_REF]. We use the term hyperplanes interchangeably for (d -1)-flats. A set P of points in R d is said to be in general position with respect to hyperplanes, if for each i-flat, i ≤ d -1, in R d there are at most i + 1 points from P lying on the i-flat.

Consider, for i ≤ d -1, a family F of i-flats such that there is a point p that belongs to all the i-flats in F. Then a set P ∈ R d \ {p} of points is said to be in general position with respect to F if each i-flat contains at most i points from P lying on the i-flat. This is called general position in projective geometry.

Similarly, we can define the notion of general position (similarly, projective general position) with respect to multivariate polynomials. Let R be a subvector space of Poly D [X], defined by a basis {f 1 (X), . . . , f b (X), 1} (or by a basis {f 1 (X), . . . , f b (X)} with deg(f i ) > 0). A subset of points are said to be in general position (or projective general position) with respect to the vector space R of polynomials if no more than b points (b -1 points) from the subset satisfy any equation of the form f (X) :

= b i=1 λ i f i (X) + λ b+1 = 0 (f (X) := b i=1 λ i f i (X) = 0)
, where all the λ j ∈ R and not all the λ j 's can be zero simultaneously.

Veronese mapping.

In this paper, one of our strategies for generalizing our results is to convert D-Point Polynomial Cover in R d to Point Hyperplane Cover (or Projective Point Hyperplane Cover) in R b by using a variant of Veronese mapping [START_REF] Matoušek | Lectures on discrete geometry[END_REF] from R d → R b . The Veronese mapping of a vector space R of D-degree polynomials, with a basis {f 1 (X), . . . , f b (X), 1} (or with a basis {f 1 (X), . . . , f b (X)} where deg(f i ) > 0), will be as the following: Φ

R : R d → R b , where Φ R (X) = (f 1 (X), . . . , f b (X)) where X = (X 1 , . . . , X d ). Observe that if p = (p 1 , . . . , p d ) satisfies the equation f (X) := b i=1 λ i f i (X) + λ b+1 = 0 (or the equation f (X) := b i=1 λ i f i (X) = 0) then Φ R (p) will also satisfy the linear equation b j=1 λ j Z j + λ b+1 = 0 (or the equation b j=1 λ j Z j = 0), on the variable vector Z = (Z 1 , . . . , Z b ).
In other words, for any set of points P in R d and F, the incidences between P and R and incidences between Φ R (P) and hyperplanes in R b (or the hyperplanes passing through the origin in R b ) are preserved under the mapping Φ R . Also, observe that there is a bijection between polynomials in R and the hyperplanes in R b (or hyperplanes passing through the origin in R b ). This transformation from polynomials to hyperplanes is also referred to as linearization.

Parameterized Complexity. The instance of a parameterized problem/language is a pair containing the actual problem instance of size n and a positive integer called a parameter, usually represented as k. The problem is said to be in FPT if there exists an algorithm that solves the problem in f (k)n O (1) time, where f is a computable function. The problem is said to admit a g(k)-sized kernel, if there exists an polynomial time algorithm that converts the actual instance to a reduced instance of size g(k), while preserving the answer. When g is a polynomial function, then the problem is said to admit a polynomial kernel. A reduction rule is a polynomial time procedure that changes a given instance I 1 of a problem Π to another instance I 2 of the same problem Π. We say that the reduction rule is safe when I 1 is a Yes instance of Π if and only if I 2 is a Yes instance. Readers are requested to refer [START_REF] Cygan | Parameterized algorithms[END_REF] for more details on Parameterized Complexity.

Lower bounds in Parameterized Algorithms.

There are several methods of showing lower bounds in parameterized complexity under standard assumptions in complexity theory. In this paper we require a lower bound technique given by Dell and Melkebeek [START_REF] Dell | Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses[END_REF]. This technique links kernelization to oracle protocols. Definition 2. Given a language L, an oracle communication protocol for L is a two-player communication protocol. The first player gets an input x and can only execute computations taking time polynomial in |x|. The second player is computationally unbounded, but does not know x. At the end of the protocol, the first player has to decide correctly whether x ∈ L. The cost of the protocol is the number of bits of communication from the first player to the second player. Proposition 1. [START_REF] Dell | Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses[END_REF] Let d ≥ 2 be an integer, and be a positive real number. If co-NP NP/poly, then there is no protocol of cost O(n d-) to decide whether a d-uniform hypergraph on n vertices has a d-hitting set of at most k vertices, even when the first player is co-nondeterministic.

Note that this implies that for any d ≥ 2 and any positive real number , if co-NP NP/poly, then there is no kernel of size O(k d-) for d-Hitting Set. In general, a lower bound for oracle communication protocols for a parameterized language L gives a lower bound for kernelization for L. Kernels: size vs number of elements. In literature, a lower bound on the kernel means the lower bound on the size of the kernel, but not necessarily on the number of input elements in the kernel. Kratsch et. al [START_REF] Kratsch | Point line cover: the easy kernel is essentially tight[END_REF] were one of the first to study lower bounds in terms of the number of input elements in the kernel. They used the results of Dell and Melkebeeke [START_REF] Dell | Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses[END_REF] along with results in two dimensional geometry to build a new technique to show lower bounds for number of input elements in a kernel for a problem. In this paper, we have adhered to the general convention by saying that a kernel has a lower bound on its size if it has a lower bound on its representation in bits, while explicitly mentioning the cases where the kernel has a lower bound on the number of input elements. From now on we will be showing lower bounds for Hyperplane Point Cover. The proof strategy is the same as that in [START_REF] Kratsch | Point line cover: the easy kernel is essentially tight[END_REF]. For this, we construct for each positive integer n and each d, a set of n points in R d with some special properties. This construction is more involved than in the case of Point Line Cover. Proof. The set P is built inductively. When n = d, it is the base case and the construction follows trivially. Assume that for d ≤ t < n, we have constructed a point set P t that satisfies the above conditions. As in [START_REF] Kratsch | Point line cover: the easy kernel is essentially tight[END_REF], our goal will be to extend the point set P t by one point. We will show that points forbidden to be added to the set P t will lie on bounded number of hyperplanes and we will call these hyperplanes forbidden hyperplanes. Observe that the number of forbidden hyperplanes arising due to conditions (1) and ( 2) is bounded by O(t d ) and O(t d 2 -1 ).

Unlike the case when d = 2, it is harder to bound the number of forbidden hyperplanes due to condition (3). Let q ∈ R d be a point where the point set P = P t ∪ {q} satisfies conditions (1) and ( 2), but not condition (3). We will call such a point q a forbidden point. Let H be the family of hyperplanes defined by each set of d points from P . Let H 1 , . . . , H d+1 be a set of d + 1 hyperplanes in H such that they intersect at point s with s ∈ R d \ P . Observe that since the point set P t satisfied all the three conditions, q will lie on at least 1 hyperplane and at most d hyperplanes from the family {H 1 , . . . , H d+1 }. Suppose q was contained in d hyperplanes from the family, then q = s as P satisfies condition [START_REF] Alimonti | Some apx-completeness results for cubic graphs[END_REF]. Therefore, we assume that q lies in at least 1 and at most d -1 hyperplanes from the family {H 1 , . . . , H d+1 }. Without loss of generality, assume that q lies on the hyperplanes {H 1 , . . . , H r } . Let A r-1 denote the (r -1) dimensional affine plane ∩ d+1 i=r+1 H i . For j ∈ [r], let the hyperplanes H j be generated by the set {q, p j 1 , . . . , p j d-1 } ⊂ P . The point s also belongs to A r-1 . Since we are interested in understanding where the forbidden point q can lie, we try to understand the inverse problem where A r-1 , s, and points p j (for all ∈ [d -1]) are fixed and q is the variable point such that ∩ d+1 i=1 H i = s ∈ R d \ P . Using elementary Euclidean geometry, we get that q lies on a d -r dimensional affine plane passing through s and the slope of the affine plane depends only on A r-1 and the points p j , j ∈ [r] and ∈ [d -1]. This implies that as we vary s on A r-1 we will span a hyperplane containing A r-1 and which only depends on the points p j , j ∈ [r] and ∈ [d -1]. Therefore, once the hyperplanes H r+1 till H d+1 and the point set

{p j t |j ∈ [r], ∈ [d -1]
} are fixed, the point q will lie on a unique hyperplane. This implies that the number of forbidden hyperplanes due to condition (3) is bounded by O(t d 2 +d-1 ).

As we have a upper bound on the number of forbidden hyperplanes, we can now use the trick of Kratsch Proof. We give a reduction from d-Hitting Set. Let (U, F, k) be an instance of d-Hitting Set. First we reduce this instance to the following instance (U , F , dk) where: 1. For each v ∈ U we make d copies {v1 , v 2 , . . . , v d }. We also refer to the set {v 1 , v 2 , . . . , v d } as the row of v. Next, we give a reduction from the instance (U , F, dk) of d-Hitting Set to a instance of Hyperplane Point Cover. The correctness of this reduction shows that there is a polynomial time reduction from d-Hitting Set to Hyperplane Point Cover such that the parameter transformation is linear.

2. U = U 1 U 2 . . . U d such that for each i ∈ {1, . . . , d} U i = {v i |v ∈ U }. 3. F ⊂ F 4.
We construct the following instance of Hyperplane Point Cover: 1. Using Lemma 4, we construct a a set P of dn points, same as the number of elements in the universe U . We arbitrarily assign each element of U to a unique point in P. 2. For a hyperedge f ∈ F , let H f be the hyperplane defined by the d points contained in f .

The set H is the family of such hyperplanes. Before we prove this claim, we need the following claim regarding a solution set with minimum number of points outside P.

Claim 3 ( ).

Let Q be a minimum sized set of points that covers all the hyperplanes in H. Also, assume that Q has the minimum possible points in Q \ P. Moreover, let q ∈ Q \ P that covers the minimum number of hyperedges uniquely. We assume that there is no other set Q of the same size as Q, with |Q \ P| = |Q \ P and with a q ∈ Q \ P that covers strictly less number of hyperedges uniquely in Q than q does in Q. Then for any element v ∈ U \ Q, at most d -1 hyperedges containing v can have no intersection with Q.

Proof of Claim 2. The forward direction is simple. A solution for (U, F, k) gives a solution for (U , F, dk) as described in Claim 1. By the correspondence of the vertices in U with the points in P, we obtain an equal sized solution set for (H, dk).

On the other hand, suppose (H, dk) be a Yes instance. Let Q be a solution as described in Claim 3. We contradict the choice of Q by exhibiting a set Q that is of the size at most that of Q and with strictly less bad points, or that that there is a point q ∈ Q that covers strictly less number of hyperedges uniquely with respect to Q than q does with respect to Q.

As argued in the proof of Claim 3, by the choice of Q, each point in Q \ P can uniquely cover at least 2 and at most d hyperplanes in H. Let q ∈ Q \ P be a point that covers minimum number of hyperedges uniquely. Such a point is called a "bad" point. Let H f ∈ H be a hyperplane uniquely covered by q. By definition, H contains a set of d points from P and corresponds to a hyperedge f ∈ F . We call such a hyperplane and its corresponding hyperedge as a "bad" hyperplane and a "bad" hyperedge respectively. Similarly, the subsystem corresponding to the hyperedge f is also called a bad subsystem.

First, suppose the hyperedge Since we considered an arbitrary q ∈ Q \ P, this implies that in a subsystem F 1 for any bad hyperedge f 1 , there are two rows where except for the vertices contained in f 1 , all other vertices are in Q. We call such rows as "covered" rows. Let one such covered row correspond to the vertex x ∈ U and let the copy of x in f be x i . Let the other covered row correspond to a vertex z 1 ∈ U . Then, by Claim 3, x i can belong to at most d -2 other bad hyperedges {f 2 , f 3 , . . . , f d-1 }. Thus there are at most d -1 bad subsystems {F 1 , F 2 , F 3 , . . . , F d-1 } that correspond to the vertex x ∈ U . Each such subsystem has two covered rows, one of which is the row corresponding to x. For the subsystem F t , t ∈ [d -1] let the other covered row be corresponding to z t ∈ U . We give a one-one map φ from the vertices {z 1 , z 2 , . . . , z d-1 } to the copies {x j |j ∈ [d], j = i}. Given j ∈ [d -1], we delete φ(z j ) from Q and include the copy of z j that belongs to f j into Q. This way we form a new subset Q . First we show that Q covers all hyperedges in F . The hyperedges that might not be covered by Q are hyperedges that contain a vertex from {x j |j ∈ [d], j = i}. Since for each t ∈ [d -1] all copies of z t belong to Q , all hyperedges of the subsystem F t are covered by Q . In fact, no hyperedge in the subsystem F t is bad. Suppose there is a x j ,j = i and a hyperedge f = {x j , u 1 , . . . , u d-1 }, for some {u 1 , . . . , u d-1 } ⊂ U , such that Q does not cover f . Then the hyperedge f = {x i , u 1 , . . . , u d-1 } is either not covered or covered by a bad point from Q \ P. As argued before, this hyperedge cannot belong to any subsystem

f is f i1,i2,...,i d = {v i1 j1 , v i2 j2 , . . . , v i d j d }, for a subset {v j1 , v j2 , . . . , v j d } ⊂ U ,
F t , t ∈ [d -1].
This implies that there are at least d bad hyperedges containing x i with respect to Q, which contradicts Claim 3. Thus, all hyperedges in F are covered by Q .

Moreover, by the arguments above, all the bad hyperedges containing a copy of x ∈ U , including f 1 , are no longer bad hyperedges with respect to Q . On the other hand, any hyperedge not belonging to the subsystems {F 1 , F 2 , F 3 , . . . , F d-1 } and that was covered by a point p in Q is still covered by p in Q . Thus, the newly constructed Q has the size at most that of Q, but where q uniquely covers strictly less number of bad hyperedges with respect to Q than it did with respect to Q. Therefore, we contradict the choice of Q.

This implies, that there is a k-sized solution for (H, dk) that only contains points from P. Therefore, the corresponding vertices will be a solution for (U , F, dk). By Claim 1, this We define orientation < u 1 , u 2 , . . . , u d , u d+1 >= sgndetM (< u 1 , u 2 , . . . , u d , u d+1 >). Here, det is the determinant function and sgn is the sign function.

Observation 1 ( ). orientation < u 1 , u 2 , . . . , u d , u d+1 >= 0 if and only if the points are not in general position.

Given a set P of points, and an arbitrary ordering P of P, an order type of P is a function that maps each ordered set of d + 1 points to their orientation. Two sets of points P and Q are said to be combinatorially equivalent if there is an ordering P of P and an ordering Q of Q such that the order types of the two ordering are the same.

As proved in [START_REF] Kratsch | Point line cover: the easy kernel is essentially tight[END_REF], two combinatorially equivalent instances are also equivalent with respect to the problem of Point Hyperplane Cover in in R d .

Observation 2. Let P and Q be two sets of points that are combinatorially equivalent. Then (P, k) is a Yes instance of Point Hyperplane Cover if and only if (Q, k) is a Yes instance of Point Hyperplane Cover.

The proof of this observation is same as the proof of Lemma 2.1 in [START_REF] Kratsch | Point line cover: the easy kernel is essentially tight[END_REF].

This leads us to the the next lemma, which follows from Theorem 3.2 in [START_REF] Kratsch | Point line cover: the easy kernel is essentially tight[END_REF] and Theorem 4.1 of [START_REF] Alon | The number of polytopes, configurations and real matroids[END_REF]. We also obtain lower bounds on the number of points in the kernel for Projective Point Hyperplane Cover. This also implies a lower bound in the number of hyperplanes in a kernel for Projective Hyperplane Point Cover.

Covering Polynomials of bounded degree with Points

In this section, we consider the D-Polynomial Point Cover problem and show that this problem is equivalent to Hyperplane Point Cover in a higher dimensional space. We utilize this to give tight polynomial kernels for D-Polynomial Point Cover, when the underlying vector space of polynomials is α-good.

Recall that in D-Polynomial Point Cover, a vector space R of D-degree polynomials in Poly D [X 1 , X 2 , . . . , X d ] are specified. The input is a set F of n polynomials from R and the objective is to find at most k points in R d that cover all the input polynomials.

We utilize the Veronese mapping from a vector space of D-degree polynomials to the subsystem of hyperplanes in Euclidean space R b . Such a mapping is a bijective mapping between the vector space of D-degree polynomials and the hyperplanes in R b . However, the mapping need not be an onto mapping from R d to R b . Let Ver R (R d ) be the image of R d under the Veronese mapping Φ R . Thus, Ver R (R d ) ⊆ R b . We show that the Hyperplane Point Cover problem for an α-good vector space R in R b when the solution set is restricted to belonging to Ver R (R d ), does not have a O(k b-) kernel unless co-NP ⊆ NP/poly. Before this, we require a few results regarding the behaviour of points under the Veronese mapping.

First, we show that a set of n points in R d that are in general position with respect to R are mapped to a set of n points in R b with respect to hyperplanes in R b . Claim 4. Let P be a set of points in R d , and R be a subspace of Poly D [X 1 , . . . , X d ] with a basis {f 1 (X), . . . , f b (X), 1} where X = (X 1 , . . . , X d ). 1. If the set P is in general position with respect to the polynomial family R then the image Φ R (P), under the Veronese mapping Φ R , is a |P|-sized set in general position with respect to hyperplanes in R b . 2. Let S = {q 1 , . . . , q } ⊆ Φ R (P) be in general position with respect to hyperplanes in R b .

Then the set S = {p 1 , . . . , p }, where p i ∈ Φ -1 R (q i ) ∩ P, will be a |S|-sized set in general position with respect to R.

Proof. 1. First, observe that if the map Φ R is injective on P then the result will directly follow. However, in general, the map Φ R need not be an injective mapping on an arbitrary set of n points in R d . We show that Φ R is injective when restricted to P if P is in general position with respect to R. To reach a contradiction, let Φ R (p 1 ) = Φ R (p 2 ) where p 1 , p 2 ( = p 1 ) ∈ P. Let S ⊆ P be of size b + 1 and p 1 , p 2 ∈ P. Observe that the set Φ R (S) will have less than b + 1 points and this will imply that there exists a hyperplane b i=1 λ i Z i + λ b+1 = 0 on which the set Φ R (S) will lie. But this implies that the polynomial b i=1 λ i f i (X) + λ b+1 = 0 will be satisfied by all the points in S. Thus, we have reached a contradiction from the fact that the point set P was in general position.

2.

The second part of the Claim follows directly from the construction of the mapping Φ R .

Next, for each n we construct a set of n points that satisfy the conditions of Lemma 4 and belong to Ver R (R d ), where R is α-good. This construction is mainly done in R d and follows exactly along the lines of the proof of Lemma 4. Proof. As in the proof of Lemma 4, we will construct the set P inductively. We start with a set P b of size b such that the set is in general position with respect to R. This can be constructed in O(1) time as R is α-good. We then extend this set one point at a time using points from the grid (as in the proof of Lemma 4). Assume that for b ≤ t < n, we have constructed a point set P t that satisfies the above conditions. The points forbidden to be added to the set P t will lie on bounded number of polynomials from R and we will call these polynomials forbidden polynomials. The hyperplane that is in bijective correspondence with a forbidden polynomial under the Veronese mapping Φ R is called a forbidden hyperplane. As in the proof of Lemma 4, we can show, using the Veronese mapping Φ R , that the number of forbidden hyperplanes arising due to conditions (1), ( 2) and ( 3) is bounded by O(t b ), O(t d 2 -1 ) and O(t b 2 +b-1 ) respectively. This also gives a bound on the number of forbidden polynomials.

As we have an upper bound on the number of forbidden polynomials, we can now use the same trick to generate points satisfying conditions ( 1 To show the other direction, we use the Veronese mapping on the vector space R of D-degree polynomials more carefully. Let the hyperplanes, to which the polynomials are mapped, be in R b . The mapping is a bijective function. Thus, in order to obtain the required result, we give a reduction from Hyperplane Point Cover in R b , where the solution set of points come from Ver R (R d ). The reduction is simply the reverse function of the Veronese mapping. Suppose an instance (H, k) of Hyperplane Point Cover where the solution set of points belong to Ver R (R d ) reduces to the instance (H , k) of D-Polynomial Point Cover. If (H, k) is a Yes instance, then there is a set S of at most k points in R b that covers all the hyperplanes in H. Consider the set S of points in R d by taking one preimage of each point in S. The set S is exactly the same size as S, and therefore contains at most k points. Moreover, by definition of the Veronese mapping, S covers all the polynomials in H . Therefore, (H , k) is also a Yes instance for D-Polynomial Point Cover.

On the other hand, if (H , k) is a Yes instance of D-Polynomial Point Cover, then there is a set S of at most k points that cover all the polynomials in H . The image of S under the Veronese mapping will be of size at most S and will cover the family H. Therefore, (H, k) will be a Yes instance of Hyperplane Point Cover when the solution points can come only from Ver R (R d ). Thus, by Lemma 13, we conclude that D-Polynomial Point Cover cannot have a kernel of size O(k b-) unless co-NP ⊆ NP/poly.

Conclusion

The D-Point Polynomial Cover problem in R d requires a set of n points in R d to be covered by at most k D-degree polynomials from a vector space R of polynomials. Although polynomial kernels for D-Point Polynomial Cover in R d can be exhibited, tight lower bounds for this problem are unknown. Similarly, a tight lower bound for the kernels for the general D-Polynomial Point Cover in R d is open, as is a tight bound for the number of polynomials in the kernel. For these problems, it might be useful to understand the structural and topological properties of the image of a Veronese mapping for a vector space R of D-degree polynomials in R d . It would be interesting to search for common structural properties of the Veronese mapping, over all vector spaces of D-degree polynomials.

Lemma 4 . 1 ) 3 )

 413 For every n ∈ Z + , there is a poly(n) time algorithm to construct a set P of n points in R d that have the following properties: (The points are in general position. (2) Let H be the family of hyperplanes defined by each set of d points from P. The hyperplanes in the family H are in general position, i.e., given r hyperplanes H 1 , . . . , H r in H with r ≤ d the dimension of the affine space ∩ r i=1 H r is d -r. (For any point p in R d \ P, there are at most d hyperplanes in H that contain p.

Lemma 5 .

 5 et. al. to generate points satisfying conditions (1) to (3) [16, Lemma 2.4]. In our case, we take a d-dimensional m × • • • × m grid with m = n d 2 +d and observe that the number of points from this d-dimensional grid that can lie on any hyperplane is bounded by m d-1 . Finally, we are ready to prove the main result. Hyperplane Point Cover in R d cannot have a kernel of size O(k d-) if co-NP NP/poly.

Claim 2 .

 2 (U, F, k) is a Yes instance of d-Hitting Set if and only if (H, dk) is a Yes instance of Hyperplane Point Cover in R d .

  and for a set {i 1 , i 2 , . . . , i d } ∈ {1, . . . , d}. We show that from the set Ŝ ={v jt |t ∈ [d], ∈ [d], = i t } at most d -2 vertices do not belong to Q. Consider the vertex v i1 j1 ∈ U . From the set {v jt |t ∈ {2, . . . , d}, ∈ [d], = i t } at most d-2 vertices do not belong to Q. Otherwise, v j1 is involvedin more than d -1 bad hyperedges, contrary to Claim 3. By pigeonhole principle, there is a v j b , b = 1 such that all vertices in {v jt | ∈ [d], = i t } belong to Q. This means that the vertices of Ŝ that are not in Q are restricted to the set {v jt |t ∈ [d] \ {b}, ∈ [d], = i t }. Again, this set can have at most d -2 vertices missing from Q as otherwise the vertex v i b j b will be involved in more than d -1 bad hyperedges, contradicting Claim 3.

Lemma 9 .Corollary 10 .

 910 Point Hyperplane Cover in R d cannot have a kernel with O(k d-) points if co-NP NP/poly. Since Point Hyperplane Cover and Hyperplane Point Cover are equivalent problems, we obtain the following corollary. Hyperplane Point Cover in R d cannot have a kernel with O(k d-) hyperplanes if co-NP NP/poly.

Corollary 11 (

 11 ). Projective Point Hyperplane Cover in R d cannot have a kernel with O(k d-1-) points if co-NP NP/poly.

Lemma 12 . 3 )

 123 Let R be a α-good vector space of D-degree polynomials in R d and let the Veronese mapping Φ R linearize R into R b . Let Ver R (R d ) be the image of Φ R . Then for every n ∈ Z + , there is a poly(n) time algorithm to construct a set P of n points in R b that have the following properties: (1) The points are in general position with respect to hyperplanes in R b . (2) Let H be the family of hyperplanes defined by each set of b points from P. The hyperplanes in the family H are in general position, i.e., given r hyperplanes H 1 , . . . , H r in H with r ≤ b the dimension of the affine space ∩ r i=1 H r is b -r. (For any point p in R b \ P, there are at most b hyperplanes in H that contain p.

  ) to (3) as in the paper Lemma 4. In this case we take a d-dimensional m × • • • × m grid with m = n b 2 +b and use the fact given any polynomial from R number of points of the grid hitting it is bounded by m d-α . This completes the proof. This helps us to prove a kernel lower bound on the restricted version of Hyperplane Point Cover described above.Lemma 13. Let R be an α-good vector space of D-degree polynomials in R d and let the Veronese mappingΦ R linearize R into R b . Then Hyperplane Point Cover, when the solution is restricted to belong to Ver R (R d ) = Φ R (R d ), cannot have a kernel of size O(k b-) unless co-NP ⊆ NP/poly.Proof. The construction of n points in Ver R (R d ) described in Lemma 12 has all the properties described in Lemma 4.The rest of the proof follows exactly as the proof of Lemma 5.Finally, the following Theorem is derived from Lemma 13 by utilizing the Veronese mapping Φ R . Theorem 14. D-Polynomial Point Cover for an α-good vector space R in R d , and having the Veronese mapping into R b , does not have a polynomial kernel of size O(k b-), unless co-NP ⊆ NP/poly. Proof. To prove the tightness of a O(k b ) kernel for D-Polynomial Point Cover in R d with the Veronese mapping into R b , first we give on upper bound on the size of a kernel. Let the polynomials in an instance of D-Polynomial Point Cover come from the vector space R, as defined earlier. The Veronese mapping Φ R is a reduction from D-Polynomial Point Cover in R d to Hyperplane Point Cover in R b . Thus, since Hyperplane Point Cover in R b has a O(k b ) kernel [17], so does D-Polynomial Point Cover in R d with the Veronese mapping into R b .

2 Preliminaries

  In this paper, we are interested in the set/subsets of polynomials whose degree is bounded by D, for some D ∈ N. In this context we define Poly D [X 1 , . . . , X d

	Multivariate Polynomials. Given a set {X 1 , X 2 , . . . , X d } of variables a real multivariate ij polynomial on these variables is of the form P (X 1 , . . . , X d ) = i1,i2,...,i d a i1i2...i d j∈[d] X j
	where [d] = {1, . . . , d} and a i1i2...i d ∈ R. The set of all real multivariate polynomials in
	the variables X 1 , . . . , X d will be denoted by R[X 1 , X 2 , . . . , X d ]. The degree of such a
	polynomial P (X 1 , . . . , X d ) is defined as deg(P ) := max{i 1 + i 2 + . . . + i d | a i1i2...i d = 0}. A
	polynomial is said to be a D-degree polynomial if its degree is D.

  In this Section, we show that Point Hyperplane Cover in R d cannot have a kernel of size k d-if co-NP NP/poly. We show by the the standard technique of polynomial parameter transformation. For a fixed d, we reduce the d-Hitting Set problem to the problem of Point Hyperplane Cover in R

	3	Kernelization Lower bound for Point Hyperplane Cover

d . For our proof, first we state the folklore equivalence between Point Hyperplane Cover in R d and Hyperplane Point Cover in R d . Lemma 3. Point Hyperplane Cover in R d and Hyperplane Point Cover in R d are equivalent problems

  Assume that there is an arbitrary ordering on the vertices ofU = {v 1 , v 2 , . . . , v n }. For each f = {v j1 , v j2 , . . . , v j d } ∈ F,and for each i 1 , i 2 , . . . , i d ∈ {1, . . . , d}, we create a subset f i1,i2,...,i d = {v i1 j1 , v i2 j2 , . . . , v i d j d }. We put f i1,i2,...,i d in the set F . 5. For clarity of arguments in what follows, we give some more definitions. For each f = {v j1 , v j2 , . . . , v j d } ∈ F, the subfamily of hyperedges F vj 1 ,vj 2 ,...,vj d = {f i1,i2,...,i d } = Also, F vj 1 ,vj 2 ,...,vj d is called a subsystem of f , for all hyperedges f ∈ F vj 1 ,vj 2 ,...,vj d . It follows from the previous definition that a row in a subsystem corresponds to the d copies of a vertex participating in the subsystem.

	{v i1 j1 , v i2 j2 , . . . , v i d j Claim 1 (

d }|i 1 , i 2 , . . . , i d ∈ {1, . . . , d}} is called a subsystem of {v j1 , v j2 , . . . , v j d }. 1 ). (U, F, k) is a Yes instance of d-Hitting Set if and only if (U , F, dk) is a Yes instance of d-Hitting Set.

Results marked with a have their proofs in the Appendix.

implies that (U, F, dk) is a Yes instance.

Hence, by Claim 2, we show that there is a linear parameter transformation from d-Hitting Set to Hyperplane Point Cover in R d . This implies that Hyperplane Point Cover in R d cannot have a kernel of size O(k d-) if co-NP NP/poly.

The following Corollary follows from Lemma 5 and Lemma 3.

Tight Kernels in Projective Geometry

In this section, we consider Projective Point Hyperplane Cover in R d , when we are only allowed to use hyperplanes passing through a fixed point, and we are not allowed to include this fixed point in the solution set of points. Without loss of generality, we can assume that that fixed point is at the origin. Also, if the point at the origin is part of the input for the set P of points to be covered, then we can reduce the instance to that of covering all the points of P except the point at the origin. This is because, even if there is one other point in P this point needs to be covered by a hyperplane through the origin and this automatically ensures that the point at the origin is covered. Thus, we assume that the point at the origin is not in P. We exhibit a tight kernelization for this problem.

We will now show the equivalence between Projective Point Hyperplane Cover problem in R d and Point Hyperplane Cover problem in R d-1 .

Lemma 7 ( ). Projective Point Hyperplane Cover

Proof sketch. The proof idea for this equivalence is to map the given point set P in R d to a point set on a hyperplane H that does not pass through the origin o in R d . Note that H is isomorphic to R d-1 . The equivalence is in showing that it is enough to cover the mapped point set with (d -2)-flats contained in H in order to extract a family of hyperplanes that pass through o and cover P. The full proof is in the Appendix.

Proof of Claim 1

Proof. In the forward direction, suppose S is a solution for d-Hitting Set in (U, F, k). We define S = {v i |i ∈ {1, . . . , d}, v ∈ S}. Suppose S is not a solution for the instance (U , F , dk). Then by definition, there is a hyperedge f {v j1 , v j2 , . . . , v j d } ∈ F and i 1 , i 2 , . . . , i d ∈ {1, . . . , d}, such that f i1,i2,...,i d ∈ F is not hit by S . This means, by the definition of S that {v j1 , v j2 , . . . , v j d } / ∈ S. However, this implies that the hyperedge f is not hit by S, which is a contradiction.

In the backward direction, suppose S is a solution for (U , F , dk). For each i ∈ {1, 2, . . . , d}, let S i = {v|v i ∈ S }. By Pigeonhole Principle, there is one i ∈ {1, . . . , d} such that |S i | ≤ k. We show that S i is a solution for the instance (U, F, k). Suppose S i is not a solution for G. Then there is a hyperedge f ∈ F that is not hit by S i . This implies that the hyperedge f i1,i2,i3...,i d ∈ F with i 1 = i 2 = . . . i d = i is also not hit by S , which is a contradiction.

Thus, the claim is proved.

Proof of Claim 3

Proof. Firstly, by the condition of minimality on Q, each point in Q \ P must uniquely cover at least 2 hyperplanes in H. Otherwise we could find a equal-sized solution Q where |Q \ P| < |Q \ P|, which is a contradiction. Suppose that there is a vertex v ∈ U \ Q such that at least a family H of d hyperedges in H containing v can have no intersection with Q. These d hyperplanes are covered by a set Q of points that are in Q \ P. Suppose Q = {u 1 , . . . , u } such that the for each j ∈ {1, . . . , }, u j uniquely covers c j hyperplanes of H . By definition, Σ j c j = d. By the minimality condition of Q and property (2) of Lemma 4, each such point in Q ⊆ Q \ P uniquely covers between 2 to d hyperplanes of H. Thus, for each j ∈ {1, 2, . . . , } the vertex u j covers at most d -c j hyperplanes not in H . We call the family of all hyperplanes covered by vertices of Q as H . This family has at most d(d -1) + d hyperplanes. We construct the following set Q:

All points of Q \ Q are included in Q. The point v is also included. For each j ∈ {1, . . . , }, let H j be the subfamily of at most d -c j hyperplanes that are uniquely covered by the vertex u j and which are not in H . Starting from j = 1, we build a subfamily H j and find a point u j corresponding to u j . First all the hyperplanes in H j are added to H j . Then, iterating a variable t from j + 1 to , we add the hyperplanes in H t till there are d hyperplanes or all hyperplanes in t≥j H t have been added. Take a point in the intersection of H j and name that point u j . We show that the last nonempty subfamily H t must be for t < . Suppose not. Then by definition, when we consider the last point u , the number of hyperplanes in H that are not yet covered by {u 1 , . . . , u -1 } are at most d -c -Σ j< c j = d -Σ j≤ c j = 0. Therefore, {c 1 , c 2 , . . . , c -1 } cover all the hyperplanes in H \ H . By definition of H , the set {v, c 1 , c 2 , . . . , c -1 } covers all the hyperplanes in H .

By definition the size of Q is at most that of Q. However, the number of vertices in Q \ P is strictly less than the number of vertices in Q \ P. This is a contradiction to the definition of Q.

Hence, we have proven the claim.

Proof of

Proof of Corollary 11

Proof. Consider two point sets P and Q containing a fixed point p. These point sets are p-fixed-point combinatorially equivalent if P and Q are combinatorially equivalent due to a bijective mapping π between an ordering P of P and Q of Q such that the label of the point p in P is mapped to the label of p in Q by π. The results in [START_REF] Alon | The number of polytopes, configurations and real matroids[END_REF] also show that given a point p, the number of p-fixed-point combinatorially distinct order types arising from point sets that contain n points including the point p is n O(n) . The rest of the proof follows in the same way as the arguments for the lower bound on the number of points in the kernel of Point Hyperplane Cover.


François Gillet
email: f.gillet@hotmail.com

Maria Teresa

Cabria Garrido

Frédéric Blanc

Christine Fournier-Chambrillon

Mélanie Nemoz

Eric Sourp

Corinne Vial-Novella

Rafael Zardoya

Stéphane Aulagnier

Johan R Michaux

M T Cabria Garrido

M Némoz

Evidence of fine-scale genetic structure for the endangered Pyrenean desman (Galemys pyrenaicus) in the French Pyrenees

Keywords: conservation genetics, Galemys pyrenaicus, genetic structure, microsatellites

établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

make it a specialist in finding and feeding on larvae of benthic macroinvertebrates (Palmeirim 65 and Hoffmann 1983;Richard 1986). The Pyrenean desman is an endangered species. It is 66 currently classified as vulnerable on the IUCN Red List (Fernandes et al. 2008) and is legally 67 protected in the 4 countries encompassing its range (Andorra, France, Portugal, and Spain). It 68 has been undergoing habitat loss and fragmentation for decades, inevitably impacting its 69 distribution (Nores et al. 2007;Némoz and Bertrand 2008). demonstrated (Gillet et al. 2015b). We sought to determine the spatial distribution of genetic 89 diversity in desman populations and to quantify gene flow across the French Pyrenees. The 90 ultimate goal of this study was to enhance our general knowledge of this endangered and 91 elusive species to better inform its conservation.

92

Material and methods

conditions for fecal samples, where PCRs were carried out in a 10-µl volume containing 0.15 107 of each 20-µM primer, 7.5 µl of Multiplex PCR kit (Qiagen Inc.), and 5 µl of DNA.

108 Amplified DNA was analyzed for length variations on an ABI 3700 sequencer using 109 GeneScan 500LIZ ® size standard, and alleles were scored with GENEMAPPER 4.0 (Applied 110 Biosystems, Foster City, California). Consensus genotypes were constructed for fecal samples 111 to prevent genotyping errors in our dataset. For this, we used a modified multitube PCR 112 approach (Taberlet et al. 1996) and repeated each PCR 4 times. Allele scores were accepted if 113 they appeared at least 3 times in 4 PCRs.

114

Statistical analyses.-Each replicate genotype was compared with the consensus 115 genotype to quantify the error rates. The consensus genotype construction and error rate 116 quantification-such as false alleles (FA) and allelic dropouts (ADO)-were both performed (http://www.ngcrawford.com/django/jost/) was used to estimate Dest statistics (Jost 2008) 140 using 1,000 bootstrap replicates.

Comment citer ce document : Gillet, F., Garrido, M. T. C., Blanc, F., Fournier-Chambrillon, C., Nemoz, M., Sourp, E., Vial-Novella, C., Zardoya, R., Aulagnier, S., Michaux, J. R. (2016) 185

To assess the level of confidence of these analyses, new datasets were simulated with 186 each alternative scenario and the same procedure to estimate their respective posterior

224

Population structure and genetic diversity.-After using the ΔK method on our 225 STRUCTURE results, the highest ΔK-value was found at K=3 (Fig. 2). The 1st cluster (C), GpyrGS18, and GpyrGS11 versus GpyrGS20) showed significant linkage disequilibrium for 236 the central cluster and 1 pair (GpyrGS33 versus GpyrGS82) for the eastern cluster after

Comment citer ce document : Gillet, F., Garrido, M. T. C., Blanc, F., Fournier-Chambrillon, C., Nemoz, M., Sourp, E., Vial-Novella, C., Zardoya, R., Aulagnier, S., Michaux, J. R. ( 2016). Evidence of fine-scale genetic structure for the endangered Pyrenean desman (Galemys pyrenaicus) in the French Pyrenees. Journal of Mammalogy, 98 (2), 523-532. DOI : 10.1093/jmammal/gyx002 11 Bonferroni correction. The inbreeding coefficient (F IS ) was significant for all 3 clusters (Table 238 2) and all pairwise F ST were significant (Table 3). Moreover, the results of the Wilcoxon test 239 under a 2-phase model (TPM) performed using the BOTTLENECK 1.2 software package 240 indicated that both the central and eastern clusters had undergone a recent bottleneck (P < 241 0.001).

242

The high observed F IS -values, especially in the western cluster (Table 2), could also individuals admixed beyond K = 1), whereas that for cluster W supported the existence of 3 247 sub-clusters (Fig. 3). This sub-structuring could explain the higher inbreeding coefficient 248 (0.434) in the western cluster, even though these sub-clusters did not seem to exhibit any clear 249 geographical distribution (Fig. 3). of individuals was weakly correlated with the geographic distance between them (r 2 = 0.05).

297

The absence of significant signal among the 3 clusters suggests that their relationships (e.g., a 298 closer link between the cluster E and C as compared to the cluster W as suggested by the 299 DIYABC results) was not driven by geographic distance alone. values that were significantly higher than zero and ranged between 0.345 (between the W and 384 E cluster) and 0.203 (between the C and W clusters). This trend also was revealed using the 385 Dest index (Table 3).

386

Despite this apparent low gene flow between clusters, they were not geographically 387 separated and they overlapped in some areas (Fig. 2). Moreover, individual cluster approximate Bayesian computation (ABC) analysis. Prior parameters are defined in Table 1.

683

Colors correspond to the colors in Fig. 2.

153

  Demographic history.-The evolutionary history of G. pyrenaicus in France was 154 investigated using approximate Bayesian computation as implemented in DIYABC 155 1.0.4.45beta software (Cornuet et al. 2010). This coalescent-based approach allows estimation 156 of the effective population size as well as the splitting time in generations for each tested 157 genetic cluster. A number of biogeographic scenarios were tested and compared to determine 158 whether the observed clusters originated from fragmentation of an ancestral common 159 population or if any cluster resulted from an admixture of the others. Specifically, the type 1 160 scenarios explored 2 consecutive divergences with a 1st divergence between 2 of the 3 161 populations, followed by divergence of the 3rd population from 1 of the 2 others (6 alternative 162 scenarios; Fig. 1). The type 2 scenarios displayed an admixture event between 2 populations, 163 leading to formation of the 3rd population (3 alternative scenarios; Fig. 1), while the type 3 164 scenario showed a radiation process, where the 3 populations would have split at the same was performed on the first 10 5 simulated datasets in the 1st run and on the first 2x10 5 datasets 175 in the 2nd run. Inspection of PCAs helped us choose the most adequate timeframe 176 corresponding to our data (maximum of 500 generations backwards in time). We used microsatellite mutation rates generally used for mammalian species (i.e., 10 -3 to 10 -5 ; Dallas 178 1992; Weber and Wong 1993; Ellegren 1995). Software default values were chosen for 179 admixture rates. To determine the most likely alternative scenarios, we used normalized 180 Euclidean distances between each simulated dataset and our observed dataset and 1% of the 181 closest simulated datasets were used to estimate the relative posterior probability (with 95% 182 confidence intervals) of each alternative scenario with a logistic regression (Cornuet et al. 183 2008). The most likely alternative scenario was that with the highest posterior probability 184 with a non-overlapping 95% confidence interval.

243 indicate a

 a Wahlund effect in the genetic clusters. To investigate this possibility, we conducted 244 an additional clustering analysis within each cluster, under the same conditions as previously 245 described. The analyses for clusters C and E did not give any evidence of substructure (all 246

250

  Demographic history.-After using DIYABC software to investigate 10 distinct 251 demographic alternate scenarios, a 2nd analysis was performed on the 2 most probable 252 alternate scenarios (those with the highest posterior probabilities) obtained in the 1st run. 253 These 2 alternate scenarios (2 and 9, Fig. 4) exhibited 2 different evolutionary demographic 254 patterns. Alternate scenario 2 reflected the separation of cluster W from more eastern 255 Pyrenean desmans, followed by the separation of cluster C from cluster E. In contrast, 256 alternate scenario 9 reflected the origin of the central cluster following a merging event 257 between the other 2 clusters. The logistic regressions performed on 1% of the closest 258 simulated datasets revealed that the most likely of all of the tested alternate scenarios was 259 alternate scenario 2, with a PP of 0.582 and a confidence interval (95% CI) of 0.475-0.689. 260 However, the confidence intervals of alternate scenarios 2 and 9 overlapped (PP of 0.418 and alternate scenarios, 2 were well-supported and thus a 2nd run with these 2 alternate scenarios 280 was launched. Finally, the software unambiguously chose 1 alternate scenario from the 2, 281 with a PP of 0.585 (95% CI of 0.565 -0.605). This alternative scenario displayed the same 282 evolutionary demographic pattern as alternate scenario 2 from Fig. 4. The median times of 283 divergence among these clusters (populations N1, N2, and N3; Fig. 3) were quite similar to Comment citer ce document : Gillet, F., Garrido, M. T. C., Blanc, F., Fournier-Chambrillon, C., Nemoz, M., Sourp, E., Vial-Novella, C., Zardoya, R., Aulagnier, S., Michaux, J. R. (2016). Evidence of fine-scale genetic structure for the endangered Pyrenean desman (Galemys pyrenaicus) in the French Pyrenees. Journal of Mammalogy, 98 (2), 523-532. DOI : 10.1093/jmammal/gyx002 13 those found for the 3 main groups (100 and 200 years ago). The mean effective population 285 sizes were estimated at 185, 160, and 120 individuals for N1, N2, and N3, respectively. 286 We used MIGRATE 3.4.4 on the 3 main clusters to calculate the migration rate per 287 generation according to N e m = (M i j *Θ j )/4, with Θ C = 2.86, Θ E = 1.14, Θ W = 1.14 and M E C = 288 0.83, M W C = 0.46, M C E = 1.38, M W E = 0.39, M C W = 0.84, M E W = 0.87. The effective number 289 of migrants per generation among clusters was low, with less than 1 migrant per generation (1 290 year) with Nm E C = 0.59, Nm W C = 0.32, Nm C E = 0.39, Nm W E = 0.11, Nm C W = 0.24 and Nm E 291 W = 0.25. 292 Isolation by distance.-The IBD analyses indicated an absence of isolation by 293 distance among clusters and within clusters E and W. In contrast, a significant signal was 294 observed within cluster C (Mantel test P < 0.05), as indicated by the relatively low Dσ 2 value 295 (0.44). However, the slight regression slope indicated that the genetic distance between pairs 296

  generated new insight into the genetic structure of Pyrenean desman 303 populations in the French Pyrenees. The large area sampled, covering the entire current 304 distributional area of the Pyrenean desman on the French side of the Pyrenees, and the use of 305 24 highly variable microsatellite markers provided a more fine-scale view of genetic structure 306 than previously available.Comment citer ce document : Gillet, F., Garrido, M. T. C., Blanc, F., Fournier-Chambrillon, C., Nemoz, M., Sourp, E., Vial-Novella, C., Zardoya, R., Aulagnier, S., Michaux, J. R.(2016). Evidence of fine-scale genetic structure for the endangered Pyrenean desman (Galemys pyrenaicus) in the French Pyrenees. Journal of Mammalogy, 98 (2), 523-532. DOI : 10.1093/jmammal/gyx002 14 Population structure and evolutionary history of the French Pyrenean desman.-The 308 results showed evidence of 3 genetically and geographically distinct clusters (Fig. 2) situated 309 in the eastern (E), central (C), and western (W) French Pyrenees. In addition, sub-structuring 310 seemed to emerge within cluster W, where 3 sub-clusters were detected. These sub-clusters 311 did not exhibit any clear geographical distribution but this may be the result of low sampling 312 within each sub-cluster (6-10 individuals). More extensive sampling in this area is needed to 313 better define this substructure. 314 The existence of eastern, central, and western genetic clusters was not evident in the 315 study of Igea et al. (2013), which suggested the existence of a single Pyrenean population that 316 would have recently colonized the Pyrenean region from a putative refuge situated in the 317 Basque Mountains after a severe bottleneck event. This hypothesis was deduced from the very 318 low levels of genetic diversity found in both mitochondrial and nuclear (intron) marker 319 sequences in this region. Our microsatellite markers, characterized by higher mutation rates 320 than mitochondrial or nuclear intronic sequences (Schlötterer 2000), allowed us to detect finer 321 genetic structure in the Pyrenean desman. Therefore, according to their different evolutionary 322 rates, both mitochondrial and nuclear markers gave complementary information concerning 323 the evolutionary history of the desman in this region. The species probably colonized the 324 Pyrenean region after the last ice age, and subsequent diversification led to the 3 genetic 325 clusters, presently distributed throughout the French Pyrenean region. The only other 326 vertebrate species having a similar reported genetic structure across the French Pyrenees is the 327 rock ptarmigan (Lagopus muta-Bech et al. 2009). However, in contrast to the Pyrenean 328 desman, the genetic structure of this bird species was associated with a significant isolation-329 by-distance effect, likely the result of short dispersal distances, and high natal and breeding 330 philopatry combined with severe habitat fragmentation. Comment citer ce document : Gillet, F., Garrido, M. T. C., Blanc, F., Fournier-Chambrillon, C., Nemoz, M., Sourp, E., Vial-Novella, C., Zardoya, R., Aulagnier, S., Michaux, J. R. (2016). Evidence of fine-scale genetic structure for the endangered Pyrenean desman (Galemys pyrenaicus) in the French Pyrenees. Journal of Mammalogy, 98 (2), 523-532. DOI : 10.1093/jmammal/gyx002 15 As no isolation by distance was detected, the structure supported by our study is likely 332 the result of concomitant environmental and anthropogenic factors. The DIYABC analysis 333 proposed that about 80 years ago clusters C and E diverged from an ancestral population, 334 which itself had diverged from the W cluster approximately 230 years ago, or that cluster C 335 was a result of an admixture event between clusters E and W that occurred about 60-80 years 336 ago, after clusters E and W diverged about 230-240 years ago. However, these estimations 337 might be underestimated given that the software algorithm does not assume migration within 338 scenario events. Moreover, these estimations were performed while considering a minimum 339 generation time of 1 year even though this information is unknown for the Pyrenean desman 340 and could be higher. Indeed, as G. pyrenaicus belongs to the family Talpidae, if we 341 extrapolate the generation time of the Pyrenean desman from that of the European mole342 (Talpa europea-1.72 years, Niethammer 1990), the estimated divergence times become 400 343 years ago for the separation of the E and W clusters and 100-140 years ago for the divergence 344 of C and E (or the admixture of E and W in the 2nd alternative scenario). 345 Human population growth over the last century, and therefore the increased human 346 impact on nature, inevitably led to riverine habitat loss and fragmentation of species' 347 populations inhabiting mountain streams. The construction and functioning of hydroelectric 348 power plants is an example of the human impact on rivers. These can lead to physical and 349 biotic modifications and alter both hydrologic and thermal regimes, thus impacting resources 350 such as benthic macroinvertebrate larvae (Queiroz et al. 1992; Céréghino and Lavandier 351 1997). Although little information is available on the Pyrenean desman, these detrimental 352 effects have been studied and highlighted by various authors for other mammals and birds 353 (Nilsson and Dynesius 1994; D'Amico et al. 2000). Furthermore, the development of such 354 infrastructures dates back to the beginning of the 20 th century in the French Pyrenees, and The very high inbreeding coefficient in the western cluster could also be explained by 373 a Wahlund effect as 3 sub-clusters were found in this population. As for the 3 main 374 populations, the impact of both anthropogenic and climatic factors (notably during the Little 375 Ice Age) along with watershed structure could jointly explain differentiation of the 3 sub-376 clusters. This sub-structure in the western population also could be due to the fact that this 377 region is characterized by a smaller proportion of favorable habitats compared to the more 378 eastern portion of the distribution (Charbonnel 2015). However, the effective population sizes Comment citer ce document : Gillet, F., Garrido, M. T. C., Blanc, F., Fournier-Chambrillon, C., Nemoz, M., Sourp, E., Vial-Novella, C., Zardoya, R., Aulagnier, S., Michaux, J. R. (2016). Evidence of fine-scale genetic structure for the endangered Pyrenean desman (Galemys pyrenaicus) in the French Pyrenees. Journal of Mammalogy, 98 (2), 523-532. DOI : 10.1093/jmammal/gyx002 17 estimated by ABC were inconsistent with this favorable habitat gradient, with a higher value 380 in the western than in the eastern population. The sub-structure of the western population 381 could have biased the effective population size estimation. 382 Gene flow seemed limited among the 3 main clusters, as indicated by pairwise F ST 383

388

  assignments from the Bayesian analysis clearly showed that some individuals shared alleles 389 from different clusters and have admixed genomes. This pattern was observed particularly 390 between the E and C clusters (Fig.2), where migrations seemed to have occurred every 2 or 3 391 generations. Although this result has been viewed as a recent expansion process in other 392 species such as the European otter (Lutra lutra-Janssens et al. 2008; Pigneur et al. 2014), 393 the general regression of the range of the Pyrenean desman over the last 3 decades did not 394 allow us to retain this hypothesis. However, this overlapping of clusters could confirm that the 395 genetics of the Pyrenean desman were not markedly impacted by the river networks (Igea et 396 al. 2013) and that its dispersal could be complex, as pointed out by Stone (1987a, b) and 397 Melero et al. (2012, 2014). Our estimates of migration rate also tended to confirm recent but 398 limited gene flow among clusters. 399 Future studies will be needed to place the patterns found here in a broader spatial 400 framework that includes the entire Pyrenean distribution of this species. For example, it is 401 possible that some individuals included in our study were migrants or descendants of migrants 402 from the Spanish side of the Pyrenees, particularly the 2 green-colored individuals in the Comment citer ce document : Gillet, F., Garrido, M. T. C., Blanc, F., Fournier-Chambrillon, C., Nemoz, M., Sourp, E., Vial-Novella, C., Zardoya, R., Aulagnier, S., Michaux, J. R. (2016). Evidence of fine-scale genetic structure for the endangered Pyrenean desman (Galemys pyrenaicus) in the French Pyrenees. Journal of Mammalogy, 98 (2), 523-532. DOI : 10.1093/jmammal/gyx002 18 central cluster shown in Fig. 2, which could have passed through the Val d'Aran. This may 404 suggest that Pyrenean desmans could cross the mountains from one side to the other. In 405 addition, contact zones between both sides of the Pyrenees have been identified for 406 Corthippus grasshoppers (Buño et al. 1994), Phylloscopus birds (Helbig et al. 2001), and 407 viviparous lizards (Zootoca vivipara-Milá et al. 2013). These contact zones, which are 408 situated across the central high Pyrenees and across the southwestern Pyrenees, could also 409 exist for the Pyrenean desman. Igea et al. (2013) suggested genetic homogeneity across the 410 distribution of Pyrenean desman using relatively slowly evolving mitochondrial and nuclear 411 markers, but further analysis of Spanish and French samples using hypervariable markers is 412 needed to gain further insight concerning the broader-scale genetic structure of the Pyrenean 413 desman. 414 Implications for conservation of the Pyrenean desman in the French Pyrenees.-415 Classified as "Vulnerable" on the IUCN Red List (Fernandes et al. 2008), the Pyrenean 416 desman is legally protected in France and is the focus of a LIFE + project 417 (LIFE13NAT/FR/000092) under a National Action Plan (Némoz and Bertrand 2008). This 418 species has been undergoing habitat loss and fragmentation for decades, particularly in France 419 where its range still requires further investigation (Némoz and Bertrand 2008). 420 The low level of genetic diversity observed in the different French Pyrenean desman 421 clusters as well as the heterozygote deficiency highlighted by the high inbreeding coefficient 422 (F IS ) values, and relatively low effective population sizes within clusters, could increase the 423 risk of extinction for this species in the future (Frankham 2005). 424 A lack of genetic diversity within the 3 main populations would lead to increased risk 425 of inbreeding depression. Greater connectivity throughout the Pyrenees should therefore be 426 fostered to facilitate individual dispersal and gene flow among the 3 main populations. ThisComment citer ce document : Gillet, F., Garrido, M. T. C., Blanc, F., Fournier-Chambrillon, C., Nemoz, M., Sourp, E., Vial-Novella, C., Zardoya, R., Aulagnier, S., Michaux, J. R. (2016

GeneticsFigure legends 680 Fig. 1 .

 6801 Figure legends 680 Fig. 1. Schematic representation of 3 scenarios designed to test the origin of the 3 populations 681

684Fig. 2 .Fig. 3 .Fig. 4 .

 234 Fig. 2. Population structure of the Pyrenean desman (Galemys pyrenaicus) in the French 685

  Isolation by distance (IBD) analyses among and within clusters defined with 142 STRUCTURE 2.3.1 were performed with GENEPOP 4.1.2. The signal strength was estimated 143 by calculating Dσ 2 (i.e., product of the population density and axial mean square parent-144 offspring distance as defined by Rousset (1997)), according to b = 1/(4πDσ 2 ). The value 145 obtained (Dσ 2 ) was inversely correlated with the IBD strength. The logarithm of the 146 Euclidean distance on GPS coordinates was used to calculate the geographic distance and âr

	147
	148	statistics were used to represent the genetic distance between pairs of individuals (Rousset
	149	2000). A Mantel's test with 10,000 permutations was used to test the significance of the
	150	correlation.
		Finally, we used BOTTLENECK 1.2 (Cornuet and Luikart 1996) to perform a

. Evidence of fine-scale genetic structure for the endangered Pyrenean desman (Galemys pyrenaicus) in the French Pyrenees. Journal of Mammalogy, 98 (2), 523-532. DOI : 10.1093/jmammal/gyx002 7 151 Wilcoxon test under a 2-phase model (TPM) to investigate recent demographic bottlenecks 152 with estimations based on 1,000 replications.

  Gillet, F., Garrido, M. T. C., Blanc, F., Fournier-Chambrillon, C., Nemoz, M., Sourp, E., Vial-Novella, C., Zardoya, R., Aulagnier, S., Michaux, J. R. (2016). Evidence of fine-scale genetic structure for the endangered Pyrenean desman (Galemys pyrenaicus) in the French Pyrenees. It is important to note that the results of the genotyping of 216 fecal samples were highly dependent on the freshness and size of the feces at the time of The percentage of detected individuals also was dependent on the 221 threshold rule of the conservative multitube approach that we used, i.e., allele scores were 222 accepted if they appeared at least 3 times in 4 PCRs. This step was nonetheless necessary to

	190 214	error was estimated for 10,000 simulated datasets generated under the best-supported significant bias in our dataset that could be attributed to null alleles. Therefore, the total
	191 215	alternative scenario. The type-II error was estimated by simulating 10,000 datasets generated number of individuals used in our analyses was 108 (38 tissue samples and 70 individuals
	192	for each alternative scenario and counting decisions in favor of the selected alternative identified from fecal samples).
	193	scenario.
	194	We also estimated historical demographic events and genetic parameters including
	195	interactions between clusters (i.e., migration rate (M)) using MIGRATE 3.4.4 (Beerli and
	196	Felsenstein 1999, 2001; Beerli 2004, 2006; Beerli and Palczewski 2010). This software is able
	197	to search through genealogies and obtain estimates of theta (Θ) and M by employing a
	198	Metropolis-Hastings Markov chain Monte Carlo (MCMC) algorithm and a likelihood ratio
	199	test, respectively. It assumes a constant Θ for each population but a variable Θ between them
	200	(pairwise migration rate estimates).
	201	We first used MIGRATE 3.4.4 with default parameters, with FST-based statistics of
	202	Θ and M, 10 short chains of 10,000 sampled genealogies, and 3 long chains of 100,000
	203	sampled genealogies. The parameter estimates of Θ and M from the previous run were used as
	204	starting values to perform a second analysis. The formula xNem = M*Θ was used to calculate
	205	the headcount of immigrants per generation, with x being the inheritance scalar (set at 4 for
	206	diploid species), Ne the effective population size, and m the mutation rate per generation and
	207	per locus.
	208
	209	Results
	210	Microsatellite genotyping.-A total of 70 individuals were identified out of the 355
	211	fecal samples analyzed with a PIDsibs of 2.24e -03 . The mean proportion of positive PCRs was
	212	67%, ranging from 53% to 76% among loci. No significant allelic dropout or false allele
		errors could be found in our data (all loci <0.001). MICRO-CHECKER did not detect any
		9 10
		Comment citer ce document :
		Gillet, F., Garrido, M. T. C., Blanc, F., Fournier-Chambrillon, C., Nemoz, M., Sourp, E.,
		Vial-Novella, C., Zardoya, R., Aulagnier, S., Michaux, J. R. (2016). Evidence of fine-scale genetic
		structure for the endangered Pyrenean desman (Galemys pyrenaicus) in the French Pyrenees.
		Journal of Mammalogy, 98 (2), 523-532. DOI : 10.1093/jmammal/gyx002 Journal of Mammalogy, 98 (2), 523-532. DOI : 10.1093/jmammal/gyx002

187 probabilities was applied, and the proportion of times the right alternative scenario had the 188 highest posterior probability was measured. According to Cornuet et al. (2010), the type-I Comment citer ce document : 217 collection as feces of Pyrenean desmans are generally small (10 to 15 mm long and 4 to 8 mm 218 wide, Bertrand 1993) and their DNA content rapidly degrades due to contact with water and 219 UV radiation (Lindahl 1993). In our study, only 20% of the collected feces could be attributed 220 to distinct individuals. 223 ensure reliable results

  would favor genetic mixing and a better response to future climatic change. Exchanges 428 between neighboring watersheds should be promoted by improving water quality, mainly at 429 lower elevations where rivers merge. Indeed, the Pyrenean desman favors rivers with high 430 water flows, which are now found at high elevations (Nores et al. 1992; Ramalhinho and Boa Although this study generated new insight into the fine-scale genetic structure of the 443 Pyrenean desman in France, a larger study, based on sensitive genetic markers such as Comment citer ce document : Gillet, F., Garrido, M. T. C., Blanc, F., Fournier-Chambrillon, C., Nemoz, M., Sourp, E., Vial-Novella, C., Zardoya, R., Aulagnier, S., Michaux, J. R. (2016). Evidence of fine-scale genetic structure for the endangered Pyrenean desman (Galemys pyrenaicus) in the French Pyrenees. Journal of Mammalogy, 98 (2), 523-532. DOI : 10.1093/jmammal/gyx002 23 Bertrand, A., 1994. Répartition géographique et écologie alimentaire de desman des pyrénées 503 G. pyrenaicus dans les Pyrénées françaises. Diplôme Universitaire de Recherche, Cornuet, J., Ravigné, V., Estoup, A., 2010. Inference on population history and model 524 checking using DNA sequence and microsatellite data with the software DIYABC ( v1 .

	504 525
	505 526	Toulouse, 217p. 0 ). BMC Bioinformatics 11, 401.
	431
	506 527	Bertrand, A., 1993. Découvrir le Desman des Pyrénées, Ed. Association des Naturalistes Cornuet, J.-M., Luikart, G., 1996. Power Analysis of Two Tests for Detecting Recent
	432	Vida 1993; Queiroz et al. 1996; Charbonnel et 2015). This preference for high water flows
	507 528	d'Ariège, 32 p. Population Bottlenecks From Allele Frequency Data. Genetics 144, 2001-14.
	433	at high elevations could contribute to the genetic structure observed in our study as this
	434 508 529	species is more inclined to live at elevations where rivers are less connected. In addition, Buño I., Torroja E., López-Fernández C., Butlin R.K., Hewitt G.M., Gosálvez J., 1994. A Cornuet, J.-M., Santos, F., Beaumont, M. a, Robert, C.P., Marin, J.-M., Balding, D.J.,
	435 509 530	enhanced management of hydroelectric infrastructures and of winter tourism at high hybrid zone between two subspecies of the grasshopper Chorthippus parallelus along the Guillemaud, T., Estoup, A., 2008. Inferring population history with DIY ABC: a user-
	436 510 531	elevations should be promoted throughout the mountain chain. Pyrenees: the west end. Heredity 73:625-634. friendly approach to approximate Bayesian computation. Bioinformatics 24, 2713-9.
	437 532	Another improvement could be achieved by increasing water flow in rivers with low doi:10.1093/bioinformatics/btn514
		Céréghino, R., Lavandier, P., 1997. Influence des éclusées hydroélectriques sur la distribution
	438	trophic resources or by restoring suitable habitats for the Pyrenean desman, notably by
	533	Coster, S.S., Kovach, A.I., 2012. Anthropogenic influences on the spatial genetic structure of
	439	placing stones and boulders in rivers to re-create adequate water flow and shelter.
	513	black bears. Conservation Genetics 13, 1247-1257. doi:10.1007/s10592-012-0368-4
	440	Connectivity between main and tributary rivers should also be favored as tributary rivers can
		doi:10.1016/S0764-4469(97)82775-8
	441	serve as refugia in case of short and sudden hydrological events (Lake 2000; Charbonnel
		2015).
	537
	444
		mouse. Mammalian Genome, 3, 452-456.
	445 469	microsatellite or SNP markers and encompassing the entire range of the species, particularly fellowship provided by ANRT (CIFRE N° 2011/1571).
	446 470	the Spanish side of the Pyrenees, is necessary to broaden overall knowledge on this threatened
	447 471 540	species and its worldwide conservation.
	472 499 541	direction among multiple sampling locations. Genetics 185, 313-26. Genetics Resources 4, 359-361. doi:10.1007/s12686-011-9548-7
	500	doi:10.1534/genetics.109.112532
	542	Ellegren, H., 1995. Mutation rates at porcine microsatellite loci. Mammalian Genome, 6,
	501	Belkhir, K., Borsa, P., Chikhi, L., Raufaste, N., Bonhomme, F., 2004. GENETIX 4.05, 376-377.
		logiciel sous Windows TM pour la génétique des populations.

). Evidence of fine-scale genetic structure for the endangered Pyrenean desman (Galemys pyrenaicus) in the French Pyrenees.

Journal of Mammalogy, 98 (2), 523-532. DOI : 10.1093/jmammal/gyx002 19 442 511 et le développement larvaire des Diptères Simuliidae d'une rivière de moyenne 512 montagne. Comptes Rendus l'Académie des Sciences. -Ser. III -Sci. la Vie. 514 Charbonnel, A., 2015. Multi-scale influence of environmental factors in the distribution of the 515 Pyrenan desman (Galemys pyrenaicus) in France. PhD thesis, University of Toulouse, 516 245p. 517 Charbonnel, A., Buisson, L., Biffi, M., D'Amico, F., Besnard, A., Aulagnier, S., Blanc, F., 518 Gillet, F., Lacaze, V., Michaux, J.R., Némoz, M., Pagé, C., Sanchez-Perez, J.M., 519 Sauvage, S., Laffaille, P., 2015. Integrating hydrological features and genetically 520 validated occurrence data in occupancy modelling of an endemic and endangered semi-521 aquatic mammal, Galemys pyrenaicus, in a Pyrenean catchment. Biological 522 Conservation 184, 182-192. doi:10.1016/j.biocon.2015.01.019 Comment citer ce document : Gillet, F., Garrido, M. T. C., Blanc, F., Fournier-Chambrillon, C., Nemoz, M., Sourp, E., Vial-Novella, C., Zardoya, R., Aulagnier, S., Michaux, J. R. (2016). Evidence of fine-scale genetic structure for the endangered Pyrenean desman (Galemys pyrenaicus) in the French Pyrenees. Journal of Mammalogy, 98 (2), 523-532. DOI : 10.1093/jmammal/gyx002 24 534 D'Amico, F., Manel, S., Mouches, C., Ormerod, S.J., 2000. River birds in regulated rivers : 535 cost or benefit ? Verhandlungen des Internationalen Verein Limnologie 27, 167-170. 536 Dallas, J.F., 1992. Estimation of microsatellite mutation rates in recombinant inbred strains of 538 Earl, D. a., vonHoldt, B.M., 2011. STRUCTURE HARVESTER: a website and program for 539 visualizing STRUCTURE output and implementing the Evanno method. Conservation genotypes in natural populations: cautions and guidelines. Molecular Ecology 10, 249-

Johan Michaux 5/2/17 05:01 Mis en forme: Justifié

4015-4026. doi:10.1111/j.1365-294X.2008.03887.x

Pritchard, J.K., Stephens, M., Donnelly, P., 2000. Inference of Population Structure Using

Multilocus Genotype Data.

Rousset, F., 2000. Genetic differentiation between individuals 13, 58-62.

Acknowledgments

449

We thank the following people who collected tissue samples: EDF agents, Pyrenees National 450 Park agents, M. Bayon, A. Bertrand, J-P. Besson, J-P. Quéré, A. Charbonnel, F. Elzear, L.

which appeared to have the largest geographic distribution (Fig. 2), mainly included samples The mean H O ranged from 0.19 in the eastern cluster to 0.23 in the central cluster, 231 while the mean H E ranged from 0.26 in the eastern cluster to 0.37 in the western cluster (see 232 Supplementary Data S1, S2, S3). The mean allelic richness ranged from 1.4 to 1.8 (Table 2).

233

Tests for HWE showed significant deviations for the eastern and western clusters. Four pairs 234 of loci (GpyrGS22 versus GpyrGS33, GpoyrGS30 versus GpyrGS74, GpyrGS33 versus Comment citer ce document : Gillet, F., Garrido, M. T. C., Blanc, F., Fournier-Chambrillon, C., Nemoz, M., Sourp, E., Vial-Novella, C., Zardoya, R., Aulagnier, S., Michaux, J. R. (2016). Evidence of fine-scale genetic structure for the endangered Pyrenean desman (Galemys pyrenaicus) in the French Pyrenees.

Version postprint

Comment citer ce document : Gillet, F., Garrido, M. T. C., Blanc, F., Fournier-Chambrillon, C., Nemoz, M., Sourp, E., Vial-Novella, C., Zardoya, R., Aulagnier, S., Michaux, J. R. ( 2016