The energy-speed-accuracy tradeoff in sensory adaptation
https://doi.org/10.1038/nphys2276

Nat Phys Nat Phys 319 nihpa 101235387 Nature physics 1745-2473 pmc-is-collection-domain yes pmc-collection-title NIHPA Author Manuscripts PMC3378065 PMC3378065.1 3378065 3378065 NIHMS359045 22737175 10.1038/nphys2276 NIHMS359045 NIHPA359045 1 Article The energy-speed-accuracy tradeoff in sensory adaptation Lan Ganhui 1 † * Sartori Pablo 2 * Neumann Silke 3 Sourjik Victor 3 Tu Yuhai 1 # 1 IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, New York 10598, USA 2 Max Planck Institute for the Physics of Complex Systems, Nothnitzer Str. 38, 01187 Dresden, Germany 3 Zentrum fur Molekulare Biologie der Universitat Heidelberg, Heidelberg, Germany # Correspondence should be addressed to YT ( yuhai@us.ibm.com ) † Present address: NCI Physical Sciences - Oncology Center, Johns Hopkins University, 3400 N Charles St., Maryland 21218, USA * These authors contributed equally to this work 25 3 2012 1 5 2012 8 5 211224 422 428 29 03 2012 01 11 2012 01 11 2012 05 06 2024 Users may view, print, copy, download and text and data- mine the content in such documents, for the purposes of academic research, subject always to the full Conditions of use:  http://www.nature.com/authors/editorial_policies/license.html#terms Adaptation is the essential process by which an organism becomes better suited to its environment. The benefits of adaptation are well documented, but the cost it incurs remains poorly understood. Here, by analysing a stochastic model of a minimum feedback network underlying many sensory adaptation systems, we show that adaptive processes are necessarily dissipative, and continuous energy consumption is required to stabilize the adapted state. Our study reveals a general relation among energy dissipation rate, adaptation speed and the maximum adaptation accuracy. This energy-speed-accuracy relation is tested in the Escherichia coli chemosensory system, which exhibits near-perfect chemoreceptor adaptation. We identify key requirements for the underlying biochemical network to achieve accurate adaptation with a given energy budget. Moreover, direct measurements confirm the prediction that adaptation slows down as cells gradually de-energize in a nutrient-poor medium without compromising adaptation accuracy. Our work provides a general framework to study cost-performance tradeoffs for cellular regulatory functions and information processing. sensory adaptation non-equilibrium system energy dissipation adaptation speed adaptation accuracy information processing pmc-status-qastatus 0 pmc-status-live yes pmc-status-embargo no pmc-status-released yes pmc-prop-open-access yes pmc-prop-olf no pmc-prop-manuscript yes pmc-prop-open-manuscript yes pmc-prop-legally-suppressed no pmc-prop-has-pdf yes pmc-prop-has-supplement yes pmc-prop-pdf-only no pmc-prop-suppress-copyright no pmc-prop-is-real-version no pmc-prop-is-scanned-article no pmc-prop-preprint no pmc-prop-in-epmc yes Living systems are highly dissipative, consuming energy to carry out different vital functions. Though it is natural to relate energy consumption with physical functions in a cell, such as biomolecule synthesis and cell motility, the costs of regulatory functions, from maintaining homeostasis to timing of the cell cycle to computing in the brain [ 1 ], remain poorly understood. Sensory adaptation is an important regulatory function possessed by many living systems. It allows organisms to adjust themselves to maintain their sensitivity and fitness in varying environments. Most sensory adaptations are facilitated by biochemical feedback networks, examples of which in systems ranging from bacterial chemotaxis [ 2 ] to osmotic sensing in yeast [ 3 ] to olfactory [ 4 ] and light sensing [ 5 ] in mammalian sensory neurons are shown in  Fig. 1 . Given the small number of molecules in the underlying chemical reactions and thermal fluctuations, the dynamics of biological networks are inherently noisy. This then raises the questions of what drives accurate adaptation in noisy biological systems and what is the energy cost of the biochemical feedback control mechanisms. We address these questions by first studying the stochastic dynamics of the core negative feedback control loop ( Fig. 1a ) shared by various adaptation systems ( Fig. 1b-e ). We show that despite their varying complexities, negative feedback control mechanisms break detailed balance, and therefore always operate out of equilibrium with energy dissipation. We find that energy dissipation is needed to stabilize the adapted state against noise. A relation between adaptation performance, characterized by its speed and accuracy, and the minimum energy cost is discovered. This energy-speed-accuracy (ESA) relationship is verified in a detailed microscopic model of the  E. coli  chemosensory system. Direct measurements of the adaptation dynamics of starving  E. coli  cells show that adaptation slows down but maintains its accuracy, confirming our predictions. Finally, general implications of our study and its comparison with other biological information processing mechanisms (such as kinetic proofreading) are discussed. Breakdown of detailed balance in negative feedback networks The 3-node negative feedback network shown in  Fig. 1a  represents a minimum network to achieve accurate adaptation [ 6 ]. A stimulus signal ( s ) causes a fast response in the output activity ( a ). The change in  a  triggers a slower change in the negative control element ( m ), which eventually cancels the effect of  s  and brings  a  back to a stimulus-independent level  a 0 . Due to the small size of a cell,  in vivo  biochemical reactions are highly noisy. The stochastic dynamics of this feedback network can be described by two coupled Langevin equations [ 7 ]: (1) a ˙ = F a ( a , m , s ) + η a ( t ) ; m ˙ = F m ( a , m ) + η m ( t ) . The functions  F a  and  F m  characterize the coarse-grained biochemical interactions,  η a  and  η m  are the noises assumed to be white with strength 2Δ a  and 2Δ m  respectively. Detailed balance condition Δ m ∂ m F a  = Δ a ∂ a F m  is satisfied in all equilibrium systems [ 8 ]. However, the negative feedback mechanism for adaptation requires the two cross derivatives of the interaction functions,  ∂F a / ∂m  and  ∂F m /∂a , to have opposite signs. This requirement directly indicates the breakdown of detailed balance in all negative feedback control systems. This means that adaptation is necessarily a nonequilibrium process and it always costs (dissipates) energy. To understand why energy dissipation is necessary for adaptation, we consider the following forms of  F a  and  F m : (2) F a ( a , m , s ) = − ω a [ a − G ( s , m ) ] , (3) F m ( a , m ) = − ω m ( a − a 0 ) [ β − ( 1 − β ) C ∂ G ( s , m ) / ∂ m ] . Here,  F a  describes the fast response dynamics of  a  with a fast rate  ω a ;  G ( s, m ) is the mean activity with opposite dependence on  s  and  m  ( ∂ m G >  0,  ∂ s G <  0).  F m  describes the slow adaptation dynamics with the adaptation speed controlled by  ω m (≪  ω a ). The factor ( a − a 0 ) in  F m  is introduced to make accurate adaptation at  a  =  a 0  (independent of  s ) possible. A  β –dependent term (in bracket) is introduced in  F m  in order to study both the equilibrium ( β  = 0) and the nonequilibrium ( β  ≠ 0) cases within the same model. For  β  = 0,  Eqs. (2 - 3 ) represent an equilibrium model as the detailed balance condition is satisfied with the constant  C  = Δ m ω a / (Δ a ω m ). For  β  ≠ 0, the model becomes nonequilibrium. For  β  = 1, we have  F m  = − ω m ( a  −  a 0 ), which corresponds to a linearized coarse-grained model for studying adaptation in  E. coli  chemotaxis [ 9 ]. From  Eqs. (2 - 3 ), there exists a steady state with a constant activity  a  =  a 0  and an  m -value given by  G ( s, m* ) =  a 0  for all values of  β . With a stimulus-independent activity  a 0 , this steady state has the desired characteristic of an accurately adapted state. However, linear stability analysis shows that this steady state is only stable when (4) β > β c ≡ C ∂ m G ( s , m ∗ ) / ( C ∂ m G ( s , m ∗ ) + 1 ) > 0 , which clearly shows that stable adaptation can only be achieved in a nonequilibrium system. To further demonstrate this point, an effective potential  H ( m ) in  m -space can be obtained by averaging over the fast-variable  a , see  Supplementary Information (SI)  for details. As shown in  Fig. 2a , for the equilibrium case  β  = 0, the desired adaptation state ( m  =  m* ) is at the maximum of  H ( m ) and therefore unstable. As  β  increases,  H ( m ) is deformed, essentially by the increasing amount of energy dissipation. When  β  >  β c , m  =  m*  becomes a minimum of  H ( m ) and stable adaptation becomes possible. The energy cost of adaptation To calculate the energy cost of adaptation, we first determine the phase-space probability density  P ( a, m, t ) for the stochastic system described by  Eqs. (1 - 3 ). The dynamics of  P ( a, m, t ) is governed by the Fokker-Planck (FP) equation: (5) ∂ P ∂ t = − ∂ ∂ m ( F m P − ∂ ∂ m Δ m P ) − ∂ ∂ a ( F a P − ∂ ∂ a Δ a P ) ≡ − ∂ J m ∂ m − ∂ J a ∂ a , where 
 J a ≡ F a P − Δ a ∂ P ∂ a  and 
 J m ≡ F m P − Δ m ∂ P ∂ m  are the two components of the probability density flux (current) in the ( a, m ) phase-space. Following previous works [ 10 – 14 ], the nonequilibrium system can be characterized by its entropy production rate  S˙ , which can be computed from  J a , J m , and  P  (see  SI  for derivation). From  S˙ , we obtain the rate at which the system dissipates energy by heating its environment characterized by an effective temperature  T eff : (6) W ˙ = ∬ [ J a 2 Δ a P + J m 2 Δ m P ] dadm , in units of  kT eff , where  k  is the Boltzmann constant. Note that the energy unit  kT eff  for the coarse-grained model can be different from the thermal energy unit  kT , even though it ultimately originates from thermal fluctuations in the underlying chemical reactions. The average activity 〈 a 〉 and the relative adaptation error  ε  can also be determined by  P ( a, m, t ): 〈 a 〉 = ∬ aPdadm ; ɛ ≡ | 1 − 〈 a 〉 / a 0 | , As  ω a  ≫  ω m , the steady state solution  P ( s ) ( a, m ) of the Fokker-Planck equation can be obtained approximately by separation of the fast variable ( a ) from the slow one ( m ). From  P ( s ) ( a, m ),  ε  and  W˙  in the adapted state can be determined. For the biologically relevant case with  β  = 1 [ 9 ], we find  ε  ≈  ε 0 exp(− c 0 ω m / Δ m ), and 
 W ˙ ≈ σ a 2 ω m 2 / Δ m  with 
 σ a 2 ≡ Δ a / ω a  the variance of the activity ( a ) fluctuation. From these results, a simple relation among the rate of energy dissipation  W˙ , the adaptation speed  ω m , and the adaptation error  ε  emerges: (7) W ˙ ≈ ( c 0 σ a 2 ) × ω m × ln ( ɛ 0 / ɛ ) , where  c 0  and  ε 0  are constants depending on system parameters and details of  G . This general ESA relation holds true for other cases ( β c  <  β  < 1) with only different expressions of  c 0  and  ε 0 .  Eq. (7)  clearly shows that higher energy dissipation is needed for more accurate and/or faster adaptation. See  SI  for detailed derivation of the ESA relation. For a specific choice of  G ( s, m ) and other parameters, the phase space dyanmics can be determined quantitatively by solving the FP  equation (5)  (see Methods). For the equilibrium model ( β  = 0) ( Fig. 2b ), the system always localizes at one of the corners of the phase space, flux vanishes everywhere ( J a  =  J m  = 0), and there is no adaptation. For the fully adaptive model ( β  = 1) ( Fig. 2c ), phase-space fluxes, a trademark of nonequilibrium systems, appear. The flux vectors form a vortex (cycle) that effectively traps the system in the adapted state, which has a constant average activity ( a 0 ) and an average  m -value ( m *) that increases with the signal  s  ( Fig. 2c , see also a Movie in  SI ). The energy cost of the negative feedback control can also be understood intuitively from a 2-state system that switches between its active ( a  = 1) and inactive ( a  = 0) states with free energies  E 1 ( m ) and  E 0 ( m ). As illustrated in  Fig. 2d , E o 0 ( m ) and  E 1 ( m ) have different dependence on  m  and they cross at an intermediate point  m*  (a specific form of  E 0,1 ( m ) is given in the Method section). If the system operates at equilibrium, it always goes to its lowest energy state ( Fig. 2d  left panel) and thus does not adapt. The strategy for adaptation is to trap the system near  m* . Since the cross-point  m*  is not a minimum on either energy lines, external free energy is consumed to push the system up the energy “hills” along the  m -coordinate to stabilize this adapted state ( Fig. 2d  right panel). The Energy-Speed-Accuracy tradeoff in  E. coli  chemotaxis To test the general ESA relation established by the coarse-grained model of adaptation, we turn to  E. coli  chemotaxis, where detailed microscopic models are available [ 15 – 19 ]. Here, we use such a microscopic model to study the energy cost of adaptation and compare the results with the general ESA relation as well as direct experimental observations. As shown in  Fig. 3a , the state of a chemoreceptor dimer is characterized by two discrete variables:  a  = 0, 1 for activity; and  m  = 0,1, …,m 0  for methylation level ( m 0  = 4 in this paper). For a given  m , the transitions between the active ( a  = 1) and inactive ( a  = 0) states are fast with a characteristic time scale  τ a ; the mean activity is determined by the free energy difference Δ E ( s, m ) between active and inactive states. Upon a change in external signal  s , the mean activity changes quickly. The receptors adapt by changing their methylation levels ( m  values) to balance the effect of  s  in Δ E ( s, m ). The methylation and demethylation reactions are catalyzed by the methyltransferase CheR and methylesterase CheB respectively. Here, we approximate the methylation and demethylation processes as one-step reactions without explicitly modeling the intermediate enzyme-substrate binding/unbinding steps. The one-step reaction rates  k R  and  k B  depend on the enzyme and substrate concentrations. This approximation does not affect the energy dissipation rate calculation significantly for Michaelis-Menten type reactions where the substrate reaches fast chemical equilibrium with the enzyme-substrate complex (See  SI  for details). To achieve accurate adaptation, CheR should preferentially enhance the methylation of the inactive receptors and CheB should preferentially enhance the demethylation of the active receptors [ 15 – 18 ]. These irreversible effects are described by two parameters  γ 1  (≤ 1) and  γ 2  (≤ 1) that suppress the demethylation rate for the inactive receptor and the methylation rate for the active receptor respectively from their equilibrium values. We study the stochastic dynamics of the chemoreceptor for different values of  γ  ≤ 1 ( γ 1  =  γ 2  =  γ  for simplicity),  γ  = 1 corresponds to the equilibrium case. The probability of a receptor in a given state ( a, m ),  P a ( m ), can be determined by solving the master equation. From  P a ( m ) and the transition rates between different states, we can compute the adaptation error  ε  and the energy dissipation rate  W˙  (see Methods for details). In  Fig. 3b , we show the dependence of  ε  and 
 Δ W ≡ W ˙ k R − 1 , which is the energy dissipation by a receptor to its environment in the form of heat during the methylation time 
 τ R ≡ k R − 1 , on  γ  for different background signals. Smaller  γ  leads to smaller error but costs more energy. By plotting  ε  versus Δ W  in  Fig. 3c , we find that  ε  decreases exponentially with Δ W  when Δ W  is less than a critical value Δ W c : (8) ɛ ≈ ɛ 0 e − α Δ W . For Δ W  > Δ W c , ε  saturates to  ε c , which depends on key parameters of the system. The exponential error-energy relationship holds true for different choices of the kinetic rates  k R  and  k B , and the prefactor  α  is found to be:  α  = ( k R  +  k B ) / 2 k B  ( Fig. 3d ,  Fig. S1 ). With the parameter correspondence  ω m  =  k R  +  k B , a 0  =  k R /( k R  +  k B ), 
 σ a 2 = a 0 ( 1 − a 0 ) = k R k B / ( k R + k B ) 2  and  c 0  = 2,  Eq. 8  found in  E. coli  chemotaxis confirms the general ESA relationship ( Eq. 7 ). Network requirements for accurate adaptation The error-energy relation ( Eq. 8 ) sets the minimum adaptation error for a given energy dissipation. To approach this optimum performance, proper conditions on the key components and parameters of the network are required. In particular, adaptation accuracy depends on the energetics and kinetics of the receptor activity, parameterized by Δ E ( s, m ) and activation time  τ a  in our model. To evaluate these dependencies, we have computed adaptation error and energy dissipation for a large number of models, each with a random parameter set (Δ E ( m ),  τ a , γ, s ), where Δ E ( m ) ≡ Δ E (0,  m ) is the  m –depedent part of Δ E ( s, m ). The results,  ε  versus Δ W  for all these models, are shown in  Fig. 4a . All the error-energy points are bounded by a “best performance” (BP) line, which agrees exactly with ( Eq. 8 ). The deviation from this BP line is caused by the finite saturation error  ε c , evident from  Fig. 3c . Taking the limit of  γ  = 0, we can derive the expression for  ε c : (9) ɛ c = | ( 1 / a 0 − 1 ) P 1 ( 0 ) − P 0 ( m 0 ) | , which shows that the saturation error results mainly from the receptor population at the methylation boundaries ( m  = 0 or  m 0 ) where the enzyme (CheB or CheR) fails to decrease or increase the receptor methylation level any further (see  SI  for details). Therefore, having large boundary energy differences (∣Δ E (0)∣, ∣Δ E ( m 0 )∣) and fast activation time 
 ( τ a ≪ k R − 1 )  can reduce  ε c  by decreasing the receptor populations at the methylation boundaries (See  SI and Fig. S2&S3  for details). These requirements for accurate adaptation are met for the aspartate receptor Tar, which has Δ E (0) ≥ 2 kT , Δ E (4) ≤ −6 kT  [ 20 ], and  τ a k R <  10 −3  [ 2 ]. Our analysis also provides a plausible explanation (smaller ∣Δ E ( m 0 )∣) for the less accurate adaptation for the serine receptor Tsr [ 21 ]. The energy sources for adaptation An examination of different adaptation networks ( Fig. 1 ) shows that the energy sources are the energy-bearing biomolecules such as ATP, GTP and SAM. For example, both the HOG1 feedback loop [ 3 ,  22 ,  23 ] in yeast osmotic shock adaptation ( Fig. 1c ) and the Calmodulin kinase II dependent feedback control [ 4 ,  24 ,  25 ] for olfactory adaptation ( Fig. 1d ) are fueled by ATP hydrolysis accompanying various phosphorylation-dephosphorylation cycles. For  E. coli  chemotaxis, adaptation is driven by hydrolysis of SAM, the methyl group donor for chemoreceptors. Since one fuel molecule (SAM) is hydrolyzed during each methylation-demethylation cycle, the adaptation accuracy is controlled by the free energy release in hydrolysis of one fuel molecule. As shown in  Fig. 4b , given the high energy release (Δ G 0  ∼ 29 kT ) from methylation by SAM [ 26 ], a modest 20% efficiency (Δ W/ Δ G 0 ) leads to a maximum adaptation accuracy of  ∼  99%, consistent with the high adaptation accuracy observed in  E. coli  chemotaxis [ 27 ]. At the same efficiency, if adaptation is driven by phosphorylation from ATP (Δ G 0 
 ∼  12 kT ), the accuracy would be  ∼  80%, consistent with the less accurate (but adequate) adaptation in the rod cell [ 5 ,  28 ]. Experimental observation of starving cell adaptation dynamics According to the ESA relation, the adaptation accuracy is controlled by the dissipated free energy, which is comprised of two parts: the internal energy of the fuel molecule and an entropic contribution. Since the entropic energy only depends on the logarithm of the fuel molecule concentration, the adaptation accuracy is not very sensitive to the change in abundance of the fuel molecule. However, the kinetic rates, e.g. the methylation rate  k R , depend strongly on the concentration of the fuel molecule. Therefore, if a cell's fuel molecule pool becomes smaller due to deficient metabolism or starvation, the adaptation should slow down while its accuracy should stay relatively unaffected. We have tested this prediction by direct measurements of  E. coli 's adaptation dynamics using fluorescent resonance energy transfer (FRET) technique [ 29 ]. As shown in  Fig. 5a-c , adaptation to a given stimulus becomes progressively slower ( Fig. 5b ) for cells that are kept in a medium without energy source. The background kinase activity (in buffer) decreases with time ( Fig. 5a  inset), indicative of the decreasing energy level of the starving cells. Remarkably, the adaptation accuracy remains almost unchanged with time (within experimental resolution) as shown in  Fig. 5c , consistent with our prediction. For an  E. coli  cell, the methylation levels of its chemoreceptors serve as the memory of the external signals it received [ 30 ]. After a change in the signal, the adaptation process “rewrites” this memory accordingly. As pointed out by Landauer [ 31 ], only erasure of information (e.g., memory) is dissipative due to phase space contraction and the resulting entropy reduction. Since changing the methylation level does not necessarily shrink the phase space, the adaptation response to a signal change does not have to cost extra energy. Instead, energy is consumed continuously to maintain the stability of the adapted state or equivalently the integrity of the memory against noise. For an  E. coli  cell with  ∼  10 4  chemo-receptors [ 32 ] and a (linear) adaptation time  ∼  10 s , the energy consumption rate is  ∼  3  ×  10 4 kT/s  (equivalently  ∼  10 3  ATP/s), which is 5-10% of the energy needed to drive a flagellar motor rotating at 100Hz [ 33 ], even when the cell is not actively sensing or adapting. The total energy budget for regulations in an  E. coli  cell is higher given the many regulatory functions needed for its survival. During starvation,  E. coli  cells are likely to have different priorities for different energy consuming functions. Thus, the slowing down of adaptation in starved cells seen in  Fig. 5a  may be seen as a way for the cells to conserve energy for other regulatory functions with higher priorities. Discussion In biochemical networks, there are many “futile cycles”, in which two pathways run simultaneously in opposite directions dissipating chemical energy with no apparent function [ 34 ]. Here, we show that these cycles, shown in  Fig. 3a  and  Fig. 2d , are crucial in powering accurate adaptation. In general, cells need to process information accurately under noisy conditions. A well-known example is the kinetic proofreading (KP) scheme for error-correction proposed by Hopfield [ 35 ]. Similar to the sensory adaptation system studied here, energy is also consumed to increase accuracy in the KP scheme [ 36 – 38 ]. However, subtle differences exist between adaptation and KP. While energy is consumed in KP to effectively lower the free energy of the already stable “correct” state to reduce error, it is used in the adaptation system to stabilize an originally unstable state ( Fig. 2a ). It remains an open question whether there are general thermodynamic principles governing cellular information processes, such as proofreading and sensory adaptation. It will also be interesting to establish the ESA relationship in other more complex adaptation systems, such as those mentioned in  Fig. 1c-e , and to relate the ESA relationship to the efficiency at maximum power studied in molecular motor systems [ 11 ,  39 ]. Biological systems consume energy to carry out various vital functions, many of which are related to regulation [ 40 ], where accuracy and speed are of primary importance. Despite the complexity of biochemical networks responsible for various regulatory functions, it has been suggested that a small set of network motifs are used repeatedly [ 41 ]. The cost-performance tradeoff studied in this paper provides a new perspective, in addition to other general considerations such as robustness [ 15 ] and evolvability [ 42 ], to understand the design principles and evolutionary origins of these regulatory circuits and their building blocks. Methods A specific case of  G ( s, m ) A simple sigmoidal form  G ( s, m ) = 1 / [1 + ( s/K d ( m )) H ] has been studied in the continuum adaptation model,  Eqs. (1 , 2 - 3 ) with  K d ( m ) =  K 0 e 2 m  and  K 0  = 1 setting the scale for  s . For results shown in  Fig. 2c&d , the Fokker Planck  equation (Eq. 5)  is solved in the region 0 ≤ a ≤1,0≤ m ≤4 with the grid size  da  = 0.02,  dm  = 0.025 and time step  dt  = 5 × 10 −4 . No flux boundary conditions are used:  J m ( a, m  = 0) =  J m ( a, m  = 4) =  J a ( a  = 0,  m ) =  J a ( a  = 1,  m ) = 0. Other parameters used are  ω m  = 5,  ω a  = 50(≫  ω m ), 
 σ a 2 = σ m 2 = 10 − 2 ,  a 0  = 0.5, and  H  = 1. Details of the  E. coli  chemoreceptor adaptation model The free energy difference Δ E ( s, m ) =  E 1 ( m ) −  E 0 ( m ) =  Ne m ( m 1  −  m ) +  N (ln[[1 +  s/K I ]/ [1 +  s/K A ]]) is taken from the Monod-Chandeux-Wyman (MWC) model of  E. coli  chemoreceptor complexes [ 9 ] with  s  the ligand concentration. We choose  E a ( s, m ) = ( a  − 1/2)Δ E ( s, m ) for simplicity. The parameters in Δ E ( s, m ) are from [ 9 ] for  E. coli  chemoreceptor Tar :  K I  = 18.2 μ M,  K A  = 3000 μ M,  e m  = 2,  m 1  = 1.  N  is the number of strongly coupled receptor dimers. Form the linear dependence of Δ E  on  N , it can be shown that the energy dissipation rate  W˙  scales linearly with  N . So only  N  = 1 is studied here and the resulting energy cost is for each receptor dimer. Note that according to [ 20 ], the adaptation speed also scales linearly with  N . Therefore, the ESA relation holds independent of  N . The dynamics of  P a ( m ) is governed by the master equation:  dP a ( m ) /dt  =  k −, a ( m  + 1) P a ( m +1) +  k + ,a ( m −1) P a ( m −1) + ω 1− a ( m ) P 1− a ( m ) − ( k − ,a ( m ) +  k + ,a ( m ) + ω a ( m )) P a ( m ), for  a  = 0,1 and  m  = 0,1, 2, 3, 4. No (transition) flux boundary conditions are used at  m  = 0 and  m  = 4. The methylation (demethylation) rate for inactive (active) receptor is set to be  k R  and  k B :  k +,0 ( m ) =  k R , k −,1 ( m ) =  k B . Their counter rates are suppressed from their equilibrium values by  γ 1  and  γ 2 : 
 k − , 0 ( m ) = k − , 0 e q ( m ) × γ 1 = k R exp [ − N e m / 2 ] γ 1 , 
 k + , 1 ( m ) = k + , 1 e q ( m ) × γ 2 = k B exp [ − N e m / 2 ] γ 2 . The activation rate  ω 0 ( m ) and deactivation rate  ω 1 ( m ) satisfy:  ω 1 ( m ) =  ω 0 ( m )exp[Δ E ( s, m )]. The activation time  τ a  ≡ [ min  ( ω 1 ( m ),  ω 0 ( m ))] −1  is set to be 10 −3 , much faster than the methylation time  τ R  ≡ 1/ k R  set by  k R  = 1. The steady state distribution 
 P a ( s ) ( m )  is solved by 
 d P a ( s ) ( m ) / d t = 0 . The energy dissipation depends on the fluxes between two states  A  and  B . For example, for  A  = ( a, m ),  B  = ( a, m+ 1), the two counter fluxes are 
 J A B = k + , a ( m ) P a ( s ) ( m )  and 
 J B A = k − , a ( m + 1 ) P a ( s ) ( m + 1 ) . The entropy production rate at link  AB  is 
 S ˙ A B = ( J A B − J B A ) ln [ J A B / J B A ] , and the total entropy production rate  S˙  of the system is the sum of 
 S ˙ A B  over all the links (see  SI  for details). The energy dissipation rate  W˙  =  kTS˙ , where  kT  is the thermal energy unit. The adaptation error can be obtained from the average activity 
 〈 a 〉 = ∑ m P 1 ( s ) ( m ) . Experiments the adaptation measurement was performed with tryptone broth-grown  E. coli  K-12 strain LJ110 Δ ( cheY cheZ ) expressing the CheY-YFP/CheZ-CFP FRET pair, a reporter for kinase activity, as described in a previous article [ 43 ]. During the measurement, cells were kept under constant flow of nutrient-free tethering buffer (10mM KPO 4 , 0.1mM EDTA, 1mM methionine, 67mM NaCl, pH 7) at a rate of 300 μ l/min and were stimulated at regular intervals with 50 μ M  α -methyl-DL-aspartate (MeAsp), a non-metabolizable aspartate analogue, until adaptation was completed. Data were acquired as in reference [ 43 ]. Supplementary Material 1 We thank Drs. Jerry Tersoff, Tom Theis, and Klaus Schwarz for comments. This work is partially supported by a NIH grant (R01GM081747 to YT), a DFG grant (SO 421/3-3 to VS), and a Cajamadrid fellowship to PS. YT initiated the work; GL, PS, and YT carried out the theoretical calculations; SN and VS performed the experiments; GL did the data analysis; all wrote the paper. 1 Niven JE Laughlin SB Energy limitation as a selective pressure on the evolution of sensory systems J Exp Biol 211 1792 1804 2008 18490395 10.1242/jeb.017574 2 Hazelbauer GL Falke JJ Parkinson JS Bacterial chemoreceptors: high-performance signaling in networked arrays Trends Biochem Sci 33 9 19 2008 18165013 10.1016/j.tibs.2007.09.014 PMC2890293 3 Hohmann S Osmotic stress signaling and osmoadaptation in yeasts Am Soc Microbiol 66 2 300 372 2002 10.1128/MMBR.66.2.300-372.2002 PMC120784 12040128 4 Menini A Calcium signalling and regulation in olfactory neurons Current Opinion in Neuro-biology 9 4 419 426 1999 10.1016/S0959-4388(99)80063-4 10448159 5 Nakatani K Tamura T Yau KW Light Adaptation in Retinal Rods of the Rabbit and Two Other Nonprimate Mammals J Gen Physiol 97 413 435 1991 2037836 10.1085/jgp.97.3.413 PMC2216483 6 Ma W Defining network topologies that can achieve biochemical adaptation Cell 138 760 773 2009 19703401 10.1016/j.cell.2009.06.013 PMC3068210 7 Sartori P Tu Y Noise Filtering Strategies in Adaptive Biochemical Signaling Networks: Application to E. Coli Chemotaxis J Stat Phys 142 1206 1217 2011 22977289 10.1007/s10955-011-0169-z PMC3439208 8 Kampen Van NG Stochastic Processes in Physics and Chemistry North-Holland Amsterdam 1981 9 Tu Y Shimizu TS Berg HC Modeling the chemotactic response of Escherichia coli to time-varying stimuli Proc Natl Acad Sci USA 105 14855 14860 2008 18812513 10.1073/pnas.0807569105 PMC2551628 10 Lebowitz JL Spohn H A Gallavotti-Cohen-Type Symmetry in the Large Deviation Funcional for Stochastic Dynmaics J Stat Phys 95 333 365 1999 11 Parmeggiani A Julicher F Ajdari A Prost J Energy transduction of isothermal ratchets: Generic aspects and specific examples close to and far from equilibrium Phys Rev E 60 2127 2140 1999 10.1103/physreve.60.2127 11970005 12 Seifert U Entropy production along a stochastic trajectory and an integral fluctuation theorem Phys Rev Lett 95 040602 2005 16090792 10.1103/PhysRevLett.95.040602 13 Tome T Entropy Production in Nonequilibrium Systems Described by a Fokker-Planck Equation Brazilian J of Phys 36 4A 1285 1289 2006 14 Qian H Phosphorylation Energy Hypothesis: Open Chemical Systems and Their Biological Functions Annu Rev Phys Chem 58 113 142 2007 17059360 10.1146/annurev.physchem.58.032806.104550 15 Barkai N Leibler S Robustness in simple biochemical networks Nature 387 913 917 1997 9202124 10.1038/43199 16 Morton-Firth CJ Bray D Predicting Temporal Fluctuations in an Intracellular Signalling Pathway J Theor Biol 192 117 128 1998 9628844 10.1006/jtbi.1997.0651 17 Yi TM Robust perfect adaptation in bacterial chemotaxis through integral feedback control Proc Natl Acad Sci USA 97 4649 4653 2000 10781070 10.1073/pnas.97.9.4649 PMC18287 18 Mello BA Tu Y Perfect and near perfect adaptation in a model of bacterial chemotaxis Biophys J 84 5 2943 2956 2003 12719226 10.1016/S0006-3495(03)70021-6 PMC1302857 19 Endres RG Wingreen NS Precise adaptation in bacterial chemotaxis through “assistance neighborhoods Proc Natl Acad Sci USA 103 35 13040 13044 2006 16924119 10.1073/pnas.0603101103 PMC1559749 20 Shimizu TS Tu Y Berg HC A modular gradient-sensing network for chemotaxis in Escherichia coli revealed by responses to time-varying stimuli Mol Syst Biol 6 1 382 2010 20571531 10.1038/msb.2010.37 PMC2913400 21 Berg HC Brown DA Chemotaxis in  E. coli  analysed by Three dimensional Tracking Nature 239 5374 500 504 1972 4563019 10.1038/239500a0 22 Ota IM Varshavsky A A yeast protein similar to bacterial two-component regulators Science 262 5133 566 569 1993 8211183 10.1126/science.8211183 23 Posas F Yeast HOG1 MAP kinase cascade is regulated by a multistep phosphorelay mechanism in the SLN1-YPD1-SSK1 “two-component” osmosensor Cell 86 6 865 875 1996 8808622 10.1016/s0092-8674(00)80162-2 24 Zufall F Shepherd GM Firestein S Inhibition of the olfactory cyclic nucleotide gated ion channel by intracellular calcium Proc Biol Sci 246 1317 225 230 1991 1686087 10.1098/rspb.1991.0148 25 Matthews HR Reisert J Calcium, the two-faced messenger of olfactory transduction and adaptation Curr Opin Neurobiol 13 4 469 475 2003 12965295 10.1016/s0959-4388(03)00097-7 26 Walsh C Posttranslational modification of proteins: expanding nature's inventory Roberts & Company Publishers 2006 27 Alon U Robustness in bachterial chemotaxis Nature 397 168 171 1999 9923680 10.1038/16483 28 Detwiler PB Engineering Aspects of Enzymatic Signal Transdcusion: Photoreceptors in the Retina Biophys J 79 6 2801 2817 2000 11106590 10.1016/S0006-3495(00)76519-2 PMC1301161 29 Sourjik V Berg HC Receptor sensitivity in bacterial chemotaxis Proc Natl Acad Sci USA 99 1 123 127 2002 11742065 10.1073/pnas.011589998 PMC117525 30 Lan G Adapt locally and act globally: strategy to maintain high chemoreceptor sensitivity in complex environments Mol Syst Biol 7 1 475 2011 21407212 10.1038/msb.2011.8 PMC3094069 31 Landauer R Dissipation and Noise Immunity in Computation and Commumnication Nature 335 779 784 1988 32 Li M Hazelbauer GL Cellular stoichiometry of the components of the Chemotaxis Signaling Complex J Bacteriol 186 12 3687 3694 2004 15175281 10.1128/JB.186.12.3687-3694.2004 PMC419939 33 Berg HC The rotary motor of bacterial flagella Ann Rev Biochem 72 19 54 2003 12500982 10.1146/annurev.biochem.72.121801.161737 34 Voet D Voet JG Pratt CW Fundamentals of biochemistry Wiley New York 1999 35 Hopfield JJ Kinetics proofreading: a new mechanism for reducing errors in biosynthetic processes requiring high specificity Proc Natl Acad Sci USA 71 10 4135 4139 1974 4530290 10.1073/pnas.71.10.4135 PMC434344 36 Savageau MA Freter RR Energy cost of proofreading to increase fidelity of transfer ribonucleic acid aminoacylation Biochemistry 18 16 3486 3493 1979 258151 10.1021/bi00583a008 37 Bennett CH Dissipation-Error Tradeoff in Proofreading Biosystems 11 2-3 85 91 1979 497372 10.1016/0303-2647(79)90003-0 38 Qian H Reducing intrinsic biochemical noise in cells and its thermodynamic limit J Mol Biol 362 3 387 392 2006 16934833 10.1016/j.jmb.2006.07.068 39 Schmidel T Seifert U Efficiency of molecular motors at maximum power EPL 83 30005 2008 40 Koshland DE Goldbeter A Stock JB Amplification and adaptation in regulatory and sensory systems Science 217 220 225 1982 7089556 10.1126/science.7089556 41 Alon U An introduction to systems biology: design principles of biological circuits CRC Press 2007 42 Kashtan N Alon U Spontaneous evolution of modularity and network motifs Proc Natl Acad Sci USA 102 39 13883 13778 2005 10.1073/pnas.0503610102 PMC1236541 16174729 43 Neumann S Differences in signalling by directly and indirectly binding ligands in bacterial chemotaxis The EMBO J 29 20 3484 3495 2010 20834231 10.1038/emboj.2010.224 PMC2964171 Figure 1 Schematic model of adaptive feedback systems.  (a)  The 3-node feedback topology and its general adaptive behavior. The inhibitory effect of the input is chosen arbitrarily and does not affect any of the conclusions in this paper.  (b-e)  Examples of sensory adaptive networks with highlighted key negative feedback loops:  (b) 
 E. coli  chemotaxis: association of ligand to methyl-accepting-chemotaxis-protein (MCP) induces the methyltransferase (CheR)/methylesterase (CheB) to add/remove methyl-groups to/from MCP respectively to counteract the influence of ligand binding;  (c)  Osmotic sensing in yeast: hyperosmotic shock deactivates osmosensor Sln1p to Sln1, which stops the SLN1-YPD1-SSK1 multi-step phospho-relay and activates the HOG1 pathway to restore cell turgidity and eventually enhances the phosphorylation of Sln1 back to active Sln1p;  (d)  Olfactory sensing in mammalian neurons: odorant binding induces activation of Adenylyl Cyclase (AC) causing the inbound Calcium (Ca 2+ ) flux, and Calmodulin (CaM) interacts with enriched Calcium to form Ca-CaM and activate AC phosphorylase Calmodulin kinase II (CAMKII) that eventually phosphorylate and deactivate AC;  (e)  Light sensing in mammalian neurons: light activates the G-protein coupled receptor (photon-sensor) that decreases the cellular level of cGMP and inhibits the inbound Calcium (Ca 2+ ) flux, which eventually turns on the kinase ORK to phosphorylate and deactivate the photon-sensor. The key high-energy biomolecules are labeled in red. Figure 2 Energetics and kinetics of adaptation.  (a)  An effective potential, obtained by averaging over the fast activity variation, is shown for the equilibrium model ( β  = 0) and the nonequilibrium models ( β  > 0). For  β  >  β c , the state at  m  =  m*  changes from being unstable to stable.  (b)  The steady state probability density  P ( a, m ) (color plot) and the phase-space fluxes ( J a , J m ) (vector field) are shown for the equilibrium model ( β  = 0). The fluxes vanish  J a  =  J m  = 0 everywhere and  P ( a, m ) is centered at the corners of the phase space.  (c)  In the nonequilibrium fully adaptive model ( β  = 1), the non-zero fluxes form a vortex (cycle) around the peak of  P ( a, m ). The peak of  P ( a, m ) has a fixed value of activity and a value of  m  that is small for low background signal (left panel) and high for high background signal (right panel).  (d)  In the equilibrium model (left panel), the system always moves downhill (green arrows) to its lowest energy state; In the nonequilibrium adaptive model (right panel), external energy ( W ) is consumed to push the system uphill (red arrows) to maintain it near the cross-over point of the active and inactive states. Figure 3 The  E. coli  chemotaxis adaptation.  (a)  The schematics of the  E. coli  chemoreceptor adaptation process. The red and blue cycles represent the receptor methylation-demethylation cycles for low and high attractant concentrations respectively, analogous to the flux cycles shown in  Fig. 2d .  (b)  The energy dissipation Δ W  per unit of time 
 ( k R − 1 )  (solid lines) and normalized adaptation error  ε/ε 0  (dotted lines) versus the parameter  γ  for different values of ligand concentration  s. ε 0  ≡ ε( γ  = 1).  (c)  The adaptation error versus different energy dissipation for different values of background ligand concentration  s . Solid lines from bottom to top represent log 10 ( s/K I ) = 1.2, 1.0, 0.5, −3.0; dashed lines from bottom to top represent log 10 ( s/K I ) = 3, 3.5, 4, 6.  K I  is the dissociation constant for the inactive receptor.  ε c  is the saturation error at Δ W  → ∞, Δ W c  is defined as the Δ W  value when  ε  = 0.99 ε c .  (d)  The prefactor  α  in the error-energy relationship and its dependence on the methyl modification rates  k R  and  k B . Figure 4 The cost-performance relationship.  (a)  Adaptive accuracy versus energy cost for over 10, 000 different models (represented by hollow dots) with random choices of parameters. log 10 γ  is randomly picked from [0, −10], log 10 τ a  is randomly picked from [−3, 3], Δ E (0) and −Δ E ( m 0 ) are randomly picked from [ 11 ,  22 ] kT , log 10 ( s/K I ) is randomly picked from [−10, 10]. The best performance line is outlined. The case for Tar is shown (dashed line) with the available energies in SAM and ATP (both at 20% efficiency) marked.  (b)  The responses to a step stimulus (from  s  = 0 to  s  =  10K I ) at  t  = 1 for the equilibrium model (black), and nonequilibrium models driven by ATP (red line) and SAM (blue line) at 20% efficiency. Figure 5 Adaption dynamics of starving  E. coli  cells.  (a)  Response of  E. coli  cells to successive addition and removal of a saturating stimulus (50 μ M MeAsp) over 7 hours' period in a medium without nutrition (stimulus time series shown at top). Changes in kinase activity were measured using FRET reporter based on a YFP fusion to the chemotaxis response regulator CheY and a CFP fusion to its phosphatase CheZ. The gray line is the monitored ratio of YFP to CFP fluorescence. The baseline YFP / CFP ratio at zero FRET is shown by the black dashed line. The black solid line indicates the adapted activity without any stimuli. The drift in the zero-FRET baseline is primarily due to the differences in the photobleaching kinetics of YFP and CFP. The inset plot shows the normalized FRET signal in response to 50 μM  MeAsp addition at 1442sec (blue), 10761sec (red) and 23468sec (black), as indicated by arrows of the same colors in the main plot. The response amplitude weakens as cells de-energize. Adaptation takes longer, but activity always returns to its pre-stimulus level with high accuracy.  (b)  The adaptation half-time, defined as the time needed to recover half of the maximum response upon MeAsp addition, increases about 3-fold (from  ∼  130sec to  ∼  410sec).  (c)  The relative adaptation accuracy remains unchanged ( ∼  95%). The symbols in (b)&(c) are from measurements and the red lines are for guide of eye.