Nicolas Dupin
email: nicolas.dupin@universite-paris-saclay.fr

Exact enumeration of local minima for kmedoids clustering in a 2D Pareto Front

Keywords: Local minimums, k-medoids, clustering, Pareto Front

K-medoids clustering is solvable by dynamic programming in O(N 3 ) time for a 2D Pareto Front (PF). A key element is a interval clustering optimality. This paper proves this property holds also for local minima for k-medoids. It allows to enumerate the local minima of k-medoids with the same complexity than the computation of global optima for k=2 ou k=3. A pseudo-polynomial enumeration scheme is designed, for small values of k. This allows to understand results obtained by local search approaches in a 2D PF.

1.

Problem statement, notation Definition 1. A 2D PF is defined as a set E of N points in R 2 , indexed with

E = {(x k , y k )} k∈[[1,N ]] such that k ∈ [[1, N ]] → x k is increasing and k ∈ [[1, N ]] → y k is decreasing.
Let Π K (E) the set of partitions of E in K subsets. K-medoids clustering is a combinatorial optimization problem indexed by Π K (E). It minimizes the sum for all the K clusters of the dissimilarity measure minimizing the sum of the squared distances from one chosen point of P , the medoid, to the other points of P :

min π∈Π K (E) P ∈π min c∈P x∈P ||x -c|| 2 (1)
Combinatorial optimization problem (1) defines global optimums. For this paper, local minima are defined using neighborhoods of the PAM (Partitioning Around Medoids) heuristic for k-medoids, adaptation of seminal Lloyd's heuristic for the k-means problem [START_REF] Schubert | Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms[END_REF].

Definition 2 (Local minima of K-medoids). For all K ∈ N * , local minima of K-medoids (for PAM) are characterized by the encoding of partitioning subsets P 1 , . . . , P K and their respective medoids c 1 , . . . , c K , with the property:

∀k ∈ [[1; K]], ∀p ∈ P k , ∀k = k, ||p -c k || ||p -c k || (2)

Local optimality and interval clustering

A global minimum of optimization problem (1) can be computed in a 2D PF by dynamic programming in O(N 3 ) time [START_REF] Dupin | k-medoids clustering is solvable in polynomial time for a 2d Pareto front[END_REF]. A key element is a necessary condition: interval optimality as in 1D clustering problems [START_REF] Grønlund | Fast exact k-means, k-medians and Bregman divergence clustering in 1d[END_REF][START_REF] Nielsen | Optimal interval clustering: Application to Bregman clustering and statistical mixture learning[END_REF]. The interval clustering property holds also for local minima for k-medoids:

Theorem 3. We suppose that points

(x i ) are sorted as in Definition 1. Each local minimum of K-Medoids in a 2dPF is only composed of clusters C i,i = {x j } j∈[[i,i ]] = {x ∈ E | ∃j ∈ [[i, i ]], x = x j }.
As a consequence, there is at most N K local optima for K-Medoids in a 2d PF of size N .

Note that this optimality property is specific for k-medoids clustering. For k-center problems, global minima exist with nested clusters [START_REF] Dupin | Unified polynomial dynamic programming algorithms for p-center variants in a 2d pareto front[END_REF]. For the k-means problem, we can give a counter example of local minima which do not fulfill the interval clustering property.

Enumeration algorithms of local optima

Theorem 3 allows to enumerate the N K possible local minimums. Lemmas help to decrease the complexity of such operation. Enumeration schemes require to prove that a candidate solution is a local minimum fulfilling 2, which can be checked easily using properties related to interval clustering:

Lemma 4. Interval clustering C 1,f1 , C f1+1,f2 , . . . , C f K-2 +1,f K-1 , C f K-1 +1
,N with medoids c 1 , . . . , c K is a local minimum if and only if both properties are fulfilled:

∀k ∈ [[1; K -1]], ||z f k -c k || ||z f k -c k+1 || (3) ∀k ∈ [[1; K -1]], ||z 1+f k -c k+1 || ||z 1+f k -c k || (4)
For enumeration schemes, it requires to compute the medoids c j,j for each cluster C j,j with j j . Lemmas 5 and 6 allows to do it efficiently for our enumeration schemes: For a general algorithm, we use O(N 2 ) additional memory space, computing first the medoids c j,j of each interval cluster C j,j in O(N 3 ) time. Then, a backtracking algorithm enumerates only partial feasible solutions for Lemma 4: if C 1,f1 , C f1+1,f2 , . . . , C f k-2 +1,f k-1 , C f k-1 +1,f k with medoids c 1 , . . . , c k partially fulfills ( 3) and ( 4), the next point

f k+1 > f k induces a new medoid c f k-1 +1,f k such that z f k -c f k-1 +1,f k z f k -c f k +1,f k+1 and z 1+f k -c f k +1,f k+1 z 1+f k -c f k-1 +1,f k .
The following recursive algorithm calls EnumLocMin(0, [], [], 0) to print all the local minimums. We use functional programming notations, as in OCaml, x :: l pop first element x in top of list l, l = x :: l = (hd l ) :: (tl l ), [] is empty list.

Conclusions and perspectives

If k-medoids clustering in a 2D PF is solvable by dynamic programming in O(N 3 ) time with an interval clustering property, this paper proves that this property holds also for local minima for k-medoids. It allows to enumerate the local minima of k-medoids with the same complexity than the computation of global optima for k = 2 ou k = 3. A pseudo-polynomial enumeration scheme is designed, for small values of k. Perspectives are to understand results obtained by local search approaches in a 2D PF and why local minima of a poor quality can be found by PAM local search in a 2D PF [START_REF] Huang | Comparing local search initialization for k-means and k-medoids clustering in a planar Pareto Front, a computational study[END_REF]. This problem and these properties are also an interesting for landscape analysis approaches.

Lemma 5 .Lemma 6 .

 56 Computing medoids (and costs) of clusters C j ,j for all j ∈ [[1; j]] for a given j ∈ [[1; N ]] runs in O(j 2 ) time and uses O(j) memory space. Computing medoids (and costs) of clusters C j,j for all j ∈ [[j; N ]] for a given j ∈ [[1; N ]] runs in O((N -j) 2 ) time and uses O(N -j) memory space. For K = 2 and K = 3, straightforward enumeration of local minima has the same complexity than computing only a global optimum: Proposition 7. Enumerating the O(N ) local minima of 2-Medoids in a 2d PF of size N runs in O(N 2 ) time using O(N ) additional memory space. Proposition 8. Enumerating the O(N 2 ) local minima of 3-Medoids in a 2d PF of size N runs in O(N 3 ) time using O(N ) additional memory space.

Algorithm : Exhaustive search of Local Minima of K-Medoids

Input: N points of a 2D PF, E = {z1, . . . , zN }, K N The medoids c j,j of each interval cluster C j,j are computed in pre-processing


Stéphane Simon

Vincent Véron

Prof Bernard Carme
email: carme.bernard@wanadoo.fr

Hospitalier Centre

Andree De Cayenne

Rosemon

Dr Christine Aznar
email: christine.aznar1@wanadoo.fr

Dr Denis Blanchet Ahu

Marc Ledy

Frédéric Neuman

Jean Delbe
email: jean.delbe@ch-cayenne.fr

Sabrina Arnaud
email: sabrina.arnaud@ch-cayenne.fr

Leishmania species identification by PCR-RFLP analysis and its applications in French Guiana

Keywords: Cutaneous leishmaniasis, Leishmania, diagnosis, species identification, PCR, RFLP, French Guiana Cutaneous leishmaniasis, Leishmania, diagnosis, species identification, PCR, 28 PCR RFLP may

Leishmania (Viannia) guyanensis was for many years the only species commonly identified in French Guiana, but precise species identifications were quite rare. We describe a new RFLP-PCR technique using a 615 bp fragment of the RNA polymerase II gene and two restriction enzymes, TspR1 and Hga1. Seven reference strains (L.(L)amazonensis, L.(V)lainsoni, L.(V)braziliensis, L.(V)guyanensis, L.(V)naiffi, L.(L)major / L.(L)infantum) and 112 clinical samples from positive lesions were used for the development of the technique. The rates of positive species identification were 85.7% for punch skin biopsy specimens, 93.1% for positive Giemsa-stained smears and 100% for positive culture supernatants. In the framework of cutaneous leismaniasis species surveillance for the 2006-2008 period, parasite identification was carried out for 199 samples from different patients. The prevalence of the various Leishmania species was 84.4% for L.(V)guyanensis, 8.0% for L.(V)braziliensis, 5.0% for L.(V)amazonensis and 2.6% for L.(V)lainsoni.

L.(V)braziliensis seems to be locally an emerging pathogen.

Please find enclosed a manuscript headed: "Leishmania species identification by PCR-RFLP analysis and its applications in French Guiana". Leishmania (Viannia) guyanensis was for many years the only species commonly identified in French Guiana, but precise species identifications were quite rare. Deforestation and settlement on the forest borders is taking place in French Guiana. Such event is favorable to emerging vector-borne and zoonotic diseases, mainly tropical parasitosis which are able to an adapting process to a peridomestic habitat. Leishmaniasis due to Leishmania (Vianna) brasiliensis seems to be one of them. With such species mucosal form of the disease can lead to devastating facial disfigurement, often occurring some time after the benignlooking cutaneous lesions, which cannot be distinguished from the lesions associated with L. (V) guyanensis. One of the practical implications of the possible spread of L.(V) brasiliensis is that there is an urgent need for an effective parasitological surveillance system.

We describe here a new RFLP-PCR technique tested on South American reference strains, then applied to different types of clinical samples and finally used for routine diagnosis in a large-scale study monitoring the species of Leishmania present in French Guiana over a three-year period (2006 -2008) Parasite identification was carried out for 199 samples from different patients.. I hope that you will find this paper suitable for publication in DMID.

Yours sincerely

Prof Bernard Carme Guiana [START_REF] Dedet | Cutaneous leishmaniasis in French Guiana: a review[END_REF]), an overseas French territory in South America, about 92% of which is 51 covered by Amazonian rainforest. It is difficult to estimate the annual incidence of this 52 disease with any degree of certainty, particularly in forested gold-mining areas, but an 53 estimate of 2 cases per 1000 inhabitants has been reported for the 1979-2000 period (Carme et 54 al. 2001). Five species of Leishmania (L.) have been described: L. (Viannia) guyanensis, the 55 predominant species, L. (L.) amazonensis, L. (V) braziliensis, L. (V.) lainsoni and L. (V.) 56 naifji. L. (Viannia) guyanensis was for many years the only species identified in French 57

Guiana, but precise species identifications were quite rare [START_REF] Raccurt | Leishmania (Viannia) braziliensis Vianna, 1911 in PCR RFLP may[END_REF]. Visceral 58 leishmaniasis is not known to be endemic in humans in French Guiana, but this zoonosis is 59 clearly re-emerging in Brazil [START_REF] Arias | The reemergence of visceral leishmaniasis in Brazil[END_REF] and in southern Europe (Dujardin et al. 60 2008). 61

Neither microscopy nor culture can provide accurate identification of Leishmania to 62 species level. Isoenzyme analysis (mulilocus enzyme electrophoresis, MLEE) has long been 63 considered the gold standard [START_REF] Gardener | Biochemical taxonomy of Leishmania. II: Electrophoretic variation of malate dehydrogenase[END_REF], but this technique is labor-intensive and 64 time-consuming. Molecular biology-based protocols are now more frequently used, except in 65 more outlying areas. Sequencing is a useful practical solution but requires costly equipment or 66 the sending of samples to highly specialized laboratories, which may be very expensive. 67

Restriction fragment-length polymorphism (RFLP) analyses [START_REF] Macedo | DNA fingerprints: a tool for identification and determination of the relationships between species and strains of Leishmania[END_REF]) are more 68 widely used. We recently developed an RFLP technique combined with DNA amplification 69 by polymerase chain reaction (PCR) that has been validated for South American strains and L. (V) braziliensis. We selected new primer set and two different enzymes, to overcome 72 this technical problem. These modifications improved the discriminatory power of the test, 73 making it possible to establish an unambiguous distribution of Leishmania species. 74

We describe here a new RFLP-PCR technique tested on South American reference 75 This PCR-RFLP method can distinguish between seven Leishmania species (figure 1): 144

L.(V.) guyanensis, L.(L) amazonensis, L.(V) naifji, L.(V) braziliensis, L.(L) major, L.(L)

SG-A consisting of L.(V.) guyanensis / L.(L) major / L.(L) infantum, SG-B consisting of 147

L.(V) braziliensis / L.(V) naifji / L.(V) lainsoni and SG-C corresponding to L.(L) amazonensis 148

(figure 2a). A second digestion, with HgaI was then carried out to identify the individual 149 species within each SG (figure 2b). During the validation phase, the data obtained in Cayenne 150 have also proved useful for species identification over the last 20 years or so (Beverley et al. 177 1987). However, it is also often difficult to achieve the required levels of sensitivity, 178 discrimination and feasibility within a single method for routine use. Indeed, fingerprinting 179 has rarely been extensively used for the direct analysis of human biopsy specimens in clinical 180 for Leishmania on the basis of microscopy. The objective of this study was not to compare the 193 reliability of diagnosis of cutaneous leishmaniasis by PCR and microscopy, but to assess the 194 feasibility and performance of PCR-RFLP identification to species level for patients already 195 diagnosed with leishmaniasis. Several studies have shown that the rate of positive PCR detection is higher than that for microscopy for the diagnosis of cutaneous leishmaniasis (26). 197 However, as shown here, the rare genuine cases that are PCR-negative cases should be 198 positive on microscopy, although the converse situation is more frequent (cases negative on 199 microscopy but positive on PCR). All samples initially testing positive by PCR were 200 successfully identified to species level with the RFLP technique. Cultures are thus the most 201 reliable method for identification to species level, but this method is more restrictive than 202 other methods and requires a biopsy. 203

The importance of recovery samples previously taken as part of routine 204 examinations, for retrospective epidemiological studies and for diagnosis and/or confirmation 205 of species identification in cases of atypical clinical presentation and/or atypical response to 206 drug treatment, has been highlighted [START_REF] Akkafa | Identification of Leishmania parasites in clinical samples obtained from cutaneous leishmaniasis patients using PCR-RFLP technique in endemic region, Sanliurfa province, in Turkey[END_REF][START_REF] Motazedian | DNA extraction and amplification of leishmania from archived, Giemsa-stained slides, for the diagnosis of cutaneous Leishmaniasis by PCR[END_REF], Volpini et 207 al. 2006). As previously stated, performance depends on the type of sample available, but also 208 on the conditions and duration of storage, although the upper limit for the recovery of 209 amplifiable DNA is believed to be around 100,000 years [START_REF] Hoss | Neanderthal population genetics[END_REF]. However, great care is 210 required to ensure that valid data are obtained. It is not the age of the DNA, but the nature of 211 the sample and the environmental conditions that have a critical effect during storage (Hoss et 212 al. 1996). The risk of cross-contamination between samples is smaller than for malaria 213 [START_REF] Aubouy | Plasmodium DNA contamination between blood smears during Giemsa staining and microscopic examination[END_REF]), but must be taken into account, particularly as concerns the 214 possibility of two slides accidentally coming into contact (S. Simon and B. Carme, French 215 Parasitology Society Congress, Nice, December 2007). 216 ln South America, cutaneous leishmaniasis was originally an exclusively wild 217 exoanthropic zoonosis developing in forest ecotopes. However, Leishmania parasites have 218 since displayed considerable plasticity, allowing them to adapt to major changes in their 219 environment (Rotureau 2006a). L. (V) guyanensis is the main species in the Guianan Visceral leishmaniasis is being diagnosed with increasing frequency in France and in 246 southern Europe and it therefore seems likely that L.(L) infantum will be considered an 247 emerging pathogen in the near future. Indeed, two imported cases of canine L.(L) infantum 248 infection were recently described in French Guiana (Rotureau et al. 2006b). A surveillance 249 system for visceral leishmaniasis, using dogs as a sentinel species and involving the 250 widespread use of PCR for screening, should be implemented.

  strains to evaluate technical adaptations and then applied to different types of clinical 76 samples. Finally, we used this technique for routine diagnosis in a large-scale study 77 monitoring the species of Leishmania present in French Guiana over a three-year period 78(2006 -2008). 79 80 Materials and methods 81 82 Patients and the diagnosis of leishmaniasis at Cayenne Hospital 83 During the period from January 2006 to December 2008, 781 samples have been 84 transmitted to the parasitology and mycology laboratory (LHUPM) by the Department of 85 Dermatology (Cayenne Hospital,) or by one of the 20 health centers distributed throughout 86 French Guiana, for testing to confirm suspected cutaneous leishmaniasis. 87 Tissue scrapings for microscopic smear examination were collected by slitting the 88 internaI border of skin lesions with a surgical blade, smearing the material adhering to the 89 blade onto a clean glass slide, and then fixing the sample in methanol and staining it with 90 Giemsa stain. Two slides per patient were evaluated by trained parasitologists. 91 92 Clinical samples 93 Clinical samples consist of punch skin biopsies and Giemsa stained smears. 94 Giemsa-stained slides with a surgical blade. Biopsy specimens for in vitro culture were 97 crushed, in sterile conditions, in 3 ml of RPMI 1640 (SIGMA, Saint Louis, MO) 98 supplemented with 20% fetal calf serum, 1 % non essential amino acids and 50 IU/ml 99 penicillin. The material was then incubated in culture flasks, at 24°C in the dark, and 100 observed under a microscope at three-day intervals over a period of four weeks. 101 102 Reference strains 103 Seven reference strains were obtained from the French National Reference Center for 104 Leishmania (CNRL, Laboratoire de Parasitologie, CHU de Montpellier, France) (table1). 105 106 DNA extraction 107 DNA was extracted from fragments of biopsy specimens, positive cultures and dermal 108 smears in PBS with the DNeasy Tissue and Blood Kit (Qiagen, Hilden, Germany), used 109 according to the manufacturer's instructions. The extracted DNA was finally eluted in 200 µl 110 of elution buffer. 111 112 PCR amplification and restriction fragment-length polymorphism 113 Based on the findings of Croan et al. 1997, we studied a RNA polymerase II gene 114 fragment. The sequencing of this region in reference strains and alignment of the sequences 115obtained by ClustalX analysis[START_REF] Thompson | CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice[END_REF]) revealed the existence of 116 polymorphism between species. The predicted restriction patterns of all available enzymes 117 were determined in silico with Webcutter 2.0 software (http://ma.lundberg.gu.se/cutter2/). 118 Two restriction enzymes, TspR1 and Hga1, distinguished effectively between the various 119 species and were therefore retained for subsequent analyses. 120The PCR primers were designed to amplify a 615 bp region of the gene. The RPOF2 (5'-AGAACATGGGCGGCC-3') and RPOR2 (5'CGAGGGTCACGTTCTTG-3') primers 122 were used. Each PCR mixture contained 10 µl of the sample, 150 µM of each dATP, 123 dCTP,dGTP, dTTP (Sigma, Saint Louis, MO), 0.1µM of each primer (Sigma) and 2.5 units of 124 Taq DNA polymerase (New England Biolabs, UK). After 5 minutes at 94°C, 40 cycles of 125 amplification (each of 30 seconds at 94°C, 30 seconds at 55°C and 1 min at 72 °C) and a final 126 polymerization at 72°C for 5 minutes were carried out on a GenAmp PCR System 9700 127 (Applied Biosystems). The amplicons were detected by electophoresis in a 1% agarose gel 128 stained with ethidium bromide and visualization under UV light. 129 As recommended by the manufacturer, 15 µl of PCR product was digested with 10 U 130 of TspRI (New England Biolabs) (2 hours at 65°C) or with 2 U of HgaI (New England 131 Biolabs) (2 hours at 37°C.). The entire reaction mixture was then analyzed by electrophoresis 132 in a 2% agarose gel containing ethidium bromide. 133 134 Sequencing 135The specificity of identification was assessed by analyzing 27 strains from samples 136 taken from patients and seven reference strains by direct sequencing with the RPOF2 and 137 RPOR2 primers (Biofidal, Lyon, France). The RNA polymerase II gene sequences obtained 138 from the seven reference strains were deposited in GenBank, under the accession numbers

  for 27 strains (one L.(L) amazonensis, 2 L.(V) lainsoni, 4 L.(V) braziliensis and 20 L.(V) 151 guyanensis strains) were controlled by sequencing: the PCR-RFLP results were confirmed in 152 all cases. 153 The rates of positive species identification were determined for 112 pathological 154 specimens (table 2) collected, all of which were classified as positive on the basis of 155 microscopy. The PCR-RFLP technique successfully identified the parasites in 24 of 28 punch 156 skin biopsy specimens (85.7 %), 27 of 29 Giemsa-stained smears (93.1 %) and all 55 cultures 157 tested (100%). 158 Of the 781 samples received between January 2006 and December 2008 for 159 confirmation of the diagnosis of leishmaniasis, 391 were classified positive (50.1%) on the 160 basis of direct examination or culture and/or PCR (115 in 2006, 116 in 2007 and 160 in 161 2008). Parasite identification was carried out for 199 samples (50.9% of the positive samples) 162 from different patients. The prevalence of the various Leishmania species was 84.4 % [78.6 -163 89.2] for L. (V) guyanensis, 8.0 % [4.7-12.7] for L. (V) braziliensis, 5.0 % [2.4 -9.0] for L. (L) 164 amazonensis and 2.6 % [0.6 -3.2] for L. (V) lainsoni. No L. (V) naiffi was identified during 165 the survey. All but three of the patients presented localized cutaneous leishmaniasis. The 166 remaining three patients presented mucocutaneous disease. Two of these three patients were 167 HIV-positive (one infected with L. (V) braziliensis and the other with L. (V) guyanensis 168 species). The third patient with mucocutaneous leishmaniasis was immunocompetent and 169 infected with L. (V) braziliensis. 170 Many different PCR-based methods targeting microsatellites, kinetoplastic DNA, 174 telomeric sequences, gp63, mini-exons, β-tubulin or ribosomal RNA (rRNA) genes have been 175 proposed (Vega Lopez 2003). Restriction fragment length polymorphism (RFLP) analyses 176

  and eco-epidemiological studies in the field, particularly in the New World. 181 This PCR-RFLP technique, based on the use of PCR primers designed to amplify a 182 615 bp region of the RNA polymerase II gene and two restriction sites (TspR1 and Hga1), 183 was able to distinguish between the five species known to be endemic and to cause cutaneous 184 disease in French Guiana and two other species: L. (L) major and L. (L) infantum, which has 185 been implicated in visceral leishmaniasis. We checked the results obtained in Cayenne during 186 the development of this test: sequencing was carried out for 27 PCR products, before RFLP 187 analysis. Sequencing confirmed the results of species identification by PCR-RFLP: 1 L. (L.) 188 amazonensis, 2 L. (V.) lainsoni, 4 L. braziliensis and 20 L. (V.) guyanensis. 189 The rate of positive PCR diagnosis varied with the type of sample used. It was highest 190 (100%) for cultures, but remained high, at 93.1% for stained and unstained smears recovered 191 from glass slides. All the samples studied were obtained from skin lesions considered positive 192

  RFLP technique is now used in French Guiana, both on a case-by-case at 255 the request of clinicians and systematically, as a way of detecting the emergence of species 256 more virulent than L.(V) guyanensis. This species is has always been considered to be the 257 predominant species in French Guiana, but monitoring of this kind is justified by the risk of 258 emergence of L. (V) brasiliensis and the need to detect L. (L) infantum, the causal agent of 259 visceral leishmaniasis, on a local scale.

Figure 1 :Figure 2a :

 12a Figure 1: Restriction profiles of the various reference strains (French National

Leishmania species identification by PCR-RFLP analysis and its applications in French 1

	Cover Letter
		PCR RFLP may 2009 V1	PBC	09/05/2009
	31	Summary (149 words)
	2 32	Guiana.
	3 33 49	Leishmania (Viannia) guyanensis was for many years the only species commonly identified in Introduction
	4 29 34 50	Stéphane SIMON 1 , Vincent VERON 1 , Bernard CARME 1,2 RFLP, French Guiana French Guiana, but precise species identifications were quite rare. We describe a new RFLP-Cutaneous leishmaniasis is a well known parasitosis firmly established in French
	5 35	1-Equipe EA 3593, Faculté de Médecine, Université des Antilles et de la Guyane, Cayenne PCR technique using a 615 bp fragment of the RNA polymerase II gene and two restriction
	6 36	2-Laboratoire Hospitalo-Universitaire de Parasitologie -Mycologie (LHUPM), Centre enzymes, TspR1 and Hga1. Seven reference strains (L.(L)amazonensis, L.(V)lainsoni,
	7 37	Hospitalier de Cayenne L.(V)braziliensis, L.(V)guyanensis, L.(V)naiffi, L.(L)major / L.(L)infantum) and 112 clinical
	8 38	samples from positive lesions were used for the development of the technique. The rates of
	9 39	Running title positive species identification were 85.7% for punch skin biopsy specimens, 93.1% for
	10 40	Leishmania species in French Guiana. positive Giemsa-stained smears and 100% for positive culture supernatants. In the framework
	11 41	of cutaneous leismaniasis species surveillance for the 2006-2008 period, parasite
	12 42	Word count for the abstract: 149 words identification was carried out for 199 samples from different patients. The prevalence of the
	13 43	various Leishmania species was 84.4% for L.(V)guyanensis, 8.0% for L.(V)braziliensis, 5.0%
	14 44	Word count for the text: 2367 for L.(V)amazonensis and 2.6% for L.(V)lainsoni. L.(V)braziliensis seems to be locally an
	15 45	emerging pathogen.
	16	None of the authors have commercial or other associations causing a potential conflict of
	17	interest.
	18
	19	This work was supported by the University of the French West Indies and French Guiana and
	20	the French Ministère de l'Enseignement Supérieur et de la Recherche Scientifique.
	21	Corresponding author:
	22	Bernard Carme. Laboratoire Hospitalo-Universitaire de Parasitologie et Mycologie Médicale,
	23	Equipe EA 3593, Centre Hospitalier de Cayenne et Faculté de Médecine de l'Université des
			1

Table 1 : Leishmania reference strains used in the study

 1

	Species	WHO Code	CNRL*	CNRL*	RNA polymerase
			strain	zymodeme	II GenBank
			number		accession number
	L. (V.) guyanensis	MHOM/GF/97/LBC6	LEM-3319	MON-45	FJ817490
	L. (V.) braziliensis	MHOM/BR/75/M2903	LEM-396	MON-43	FJ817491
	L. (L.) amazonensis	MHOM/BR/73/M2269	LEM-690	MON-132	FJ817492
	L. (L.) infantum	MHOM/FR/78/LEM75	LEM-75	MON-1	FJ817493
	L. (V.) lainsoni	MHOM/BR/81/M6426	LEM-2208	MON-149	FJ817494
	L. (L.) major	MHOM/SU/73/5-ASKH	LEM-134	MON-4	FJ817495
	L. (V.) naiffi	MDAS/BR/79/M5533	LEM-2204	MON-148	FJ817496

* CNRL: Centre National de Référence des Leishmanioses (The French National Reference Center for Leishmania), Montpellier University Hospital, France (Director: JP Dedet).

Table 1

 1

	PCR RFLP avril 2009 V1	PBC	08/05/2009

Table 2 : Leishmania species determination by PCR-RFLP as a function of the nature of the sample

 2

	Type of sample *	Number PCR + Species determination by RFLP
	Punch skin biopsy	28	24	24
			85.7 %
	Giemsa-stained slide	29	27	27
			93.1 %
	Culture (positive)	55	55	55
			100%
	Total	112	106	106	°(94.6
			94.6%		%)
	* from lesions classified as positive by microscopy
	° 100% of PCR + cases

Table 2

 2

	PCR RFLP avril 2009 V1	PBC	08/05/2009

carme.bernard@wanadoo.fr

(Rotureau et al. 2006a), although it proved difficult to distinguish between L. (V) guyanensis

under sterile conditions and with local anesthesia (lidocaine). Smears were recovered from

infantum and L.(V) lainsoni. Initial digestion with TspRI identified three subgroups (SG):

ecoregion complex(Rotureau 2006b) and the ecologically associated areas of the Amazon


Stéphane Chrétien
email: stephane.chretien@univ-fcomte.fr

The Two Stage l 1 Approach to the Compressed Sensing Problem

This paper gives new results on the recovery of sparse signals using l1-norm minimization. We introduce a twostage l1 algorithm equivalent to the first two iterations of the alternating l1 relaxation introduced in [1].

I. INTRODUCTION

The Compressed sensing problem is currently the focus of an extensive research activity and can be stated as follows : Given a sparse vector x * ∈ R n and an observation matrix A ∈ R m×n with m ≪ n, try to recover the vector x from the small measurement vector y = Ax * . Although the problem consists of solving an overdetermined system of linear equations, enough sparsity will allow to succeed as shown by the following lemma (where Σ s will denote the set of all s-sparse vectors, i.e. vectors whose components are all zero except for at most s of them), Lemma I.1 [START_REF] Cohen | Compressed sensing and best k-term approximation[END_REF] If A is any m × n matrix and 2s ≤ m, then the following properties are equivalent :

i. The decoder ∆ 0 (y) given by ∆ 0 (y) = argmin x∈R n x 0 s.t. Ax = y.

k satisfies ∆ 0 (Ax) = x, for all x ∈ Σ s , ii. For any set of indices T with #T = 2k, the matrix A T has rank 2s where A T stands for the submatrix of A composed of the columns indexed by T only.

A. The l 1 and the Reweighted l 1 relaxations . The main problem with decoder ∆ 0 is that the optimization problem (1) is in general NP-hard. For this reason, the now standard l 1 relaxation strategy is adopted, i.e. the decoder ∆ 1 (y) is obtained as

∆ 1 (y) = argmin x∈R n x 1 s.t. Ax = y. (2)
Now, solving (2) can be done in polynomial time and thus ∆ 1 (y) can be efficiently computed. The second problem is to give robust conditions under which exact recovery holds. One such condition was given by Candes Romberg and Tao [START_REF] Candes | Robust uncertainty principles : Exact signal reconstruction from highly incomplete frequency information[END_REF] and is now known as the Uniform Uncertainty Principle (UUP) or as the Restricted Isometry Property (RIP). One of the main remaining challenges is to reduce the number of observations m needed to recover a given sparse signal x. One idea is the use of l p , p < 0 < 1 decoders ∆ p (y). The main draw back of the approach using l p , p < 0 < 1 norm minimization is that the resulting decoding scheme is again NP-Hard. Another idea is to use a reweighted l 1 approach as proposed in [START_REF] Candes | Enhancing sparcity by reweighted l 1 minimization[END_REF].

Algorithm 1 Reweighted l 1 algorithm (Rew-l 1 ) Input u > 0 and L ∈ N * z (0) u = e x (0) u ∈ min x∈R n , Ax=y x 1 l = 1 while l ≤ N do z (l) u = 1 |x (l) |+u componentwise x (l) u ∈ argmax x∈R n , Ax=y n i=1 w (l-1) i |x i |. l ← l + 1 end while Output z (L) u and x (L) u .
The main intuition behind this reweighted ℓ 1 relaxation is the following. The greater the component x i becomes, the smaller weight it should receive since it can be considered that this component should not be set to zero.

The main drawback of the reweighted l 1 approach is that an unknown parameter is to be tuned whose order of magnitude is hard to know ahead of time.

B. The Alternating l1 algorithm

Another approach was proposed in [START_REF] Chretien | An alternating l 1 for the compressed sensing problem[END_REF] and uses Lagrange duality. Let us write down problem (1), to which ∆ 0 is the solution map, as the following equivalent problem max z∈{0,1} n ,x∈R n e t z s.t. z i x i = 0, i = 1, . . . , n, Ax = y where e denotes the vector of all ones. Here since the sum of the z i 's is maximized, the variable z plays the role of an indicator function for the event that x i = 0. This problem is clearly nonconvex due to the quadratic equality constraints z i x i = 0, i = 1, . . . , n. However, these constraints can be merged into the unique constraint D(z)x 1 = 0, leading to the following equivalent problem

max z∈{0,1} n ,x∈R n e t z s.t. D(z)x 1 = 0, Ax = y. (3)
The Alternating l 1 algorithm consists of a suboptimal alternating minimization procedure to approximate the dual function at u. The algorithm is as follows.

Algorithm 2 Alternating l 1 algorithm (Alt-l 1 ) Input u > 0 and L ∈ N * z (0) u = e x (0) u ∈ max x∈R n , Ax=y L(x, z (0) , u) l = 1 while l ≤ N do z (l) u ∈ argmax z∈{0,1} n L(x (l) u , z, u) x (l) u ∈ argmax x∈R n , Ax=y L(x, z (l) u , u) l ← l + 1 end while Output z (L) u and x (L) u .
Notice that, similarly to the reweighted l 1 algorithm, the Alternating l 1 method also requires the tuning of an unknown parameter u. However, the main motivation for this proposal is that this parameter u has a clear meaning : it is a dual variable which, in the case where the dual function θ(u) is well approximated by the sequence L(x (l) , z (l) , u), can be efficiently optimized without additional prior information, due to the convexity of the dual function.

II. THE TWO STAGE l 1 METHOD

The main remark about the alternating l 1 method is the following (see [START_REF] Chretien | An alternating l 1 for the compressed sensing problem[END_REF]) : for a given dual variable u, the alternating l 1 algorithm can be seen a sequence (x (l) u ) l∈N of truncated l 1norm minimizers of the type

x l u = argmin x∈R n x T l u 1 s.t. Ax = y. ( 4
)
where T l u is the set of indices for which |x l-1 i | < 1 u . Therefore, the Alternating l 1 algorithm can be seen as an iterative thresholding scheme with threshold value equal to 1 u . Now assume for instance that a fraction ρm of the non zero components is well identified by the plain l 1 step with solution x (l) . Then, the practitioner might ask if the appropriate value for u is the one which imposes an l 1 penalty on the index set corresponding to the n -ρm smallest components of x (l) . Moreover, the large scale simulation experiments which have been performed on the plain l 1 relaxation seemed to agree on the fact that the breakdown point occurs near m 4 . Thus, a practitioner could be tempted to wonder whether ρ = 1 4 is a sensible value. Motivated by the previous practical considerations, the two stage l 1 algorithm is defined as follows (the parameter u is now replaced by the parameter ρ = 1 u ). Notice that we restrict ρ to lie in (0, 1 2 ). The reason should be obvious since, due to Lemma I.1, even decoder ∆ 0 (y) is unable to identify more that m 2 -sparse vectors. Another remark is that the procedure could be continued for more than 2 steps but simulation experiments of the Alternating l 1 method seem to confirm that in most cases two steps suffice to converge. Algorithm 3 Two stage l 1 algorithm (2Stage-l 1 ) Input ρ ∈ (0, 1 2 )

Step 0 : x (0) ∈ argmax x∈R n , Ax=y x 1 and T =index set of the ρm largest components of x (0)

Step 1 :

x (1) ∈ argmax x∈R n , Ax=y x T c 1 Output x (1) ρ .

III. MAIN RESULTS

At

Step 1 of the method, a subset T is selected with cardinal ρm and optimization is then performed with objective function x T c 1 . In this section, we will adopt the following notations : S will denote the support of x * , T will denote the index set of the ρm largest components of x (0) as defined in the two-stage l 1 algorithm. T c g will be an abbreviation of (T c ) g , the "good" subset of T c or, in mathematical terms, the subset of indices of S which also belong to T c . On the other hand, T c b will denote the complement of T c g in T c .

Lemma III.1 Assume the cardinal of T c

g is less than γ/2 and that A satisfies RIP (δ, γs). Let h (1) = x (1) -x * . Then, there exists a positive number C * depending on x * such that h

(1) T 1 ≤ C * x * T c b 1 . Moreover, if h (1) T 1 = 0, then x * T c b 1 = 0.
Proof. Let N (h T ) denote the optimal value of the problem

min hT b ∈R n-s x * T c b + h T c b 1 (5) subject to A T c b (x * T c b + h T c b ) + A T c g x (1) g = y -A T (x * T + h T ).
Assume that x * T c b = 0. Then, N (h T ) the role of a norm for h T although it does not satisfy the triangle inequality. In particular, N (h T ) is nonnegative, convex and N (h T ) = 0 implies that h T = 0.

Nonnegativity and convexity are straightforward. Assume that N (h T ) = 0, i.e. the solution h of ( 5) is null. This implies that A T c g x

(1)

T c g = y -A T x * T c = A T c b x T c b , which implies that x (1) T c g -x T c
b is in the kernel of A T c g . Using the fact that T c g has cardinal less that γs/2 and the RIP (δ, γs) assumption, we conclude that x

(1)

T c g = x T c b .
In order to finish the proof of the lemma, it remains to recall that N (h T ) is convex and that, by Theorem 1.1 in [START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF], h (1) 1 (and thus h

(1) T 1 ) is bounded from above by C inf #U ≤γ/2 x U c 1 in order to obtain existence of a sufficiently small positive constant C * depending on x * such that N (h T ) ≥ C * h T 1 for all h T in the ball B(0, C x * 1 ). The desired result then follows.

To prove that N (h T ) = 0 if h T = 0 is a bit harder. Thus, assume that h T = 0. Then, the solution h of ( 5) is just the solution of

min hT b ∈R n-s h T c b 1 A T c b h T c b = y -A T -x * T -A T c g x (1) g . Now since y = Ax * , we obtain that y -A T -x * T -A T c g x (1)
g = A T c g (x * T c -x (1)
g ) and thus, the right hand side term is nothing but the image of a γs/2-sparse vector. Now, recalling that we assumed RIP (δ, γs), Theorem 1.1 in [START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF] implies that h must be the sparsest solution of the system

A T c b h T c b = y - A T x * T -A T c g x (1)
g from which we deduce that h is γs/2-sparse. Therefore the vector (h T c b , x

(1)

T c g ) is γs which solves A T c x T c = y -A T x *
T . On the other hand, x * T c also solves

A T c x T c = y - A T x *
T and its support is included in the support of (h T c b , x

(1) T c g ). Therefore, (h T c b , x

(1) T c g )-x * T c is a γs/2 sparse vector which lies in the kernel of A. Using again the fact that RIP (δ, γs) holds, we conclude that (h T c b , x Theorem III.1 Assume that RIP (δ, γs) holds and that an index set T g of cardinal greater than or equal to (1 -γ/2)s has been recovered at Step 0 after thresholding, then x (1) satisfies

x (1) -x * 1 ≤ C * * x * T c
b . for some constant C * * depending on x * .

Proof. The vector x (1) satisfies

x (1) T c 1 ≤ x * T c 1 . (6)
Let us write h (1) = x (1) -x * . Using (6), a now standard decomposition gives

x * T c g 1 -h T c g 1 + h T c b 1 -x * T c b 1 ≤ x * T c g 1 + x * T c b 1 . We thus obtain h T c b 1 ≤ h T c g 1 + 2 x * T c b 1 . (7)
However, since RIP (δ, γs) holds, N SP (C, γ/2s) holds too, with C < 1. Therefore, we obtain that

h T c g 1 ≤ C( h T c b 1 + h T 1 ). (8)
Combining ( 7) and (8), we obtain

h T c b 1 ≤ C 1 -C h T 1 + 2 1 -C x * T c b 1 . (9)
As a consequence, we obtain that

h 1 ≤ C(2 x * T c b 1 + C ′ h T 1 ) + h T 1 + 2 x * T c b 1 +C h T 1 + h T 1 = (1 + C + CC ′ ) h T 1 + 2(1 + C) x * T c b 1 . which, using Lemma III.1, implies h 1 ≤ ((1 + C + CC ′ )C * + 2(1 + C)) x * T c b 1 . (10)
which is the desired bound.

The following corollary is a straightforward consequence of the previous theorem.

R ÉF ÉRENCES

  x * T c = 0. Thus, h T c b = 0 and x (1) T c g ) = x *T c . Using this lemma, we deduce the following theorem.

Corollary III. 1

 1 FIG. 1. Rate of success over 300 Monte Carlo experiments in recovering the support of the signal vs. signal sparsity k for n = 128, m = 50, L = 4, u = 3. A and nonnul components of x were drawn from the gaussian N (0, 1) distribution. The results for the two-stage l 1 method are represented by the "+ in a circle" sign.