Wei-Lin Hu

Christopher J Pappas

Jun-Jie Zhang

You-Yun Yang

Jie Yan

Mathieu Picardeau
email: mathieupicardeau@pasteur.frx.

Frank Yang

X Frank Yang
email: xfyang@iupui.edu

The EbpA-RpoN regulatory pathway of the pathogen Leptospira interrogans is essential for survival in the environment

Keywords:

INTRODUCTION

Leptospires are a group of spirochetes that include both saprophytic and pathogenic species within the genus Leptospira [START_REF] Adler | Leptospira and leptospirosis[END_REF]. Pathogenic species including L. interrogans, are the causative agents of leptospirosis, the most widespread zoonotic infectious disease in the world. Saprophytic species including L. biflexa, are found primarily in aquatic and terrestrial environments and are considered non-pathogenic. Pathogenic leptospires also can survive in the terrestrial environment for a prolonged period, and humans are typically infected by direct or indirect contact with soil or water that is contaminated with the urine of infected animals.

L. interrogans must adapt to both aquatic and mammalian host conditions in order to be successfully maintained in its zoonotic cycle. Some progress has been made on how L. interrogans alters its gene expression to cope with environmental change. Whole-genome microarrays and high-throughput RNA sequencing analyses revealed global changes in transcript levels of L. interrogans in response to temperature [START_REF] Lo | Effects of temperature on gene expression patterns in Leptospira interrogans serovar Lai as assessed by whole-genome microarrays[END_REF], osmolality (3), iron depletion (4), serum exposure [START_REF] Patarakul | Global transcriptomic response of Leptospira interrogans serovar Copenhageni upon exposure to serum[END_REF], interaction with phagocytic cells [START_REF] Xue | Transcriptional responses of Leptospira interrogans to host innate immunity: significant changes in metabolism, oxygen tolerance, and outer membrane[END_REF], and cultivation in a host-adapted model (the dialysis membrane chambers model) [START_REF] Caimano | A model system for studying the transcriptomic and physiological changes associated with mammalian host-adaptation by Leptospira interrogans serovar Copenhageni[END_REF]. Understanding how L. interrogans senses environmental and host signals and regulates its gene expression has just begun to be explored.

Little is known about the regulation of gene expression in L. interrogans. It was shown that the PerR homolog in L. interrogans acted as a regulator of the oxidative stress response [START_REF] Matsunaga | Response of Leptospira interrogans to physiologic osmolarity: relevance in signaling the environment-to-host transition[END_REF][START_REF] Lo | Transcriptional response of Leptospira interrogans to iron limitation and characterization of a PerR homolog[END_REF][START_REF] Pappas | A replicative plasmid vector allows efficient complementation of pathogenic Leptospira strains[END_REF]. The KdpE sensor was shown to be an activator of the KdpABC potassium transporter [START_REF] Matsunaga | Positive regulation of Leptospira interrogans kdp expression by KdpE as demonstrated with a novel beta-galactosidase reporter in Leptospira biflexa[END_REF]., The LexA repressor bound to the promoter of recA is involved in DNA repair [START_REF] Cune | The Leptospira interrogans lexA gene is not autoregulated[END_REF]. HemR regulates the heme biosynthetic pathway [START_REF] Louvel | Heme rescues a two-component system Leptospira biflexa mutant[END_REF][START_REF] Morero | HemR is an OmpR/PhoB-like response regulator from Leptospira, which simultaneously effects transcriptional activation and repression of key haem metabolism genes[END_REF]. Despite these advances, the regulatory pathways underlying environmental sensing and host adaptation of L. interrogans remain poorly understood, largely due to the lack of a robust system for genetic manipulation of Leptospira.

One common mechanism of regulating bacterial gene expression is the use of an alternative sigma factors (σ). In addition to the housekeeping sigma factor σ 70 (RpoD), Leptospira species have several alternative sigma factors, including σ 54 (RpoN), σ F (FliA,), σ B , and 5 to 11 extracytoplasmic function (ECF) sigma factors (σ E ) [START_REF] Fouts | What makes a bacterial species pathogenic?: comparative genomic analysis of the genus Leptospira[END_REF][START_REF] Picardeau | Genome sequence of the saprophyte Leptospira biflexa provides insights into the evolution of Leptospira and the pathogenesis of leptospirosis[END_REF][START_REF] Ren | Unique physiological and pathogenic features of Leptospira interrogans revealed by whole-genome sequencing[END_REF]. Among these alternative σ factors, σ 54 is phylogenetically different from the other σ factors; all other alternative σ factors belong to the σ 70 family. σ 54 recognizes a unique -24/-12 promoter sequence (instead of the -35/-10 promoter sequence for σ 70 ). In addition, transcriptional activation from a σ 54 -type promoter always requires a bacterial enhancer binding protein (EBP) [START_REF] Bush | The role of bacterial enhancer binding proteins as specialized activators of sigma54-dependent transcription[END_REF][START_REF] Wigneshweraraj | Modus operandi of the bacterial RNA polymerase containing the sigma54 promoter-specificity factor[END_REF]. A typical EBP consists of an N-terminal allosteric effector binding domain for sensing the signal, an AAA+ NTPase domain for σ 54 activation, and a C terminal helix-turn-helix domain for DNA binding. The EBP binds to the enhancer region, where it curves toward and interacts with the σ 54 holoenzyme. Upon sensing a signal, the EBP is activated, which in turn activates σ 54 by AAA+-type ATPase activity. This activation energy promotes the closed complex of the holoenzyme and the formation of an open complex at the promoter, resulting in the transcriptional activation of σ 54 -dependent genes.

σ 54 has been shown to modulate many cellular processes including nitrogen assimilation, motility, virulence, and biofilm formation in bacteria [START_REF] Bush | The role of bacterial enhancer binding proteins as specialized activators of sigma54-dependent transcription[END_REF][START_REF] Wigneshweraraj | Modus operandi of the bacterial RNA polymerase containing the sigma54 promoter-specificity factor[END_REF][START_REF] Francke | Comparative analyses imply that the enigmatic Sigma factor 54 is a central controller of the bacterial exterior[END_REF]. Previous experiments have ascertained that rpoN, while typically associated with pathogenic adaptation to host environment, has also been shown to play a role in ecological adaptation and survival. Therefore, we attempted to characterize the role of an rpoN regulon in pathogenic Leptospira [START_REF] Francke | Comparative analyses imply that the enigmatic Sigma factor 54 is a central controller of the bacterial exterior[END_REF][START_REF] Cytryn | Transcriptional and physiological responses of Bradyrhizobium japonicum to desiccation-induced stress[END_REF][START_REF] Hwang | Roles of RpoN in the resistance of Campylobacter jejuni under various stress conditions[END_REF]. In this study, using a combination of bioinformatic, biochemical, and genetic approaches, we report identification of the EbpA-RpoN regulatory pathway in L. interrogans. This pathway constitutes a σ 54 activator (LMANv2_37011, hereafter referred to as EbpA), σ 54 (LMANv2_590036, RpoN), and at least three downstream targets. We found that this pathway is not essential for mammalian infection but plays an important role in L. interrogans adaptation to diverse environmental conditions during the enzootic cycle. and 50 μg/ml of spectinomycin (Sigma) as previously described [START_REF] Eshghi | A putative regulatory genetic locus modulates virulence in the pathogen Leptospira interrogans[END_REF]. The ebpA construct was then randomly cis-inserted into the genome of ebpA1 -(Man 250) via conjugation between Man250 and E. coli strain SM10 carrying pAL614-ebpA as previously described [START_REF] Eshghi | Leptospira interrogans lpxD homologue is required for thermal acclimatization and virulence[END_REF].

MATERIALS AND METHODS

Strains

Sequence analysis was performed as previously described [START_REF] Eshghi | Leptospira interrogans lpxD homologue is required for thermal acclimatization and virulence[END_REF] and revealed the ebpA -/+ clone used in this study was cis inserted into LMANv2_590053.

RNA isolation and qRT-PCR.

For the initial qRT-PCR analysis of wild type and epbA1 - samples by relative quantity, leptospires were grown in EMJH at 28°C and harvested when bacterial growth reached late logarithmic phase (10 7 /ml). Total RNA was isolated using Trizol according to the manufacturer's instructions (Invitrogen) and genomic DNA was digested using RNase-free DNase I (Promega). RNA was then further purified using RNeasy Mini Kit (Qiagen, Valencia, CA). cDNA was synthesized using the SuperScript III reverse transcriptase with random primers (Invitrogen, Carlsbad, CA Recombinant protein expression and purification. Recombinant RpoN was produced in E.

coli using the aLICator LIC cloning and expression system (Thermo Scientific). Briefly, the full-length rpoN gene was amplified from L. interrogans serovar Manilae strain L495 using primers pLATE52-rpoN F/pLATE52-rpoN R (Table 1) and cloned into pLATE52 to generate the pLATE52 rpoN plasmid, which was then transformed into One Shot® TOP10

Chemically Competent E. coli (Invitrogen) for sequencing. The plasmid containing the rpoN sequence was transformed into E. coli BL21 (DE3) (Novagen) to form E. coli BL21DE3 pLATE52-rpoN . All of the engineered bacteria were cultured in 100 μg/ml ampicillin-containing LB broth to express the recombinant proteins under induction by 0.5 mM isopropyl-β-D-thiogalactoside (IPTG) (Sigma). The His6-tagged recombinant proteins were purified using the Ni-NTA column according to the manufacturer's instructions (Qiagen) and analyzed by SDS-PAGE. To obtain the recombinant protein EbpA, the full-length ebpA gene was PCR amplified from L. interrogans strain L495 genomic DNA using the primers pGEX-4T-2-ebpA F/pGEX-4T-2-ebpA R (Table 1). The product was cloned into pMD18-T to form a recombinant pMD18-T ebpA plasmid for sequencing. The pMD18-T ebpA and pGEX-4T-2 vectors (Amersham Pharmacia Biotech) were digested with both BamHI and NotI endonucleases (New England Biolabs, NEB). The recovered ebpA gene segment was linked to the linearized pGEX-4T-2 using T4 DNA ligase (NEB) to form the pGEX-4T-2 ebpA plasmid. pGEX-4T-2 ebpA was transformed into E. coli BL21 (DE3)

(Novagen) to generate E. coli BL21DE3 pGEX-4T-2-ebpA . The recombinant EbpA protein (rEbpA)

was expressed by induction with 0.5 mM IPTG (Sigma), and the fusion protein with GST was extracted from the cell lysates after ultrasonication using Bio-Scale Mini Profinity GST Cartridges (Bio-Rad). The rEbpA protein was cleaved with thrombin (Amersham Pharmacia Biotech) and purified further with Amicon Ultra-4 centrifugal filter (Millipore, NMWL 50 kDa) to remove the GST and thrombin. The soluble recombinant protein was filtered by using a 0.22 μm pore size membrane filter, examined by SDS-PAGE and measured by using the BCA protein assay kit (Bio-Rad).

Electrophoretic mobility shift assay (EMSA).

Primers used in EMSA are listed in Table 1.

Synthesized or PCR-amplified DNA probes were end-labeled with biotin using biotin-labeled forward primers (Invitrogen, Shanghai, China). EMSA was performed by using the LightShift™ Chemiluminescent EMSA Kit (Thermo Scientific). Briefly, 200 nM labeled probe was mixed with various amounts of purified rRpoN or rEbpA in 20 μl of the gel shift binding buffer containing 10 mM Tris (pH 7.5), 50 mM KCl, 1 mM dithiothreitol (DTT), 5

mM MgCl 2 and 5% v/v glycerol. After being incubated at 37°C for 30 min, the samples were analyzed by 10% non-denaturing polyacrylamide gel electrophoresis at 60 V for 3-6 h. Then, DNA was transferred onto a positively charged nylon membrane (Roche Applied Science, USA) by electroblotting (380 mA for 80 min). After UV cross-linking, blotting and washing, the membrane was conjugated by stabilized streptavidin-horseradish peroxidase. Signals were detected following the manufacturer's instructions after exposure using a camera equipped with a CCD imager (FluorChem E, ProteinSimple).

Growth curve, survival, and cell morphology. L. interrogans strains, including the ebpA1 mutant, were first grown in standard EMJH medium to late log phase (10 7 /ml). Then, the bacteria-containing media was diluted at a ratio of 1:10 into EMJH or EMJH with 5 mM alanine replacing the NH 4 Cl. For the water survival test, L. interrogans strains were grown to late logarithmic phase before they were harvested by centrifugation. The supernatants were drained thoroughly, and the cells were re-suspended to the original volume in spring water (pH 7.2) (Kirkland Signature). All cultures were incubated at 30°C, and the motile leptospires were enumerated every 24 hours under dark-field microscopy by Petroff-Hausser counting chamber according to the manufacturer's instructions (Hausser Scientific, PA). The viability of the spirochetes was confirmed by growth in standard EMJH medium.

Cell morphology was measured in wild type, ebpA1 -, ebpA2 -, and ebpA -/+ cells grown in standard EMJH medium to late-logarithmic phase (10 7 /ml) as described above. The lengths of 100-200 cells of each strain were measured using an Olympus Bx53 microscope and Olympus CellSens Dimension 1.7.1 software (Olympus, Hamburg, Germany). Fields were randomly selected for measuring leptospire cell length. Average length and standard error of the mean were calculated by Graphpad software (Prism, San Diego, CA). Statistical analyses were completed by one-way ANOVA and Tukey's HSD test, where significance was defined as P<0.05.

Determination of the contribution of EbpA to virulence in Mongolian gerbils.

Three-week-old male Mongolian gerbils (Meriones unguiculatus) were purchased from Janvier labs (Janvier, Le Geneste-Saint-Isle, France). Four gerbils per group were tested for survival against wild type, epbA1 -, or epbA2 -strains in accordance with the guidelines of the Animal Care and Use Committees of the Institut Pasteur (authorization B-75-1132).

Following intraperitoneal injection with 10 4 or 10 6 leptospires, gerbils were observed twice daily until day 21 post inoculation. Following euthanasia at day 21, approximately 300 μl of blood was collected along with kidneys by dissection. The outgrowth of spirochetes in these tissue cultures was assessed using dark-field microscopy.

RESULTS

In silico prediction of RpoN (σ 54 ) regulatory network in L. interrogans. Genome sequences reveal that all sequenced Leptospira species (including pathogenic, saprophytic, and intermediate strains) have the alternative sigma factor σ 54 . To study the role of σ 54 in the enzootic cycle of L. interrogans, we first performed in silico analysis of the σ 54 network in L.

interrogans. Since its activation always requires an activator, an EBP, which has a conserved domain for activation of σ 54 -polymerase-dependent transcriptional initiation, we analyzed the presence of EBPs among Leptospira species. Our analyses revealed that all pathogenic

Leptospira have two activators (herein named as Leptospira enhancer-binding protein A and B: EbpA [LMANv2_37011, fhlA-like [START_REF] Bush | The role of bacterial enhancer binding proteins as specialized activators of sigma54-dependent transcription[END_REF][START_REF] Francke | Comparative analyses imply that the enigmatic Sigma factor 54 is a central controller of the bacterial exterior[END_REF]] and EbpB [LMANv2_590040, NtrC-like [START_REF] Bush | The role of bacterial enhancer binding proteins as specialized activators of sigma54-dependent transcription[END_REF][START_REF] Francke | Comparative analyses imply that the enigmatic Sigma factor 54 is a central controller of the bacterial exterior[END_REF]]. These results suggest that within the σ 54 regulon, there are two pathways, EbpA-RpoN (σ 54 ) and EbpB-RpoN (σ 54 ), that activate two sets of genes that utilize a σ 54 -type promoter (Fig. 1).

Because σ 54 recognizes a unique -24/-12 promoter sequence, σ 54 -dependent genes can be predicted in silico. In this regard, Francke et al. performed a comparative genome analysis of over 300 genuses, based on the frequency representation of the σ 54 promoter [START_REF] Francke | Comparative analyses imply that the enigmatic Sigma factor 54 is a central controller of the bacterial exterior[END_REF]. Based on their results, we searched the L. interrogans genomes using Promscan Analysis Tools (http://www.promscan.uklinux.net) and queried for genes containing a putative RpoN binding sequence in putative promoter regions. We identified 13 putative RpoN (σ 54 )-type promoters for 22 genes in L. interrogans 56601 and L495 strains (where genes shared by the same promoter were grouped) (Table 2). Twenty-one of these genes were located on chromosome I, and one gene was located on chromosome II. Five of these genes encode hypothetical proteins, and seventeen genes encode proteins with assigned functions such as nitrogen assimilation, glutamine synthesis, alanine racemization, flagellar synthesis, sodium bile acid symport, and lipid A biosynthesis. Given that L. interrogans has two EBPs, we predicted that one set of these twenty-two genes is controlled by the EbpA-RpoN pathway, and the other set is governed by EbpB-RpoN.

Inactivation and complementation of the enhancer binding protein gene ebpA. To investigate the function of the σ 54 regulon in L. interrogans, we initially attempted to inactivate rpoN (encoding σ 54 ) in L. interrogans strains. However, multiple attempts were unsuccessful. A random transposon mutant library in L. interrogans serovar Manilae strain L495 also has not yet yielded an rpoN-disrupted mutant [START_REF] Bourhy | Random insertional mutagenesis of Leptospira interrogans, the agent of leptospirosis, using a mariner transposon[END_REF]. However, the library did yield two biologically distinct mutants with transposon insertion within the proximal region of ebpA [START_REF] Murray | Genome-wide transposon mutagenesis in pathogenic Leptospira species[END_REF] . These biologically distinct mutants were named ebpA1 (transposon library ID: M250) and ebpA2 (transposon library ID: M1407).

To study the function of ebpA and to fulfill molecular Koch's postulates, we first performed complementation for ebpA (named epbA -/+ ) by randomly cis-insertion of a wild-type copy of ebpA (including its upstream native promoter) into the ebpA1 mutant.

Subsequent sequence analysis revealed that one of the ebpA -/+ clones used in this study harbored an epbA insertion at the distal region of LMANv2_590053 (conserved protein of unknown function) at NT 4079032. qRT-PCR analyses demonstrated that the two epbA mutants did not express ebpA; whereas the complemented strain ebpA -/+ successfully restored ebpA expression (Fig. 2).

Deletion of ebpA affects cell morphology in L. interrogans. Qualitative examination of the ebpA mutant by microscopy revealed no defect in motility. However, we observed that the ebpA mutant appeared shorter in length than the wild type strain. Further quantitative analyses of cell length showed that the two ebpA mutants were significantly shorter in cell length (7.365 μm ± 0.1782 μm, P<0.01 and 7.566 μm ± 0.1631 μm, P<0.01) than the wild type (10.99 μm ± 0.3118 μm) when grown to mid-to-late logarithmic phase.

Complementation of ebpA1 restored the cell length in epbA -/+ (10.47 μm ± 0.2129 μm, P<0.01) (Fig. 3).

Identification of EbpA-regulated genes by qRT-PCR. To identify genes controlled by the EbpA-RpoN pathway, initial qRT-PCR analysis by relative fold change between wild type and the ebpA mutants was performed. Among the twenty-two predicted RpoN-controlled genes, three genes -LMANv2_31003 (amtB, ammonia transporter gene), LMANv2_200027

(a conserved exported protein), and LMANv2_290065 (a putative outer membrane protein)had significantly lower expression in the ebpA mutant than the wild-type strain (P<0.01) (Fig. 4A). Based on this information, a second analysis was performed by comparing the absolute transcript levels of the above identified genes to copies of 16S rRNA, which is constitutively expressed under standard in vitro growth conditions at 30˚C [START_REF] Carrillo-Casas | Selection of the internal control gene for real-time quantitative rt-PCR assays in temperature treated Leptospira[END_REF] in wild-type, the ebpA mutants and epbA -/+ . This study re-confirmed the above findings of significantly lower expression of amtB, LMANv2_200027, and LMANv2_290065 in the ebpA mutant compared to wild type (5-10 fold change) (Fig. 4B). The complemented strain epbA -/+ restored expression of amtB, LMANv2_200027, and LMANv2_290065) (Fig. 4B). These results

suggest that EbpA-RpoN regulates expression of amtB, LMANv2_200027, and LMANv2_290065.

RpoN and EbpA bind to the promoter region of amtB, LMANv2_200027, and

LMANv2_290065. To demonstrate that amtB, LMANv2_200027, and LMANv2_290065 have an RpoN (σ 54 ) promoter, we purified recombinant RpoN of L. interrogans and performed EMSA assay. A 50 bp oligonucleotide encoding the predicted -24/-12 promoter region of amtB, LMANv2_200027, and LMANv2_290065 was end-labeled with biotin and mixed with different amounts of purified recombinant RpoN in binding buffer. The results showed that L.

interrogans RpoN bound to the predicted σ 54 promoter of amtB, LMANv2_200027, and LMANv2_290065 in a dose-dependent manner (Fig. 5A). The bindings were specific, since unlabeled DNA fragments could compete for binding and no binding was observed when bovine serum albumin (BSA) was used instead of RpoN. Furthermore, mutated probes (MRN027: -25TGGCA>AAAAT; -14TTGC>AATT, MRN065: -25TGGCA>AAAAT;

-14TTGC>AATT or MRN003: -25TGGTA>AAAAT; -14TTGC>AATT) in the -24/-12 region did not show binding (Fig. 5B). These data provide biochemical evidence that amtB, LMANv2_200027, and LMANv2_290065 have an RpoN (σ 54 )-type promoter.

Since L. interrogans has two predicted EBPs, a gene with an RpoN (σ 54 )-type promoter can be activated either by EbpA or by EbpB. To gain biochemical evidence that amtB, LMANv2_200027, and LMANv2_290065 are under the control of EbpA, we further performed EMSA using recombinant EbpA. Because EbpA is a putative enhancer-binding protein that can bind at a site far from the promoter, 500 bp DNA fragments of the amtB, LMANV_200027, or LMANV_290065 promoter regions (EA003, EA027, EA065, -450 bp and +50 bp relative to the ATG start codon) were used for the EMSA assays. As shown in Fig. 6A, rEbpA was capable of binding to the upstream region of amtB, LMANv2_200027, and LMANv2_290065. Unlabeled EA003, EA027, or EA065 could compete for binding, but sheared salmon sperm DNA did not. In addition, no DNA-BSA complex was observed (Fig. 6B). Furthermore, neither rRpoN nor rEbpA bound to the sigma70-type promoter region (L41) of lipL41. On the other hand, rRpoN bound to the promoter region of lipL41 when the sigma70-type promoter was replaced with a sigma54-type promoter (RL41) (Fig. 6C).

However, rEbpA could not bind to RL41 despite that RL41 contained a sigma54-type promoter, suggesting that rEbpA binding to amtB, LMANv2_200027, and LMANv2_290065 is specific. The results of these biochemical experiments, along with the genetic data above, suggest that EbpA is the regulator that activates amtB, LMANv2_200027, and

LMANv2_290065 by binding to the upstream binding regions near their promoters.

The ebpA mutant had reduced growth and survival under various conditions. amtB, predicted to encode an ammonia transporter protein (PSORT-B, TMhmm), is putatively co-transcribed with glnK, which encodes a nitrogen regulatory protein in L. interrogans [START_REF] Patarakul | Global transcriptomic response of Leptospira interrogans serovar Copenhageni upon exposure to serum[END_REF][START_REF] Heinrich | Interaction of the membrane-bound GlnK-AmtB complex with the master regulator of nitrogen metabolism TnrA in Bacillus subtilis[END_REF]. We therefore examined the growth of the ebpA mutant in EMJH liquid media with alternative nitrogen sources. There was no significant difference in growth observed between wild-type and ebpA1 -grown in standard EMJH media with 5 mM ammonium chloride (Fig. 7A) [START_REF] Johnson | Differentiation of pathogenic and saprophytic letospires. I. Growth at low temperatures[END_REF][START_REF] Ellinghausen | Nutrition of Leptospira pomona and growth of 13 other serotypes: fracionation of oleic albumin complex and a medium of bovine albumin and polysorbate 80[END_REF]. However, when 5 mM L-alanine, a poor nitrogen source, was supplemented in nitrogen-free EMJH media, the ebpA1 -mutant had significantly reduced growth compared to the wild type (Fig. 7B).

To investigate the survival abilities of the ebpA1 mutant in stress conditions, wild type, ebpA1 -, and epbA1 -/+ strains were cultivated in either 1:10 diluted EMJH or in spring water.

The ebpA mutant had a lag phase at the initial stage in nutrient-limited media (Fig. 7C).

Wild-type L. interrogans can survive in spring water for weeks, and the spirochetal numbers remained high till week 5, and the numbers began to drop at week 6 (Fig. 7D). At weeks 6, wild-type spirochetes remained alive and cultivable (data not shown). In contrast, the numbers of the ebpA mutant began dropped significantly at less than week 1 (Fig. 7D). At week 4, althrough some mutant spirochetes remained (Fig. 7D), but no live and cultivable mutant spirochetes could be detected (data not shown). These results suggest that EbpA is important for Leptospira to survive in water.

ebpA is dispensable for virulence. To determine if ebpA plays a role in virulence, 10 4 cells of either wild type or epbA2 were inoculated into gerbils, and the gerbils were observed for 21 days. Data indicate that the abrogation of the ebpA gene does not reduce mortality in gerbils (Fig. 8). Similar results were found between wild type and ebpA1 when 10 6 cells were inoculated intraperitoneally (data not shown). Viable spirochetes for all of the strains inoculated were recovered from renal tissue and blood. These results suggest that EbpA is not essential for mammalian infection.

DISCUSSION

Little is known about the signaling and regulatory pathways underlying the differential gene expression of L. interrogans. In this study, we provide bioinformatic, genetic, and biochemical evidence to demonstrate the presence of the EbpA-RpoN pathway in which the bacterial enhancer-binding protein EbpA and the sigma factor σ 54 work together to activate at least three genes from their σ 54 -type promoters: amtB (encoding ammonia transporter),

LMANv2_200027 (encoding a conserved exported protein), and LMANv2_290065 (encoding a putative outer membrane protein). This pathway appears not to be essential for mammalian infection, but plays an important role for L. interrogans to survive in the environment.

RpoN has been shown to be involved in regulation of many bacterial functions such as nitrogen metabolism, flagellar biosynthesis, osmotolerance, pH changes, biofilm formation, motility, colonization, lipoprotein biosynthesis and a Type III secretion system [START_REF] Francke | Comparative analyses imply that the enigmatic Sigma factor 54 is a central controller of the bacterial exterior[END_REF][START_REF] Fisher | Borrelia burgdorferi sigma54 is required for mammalian infection and vector transmission but not for tick colonization[END_REF][START_REF] Jovanovic | Regulation of the co-evolved HrpR and HrpS AAA+ proteins required for Pseudomonas syringae pathogenicity[END_REF][START_REF] Zhao | Promoter and regulon analysis of nitrogen assimilation factor, sigma54, reveal alternative strategy for E. coli MG1655 flagellar biosynthesis[END_REF]. Bioinformatics analysis predicted 13 putative RpoN (σ 54 )-type promoters controlling 22 genes in L. interrogans. Using the ebpA mutant and EMSA assay, we demonstrated that at least three of these genes amtB, LMANv2_200027, and LMANv2_290065, are under the control of EbpA. Other predicted RpoN-dependent genes could be controlled by EbpB.

Interestingly, 3 of these genes have been demonstrated to be under the control of RpoN in other bacteria: lpxC, which is responsible for the first committed step in lipid A biosynthesis regulated by RpoN in Aquifex aeolicus [START_REF] Vidangos | DNA recognition by a sigma(54) transcriptional activator from Aquifex aeolicus[END_REF]; pstA, encoding phosphoenolpyruvate-protein phosphotransferase, which participates in regulation of the σ 54 -dependent promoter in Rhizobium etli [START_REF] Michiels | The Rhizobium etli rpoN locus: DNA sequence analysis and phenotypical characterization of rpoN, ptsN, and ptsA mutants[END_REF]; and glnA, encoding glutamine synthetase, the RpoN-dependent gene in E. coli [START_REF] Reitzer | Metabolic context and possible physiological themes of sigma(54)-dependent genes in Escherichia coli[END_REF]. Other putative RpoN-dependent genes include ones encoding a sodium bile acid symporter, a pyridoxamine-phosphate oxidase, an endoflagellar biogenesis protein, an alanine racemase, and proteins with unknown function. Although they remain to be confirmed, these observations suggest multi-functional roles of RpoN in L. interrogans.

We demonstrated that the ebpA mutant had impaired ability to use alanine as an alternative nitrogen source, and more importantly, had reduced survival in water. Bacteria assimilate a variety of inorganic nitrogen sources; such as ammonia, amino acids, peptides, polyamines and related compounds, cytosine, nucleosides, and other compounds [START_REF] Reitzer | Nitrogen assimilation and global regulation in Escherichia coli[END_REF].

Ammonia supports the fastest growth rate and is therefore considered the preferred nitrogen source among most bacteria. Ammonia and ammonium transport proteins belonging to the Amt protein family are ubiquitous in prokaryotes. Nearly all prokaryotes encode at least one Amt protein and in some cases two or three homologues within their respective genomes [START_REF] Javelle | Complex formation between AmtB and GlnK: an ancestral role in prokaryotic nitrogen control[END_REF]. Based on analyses of the genomes of leptospires, three genes were predicted to be involved in nitrogen assimilation. amtB (LIC10441) and glnK (LIC10440), co-transcribed as an operon and encoding ammonia permease and nitrogen regulatory protein II (PII), respectively (5), were dramatically down-regulated in both of the ebpA mutant strains in our study. PII serves as a signal transduction protein for sensing external ammonium availability and nitrogen status of the cell. Ammonia permease acts as a channel for ammonium transport.

In E. coli and other bacteria, amtB-glnK are also considered a signal transduction pathway. In a nitrogen/ammonia-rich environment, GlnK is physically bound to AmtB, disrupting uptake of free ammonia [START_REF] Conroy | The crystal structure of the Escherichia coli AmtB-GlnK complex reveals how GlnK regulates the ammonia channel[END_REF]. However, in an ammonium/nitrogen-scarce environment, GlnK is unbound from AmtB, allowing GlnK to interact intracellularly with other proteins, most of which are unknown [START_REF] Jack | The signal transduction protein GlnK is required for NifL-dependent nitrogen control of nif gene expression in Klebsiella pneumoniae[END_REF][START_REF] Coutts | Membrane sequestration of the signal transduction protein GlnK by the ammonium transporter AmtB[END_REF]. In turn, this suggests that AmtB moonlights as a sensor of external nitrogen availability. Further, it has been previously suggested the AmtB-GlnK complex is critical for sensing and responding to nitrogen scarcity [START_REF] Reitzer | Nitrogen assimilation and global regulation in Escherichia coli[END_REF]. Our data suggest a similar pattern in Leptospira: the reduced expression of amtB and glnK in ebpA mutants may create an inadequate intracellular stress response to nitrogen scarcity. There is another gene, amt3 (LIC10589, LMANv2_130007), which encodes an alternative ammonium transporter that does not appear having a RpoN-type promoter. The presence of the alternative ammonium transporter LMANv2_130007 may explain the lack of growth defect in the ebpA mutant when growing in a nitrogen-rich medium. Activation of LMANv2_130007 or another as yet unidentified ammonium transporter may work redundantly to ensure sufficient uptake of nitrogen under conditions when EbpA-RpoN is inactivated. Concordantly, previous studies have shown that expression of the glnK-amtB operon is generally induced during growth under limited ammonium conditions. Thus, loss of ammonia transport along with loss of GlnK intracellular signaling may explain the observed growth phenotype of the ebpA mutant when grown with a poor nitrogen source such as alanine and spring water [START_REF] Javelle | Complex formation between AmtB and GlnK: an ancestral role in prokaryotic nitrogen control[END_REF]. During infection, leptospires are exposed to a nutrient-rich host environment. It has been reported

that amtB and glnK were down-regulated when exposed to serum [START_REF] Patarakul | Global transcriptomic response of Leptospira interrogans serovar Copenhageni upon exposure to serum[END_REF]. This may explain why ebpA and amtB are dispensable for virulence during infection.

We found that the ebpA mutant has shortened cell length. This may be due to a variety of global response changes within the bacterium upon disruption of the epbA-rpoN pathway.

One possibility is that the lack of a strong nitrogen source in the bacterium may partially activate the stringent response pathway (rel) in leptospires, as rel activation in Borrelia burgdorferi is important as an alarmone response that results in global changes within that species 41). Likewise, rel has been associated with cell morphology changes in other bacteria [START_REF] Drecktrah | The Borrelia burgdorferi RelA/SpoT homolog and stringent response regulate survival in the tick vector and global gene expression during starvation[END_REF]. This phenotype was also observed in a previously described lpxD mutant [START_REF] Eshghi | Leptospira interrogans lpxD homologue is required for thermal acclimatization and virulence[END_REF]. In addition to shortened length of the ebpA mutant, it remains unclear whether the mutant also has abnormal cell width, helical pitch or flagellar length. Further study using cryo-electron microscopy will likely yield interesting finding on the nature of the morphological phenotype of the ebpA mutant.

We observed that the complemented strain produces higher levels of ebpA transcript levels than the wild type (Fig. 2.), as well as for those EbpA-controlled genes (Fig. 4). One possibility is the gene dosage. This is possible but unlikely since our random nested PCR only revealed insertion into one gene (lmanv2_590053). Another possibility is that insertion of ebpA into lmanv2_590053 has allowed increased expression of ebpA. Increased expression of EbpA in turn increased expression of EbpA-dependent genes.

In summary, we demonstrate that the presence of the EbpA-RpoN regulatory pathway is important for the environmental survival of L. interrogans. This pathway does not appear to be essential for mammalian survival based on our findings. The non-essential nature of EbpA-RpoN for virulence is somewhat not surprising, since the saprophytic strain L. biflexa also contains EbpA and RpoN. Both species may face various hostile and nutrient-scarce conditions when positioned in the natural environment [START_REF] Trueba | Adaptation of Leptospira interrograns (sensu stricto) to fresh water[END_REF][START_REF] Andre-Fontaine | Waterborne leptospirosis: survival and preservation of the virulence of pathogenic Leptospira spp. in fresh water[END_REF]. Both species also encode other factors (e.g., σ E ) to respond to environmental stresses [START_REF] Scola | Partial rpoB gene sequencing for identification of Leptospira species[END_REF][START_REF] Redfield | General stress transcription factor sigmaB of Bacillus subtilis is a stable protein[END_REF]. On the other hand, pathogenic L. interrogans encodes EbpB, which is lacking in saprophytic L. biflexa, where

EbpB is an NtrC-type of EBP. Interestingly, B. burgdorferi, another spirochetal pathogen, has an NtrC-type EBP, Rrp2. Rrp2, working together with RpoN, controls expression of RpoS, which in turn governs multiple factors required for mammalian infection [START_REF] Boardman | Essential role of the response regulator Rrp2 in the infectious cycle of Borrelia burgdorferi[END_REF][START_REF] Hubner | Expression of Borrelia burgdorferi OspC and DbpA is controlled by a RpoN-RpoS regulatory pathway[END_REF][START_REF] Yang | The response regulator Rrp2 is essential for the expression of major membrane lipoproteins in Borrelia burgdorferi[END_REF]. Previous research on the ntrC locus of pathogenic Leptospira has demonstrated that this locus has undergone several evolutionary rearrangements compared to other pathogenic spirochetes [START_REF] Zuerner | Analysis of a Leptospira interrogans locus containing DNA replication genes and a new IS, IS1502[END_REF]. Therefore, it is tempting to postulate that for the two RpoN pathways of L. interrogans, while EbpA-RpoN is important for environmental survival, EbpB-RpoN may play a role in mammalian-phase adaptation. either ebpA1 -or ebpA2 -: P < 0.01; ebpA -/+ vs. ebpA1 -: P < 0.01.

q-LMANv2_200026 R CGTCCATGATCGGAACTTCT secE q-LMANv2_260002 F GCAGAATTGGAAAAGGTCCA qRT-PCR primer set (LMANv2_2 60002 F) q-LMANv2_260002 R CTAACCAGCCACTTCCCAAA glnA q-LMANv2_500019 F TTGCGGATACCGCTTATTTC qRT-PCR primer set (LMANv2_5 00019) q-LMANv2_500019 R AGTACCAGGACGGTGACCAG glnK q-LMANv2_310004 F AAGCGACGTTCAAGGTTACG qRT-PCR primer set (LMANv2_3 10004) q-LMANv2_310004 R GCGGAACTTCCTCTTTCTCC nctP1 q-LMANv2_210009 F TCCCGCAAATTTGAAAAGAC qRT-PCR primer set (LMANv2_2 10009) q-LMANv2_210009 R TCGACGTTCTTTGTGGATGA pdxH q-LMANv2_210047 F GTTAGCCTCACCGCAAAGTC qRT-PCR primer set (LMANv2_2 10047) q-LMANv2_210047 R ATCGTGTAAACGGCTGGAAC LMANv2_24 0139 q-LMANv2_240139 F TTCCGGTCCAGAGACTTTTG qRT-PCR primer set q-LMANv2_240139 R GATCGAAACGTTTTCGGAGA LMANv2_24

  and culture conditions. The pathogen L. interrogans serovar Manilae strain L495 and biologically distinct transposon mutant LMANv2_37011 -/ebpA -strains -ebpA1 - -Johnson-Harris (EMJH) liquid medium[START_REF] Johnson | Differentiation of pathogenic and saprophytic letospires. I. Growth at low temperatures[END_REF][START_REF] Ellinghausen | Nutrition of Leptospira pomona and growth of 13 other serotypes: fracionation of oleic albumin complex and a medium of bovine albumin and polysorbate 80[END_REF] at 30°C.Escherichia coli strains XL-10, BL21 (DE3), and SM10 were grown in Luria-Bertani (LB) broth or agar with antibiotics as described below.Construction of ebpA mutants and the complemented strain. ebpA was previously disrupted in wild type L. interrogans serovar Manilae strain L495 by the Himar1 random transposon system[START_REF] Murray | Genome-wide transposon mutagenesis in pathogenic Leptospira species[END_REF]. Transposon insertion of epbA in ebpA1 -occurred at NT 3149215 in the proximal region of epbA. Transposon insertion of epbA in ebpA2 -occurred at NT 3148873 in the proximal region of epbA. The native ebpA allele along with its native promoter region (including 300 bp upstream of +1) from L. interrogans serovar Manilae strain L495 was PCR amplified with XhoI 5' and 3' overhangs using primers ebpAx1 & ebpAx2 (Table1) and T-A ligated into pCRII-TOPO plasmid (Life Technologies, Waltham, MA). The resulting plasmid was transformed into XL-10 competent cells according to the manufacturer's instructions (Stratagene, La Jolla CA). This plasmid was re-named 'pCRII-TOPO-ebpA'. XL-10 cells containing pCRII-TOPO-ebpA were grown in 5 ml of LB broth with 50 μg/ml of kanamycin (Sigma) and 50 μg/ml ampicillin (Euromedex) to late log phase (10 7 /ml), followed by plasmid extraction by QIAprep Spin Miniprep Kit (Qiagen). The ebpA gene was released from pCRII-TOPO-ebpA by 1 unit of XhoI restriction endonuclease (Thermo Scientific, Waltham, MA) and gel extracted by QIAquick Gel Extraction Kit (Qiagen), following the respective manufacturer's instructions. and the gene was ligated with T4 ligase according to the manufacturer's instructions (New England Biolabs) into the dephosphorylated XhoI site of conjugative plasmid pAL614 carrying a modified Himar1 transposon element along with an aadA (spectinomycin resistance) cassette (gift from Ben Adler). The resulting plasmid was renamed pAL614-ebpA. It was transformed into BL21(DE3) E. coli and grown in LB broth with 0.3 mM diaminopimelic acid (DAP, Sigma)

#

  Restriction endonuclease cut sites are underlined. The sequences in bold are the predicted binding sites for RpoN. Lowercase nucleotides are the mutated sites.

Figure 2 .

 2 Figure 2. qRT-PCR analysis of ebpA expression. RNAs were isolated from wild-type (WT),the ebpA mutants (ebpA1 -, ebpA2 -), and the complemented strain (ebpA -/+ ) and subjected to qRT-PCR analyses. Levels of ebpA expression were reported relative to the level of 16S rRNA in each sample.

Figure 3 .

 3 Figure 3. Cell morphology of the ebpA mutants and the complemented strain. A: Morphology of wild type and ebpA1 -grown in EMJH medium examined under a dark-field microscope. Images were taken at a magnification of 500X. B: Quantitation of cell length. A total of 200 randomly selected cells from each strain were measured. WT: 10.99 μm ± 0.3118,

Figure 4 .

 4 Figure 4. Identification of genes regulated by EbpA. A: qRT-PCR assessment of expression of putative RpoN-regulated genes. B: qRT-PCR analyses to confirm EbpA-dependent expressionof LMANv2_200027, LMANv2_290065 and LMANv2_310003/amtB. For expression of all three genes: WT vs. ebpA1 -or ebpA2 -: P < 0.01; ebpA -/+ vs. ebpA1 -: P < 0.01; WT vs. ebpA -/+ : P < 0.01.

Figure 5 .

 5 Figure 5. EMSA analysis for identification of RpoN (sigma 54 )-type promoter. A: RpoN binding to the promoter region of LMANv2_200027, LMANv2_290065 or amtB. Various concentrations of rRpoN (labeled on the top, in nM) were incubated with DNA fragments containing the promoter region of LMANv2_200027, LMANv2_290065 or amtB (labeled at the bottom). Probe names are indicated on the left at the position of unbound DNA, while bound DNA is denoted by arrows. B: Specificity of rRpoN binding to the promoter. MRN027, MRN065 and MRN003 are the probes with mutation at the predicted sigma54 sequence region (labeled at the bottom, the far right lane in each gel). Exclusion (-) or inclusion of 10, 50, and 100-fold unlabeled competitor DNA (labeled as ×10, x50, and x100, respectively), or absence (-) or presence of 60 nM (+) of BSA are indicated on top of each lane. Probe names are labeled below the images. Bound DNA is denoted by arrows.

Figure 6 :

 6 Figure 6: EMSA analysis for identification of EbpA-regulated genes. A: EbpA bindings to the upstream region of LMANv2_200027, LMANv2_290065 and amtB. Various concentrations of rEbpA (labeled on the top, in nM) were incubated with DNA fragments from upstream region of LMANv2_200027, LMANv2_290065 or amtB. Probe names are indicated on the left at the position of unbound DNA, while bound DNA is denoted by arrows. B: Specificity of rEbpA binding to the upstream region of LMANv2_200027, LMANv2_290065 and amtB. ). Exclusion (-) or inclusion of 50 or 100-fold unlabeled competitor DNA (labeled as x50 and x100, respectively), absence (-) or presence of 60 nM (+) of BSA, absence (-) or presence of 100-fold (+) of sheared salmon sperm (SS) DNA, are indicated on top of each lane. C: Ability of rRpoN and rEbpA to bind to the promoter region of lipL41. Probe L41 (top panel) contains a sigma70-type lip41 promoter. Probe RL41 (bottom panel) contains the lipL41 promoter region that the promoter sequence was replaced with the sigma54 promoter sequence.

Figure 7 .

 7 Figure 7. Growth of the ebpA mutant in various conditions. The wild type L. interrogans strain, the ebpA mutant and its complementary strain were grown to late-log phase (10 7 /ml) and then subcultured into regular EMJH (A), EMJH with 5 mM alanine replacing NH 4 Cl (B), or 1:10 diluted regulated EMJH (C). For the water survival test (D), L. interrogans wild type, the ebpA mutant and its complementary strains were harvested by centrifugation and re-suspended in mineral water. The dotted line in D is the limit of detection. All cultures were incubated at 30°C, and the motile leptospires were counted directly under dark-field microscopy. Error bars indicate standard error from triplicate cultures. * represents statistical differences between the wild-type

Table 1 .

 1 Each cassette was amplified from L. interrogans

	). Using the cDNAs as the

TABLE 1 . Primers used in this study.

 1

Table 2 : Leptospira genes containing a perfect RpoN binding sequence in the putative promoter regions.

 2

	Gene	Function	Matching sequence
	LMANv2_200027	tetratricopeptide repeat protein,	TGGCACGCTGCTTGCA
		outermembrane protein
	raiA	sigma 54 modulation protein, ribosomal	TGGCACGCTGCTTGCA
	(LMANv2_200026)	subunit interface protein
	lpxC	UDP-3-O-[3-hydroxymyristoyl]	TGGCATAGAGTTTGCT
	(LMANv2_430009)	N-acetylglucosamine deacetylase
	ptsA	phosphoenolpyruvate-protein	TGGCATAGAGTTTGCT
	(LMANv2_430010)	phosphotransferase
	secE	preprotein translocase subunit	TTCAAAAGCCGTGCCG
	(LMANv2_260002)
	nusG	transcription antiterminator	TTCAAAAGCCGTGCCG
	(LMANv2_260003)
	rplK	50S ribosomal protein L11	TTCAAAAGCCGTGCCG
	(LMANv2_260004)
	rplA	50S ribosomal protein L1	TTCAAAAGCCGTGCCG
	(LMANv2_260005)
	rplJ	50S ribosomal proteinL10	TTCAAAAGCCGTGCCG
	(LMANv2_260006)
	rplL	50S ribosomal protein L7/L12	TTCAAAAGCCGTGCCG
	(LMANv2_260007)
	LMANv2_290065	outer membrane protein	TGCAAAATATATGCCA
	glnA	glutamine synthetase	TGGTACAATATTTGCA
	(LMANv2_500019)

Predicted RpoN regulatory network in L. interrogans.

  The L. interrogans genome encodes a σ 54 alternative sigma factor, and two bacterial enhancer-binding proteins (EbpA, EbpB) that activate the genes with a σ 54 -type promoter. Both EbpA and EbpB are predicted to have three functional domains: an N-terminal domain that receives a distinct signal, a central domain that activates σ 54 , and a C-terminal domain that binds to DNA. EbpA contains two putative GAF domains in its receiver domain, whereas EbpB contains a receiver domain (REC) conserved for all the two-component system response regulator proteins. EbpA and EbpB respond to different

signals, forms oligomer, interact with RpoN (σ 54 ), and each activates a specific set of σ 54 -dependent genes. RNP: RNA polymerase.

ACKNOWLEDGMENTS

This work was supported in part by grants from the National Natural Science Foundation of China (No. 81501713, WLH), China Postdoctoral Science Foundation (No. 2015M570516, WLH), National Science Foundation grant IIA-1159099 (CJP) and the Institut Pasteur (MP).

and the ebpA mutants with a P < 0.001 using the Student t test.


Cristian Dumitrescu
email: cristiand43@gmail.com

A randomized, efficient algorithm for MAX2SAT

Keywords:

come

A randomized, efficient algorithm for MAX2SAT

Introduction

In MAX2SAT, we are given a 2SAT expression involving a set of clauses, each with at most two literals in it, and an integer K. We are asked whether there is a truth assignment that satisfied at least K of the clauses. We call this the MAX2SAT problem. We note that if the 2SAT expression considered has m clauses, then the truth assignment mentioned above must leave at most m -K clauses unsatisfied.

Definition 1. We know that there is (at least) a truth assignment that satisfies a maximum number of clauses M and leaves unsatisfied a minimum number of clauses m -M, where m represents the number of clauses of the 2SAT expression under consideration. The truth assignment satisfying this condition will be called the maximal truth assignment (there is at least one).

Proposition 1. (see [Papadimitriou,94] and [START_REF] Hopcroft | [END_REF]). MAX2SAT is NPcomplete.

Proof. For the proof, see the references listed above (see [Papadimitriou,94] , theorem 9.2, page 186 ).

The presentation of the algorithm

We will present first the well known randomized algorithm for 2SAT. This is the Papadimitriou algorithm from 1991 (see [Papadimitriou, 1991]). We also note that Schoning discussed a similar algorithm for 3SAT in 1991 (see [Schoning, 1991]).

Papadimitriou's algorithm for 2SAT.

Input: a 2SAT expression in 𝑛 variables.

Guess an initial truth assignment, uniformly at random.

Repeat 𝐶 • 𝑛 2 times:

If the formula is satisfied by the actual assignment, stop and accept.

Let C be some clause not being satisfied by the actual assignment. Pick one of the (at most) two literals in the clause at random, and flip its truth value.

Update.

Stop and reject, the expression is not satisfiable.

In the next section, I will prove that this algorithm performs well even for the MAX2SAT problem, so in the Papadimitriou algorithm, all we need to modify is the definition of "satisfies" (related to an assignment), since in the context of MAX2SAT, we will not need all the clauses to be satisfied.

The MAX2SAT algorithm.

Input: a 2SAT expression with m clauses.

Guess an initial truth assignment, uniformly at random.

Repeat 𝐶 • 𝑚 2 times:

If the actual truth assignment satisfies the MAX2SAT condition, stop and accept.

Let C be some clause not being satisfied by the actual assignment. Pick one of the (at most) two literals in the clause at random, and flip its truth value.

Update.

Stop and reject, the expression is not satisfiable.

In other words, I will prove that if a MAX2SAT satisfying assignment exists, then the MAX2SAT algorithm will find it with high probability. Note that running the algorithm a quadratic number of times, in the number of clauses is stronger than running it a quadratic number of times in the number of variables. A given 2SAT expression with m clauses can have at most 2m variables, and at least a number of variables of order of magnitude √m (up to a multiplicative constant).

Analysis of the algorithm

In this section, I will present the main theorem. We assume that the reader is also familiar with the 3SAT to MAX2SAT reduction. For reference, see [Papadimitriou,94] , theorem 9.2, page 186. A given MAX2SAT problem is called a reduction of a 3SAT problem if it is equivalent to a given 3SAT problem. Basically, given an instance of 3SAT, we construct an instance of MAX2SAT as follows. For each variable or literal x, we write x' for its negation. For each 3SAT clause (x ˅ y ˅ z) , we add to the MAX2SAT expression the following conjunction of ten clauses:

(x)˄ (y)˄ (z)˄ (w) ˄ (x ′ ˅ y ′ ) ˄ (y ′ ˅ z ′ ) ˄ (z ′ ˅ x ′ ) ˄ (x ˅ w ′ ) ˄ (y ˅ w ′ ) ˄ (z ˅ w′)
Here, the variable w is particular to the chosen 3SAT clause. If the 3SAT expression has m clauses, then the MAX2SAT expression thus constructed has 10 • m clauses. We set the MAX2SAT threshold at 7 • m . Then, there is a MAX2SAT maximal truth assignment that satisfies 7 • m clauses if and only if the original 3SAT expression is satisfiable.

Theorem. Given a MAX2SAT problem, that is a reduction of a given 3SAT problem with m clauses, then with high probability, after C • m 2 steps, the MAX2SAT algorithm will find a MAX2SAT satisfying assignment (where C is a constant and m is the number of clauses in the original 3SAT expression).

Proof. For the proof, we will use the principle of induction, following the number of clauses in the MAX2SAT expression (actually the number of clauses of the original 3SAT expression). We will consider the Markov chain approach considered in [Schoning, 1991] and [Papadimitriou, 1991]. We will also consider the expected travelled distance (by the Markov chain associated to the algorithm) towards the absorbing barrier 0 (note that the direction of travel is important).

We are given a 3SAT problem with m clauses. We construct the equivalent MAX2SAT problem. The MAX2SAT problem will have 10 • m clauses, each 3SAT clause will be replaced by a group of 10 clauses. The 3SAT problem is satisfiable if and only if its MAX2SAT reduction has a maximal truth assignment with 7 • m satisfied clauses.

We write P(N) for the statement : after C • N 2 steps (where 10 • N is the number of clauses in the MAX2SAT expression that is equivalent to a 3SAT expression with N clauses ), the Markov chain associated to the MAX2SAT algorithm will have an expected travel distance (towards the absorbing state with Hamming distance 0) given by the square root of the number of flips performed by the algorithm (up to a multiplicative constant), on any MAX2SAT expression that is equivalent to a 3SAT expression with N clauses (or else the chain will hit the absorbing state). So if the algorithm performs C • N 2 steps, then the expected travel distance is C 1 • √𝐶 • N (where C 1 is a constant greater than 1).

We start with N = 2. For N = 2 , the original 3SAT expression has only two clauses.

We can consider all possible combinations , it is a simple case by case analysis. By suitably choosing the constant C, it is clear that the statement P(2) is true, .

We want to prove that if we assume that P(α) is true for all integers α < N , then P(N) is also true.

Let's consider a 2SAT expression φ with 10 • N clauses (the MAX2SAT equivalent to a 3SAT expression with N clauses). We consider the expression ψ , by eliminating a group of 10 clauses (associated to one of the clauses of the original 3SAT expression). We call this group, the special group of 10 clauses. The expression ψ will have 10 • (N -1) clauses. When working on the expression φ , we assume that the algorithm will touch this special group of clauses a number of times K. That means that if the algorithm takes C • N 2 steps (where N is the number of clauses in the expression φ ), then C • N 2 -K steps will be taken within the expression ψ , and K steps will involve the special group of clauses considered above.

We assume that the associated Markov chain will take n 1 steps within the expression ψ, then it will touch the special group of clauses considered above, then it will take n 2 steps within the expression ψ, then it will touch the special group of clauses considered above again, and so on, until it will take n 𝐾 steps within the expression ψ, then it will touch the special group of clauses considered above for the last time, and then it will take the last n 𝐾+1 steps within the expression ψ.

We are only interested in studying what happens if the original 3SAT expression is satisfiable.

Any group of 10 clauses (as described above) will have at most 6 unsatisfied clauses, and at least 3 unsatisfied clauses . The whole expression φ will have at least 3 • N unsatisfied clauses in the maximal truth assignment. As long as the algorithm does not find a maximal truth assignment, the probability of choosing an unsatisfied clause from the special group (at every step of the algorithm) is at most p = 6 3N = 2 N . That means that if the algorithm makes C • N 2 steps, then the expected number of hits of an unsatisfied clause from the special group is at most 2 • C • N . In other words, the inequality K < 2 • C • N will be satisfied with high probability.

From the inductive hypothesis, when the algorithm works within ψ , it will drift towards zero with an expected speed, and when it touches an unsatisfied clause in the special group of clauses, the worst it can do is to backtrack one unit (away from the absorbing state 0).

That means that we have the following equation (this counts the number of steps within ψ , and when it touches the unsatisfied clause considered above).

n 1 + n 2 + n 3 + ⋯ … … … + n K+1 = C • N 2 -K (1)
The overall, expected travel distance of the associated Markov chain (when the algorithm works on φ), will be at least:

D = C 1 • ((n 1 ) 1 2 + (n 2 ) 1 2 + ⋯ … … . + (n K+1 ) 1 2 ) -K (2)
We also work under the conditions n i ≥ 1, for all i ∊ {1, 2, 3, … . K + 1} , and we assume that K < 2 • C • N , as we discussed before.

We want to find the minimum value that D can take, under the constraint given by equation ( 1). We can apply the method of Lagrange multipliers, more precisely the Karush-Kuhn-Tucker minimization conditions, and we find that the minimum of D has the form C 2 • √𝐶 • N , where the constant C 2 is greater than 1 (for a suitably chosen constant C ).

There is also a geometrical way to see this, but this is only an approximation. We consider the variables z i = n i 1 2 , for all i ∊ {1, 2, 3, … . K + 1} . We have to study the intersection of a hyperplane and a hypersphere (a K -sphere), in the region where all the coordinates are greater or equal to 1. The hyperplane is given by the equation C 1 • (z 1 + z 2 + ⋯ … + z K+1 ) = constant , and the hypersphere is given by the equation

z 1 2 + z 2 2 + z 3 2 + ⋯ … . . z K+1 2 = C • N 2 -K .
Let's study the KKT conditions (see [START_REF] Kkt | Lagrange Multipliers and the KKT conditions[END_REF]). We define the following functions:

In the following, we have 𝑥 = (𝑥 1 , 𝑥 2 , 𝑥 3 , … … . . 𝑥 𝐾+1 ) and

λ = (λ 1 , λ 2 , λ 3 , … … . . λ K+1 ) f(x) = C 1 • (z 1 + z 2 + ⋯ … + z K+1 ) -K h(x) = z 1 2 + z 2 2 + z 3 2 + ⋯ … . . z K+1 2 -C • N 2 + K g i (x) = 1 -x i , for i = 1,2,3 … … . K + 1 L(x, µ, λ ) = f(x) + µ • h(x) + ∑ λ i • g i (x) K+1 i=1 L(x, λ ) = f(x) + ∑ λ i • g i (x) K+1 i=1
Then, the KKT result states that 𝑥 * is a local minimum if and only if there is a unique 𝜆 * , such that the following conditions are satisfied:

∇ x L(𝑥 * , µ * , λ * ) = 0 (3) λ i * ≥ 0 , for i = 1,2,3…..,K+1 (4)
λ i * • g i (𝑥 * ) = 0 , for i = 1,2,3,…..,K+1 (5)
g i (𝑥 * ) ≤ 0 , for i = 1,2,3,……., K+1 (6)
h(𝑥 * ) = 0 (7)

The matrix ∇ xx L(𝑥 * , λ * ) is positive semi-definite.

We consider the general case, in which we can assume that λ 1 = λ 2 = ⋯ … = λ m = 0 with 1 ≤ m ≤ K, and also x m+1 = x m+2 = ⋯ … = x K+1 = 1 . This is the most general case for which relations (5) will be satisfied. We also emphasize that m must be greater or equal to 1, otherwise all 𝑥 𝑖 will be 1 and relation (7) will not be satisfied. We also note that condition ( 8) is automatically satisfied.

Under these conditions, it is easily verified that:

min f(x) = f(x * ) = C 1 • (√m • √C • N 2 -2K + m -1 + K + 1 -m) -K (9)
We are only interested in what is happening for large values of N, because these are the interesting problems for us (we can always take care of the few other cases by direct algorithm testing).

We assumed that C 1 > 1 , and 1 ≤ m ≤ K , and we also know that K < 2 • C • N . It can be easily verified that for any value of m (for any local minimum), the expression min f(x) will take the form C 2 • √𝐶 • N , where the constant C 2 is greater than 1.

As a result of the standard KKT calculations, we reach the conclusion that P(N) is true, and the inductive step is proved. QED.

The MAX2SAT algorithm always finds a maximal truth assignment, not only when the maximal truth assignment satisfies all the clauses When a literal is flipped in an unsatisfied clause that will be satisfied in the maximal truth assignment, the Hamming distance to a solution decreases by 1 with probability at least 1 2

. When a literal is flipped in an unsatisfied clause that will remain unsatisfied in the maximal truth assignment, the Hamming distance indeed increases by 1, but enough clauses will become unsatisfied at this step, with this flip (and these clauses will be satisfied in the maximal truth assignment) , such that the deviation will be corrected al later stages of the algorithm. In general, the closer we get to a solution (in terms of the Hamming distance), the more likely it is that the next chosen clause will remain unsatisfied in the maximal truth assignment. That is not always true though, especially if we have many long range variables (variables that appear in many clauses), that do not have the right truth assignment at this moment. A direct proof of the theorem above (without induction) would not be a simple matter.

The general procedure will look like this. We consider a 3SAT problem. We find the equivalent MAX2SAT problem, and we run the MAX2SAT algorithm in this problem.

Discussion and conclusions

For general implications, related to efficiently solving NPcomplete problems, see [Fortnow, 2013]. An interesting application is related to the problem of automated theorem proving using an efficient algorithm for NPcomplete problems (see [A1]). The impact of this type of algorithm in mathematics, cryptography, science in general is hard to estimate.

Aknowledgements.

I emphasize that Professor Fortnow's book ( [Fortnow, 2013]) was a great source of inspiration and motivation that led me to seriously consider this problem. Also, Professor Uwe Schoning , Professor Lance Fortnow, and Professor C. Papadimitriou corrected some errors that I had in many previous versions of this paper, and for that I am very grateful. I must emphasize though, that the final version of my paper did not receive feedback from these experts in the field, so I do not claim that I have their endorsement. If there are still flaws in my work, that is all my fault.

Appendices

A1. Godel's letter to John von Neumann. In his letter, Godel writes: "One can obviously easily construct a Turing machine, which for every formula F in first order predicate logic and every natural number n, allows one to decide if there is a proof of F of length n (length = number of symbols). Let 𝜓(𝐹, 𝑛) be the number of steps the machine requires for this and let 𝜑(𝑛) = 𝑚𝑎𝑥 𝐹 𝜓(𝐹, 𝑛). The question is how fast 𝜑(𝑛) grows for any optimal machine" (see [Godel, 1956]. Now we consider this. In [START_REF] Hopcroft | [END_REF], we have theorem 13.1, at page 325, where it is proved that for each Turing machine (deterministic or nondeterministic) M that is time bounded by a polynomial 𝑝(𝑛), a log-space algorithm exists, that takes as input a string x and produces a Boolean expression 𝐸 𝑥 that is satisfiable if and only if M accepts x.

This means that the process of seeking a proof (of reasonable length) of a mathematical statement can be completely automatized. With the algorithm presented in this paper, Godel's vision can be made reality.

Cristian Dumitrescu. Biographical notes. I was born in 1964 in Romania. In 1988 I graduated the University of Bucharest, Faculty of Mathematics with a BSc. In Mathematics. I worked as a high school teacher of mathematics and computer programmer for various companies and software houses in Romania, UK and Canada. I have been a Canadian citizen since 1998. In the last 20 years I have been working in a different field of activity, but I have always kept close to my heart mathematics and physics.


Elek Pafka

Nothing Gained by only Counting Dwellings per Hectare: A hundred years of confusing urban densities

Urban density measures are broadly used in urban planning as tools for calculating development yields, defining indicative targets, or development controls. A century ago Raymond Unwin argued in the influential pamphlet "Nothing Gained by Overcrowding" that limiting the number of dwellings per land area would be the simplest and best way to avoid overcrowding of both buildings and people, a measure which became widespread. The same measure was used by Jane Jacobs when describing the minimum density required for a vital neighbourhood. This density measure is however highly problematic as it does not account for the size of dwellings, mix of uses or size of households, factors that vary significantly in time and space. This implies that the number of dwellings per hectare alone is not useful for historic comparisons, urban versus suburban comparisons, or comparisons between different social contexts. Likewise, pedestrian flow surveys conducted in three urban areas from Melbourne show that dwelling density is not a reliable indicator of streetlife intensity. Furthermore, it is shown that its vagueness makes it particularly vulnerable to be linked to any type of qualitative conception of density, thus contributing to the ongoing confusion and misuse in the density debate. It is concluded that dwelling density on its own is not an adequate measure to describe urban environments, and instead multi-variable density models need to be used in both research and urban planning. Such a model is illustrated for a range of urban morphologies.

Introduction

Urban density is a key concept in urban theory and planning practice, at the core of often conflicting theories concerning the relationship between urban form, human wellbeing and environmental sustainability. Measures of density relate the number of certain entities such as people, ground floor area, gross floor area, built volume or dwellings, to a reference area, which can be a lot, neighbourhood, city, region or else. The combination of these results in a large number of possible measures, which without detailed specification can and do lead to confusion and misunderstandings. Further confusion is caused by the multitude of terminologies in use for the same measure or the same term used for different measures. For instance Floor Area Ratio (FAR) can be referred to as plot ratio in the UK, Floor Space Index (FSI) in India, Gross Plot Ratio (GPR) in Singapore and Floor Space Ratio (FSR) in New South Wales. On the other hand Residential Density may refer to the number of dwellings per hectare but also to the number of residents relative to the area of residential land. Gross Density can refer to the reference area being a lot together with half the width of adjacent streets, or it can encompass a neighbourhood, city or metropolitan region. While it has been recognised long ago that urban density is "plagued by numerous myths" [START_REF] Lynch | A theory of good city form[END_REF] and there have been numerous attempts to disentangle density measures [START_REF] Churchman | Disentangling the Concept of Density[END_REF][START_REF] Cheng | Understanding Density and High Density[END_REF][START_REF] Boyko | Clarifying and re-conceptualising density[END_REF], much confusion remains.

Probably the most common measure in the Anglosphere is the number of dwellings per hectare, while other measures such as people density, site coverage and floor area ratio are also in use. These measures are used in planning as tools for calculating development yields, defining indicative targets, or development controls. In Australia the measure of dwellings per hectare was notably used by the Commonwealth Housing Commission in 1944 to recommend desirable net densities of 20dw/ha for single dwelling neighbourhoods, 27 dw/ha for attached dwellings and 100 dw/ha for multi-storey units [START_REF] Dodson | The use of density in Australian planning[END_REF]. Currently dwellings density is the most widely used urban density measure in Australia [START_REF] Griffiths | Density targets: Measuring everything except that which makes life worthwhile? 10[END_REF]. It is the key density zoning parameter in Western Australia and is widely used in regional and metropolitan strategies such as the South Australia Planning Strategy 2010 (Government of South Australia 2011), the Sydney Metropolitan Plan 2036 (Government of New South Wales 2010), Melbourne 2030 and its successor the Draft Plan Melbourne (State of Victoria 2002;[START_REF] Pafka | Places as Intersecting Flows: Mapping Urban Morphologies, Functional Constellations and Pedestrian Rhythms. 4th Global Conference: Space and Place[END_REF]. In these documents typically minimum density targets aim to improve access to public transport and community services, while maximum density controls aim to protect private space amenity.

This paper examines the problems associated with using dwellings per hectare as a single density measure and proposes an alternative multivariate approach.

A weak planning tool

In the book Town Planning in Practice (1909) and the influential pamphlet "Nothing Gained by Overcrowding!" (1912) the English town planner Raymond Unwin argued that limiting the number of dwellings per acre would be the simplest and best way to avoid overcrowding of both buildings and people. He contended that this would be a better measure than limiting the ratio of cubic metres of building to land area, as it would have the additional advantage of limiting the density of people as well. The proposed target of a maximum gross density of 17 dw/ha (7 dw/acre) was to be achieved by imposing a maximum net density ranging between 20-35 dw/ha, depending on the cost and size of the dwelling. With the average household at the time of 5 persons, his target implied a gross population density of around 90 people per hectare. Similar density controls are in place today, for instance in parts of Perth net dwelling density is limited to 20 per hectare. However, with the considerably diminished average household size the resulting gross population density is below 35 p/ha. Concomitantly, with the increasing size of dwellings, internal density has been continually diminishing as well (Figure 1). This highlights the problem that urban densities measured as dw/ha do not reliably reflect population numbers, and that comparisons in time loose validity as houses get larger and families smaller. But it is not just time comparisons of dwelling density which are misleading. Comparing suburban densities with urban densities can be equally misleading given the large differences between dwelling size and household size between inner city and suburban fringe. In Melbourne's CBD the average dwelling size is around 60m 2 (City of Melbourne 2010) while on the fringe new single dwellings are 250m 2 (James 2009). In the same time average household size is 1.8 in the CBD and 3.5 in suburbs on the fringe (Australian Bureau of Statistics 2011). Thus while 200dw/ha in the CBD is a tenfold dwelling density compared to 20dw/ha at the fringe, building density is only threefold, while residential density is fivefold.

Comparisons of dwellings per hectare get even more confusing however when it involves different social contexts. Comparing parts of an informal settlement in India with "high-density" residential areas such as parts of Manhattan in terms of dwellings per hectare can indicate a similar density of ca.600 dw/ha (gross at neighbourhood level), but while actual built density is three times higher in Manhattan, population density is three times higher in the informal settlement, as a result of the vastly different dwelling and household sizes [START_REF] Dovey | The urban density assemblage: Modelling multiple measures[END_REF]. A good illustration of the problems related to international comparisons of dw/ha measures is provided by the examples presented in the DBook catalogue of densities [START_REF] Fernández Per | DBook: Density, Data, Diagrams, Dwellings, a+t ediciones[END_REF]. For the examples in the same range of 210-230 dw/ha net, the population density is 259 people/ha in a Tokyo example, 447 p/ha in a Rotterdam case, 616 p/ha in Las Palmas, 812 p/ha in Singapore, and 1056 p/ha in Hanoi. Remarkably the Hanoi example with the highest people density has the second lowest building density when measured as FAR (Figure 2).

Considering the above, it is not surprising that attempts to correlate net dwelling densities and built form lead to incoherent results. For instance row houses have been considered to be 40-60 dw/ha [START_REF] Lynch | Site Planning[END_REF], 32-142 dw/ha [START_REF] Alexander | Density Measures: A Review and Analysis[END_REF] or 50-100 dw/ha [START_REF] Cheng | Understanding Density and High Density[END_REF], and was recognised that other housing typologies are not less likely to occur within the same ranges.

Thus while for abstract homogenous urban environments with similar and stable family sizes and similar dwelling sizes the measure of dwelling per hectare could have been a useful simplification, in a heterogeneous and changing world it is generally inadequate.

A history of confusion

Confusion related to the number of dwellings per hectare is persistent throughout history, and not only limited to dwelling size, household size, mix of uses and built form, but is often further combined with common misunderstandings about net and gross densities. The scale at which density is measured greatly influences the numeric outcome, as with increasing area more non-residential land is included. Centred on the same suburban location, the site density of 25dw/ha might become 12dw/ha at neighbourhood level and 7dw/ha at metropolitan level [START_REF] Forsyth | Measuring Density: Working Definitions for Residential Density and Building Intensity[END_REF].

Examples of such confusion are abundant and include some of the most noted urban writers. An outstanding case is Lewis Mumford's attempt to promote Ebenezer Howard's Garden City model in the foreword to Garden Cities of To-Morrow (1946 pp.31-32). Here he repudiates the idea that Howard was advocating low densities, estimating that the indicated minimum lot size would result in a gross residential density of 225-240 people per hectare, much higher than Unwin's 90-120 people per hectare. However, Mumford's figures are incorrect, because the inconsistent assumptions made regarding household size and the ratio between net and gross densities. Unwin explicitly referred to households of 5, not 3-4 people, while Howard's earlier work assumed households of 5.5, not 5 people. Furthermore, Unwin's 30 dw/ha was a net measure and in fact he advocated a gross density of 17 dw/ha [START_REF] Unwin | Nothing Gained by Overcrowding! How the Garden City type of development may benefit both owner and occupier[END_REF]), implying a gross population density of 90 people/ha. In Howard's scheme, the minimum lot size is equivalent of a net 55 dw/hectare, but when calculating the gross density, Mumford used an implausible net to gross ratio of 84%. This figure may have come from Unwin's proposal to reduce road surfaces to only 16% of the total development area, by creating very large blocks of ca.200x100 metres and narrow streets of 13 metres. But he also provided communal gardens and recreation spaces in the interior of the block, hence used a net to gross ratio of 58% in his calculations. On the other hand Howard's Garden City plan is entirely different, providing wide streets, 36m wide boulevards, a 128m wide circular avenue and a 60ha large central park, while the total number of streets was also much higher due to blocks about half the size of those in Unwin's scheme (Figure 3). While Howard's conceptual diagram and description don't correlate perfectly, it is clear that the net to gross ratio of his scheme couldn't be 86% but close to 40%. Thus the implied gross population density within residential areas in Howard's scheme was 110 p/ha, close to Unwin's 90p/ha. When including the industrial areas at the fringe and public buildings in the centre, the Garden City had only 30,000 people per 1,000 acres or 75 p/ha [START_REF] Howard | Garden Cities of To-Morrow[END_REF]). In the end in practice neither Howard's ideal nor Unwin's targets were achieved, as when the Garden City of Letchworth eventually reached a population of 33,000 inhabitants, it extended over three times the envisioned area, at a density of less than 30 p/ha overall and even its densest district only reaching 52p/ha (UK Office for National Statistics 2011), way below Mumford's presumptions of 225-240 p/ha.

Density and intensity

The measure of dwelling density was also used by Jane Jacobs, who saw the concentration of people as one of four preconditions of urban vitality, and used the hybrid-measure of dwellings per hectare to link measured density to streetlife intensity [START_REF] Jacobs | The death and life of great American cities[END_REF]). However, when writing about density, her concern was the number of people walking and residents with eyes on the street. Thus the minimum net 250 dw/hectare (100 dw/acre) suggested as a condition for vitality, is a poor descriptor of what she was aiming for: a minimum density of residents, workers and attractions for visitors, per gross land area. While the use of this measure stemmed from a lack of choice, as it was the only available data provided by planning departments at the time, it represents a rare lapse in Jacobs' otherwise critical questioning of planning practices. This distinction between density and streetlife intensity central in Jacobs' writing is similar to the distinction between extensive and intensive properties that is fundamental to Deleuzian ontology. Unlike extensive quantities (ex. area) that are additive, intensive quantities (ex. temperature, speed) are indivisible and produce change only when there is a difference in their degree of intensity. The equivalent distinction in mathematics is between metric and non-metric spaces (DeLanda 2005). In the urban realm, intensity can be seen as emerging from the interactions and differences between people, as mediated by built form [START_REF] Dovey | Density withouth intensity and what to do about it: reassembling public/private interfaces in Melbourne's Southbank hinterland[END_REF]. Thus static measures of density such as dwelling density, floor area ratio, or the number of people per hectare counted on census night, are extensive attributes of space relatively easy to measure, whereas streetlife vitality is an intensive attribute defined by the multiplicity of encounters between people, which so far eluded methods of measurement and representation.

To investigate the relationship between density and intensity, three case study sites have been selected in Melbourne. The density measures are based on surveys of 25ha (500x500m) reference areas, which correspond to an average walking distance. The daily rhythms of pedestrian flows at the centre of each area have been recorded between 6am to 12am. The time sample was 15 minutes per hour for each flow, recorded every two hours. Flows in each direction have been recorded separately and represented in a chart graph (Figure 4) as an overlay of northbound rhythms (blue) and southbound rhythms (orange). Two-directional flows corresponding to face-to-face encounters thus appear as a mix of the two (green). While the total number of people is an extensive attribute, the basic level of visual interaction between pedestrians represented by colours is an intensive attribute of streetlife. This simple representation does only capture one key aspect of streetlife intensity, and does not account for differences in speed and nuanced variations in movement path orientation. Such differences have been captured with time lapse video recording, but haven't shown major differences between these study areas. The resulting diagrams allow a basic comparison of the density, urban morphology and intensity of the three case study areas.

In the CBD the residential density is only 35dw/ha, but there is a high job density as well as a high number of day visitors. The residential density in Southbank is three times higher than in Fitzroy, but the magnitude of pedestrian flows is lower and the level of encounter is even more limited. This relatively high level of pedestrian flows in Fitzroy and their balanced mix is similar to other creative clusters in London and New York, and is related to a morphology characterised by small grain size [START_REF] Pafka | Places as Intersecting Flows: Mapping Urban Morphologies, Functional Constellations and Pedestrian Rhythms. 4th Global Conference: Space and Place[END_REF]. The measure of dwellings per hectare provides no indication of either building density (FAR), internal density, or density of people on the street, and neither does it correlate with the observed streetlife intensity.

These examples demonstrate that dw/ha is not an adequate measure for comparisons between urban and suburban areas, comparisons in time or comparisons between different social contexts, nor does it provide a reliable indication of building type or urban intensity, and it has a high potential to mislead.

Politics of density

After demonstrating that dwelling density is not a good tool for analysing urban environments, new questions arise: why would planners and planning departments choose such a vague measure when more precise measures are available? Is the more widespread use of this measure in the Anglosphere related to the higher degree of suburbanisation? Why after so many attempts to bring clarity in the urban density debate, little progress is made?

A very simple argument in favour of dw/ha provided by Unwin was that it is easier to calculate. This argument has been reiterated more recently in the "Urban Density Definitions" report of the Australian Department of Health, Housing, Local Government and Community Services (1993) which stated that dw/ha "relates more directly to opportunities for collecting, aggregating or updating data", and therefore is a better measure than population density. While this practical advantage possibly explains in part its ongoing popularity, is not fully explanatory. A further clue is provided by Unwin's initial argument that limiting the number of dwellings to land area is a good instrument for population density control. While this aim is rarely stated as such, and did not stand the test of time, it reveals that what the measure can do is to bring people density and building density into one combined hybrid concept. The resulting ambiguity combined with the impression of being "a more finite and less fluid unit of measurement" (ibid.) makes it particularly vulnerable for being appropriated for various purposes.

The appropriation of density conceptions for political purposes has a long history and continues today [START_REF] Ross | Nothig Gained by Overcrowding": The History and Politics of Urban Population Control[END_REF]. A detailed exploration of the political dimensions of density conceptions is provided by Nikolai [START_REF] Roskamm | The Concept of Density[END_REF], whose work provides a starting point for understanding the appeal of the dwelling density concept. Roskamm argues that the concept of "density" applied to the urban realm is an abstraction, the word being an empty signifier. Throughout history the term has been constructed and appropriated by different fields of science and practice in various ways. Such a process does not lead to clarification, but to the coexistence of different and often conflicting conceptions. Measured density conceptions are fictionalisations, reductions and abstractions of reality. These are often linked to qualitative conceptions of density, by which the quantitative concept acquires a metaphorical meaning, while the qualitative conception acquires scientific aura, as he puts it becoming a "potentially computable metaphor".

A striking example of such a process is the concept of "Volksdichte" (national density) which appeared in the 19th century in Germany. Geographers established the term to describe and analyse the relationship within a country between the number of people and the available resources. It has been argued that as population density at the scale of the nation increases, societies develop more efficient forms of land use. In the 1920s this concept has been altered to imply the superiority of nations having higher density. This line of thought has been traced from the geographers Friedrich Ratzel and Karl Haushofer to the latter's student Rudolf Hess a friend and later deputy of Hitler [START_REF] Roskamm | Dichte: Eine transdisziplinäre Dekonstruktion[END_REF]. The relationship of nation to space became central in Mein Kampf, where it was argued that there is an upper limit to land use efficiency (a similar concept to that of carrying capacity), and that the only option for a nation which reached the maximum sustainable level of Volksdichte to further develop, is to expand its living space, its "Lebensraum" [START_REF] Roskamm | Dichte: Eine transdisziplinäre Dekonstruktion[END_REF].

The quantitative measure of dwelling density has been similarly linked to various qualitative conceptions of density. Expressions of such processes are the various standards of maximum or minimum dwellings per hectare, or the designation of numeric thresholds for "low", "medium" or "high" densities. In Australia thresholds are set by planning departments at around 20dw/ha (net) for low density, respectively 60 dw/ha for high density. Such arbitrary thresholds are socio-political constructs, well illustrated by variations between countries, for instance in the Netherlands "high density" starts at 100dw/ha and in Israel it starts at 290dw/ha [START_REF] Churchman | Disentangling the Concept of Density[END_REF].

The choice of the measure is of particular significance, because as noted above, dwelling density obscures the diverse possible relationships between built and population densities and maximises the measured difference between urban and suburban areas. Its vagueness makes it particularly vulnerable to be linked to any type of qualitative conception of density.

Multi-variable density models

It has been shown by [START_REF] Dovey | The urban density assemblage: Modelling multiple measures[END_REF] that any single measure of urban density is limited, and does not reflect the complexity and multidimensionality of urban environments. It also has been argued that ultimately what matters is the much more difficult to measure intensive property of urban space, variously referred to as urban vitality [START_REF] Jacobs | The death and life of great American cities[END_REF], visual density [START_REF] Sennett | The uses of disorder: personal identity & city life[END_REF], the density of interactions [START_REF] Häussermann | Phänomenologie und Struktur städtischer Dichte[END_REF], the density of experiences [START_REF] Wolfrum | Urbane Dichte: Plädoyer für Erlebnisdichte in Städten[END_REF], the buzz [START_REF] Storper | Buzz: face-to-face contact and the urban economy[END_REF] or urban intensity [START_REF] Shelton | The making of Hong Kong: from vertical to volumetric[END_REF]). Nevertheless, planning professionals and decision makers do require precise and objective tools to describe, analyse and control urban development. However, particularly the impression of being a simple, universal, exact and objective measure encompassing both aspects of people and buildings is what makes dw/ha vulnerable to misuse. Instead of relying on a single measure with a very high potential to mislead, it seems more worthwhile to consider multiple measures at the same time, such as population density, job density, site coverage and floor area ratio. Together multiple measures are at least getting closer to describing the complexity of urban environments. In the last decade several multi-dimensional models have been proposed, including: the three dimensional "Spacematrix", a model combining FAR and MIX (Mixed use index) and a chart with six density variables.

In Spacematrix [START_REF] Pont | Spacematrix: Space, Density and Urban Form[END_REF] argue that rather than relying on a single part-measure of density, multiple measures should be combined to better describe urban environments through the prism of building density. Spacematrix is defined as a three dimensional diagram which represents three different measures: FAR (which they refer to as Floor Space Index), coverage (referred to as Ground Space Index) and Network Density (N). Together these measures characterize the typomorphology of an urban environment, in which differences in street patterns and building typology are recorded. However, considering that axonometric representation is not useful, the authors decided to go back to 2D projections of this model named "Spacemate". The FSI & GSI Spacemate, on which gradients of building height and OSR (Open Space Ratio, a measure of "spaciousness" defined as the amount of open space divided by gross floor area) are also represented, is a tool which relates building density to urban form. This highlights the tension between the need to capture the whole complexity of the phenomena and the practical need for simplicity of representation.

While the Spacematrix model only addresses built form, another model that incorporates the functional mix of urban neighbourhoods has been proposed by [START_REF] Hoek | The MXI (Mixed-use Index) as Tool for Urban Planning and Analysis[END_REF]. The model comprises a chart that represents FAR on the vertical axis and an index of land use mix (MXI) on the horizontal axis. It has been shown that in this model, urban neighbourhoods with similar character (19th century urban expansions, modernist districts, CBDs, etc) cluster in the same area of the chart. As this model has been developed based on examples found in the Netherlands, it remains to be tested in different cultural contexts.

A more complex multi-dimensional model, which encompasses both building and population density measures was proposed by [START_REF] Patel | Analyzing urban layouts -can high density be achieved with good living conditions?[END_REF]. His model illustrated with a sophisticated diagram shows, how at the scale of a neighbourhood gross population density (GD) and net population density (ND) are mediated by the plot factor (PF), the ratio of private to public land. Further the model illustrates how the link between net population density and net floor space index (FSI) is mediated by the ratio of built area per capita (BUA). A sixth measure is the public ground area per capita (PGA) which is linked to PF, FSI and BUA, via the formula PGA=BUA/FSIxPF. The model demonstrates that while one or two of these measures are fixed, the others can change. A variety of examples from India and the United States demonstrate how no single density measure can reliably characterise particular urban morphologies. In this model with six variables at least three have to be known to determine the other three. While the model is complex, it still doesn't include key morphological and sociological aspects, most notably functional mix and pedestrian flow rhythms.

A more simple and open way to approach the issue of multi-dimensionality of concentration proposed here, is by comparing various density measures as illustrated in Figure 5. For each of the three examples presented earlier, the diagram shows three building density measures followed by three population densities. Density values are expressed as a proportion of the highest value for each example. This shows that there is no consistency between urban morphology and density measures. While Fitzroy (green) generally scores lowest in all building density and two static population density measures, it has a higher pedestrian flow than Southbank (blue), despite the latter having a much higher FAR. The CBD (red) has a similar population and dwelling density as Fitzroy, yet a much larger job density and pedestrian flows. The big fluctuations of profile for different urban conditions illustrate that no single measure of density can be used to simply predict urban outcomes. The exceptional consistency between dwelling and population density is the result of the consistency of household sizes in Melbourne's inner city apartments. These incipient attempts to capture complex urban phenomena through pairs or systems of precise measures, have still a long way to go to handle aspects such as walkability, streetlife and multi-scale relationships. As a first step however, there needs to be a shift from single density measures towards more complex models that integrate multiple aspects of urban concentration.

Conclusions

It has been shown that the measure of dwellings per hectare should be treated with caution, as comparisons between urban and suburban areas, comparisons in time or comparisons between different social contexts can be easily misleading.

Further it has been shown that dwelling density is particularly vulnerable for being misused, as it obscures the diverse possible relationships between built and population densities and maximises the measured difference between urban and suburban areas. Its vagueness makes it particularly vulnerable to be linked to any type of qualitative conception of density, while maintaining the impression that it is an objective and sound measure.

As no single measure of urban density is sufficient to capture the various aspects for concentration, multi-variable models need to be used. Several such models have been proposed in the past few years that need to be further tested and developed.

Figure 1 .

 1 Figure 1. Unwin's 1911 vision addressing "overcrowding" assumed a dwelling area per person of ca.18m 2 . In Australia dwelling area per person increased rapidly as result of diminishing household size and concomitantly growing dwelling size (Source: author, based on ABS figures).

Figure 2 .

 2 Figure 2. Range of building types at 210-230 dw/ha, illustrating vast population and building density variations depending on dwelling and household size. Source: Fernández Per et al. (2007).

Figure 3 .

 3 Figure 3. Unwin's Scheme II and Howard's Garden City.

Figure 4 .

 4 Figure 4. Three case studies in Melbourne compared, showing the absence of a simple correlation between the measures of dwellings per hectare, FAR and intensity of pedestrian flows (Source: author's survey 2012).

Figure. 5

 5 Figure.5 Density measures profiles for three 25ha case study areas is Melbourne. Sources: author's survey 2012, (Australian Bureau of Statistics 2011), (City of Melbourne 2010).

Acknowledgements

This paper emerges from the ongoing PhD research Urban Density Rhythms conducted at the University of Melbourne that investigates the relationship between urban density, morphology and rhythms of everyday life. I thank Kim Dovey as well as the peer-reviewers for the critical feedback provided to earlier versions of this paper.