Fully dynamic cycle-equivalence in graphs - Henzinger, Monika H (35th Annual Symposium on Foundations of Computer Science)
Two edges e/sub 1/ and e/sub 2/ of an undirected graph are cycle-equivalent iff all cycles that contain e/sub 1/ also contain e/sub 2/, i.e., iff e/sub 1/ and e/sub 2/ are a cut-edge pair. The cycle-equivalence classes of the control-flow graph are used in optimizing compilers to speed up existing control-flow and data-flow algorithms. While the cycle-equivalence classes can be computed in linear time, we present the first fully dynamic algorithm for maintaining the cycle-equivalence relation. In an n-node graph our data structure executes an edge insertion or deletion in O(/spl radic/n log n) time and answers the query whether two given edges are cycle-equivalent in O(log/sup 2/ n) time. We also present an algorithm for plane graphs with O(log n) update and query time and for planar graphs with O(log n) insertion time and O(log/sup 2/ n) query and deletion time. Additionally, we show a lower bound of /spl Omega/(log n/log log n) for the amortized time per operation for the dynamic cycle-equivalence problem in the cell probe model.< >

Proton translocating transhydrogenase and NAD- and NADP-linked isocitrate dehydrogenases operate in a substrate cycle which contributes to fine regulation of the tricarboxylic acid cycle activity in mitochondria - Sazanov, Leonid A; Jackson, Julie (FEBS Letters)
H+-transhydrogenase (H+-Thase) and NADP-linked isocitrate dehydrogenase (NADP-ICDH) are very active in animal mitochondria but their physiological function is only poorly understood. This is especially so in the case of the heart and muscle, where there are no major consumers of NADPH. We propose here that H+-Thase and NADP-ICDH have a combined function in the fine regulation of the activity of the tricarboxylic acid (TCA) cycle, providing enhanced sensitivy to changes in energy demand. This is achieved through cycling of substrates by NAD-linked ICDH, NADP-linked ICDH and H+-Thase. It is proposed that NAD-ICDH operates in the forward direction of the TCA cycle, but NADP-ICDH is driven in reverse by elevated levels of NADPH resulting from the action of the transmembrane proton electrochemical potential gradient (Δp) on H+-Thase. This has the effect of increasing the sensitivity to allosteric modifiers of NAD-ICDH (NADH, ADP, ATP, Ca2+ etc), potentially giving rise to large changes in the net flux from iso-citrate to α-ketoglutarate. Furthermore, changes in the level of Δp resulting from changes in the demand for ATP would, via H+-Thase, shift the redox state of the NADP pool and this, in turn, would lead to a change in the rate of the reaction catalysed by NADP-ICDH and hence to an additional and complementary effect on the net metabolic flux from isocitrate to α-ketoglutarate. Other consequences of this substrate cycle are, (i) the production of heat at the expense of Δp, which may contribute to thermoregulation in the animal, and (ii) an increased rate of dissipation of Δp (leak).

Inhibition of the respiratory burst in mouse macrophages by ultra-low doses of an opioid peptide is consistent with a possible adaptation mechanism - Efanov, Alexander; Koshkin, Aleksei; Sazanov, Leonid A; Borodulina, O I; Varfolomeev, Sergei; Zaǐtsev, Sergei (FEBS Letters)
The respiratory burst induced by phorbol myristate acetate in mouse macrophages was inhibited by ultra-low doses (10-15 -10-13 M) of an opioid peptide [d-Ala2] methionine enkephalinamide. The effect disappeared at concentrations above and below this range. The inhibition approached 50% and was statistically significant (P < 0.001). Increasing the time of the opioid incubation with cells brought about a shift in the maximal effect to lower concentrations of the opioid (from 10-13 to 5 · 10-15 M) and led to a decrease in the value of the effect, fully in accord with the previously proposed adaptation mechanism of the action of ultra-low doses.

Morphological and chemical characteristics of substance P receptor immunoreactive neurons in the rat neocortex - Kaneko, Takeshi; Shigemoto, Ryuichi; Nakanishi, Shigetada; Mizuno, Noboru (Neuroscience)
Substance P receptor-expressing neurons in the rat cerebral neocortex were examined by single- and double-immunolabeling methods with an affinity-purified specific antibody to substance P receptor. Substance P receptor immunoreactivity was observed exclusively in non-pyramidal neurons. About a quarter of these substance P receptor-positive neocortical neurons showed intense immunoreactivity, and the other three quarters displayed weak substance P receptor immunoreactivity. The neurons showing intense substance P receptor immunoreactivity were large multipolar cells with a few long aspiny or sparsely-spiny dendrites, and were scattered throughout the neocortical layers except for layer I, and also in the underlying white matter. The weakly immunoreactive neurons were medium-sized multipolar cells with oval to round somata and aspiny varicose dendrites, and were distributed in all cortical layers with a bias to layers II-III and the superficial part of layer V. The double-immunofluorescence study revealed that almost all substance P receptor-positive neurons were immunoreactive for GABA, but negative for glutaminase. Substance P receptor immunoreactivity in GABAergic neocortical neurons were further examined by the double-immunofluorescence method with antibodies to markers for subgroups of GABAergic neurons. Somatostatin immunoreactivity was found in 89% of neurons with intense substance P receptor immunoreactivity, and in 1.5% of neurons with weak substance P receptor immunoreactivity. Neuropeptide Y immunoreactivity was also observed in 92% of neurons with intense immunoreactivity for substance P receptor, and in 1.6% of neurons with weak immunoreactivity for substance P receptor. In contrast, parvalbumin immunoreactivity was seen in 1.3% of neurons with intense substance P receptor immunoreactivity, and in 59% of weak substance P receptor immunoreactivity. Calbindin D28k immunoreactivity was found in 12 and 19% of neurons, respectively, with weak and intense immunoreactivities for substance P receptor. Virtually no cells showing substance P receptor immunoreactivity displayed immunoreactivity for vasoactive intestinal polypeptide or choline acetyltransferase. These results indicate that the neocortical neurons expressing substance P receptor constitute a subpopulation of GABAergic non-pyramidal cells, and are segregated into neurons with intense immunoreactivity and those with weak immunoreactivity for substance P receptor; the vast majority of neurons with intense substance P receptor immunoreactivity contain somatostatin and neuropeptide Y, and the majority of neurons with weak substance P receptor immunoreactivity have parvalbumin.

Differential expression of five N-methyl-D-aspartate receptor subunit mRNAs in the cerebellum of developing and adult rats - Akazawa, Chihiro; Shigemoto, Ryuichi; Bessho, Yasumasa; Nakanishi, Shigetada; Mizuno, Noboru (Journal of Comparative Neurology)
Five N-methyl-D-aspartate (NMDA) receptor subunits have been identified thus far: NR1, NR2A, NR2B, NR2C, and NR2D. Here, we have analyzed the expression patterns of mRNAs for the NMDA receptor subunits in the developing and adult rats by in situ hybridization. The developmental changes of the expression patterns were most salient in the cerebellum. In the external granular layer, hybridization signals of mRNAs for NR1, NR2A, NR2B, and NR2C appeared by postnatal day 3, but no NR2D mRNA was expressed at any developmental stage examined. The NR1 mRNA was expressed in all cerebellar neurons at all developmental stages examined. The signals for the NR2A mRNA appeared in Purkinje cells and granule cells during the second postnatal week. The signals for the NR2B mRNA in granule cells were seen transiently during the first 2 weeks after birth. The signals for NR2C mRNA appeared in granule cells and glial cells during the second postnatal week. The signals for NR2D mRNA appeared transiently in Purkinje cells during the first 8 postnatal days; in adult rats, these were seen in stellate and Golgi cells. In the cerebellar nuclei, mRNAs for NR1, NR2A, NR2B, and NR2D were more or less expressed on postnatal day 0, while expression signals for the NR2C mRNA were first detected in postnatal day 14. Thus, the most conspicuous changes of expression patterns were observed in the cerebellar cortex during the first 2 weeks after birth, when development and maturation of the cerebellum proceed most rapidly.

Distribution of the messenger rna for the prostaglandin e receptor subtype ep3 in the mouse nervous system - Sugimoto, Yukihiko; Shigemoto, Ryuichi; Namba, Tsunehisa; Negishi, Manabu; Mizuno, Noboru; Narumiya, Shuh; Ichikawa, Atsushi (Neuroscience)
Distribution of the messenger RNA for the prostaglandin E receptor subtype EP3 was investigated by in situ hybridization in the nervous system of the mouse. The hybridization signals for EP3 were widely distributed in the brain and sensory ganglia and specifically localized to neurons. In the dorsal root and trigeminal ganglia, about half of the neurons were labeled intensely. In the brain, intensely labeled neurons were found in Ammon's horn, the preoptic nuclei, lateral hypothalamic area, dorsomedial hypothalamic nucleus, lateral mammillary nucleus, entopeduncular nucleus, substantia nigra pars compacta, locus coeruleus and raphe nuclei. Moderately labeled neurons were seen in the mitral cell layer of the main olfactory bulb, layer V of the entorhinal and parasubicular cortices, layers V and VI of the cerebral neocortex, nuclei of the diagonal band, magnocellular preoptic nucleus, globus pallidus and lateral parabrachial nucleus. In the thalamus, moderately labeled neurons were distributed in the anterior, ventromedial, laterodorsal, paraventricular and central medial nuclei. Based on these distributions, we suggest that EP3 not only mediates prostaglandin E2 signals evoked by blood-borne cytokines in the areas poor in the blood-brain barrier, but also responds to those formed intrinsically within the brain to modulate various neuronal activities. Possible EP3 actions are discussed in relation to the reported neuronal activities of prostaglandin E2 in the brain.

Molecular diversity of glutamate receptors and their physiological functions - Nakanishi, Shigetada; Masu, Masayuki; Bessho, Yasumasa; Nakajima, Yoshiaki; Hayashi, Yasunori; Shigemoto, Ryuichi (Experientia Supplementum)
Glutamate receptors play an important role in many integrative brain functions and in neuronal development. We report the molecular diversity of NMDA receptors and metabotropic glutamate receptors on the basis of our studies of molecular cloning and characterization of the diverse members of these receptors. The NMDA receptors consist of two distinct types of subunits. NMDAR1 possesses all properties characteristic of the NMDA receptor-channel complex, whereas the four NMDAR2 subunits, termed NMDAR2A-2D, show no channel activity but potentiate the NMDAR1 activity and confer functional variability by different heteromeric formations. The NMDA receptor subunits are considerably divergent from the other ligand-gated ion channels, and the structural architecture of these subunits remains elusive. The mGluRs form a family of at least seven different subtypes termed mGluR1-mGluR7. These receptor subtypes have, seven transmembrane segments and possess a large extracellular domain at their N-terminal regions. The seven mGluR subtypes are classified into three subgroups according to their sequence similarities, signal transduction mechanisms and agonist selectivities: mGluR1/mGluR5, mGluR2/mGluR3 and mGluR4/mGluR6/mGluR7. On the basis of our knowledge of the molecular diversity of the NMDA receptors and mGluRs, we have studied the physiological roles of individual receptor subunits or subtypes. We have shown that K(+)-induced depolarization or NMDA treatment in primary cultures of neonatal cerebellar granule cells induces the functional NMDA receptor and specifically up-regulates NMDAR2A mRNA among the multiple NMDA receptor subunits through the increase in resting intracellular Ca2+ concentrations. Our study demonstrates that the regulation of the specific NMDA receptor subunit mRNA governs the NMDA receptor induction that is thought to play an important role in granule cell survival and death. Analysis of an agonist selectivity and an expression pattern of mGluR6 has indicated that mGluR6 is responsible for synaptic neurotransmission from photoreceptor cells to ON-bipolar cells in the visual system. We have also investigated the function of mGluR2 in granule cells of the accessory olfactory bulb by combining immunoelectron-microscopic analysis with slice-patch recordings on the basis of the identification of a new agonist selective for this receptor subtype. Our results demonstrate that mGluR2 is present at the presynaptic site of granule cells and modulates inhibitory GABA transmission from granule cells to mitral cells. This finding indicates that the mGluR2 activation relieves excited mitral cells from GABA inhibition but maintains the lateral inhibition of unexcited mitral cells, thus resulting in enhancement of the signal-to-noise ratio between the excited mitral cells and their neighboring unexcited mitral cells.

Immunohistochemical localization of substance P receptor in the central nervous system of the adult rat - Nakaya, Yoshifumi; Kaneko, Takeshi; Shigemoto, Ryuichi; Nakanishi, Shigetada; Mizuno, Noboru (Journal of Comparative Neurology)
In an attempt to reveal the function sites of substance P (SP) in the central nervous system (CNS), the distribution of SP receptor (SPR) was immunocytochemically investigated in adult rat and compared with that of SP- positive fibers. SPR-like immunoreactivity (LI) was mostly localized to neuronal cell bodies and dendrites. Neurons with intense SPR-LI were distributed densely in the cortical amygdaloid nucleus, hilus of the dentate gyrus, locus ceruleus, rostral half of the ambiguus nucleus, and intermediolateral nucleus of the thoracic cord; moderately in the caudatoputamen, nucleus accumbens, olfactory tubercle, median, pontine, and magnus raphe nuclei, laminae I and III of the caudal subnucleus of the spinal trigeminal nucleus, and lamina I of the spinal cord; and sparsely in the cerebral cortex, basal nucleus of Meynert, claustrum, gigantocellular reticular nucleus, and lobules IX and X of the cerebellar vermis. Neurons with weak to moderate SPR-LI were distributed more widely throughout the CNS. The regional patterns of distribution of SPR-LI were not necessarily the same as those of SP-positive fibers. The entopeduncular nucleus, substantia nigra, and lateral part of the interpeduncular nucleus showed intense SP-LI but displayed almost no SPR-LI. Conversely, the hilus of the dentate gyrus, anterodorsal thalamic nucleus, central nucleus of the inferior colliculus, and dorsal tegmental nucleus showed intense to moderate SPR-LI but contained few axons with SP-LI. These findings confirmed the presence of the 'mismatch' problem between SP and SPR localizations. However, the distribution of SPR- LI was quite consistent with that of the SP-binding activity, which has been studied via autoradiography. This indicates that the sites of SPR-LI revealed in the present study represent most, if not all, sites of SP-binding activity.

Molecular characterization of a new metabotropic glutamate receptor mGluR7 coupled to inhibitory cyclic AMP signal transduction - Okamoto, Naoyuki; Hori, Seiji; Akazawa, Chihiro; Hayashi, Yasunori; Shigemoto, Ryuichi; Mizuno, Noboru; Nakanishi, Shigetada (Journal of Biological Chemistry)
A cDNA clone for a new rat metabotropic glutamate receptor termed mGluR7 was isolated through polymerase chain reaction-mediated DNA amplification by using primer sequences conserved among the metabotropic receptor (mGluR) family and by the subsequent screening of a rat forebrain cDNA library. The cloned mGluR7 subtype consists of 915 amino acid residues and exhibits a structural architecture common to the mGluR family with a large extracellular domain preceding the seven putative membrane-spanning domains. mGluR7 shows the highest sequence similarity to mGluR4 and mGluR6 among the members of the mGluR family. Similar to mGluR4 and mGluR6, mGluR7 inhibits forskolin- stimulated cyclic AMP accumulation in response to agonist interaction and potently reacts with L-2-amino-4-phosphonobutyrate and L-serine-O-phosphate in Chinese hamster ovary cells transfected with the cloned cDNA. RNA blot and in situ hybridization analyses of mGluR7 mRNA indicated that it is widely expressed in many neuronal cells of the central nervous system and is thus different from the more limitedly expressed mGluR4 or mGluR6 mRNA. mGluR7 together with mGluR4 thus corresponds to the putative L-2-amino-4- phosphonobutyrate receptor which plays an important role in modulation of glutamate transmission in the central nervous system.

Distinct cellular localization of mRNAs for three subtypes of prostaglandin E receptor in kidney - Sugimoto, Yukihiko; Namba, Tsunehisa; Shigemoto, Ryuichi; Negishi, Manabu; Ichikawa, Atsushi; Narumiya, Shuh (American Journal of Physiology)
Distribution of the mRNAs for three subtypes of prostaglandin E (PGE) receptors in the mouse kidney was investigated by in situ hybridization. The mRNA for EP1 subtype, which is coupled to Ca2+ mobilization, was specifically localized to the collecting ducts from the cortex to the papilla. The mRNA for EP2 subtype, which is linked to stimulation of adenylate cyclase, was localized to the glomeruli. The mRNA for EP3 subtype, which is coupled to inhibition of adenylate cyclase, was located densely in the tubules in the outer medulla and in the distal tubules in the cortex. These results exhibit distinct cellular localization of three subtypes of PGE receptor in the kidney and suggest that PGE2 exerts multiple functions via these subtypes expressed in different segments of the nephron.

Immunohistochemical localization of substance P receptor in the superior colliculus. A light and electron microscope study in the rat - Ogawa Meguro, Reiko; Shigemoto, Ryuichi; Itoh, Kazuo; Konishi, Akira; Mizuno, Noboru (Neuroscience Letters)
The superficial layers of the superior colliculus (SC) have been known to contain many axons showing substance P-like immunoreactivity (SP-LI). We, therefore, immunohistochemically examined the distribution of SP receptor (SPR) in the superficial layers of the SC in the rat by using a specific antibody against SPR. The majority of SC neurons with SPR-LI were distributed in the zonal and the superficial gray layers, the rest of them were in the optic layer. Electron microscopy revealed that SPR-immunoreaction products in SC neurons were distributed not only in postsynaptic sites, but also in non-synaptic regions of perikaryal and dendritic profiles.

Expression of mRNAs of l-AP4-sensitive metabotropic glutamate receptors (mGluR4, mGluR6, mGluR7) in the rat retina - Akazawa, Chihiro; Ohishi, Hitoshi; Nakajima, Yoshiaki; Okamoto, Naoyuki; Shigemoto, Ryuichi; Nakanishi, Shigetada; Mizuno, Noboru (Neuroscience Letters)
Expression patterns of mRNAs of l-AP4-sensitive metabotropic glutamate receptors (mGluR4, mGluR6, mGluR7) in the rat retina were examined by northern blot analysis and in situ hybridization histochemistry. Expression patterns of mGluR4 and mGluR7 mRNAs were quite different from that of mGluR6 mRNA which was expressed at the outer part of the inner nuclear layer. The mGluR4 mRNA was expressed on the cell bodies of the ganglion cells, but not in the inner or outer nuclear layer. The expression of mGluR7 mRNA was observed throughout the entire region of the inner nuclear layer and on the cell bodies of the ganglion cells.

Induction mechanism of long term depression in cultured Purkinje neurons - Hirano, Tomoo; Kasono, Keizo; Ryuichi Shigemoto; Nakanishi, Shigetada
The induction mechanism of cerebellar long term depression (LTD) has been analysed in a cerebellar culture. Using nitr-5, a photolabile Ca chelator, we demonstrated that an increase in postsynaptic Ca together with glutamate application is sufficient to induce the LTD of glutamate responsiveness in Purkinje cells. It has also been shown that one subtype of genetically defined metabotropic glutamate receptor, mGluR1, is involved in the LTD induction. We raised antibodies which specifically recognized mGluR1 and inactivated its function. The antibodies suppressed the LTD induction in the cultured Purkinje cells.

Antibodies inactivating mGluR1 metabotropic glutamate receptor block long-term depression in cultured Purkinje cells - Shigemoto, Ryuichi; Abe, Takaaki; Nomura, Sakashi; Nakanishi, Shigetada; Hirano, Tomoo (Neuron)
Antibodies were raised against two distinct extracellular sequences of the rat mGluR1 metabotropic glutamate receptor expressed as bacterial fusion proteins. Both antibodies specifically reacted with mGluR1 in the rat cerebellum and inhibited the mGluR1 activity as assessed by the analysis of glutamate-stimulated inositol phosphate formation in CHO cells expressing mGluR1. Using these antibodies, we examined the role of mGluR1 in the induction of long-term depression in cultured Purkinje cells. In voltage- clamped Purkinje cells, current induced by iontophoretically applied glutamate was persistently depressed by depolarization of the Purkinje cells in conjunction with the glutamate application. The mGluR1 antibodies completely blocked the depression of glutamate-induced current. The results indicate that activation of mGluR1 is necessary for the induction of cerebellar long-term depression and that these mGluR1 antibodies can be used as selective antagonists.

Developmentally regulated postsynaptic localization of a metabotropic glutamate receptor in rat rod bipolar cells - Nomura, Akinori; Shigemoto, Ryuichi; Nakamura, Yasuhisa; Okamoto, Naoyuki; Mizuno, Noboru; Nakanishi, Shigetada (Cell)
The retinal bipolar cell receiving glutamate transmission from photoreceptors mediates a key process in segregating visual signals into ON center and OFF center pathways. This transmission involves a G protein- coupled metabotropic glutamate receptor (mGluR). Immunocytochemical and immunoelectron microscopic studies indicate the restricted localization of a specific mGluR subtype, mGluR6, at the postsynaptic site of the rat rod bipolar cell. This specialization is developmentally regulated: mGluR6 is initially distributed in both the soma and dendrites and is finally concentrated on the postsynaptic site. The mGluR6 localization is reversed when photoreceptors degenerate in the mutant rat with retinal dystrophy. Evidence is thus presented indicating specialized, developmentally regulated receptor distribution in the central nervous system and the crucial role of mGluR6 in photoreceptor-bipolar cell synaptic transmission.

Immunohistochemical localization of metabotropic glutamate receptors, mGluR2 and mGluR3, in rat cerebellar cortex - Ohishi, Hitoshi; Ogawa Meguro, Reiko; Shigemoto, Ryuichi; Kaneko, Takeshi; Nakanishi, Shigetada; Mizuno, Noboru (Neuron)
The distribution of the metabotropic glutamate receptors mGluR2 and mGluR3 was immunohistochemically examined in the rat cerebellar cortex at both light and electron microscope levels. An antibody was raised against a fusion protein containing a C-terminal portion of mGluR2. On immunoblot, the antibody reacted with both mGluR2 and mGluR3 in rat brain. mGluR2/3 immunoreactivity was expressed in cell bodies, dendrites, and axon terminals of Golgi cells, as well as in presumed glial processes. Golgi axon terminals with mGluR2/3 immunoreactivity were often encountered in the vicinity of glutamatergic mossy fiber terminals. The results suggest that transmitter glutamate may exert control influences upon Golgi cells not only through dendritic mGluR2/3, but also through axonal mGluR2/3.

Estimates on stochastic oscillatory integrals and on the heat kernel of the magnetic Schrödinger operator - Erdös, László (Duke Mathematical Journal)

Mechanisms shaping glutamate-mediated excitatory postsynaptic currents in the CNS - Jonas, Peter M; Spruston, Nelson (Current Opinion in Neurobiology)
Excitatory postsynaptic currents in neurones of the central nervous system have a dual-component time course that results from the co-activation of AMPA/kainate-type and NMDA-type glutamate receptors. New approaches in electrophysiology and molecular biology have provided a better understanding of the factors that determine the kinectics of excitatory postsynaptic currents. Recent studies suggest that the time course of neurotransmitter concentration in the synaptic cleft, the gating properties of the native channels, and the glutamate receptor subunit composition all appear to be important factors.

Detailed passive cable models of whole-cell recorded CA3 pyramidal neurons in rat hippocampal slices - Major, Guy; Larkman, Alan; Jonas, Peter M; Sakmann, Bert; Jack, Julian (Journal of Neuroscience)
Tight-seal whole-cell recordings were made from cleaned somata of CA3 pyramidal cells deep in hippocampal slices from 19–21-d-old rats. The cells were filled with biocytin, and their voltage responses to short current pulses were recorded. After washout of initial sag, responses scaled linearly with injected current and were stable over time. The dendritic and axonal arbors of four cells were reconstructed and measured using light microscopy. Dendritic spines and axonal boutons were counted and the additional membrane area was incorporated into the relevant segments. The morphology of each neuron was converted into a detailed branching cable model by assuming values for specific membrane capacitance Cm and resistance Rm, and cytoplasmic resistivity Ri. These parameters were optimized for each cell by directly matching the model's response to that of the real cell by means of a modified weighted least-squares fitting procedure. By comparing the deviations between model and experimental responses to control noise recordings, approximate 95% confidence intervals were established for each parameter. If a somatic shunt was allowed, a wide range of possible Rm values produced acceptable fits. With zero shunt, Cm was 0.7–0.8 microFcm-2, Ri was 170–340 omega cm, and Rm ranged between 120 and 200 k omega cm2. The electrotonic lengths of the basal and oblique dendrites were 0.2–0.3 space constants, and those of the apical tufts were 0.4–0.7 space constants. The steady-state electrical geometry of these cells was therefore compact; average dendritic tip/soma relative synaptic efficacies were > 93% for the basal and oblique dendrites, and > 81% for the tufts. With fast transient synaptic inputs, however, the models produced a wide range of postsynaptic potential shapes and marked filtering of voltage-clamp currents.

Na+-activated K+ channels localized in the nodal region of myelinated axons of Xenopus - Koh, Duk; Jonas, Peter M; Vogel, Werner (Journal of Physiology)
1. A potassium channel activated by internal Na+ ions (K+Na channel) was identified in peripheral myelinated axons of Xenopus laevis using the cell-attached and excised configurations of the patch clamp technique. 2. The single-channel conductance for the main open state was 88 pS with [K+]o = 105 mM and pS with [K+]o = 2.5 mM ([K+]i = 105 mM). The channel was selectively permeable to K+ over Na+ ions. A characteristic feature of the K+Na channel was the frequent occurrence of subconductance states. 3. The open probability of the channel was strongly dependent on the concentration of Na+ ions at the inner side of the membrane. The half-maximal activating Na+ concentration and the Hill coefficient were 33 mM and 2.9, respectively. The open probability of the channel showed only weak potential dependence. 4. The K+Na channel was relatively insensitive to external tetraethylammonium (TEA+) in comparison with voltage-dependent axonal K+ channels; the half-maximal inhibitory concentration (IC50) was 21.3 mM (at -90 mV). In contrast, the channel was blocked by low concentrations of external Ba2+ and Cs+ ions, with IC50 values of 0.7 and 1.1 mM, respectively (at -90 mV). The block by Ba2+ and Cs+ was more pronounced at negative than at positive membrane potentials. 5. A comparison of the number of K+Na channels in nodal and paranodal patches from the same axon revealed that the channel density was about 10-fold higher at the node of Ranvier than at the paranode. Moreover, a correlation between the number of K+Na channels and voltage-dependent Na+ channels in the same patches was found, suggesting co-localization of both channel types. 6. As weakly potential-dependent ('leakage') channels, axonal K+Na channels may be involved in setting the resting potential of vertebrate axons. Simulations of Na+ ion diffusion suggest two possible mechanisms of activation of K+Na channels: the local increase of Na+ concentration in a cluster of Na+ channels during a single action potential or the accumulation in the intracellular axonal compartment during a train of action potentials.

Differences in Ca(2+) permeability of AMPA-type glutamate receptor channels in neocortical neurons caused by differential GluR-B subunit expression - Jonas, Peter M; Racca, Claudia; Sakmann, Bert; Seeburg, Peter; Monyer, Hannah (Neuron)
Fast excitatory synaptic transmission in the CNS is mediated by AMPA-type glutamate receptor (GluR) channels. Heterologous expression suggested that the Ca2+ permeability of these receptors critically depends on the subunit composition. Using patch-clamp techniques in brain slices, we found that the Ca2+ permeability of native AMPA-type GluRs was markedly higher in nonpyramidal (P(Ca)/P(K) ≃ 0.63) than in pyramidal (P(Ca)/P(K) ≃ 0.05) neurons of rat neocortex. Analysis of mRNA in single cells indicated that the relative abundance of GluR-B-specific mRNA was significantly lower in nonpyramidal (GluR-B/GluR-non-B ≃ 0.3) than in pyramidal (GluR-B/GluR-non-B ≃ 3) cells. This suggests that differences in relative abundance of GluR-B- specific mRNA generate functional diversity of AMPA-type GluRs in neurons with respect to Ca2+ permeability.

Modeling with simplicial complexes (topology, geometry and algorithms) - Edelsbrunner, Herbert (Proceedings of the 6th Canadian Conference on Computational Geometry)

Ray shooting in polygons using geodesic triangulations - Chazelle, Bernard; Edelsbrunner, Herbert; Grigni, Michelangelo; Guibas, Leonidas; Hershberger, John; Sharir, Micha; Snoeyink, Jack (Algorithmica)
Let P be a simple polygon with n vertices. We present a simple decomposition scheme that partitions the interior of P into O(n) so-called geodesic triangles, so that any line segment interior to P crosses at most 2 log n of these triangles. This decomposition can be used to preprocess P in a very simple manner, so that any ray-shooting query can be answered in time O(log n). The data structure requires O(n) storage and O(n log n) preprocessing time. By using more sophisticated techniques, we can reduce the preprocessing time to O(n). We also extend our general technique to the case of ray shooting amidst k polygonal obstacles with a total of n edges, so that a query can be answered in O(√ log n) time.

Algorithms for bichromatic line-segment problems and polyhedral terrains - Chazelle, Bernard; Edelsbrunner, Herbert; Guibas, Leonidas; Sharir, Micha (Algorithmica)
We consider a variety of problems on the interaction between two sets of line segments in two and three dimensions. These problems range from counting the number of intersecting pairs between m blue segments and n red segments in the plane (assuming that two line segments are disjoint if they have the same color) to finding the smallest vertical distance between two nonintersecting polyhedral terrains in three-dimensional space. We solve these problems efficiently by using a variant of the segment tree. For the three-dimensional problems we also apply a variety of recent combinatorial and algorithmic techniques involving arrangements of lines in three-dimensional space, as developed in a companion paper.

Three-dimensional alpha shapes - Edelsbrunner, Herbert; Mücke, Ernst (ACM Transactions on Graphics)
Frequently, data in scientific computing is in its abstract form a finite point set in space, and it is sometimes useful or required to compute what one might call the `'shape” of the set. For that purpose, this article introduces the formal notion of the family of alpha-shapes of a finite point set in R3. Each shape is a well-defined polytope, derived from the Delaunay triangulation of the point set, with a parameter alpha is-an-element-of R controlling the desired level of detail. An algorithm is presented that constructs the entire family of shapes for a given set of size n in time O(n2), worst case. A robust implementation of the algorithm is discussed, and several applications in the area of scientific computing are mentioned.

Quantal analysis of excitatory postsynaptic currents at the hippocampal mossy fiber-CA3 pyramidal cell synapse - Von Kitzing, Eberhard; Jonas, Peter M; Sakmann, Bert (Molecular and cellular mechanisms of neurotransmitter release)

Genetic and statistical analyses of strong selection on polygenic traits: What, me normal? - Turelli, Michael; Barton, Nicholas H (Genetics)
We develop a general population genetic framework for analyzing selection on many loci, and apply it to strong truncation and disruptive selection on an additive polygenic trait. We first present statistical methods for analyzing the infinitesimal model, in which offspring breeding values are normally distributed around the mean of the parents, with fixed variance. These show that the usual assumption of a Gaussian distribution of breeding values in the population gives remarkably accurate predictions for the mean and the variance, even when disruptive selection generates substantial deviations from normality. We then set out a general genetic analysis of selection and recombination. The population is represented by multilocus cumulants describing the distribution of haploid genotypes, and selection is described by the relation between mean fitness and these cumulants. We provide exact recursions in terms of generating functions for the effects of selection on non-central moments. The effects of recombination are simply calculated as a weighted sum over all the permutations produced by meiosis. Finally, the new cumulants that describe the next generation are computed from the non-central moments. Although this scheme is applied here in detail only to selection on an additive trait, it is quite general. For arbitrary epistasis and linkage, we describe a consistent infinitesimal limit in which the short-term selection response is dominated by infinitesimal allele frequency changes and linkage disequilibria. Numerical multilocus results show that the standard Gaussian approximation gives accurate predictions for the dynamics of the mean and genetic variance in this limit. Even with intense truncation selection, linkage disequilibria of order three and higher never cause much deviation from normality. Thus, the empirical deviations frequently found between predicted and observed responses to artificial selection are not caused by linkage-disequilibrium-induced departures from normality. Disruptive selection can generate substantial four-way disequilibria, and hence kurtosis; but even then, the Gaussian assumption predicts the variance accurately. In contrast to the apparent simplicity of the infinitesimal limit, data suggest that changes in genetic variance after 10 or more generations of selection are likely to be dominated by allele frequency dynamics that depend on genetic details.

The reduction in fixation probability caused by substitutions at linked loci - Barton, Nicholas H (Genetical Research)
The probability of fixation of a mutation with selective advantage s will be reduced by substitutions at other loci. The effect of a single substitution, with selective advantage S0016672300032857inline1, can be approximated as a sudden reduction in the frequency of the favourable allele, by a fraction w = 1 −(s/S)r/s (where r is the recombination rate). An expression for the effect of a given sequence of such catastrophes is derived. This also applies to the ecological prxoblem of finding the probability that a small population will survive, despite occasional disasters. It is shown that if substitutions occur at a rate Δ, and are scattered randomly over a genetic map of length R, then an allele is unlikely to be fixed if its advantage is less than a critical value, Scrit = (π2/6)(2ΔS/(Rlog(S/s))). This threshold depends primarily on the variance in fitness per unit map length dueto substitutions, var(W)/R = 2ΔS/R. With no recombination, the fixation probability can be calculated for a finite population. If Δ > s, it is of the same order as for a neutral allele ( ≈ Δ/(2N(Δ−s))), whilst if S0016672300032857inline2, fixation probability is much higher than for a neutral allele, but much lower than in the absence of hitch-hiking S0016672300032857inline3. These results suggest that hitch-hiking may substantially impede the accumulation of weakly favoured adaptations.

Selecting heavily covered points - Chazelle, Bernard; Edelsbrunner, Herbert; Guibas, Leonidas; Hershberger, John; Seidel, Raimund; Sharir, Micha (SIAM Journal on Computing)
A collection of geometric selection lemmas is proved, such as the following: For any set P of n points in three-dimensional space and any set S of m spheres, where each sphere passes through a distinct point pair in P. there exists a point x, not necessarily in P, that is enclosed by Ω(m2/(n2 log6 n2/m)) of the spheres in S. Similar results apply in arbitrary fixed dimensions, and for geometric bodies other than spheres. The results have applications in reducing the size of geometric structures, such as three-dimensional Delaunay triangulations and Gabriel graphs, by adding extra points to their defining sets.

Counting triangle crossings and halving planes - Dey, Tamal; Edelsbrunner, Herbert (Discrete & Computational Geometry)
Every collection of t≥2 n2 triangles with a total of n vertices in ℝ3 has Ω(t4/n6) crossing pairs. This implies that one of their edges meets Ω(t3/n6) of the triangles. From this it follows that n points in ℝ3 have only O(n8/3) halving planes.

Brain-derived neurotrophic factor increases neurotrophin-3 expression in cerebellar granule neurons - Leingärtner, Axel; Heisenberg, Carl-Philipp J; Kolbeck, Roland; Thoenen, Hans; Lindholm, Dan (Journal of Biological Chemistry)
Neurotrophin-3 (NT-3) is a member of the neurotrophin gene family and is highly expressed in the developing rat cerebellum. Here we show that brain-derived neurotrophic factor (BDNF) increased by approximately 10-fold the NT-3 mRNA levels in cultured cerebellar granule neurons isolated from postnatal rats, whereas nerve growth factor (NGF) and NT-3 itself had no effect. The effect of BDNF was additive to that of triiodothyronine (T3), which also increased NT-3 mRNA in these neurons. The drug K252a inhibited the BDNF-mediated stimulation of NT-3 expression, suggesting an involvement of trkB receptors. Nuclear run-on experiments showed that BDNF enhanced NT-3 transcription, whereas the stability of NT-3 mRNA remained unchanged. The data presented are the first demonstration that one neurotrophin regulates the expression of another and provide evidence that NT-3 production in granule neurons is regulated by both BDNF and T3.

NMDA potentiates NGF-induced sprouting of septal cholinergic fibres - Heisenberg, Carl-Philipp J; Cooper, John; Berke, J; Sofroniew, Michael (Neuroreport)
NERVE growth factor (NGF) injected into the otherwise unlesioned adult rat septum induced sprouting of presumptive cholinergic fibres positive for p75(NGFR) and acetylcholinesterase (AChE). These fibres did not stain for tyrosine hydroxylase and therefore did not represent sympathetic ingrowth. Neurofilament staining on adjacent sections revealed fibres with similar morphology, suggesting new outgrowth in the form of sprouting rather than the upregulation of p75(NGFR) and AChE in pre-existing fibres. Simultaneous injections of subneurotoxic doses of N-methyl-D-aspartate (NMDA) significantly potentiated the effect of NGF on cholinergic fibre sprouting and caused pronounced glial fibrillary acidic protein (GFAP)positive astrocytosis. Application of NMDA alone did not elicit sprouting of this type. These findings indicate that NGF can induce the sprouting of uninjured adult rat septal cholinergic fibres in vivo and suggest that reactive astrocytes are not inhibitory to cholinergic axonal outgrowth, and might serve as a substrate for growing axons in the presence of NGF.

Proving safety properties of hybrid systems - Kapur, Arjun; Henzinger, Thomas A; Manna, Zohar; Pnueli, Amir (3rd International Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems)
We propose a methodology for the specification, verification, and design of hybrid systems. The methodology consists of the computational model of Concrete Phase Transition Systems (cptss), the specification language of Hybrid Temporal Logic (htl), the graphical system description language of Hybrid Automata, and a proof system for verifying that hybrid automata satisfy their HTL specifications. The novelty of the approach lies in the continuous-time logic, which allows specification of both point-based and interval-based properties (i.e., properties which describe changes over an interval) and provides direct references to derivatives of variables, and in the proof system that supports verification of point-based and interval-based properties. The proof rules demonstrate that sound and convenient induction rules can be established for continuous-time logics. The proof rules are illustrated on several examples.

Verification methods for the divergent runs of clock systems - Henzinger, Thomas A; Kopke, Peter (3rd International Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems)
We present a methodology for proving temporal properties of the divergent runs of reactive systems with real-valued clocks. A run diverges if time advances beyond any bound. Since the divergent runs of a system may satisfy liveness properties that are not satisfied by some convergent runs, the standard proof rules are incomplete if only divergent runs are considered. First, we develop a sound and complete proof calculus for divergence, which is based on translating clock systems into discrete systems. Then, we show that simpler proofs can be obtained for stronger divergence assumptions, such as unknown -divergence, which requires that all delays have a minimum duration of some unknown constant . We classify all real-time systems into an infinite hierarchy, according to how well they admit the translation of eventuality properties into equivalent safety properties.

Temporal proof methodologies for timed transition systems - Henzinger, Thomas A; Manna, Zohar; Pnueli, Amir (Information and Computation)
We extend the specification language of temporal logic, the corresponding verification framework, and the underlying computational model to deal with real-;time properties of reactive systems. The abstract notion of timed transition systems generalizes traditional transition systems conservatively: qualitative fairness requirements are replaced (and superseded) by quantitative lower-bound and upper-bound timing constraints on transitions. This framework can model real-time systems that communicate either through shared variables or by message passing and real-time issues such as timeouts, process priorities (interrupts), and process scheduling. We exhibit two styles for the specification of real-time systems. While the first approach uses time-bounded versions of the temporal operators, the second approach allows explicit references to time through a special clock variable. Corresponding to the two styles of specification, we present and compare two different proof methodologies for the verification of timing requirements that are expressed in these styles. For the bounded-operator style, we provide a set of proof rules for establishing bounded-invariance and bounded-responce properties of timed transition systems. This approach generalizes the standard temporal proof rules for verifying invariance and response properties conservatively. For the explicit-clock style, we exploit the observation that every time-bounded property is a safety property and use the standard temporal proof rules for establishing safety properties.

Symbolic model checking for real-time systems - Henzinger, Thomas A; Nicollin, Xavier; Sifakis, Joseph; Yovine, Sergio (Information and Computation)
We describe finite-state programs over real-numbered time in a guarded-command language with real-valued clocks or, equivalently, as finite automata with real-valued clocks. Model checking answers the question which states of a real-time program satisfy a branching-time specification (given in an extension of CTL with clock variables). We develop an algorithm that computes this set of states symbolically as a fixpoint of a functional on state predicates, without constructing the state space. For this purpose, we introduce a μ-calculus on computation trees over real-numbered time. Unfortunately, many standard program properties, such as response for all nonzeno execution sequences (during which time diverges), cannot be characterized by fixpoints: we show that the expressiveness of the timed μ-calculus is incomparable to the expressiveness of timed CTL. Fortunately, this result does not impair the symbolic verification of "implementable" real-time programs-those whose safety constraints are machine-closed with respect to diverging time and whose fairness constraints are restricted to finite upper bounds on clock values. All timed CTL properties of such programs are shown to be computable as finitely approximable fixpoints in a simple decidable theory.

Finitary fairness - Alur, Rajeev; Henzinger, Thomas A (Proceedings 9th Annual IEEE Symposium on Logic in Computer Science)
Fairness is a mathematical abstraction: in a multiprogramming environment, fairness abstracts the details of admissible (“fair”) schedulers; in a distributed environment, fairness abstracts the speeds of independent processors. We argue that the standard definition of fairness often is unnecessarily weak and can be replaced by the stronger, yet still abstract, notion of finitary fairness. While standard weak fairness requires that no enabled transition is postponed forever, finitary weak fairness requires that for every run of a system there is an unknown bound k such that no enabled transition is postponed more than k consecutive times. In general, the finitary restriction fin(F) of any given fairness assumption F is the union of all w-regular safety properties that are contained in F. The adequacy of the proposed abstraction is demonstrated in two ways. Suppose that we prove a program property under the assumption of finitary fairness. In a multiprogramming environment, the program then satisfies the property for all fair finite-state schedulers. In a distributed environment, the program then satisfies the property for all choices of lower and upper bounds on the speeds (or timings) of processors

Real-time system = discrete system + clock variables - Alur, Rajeev; Henzinger, Thomas A (Theories and Experiences for Real-Time System Development)
We introduce a temporal logic for the specification of real-time systems. Our logic, TPTL, employs a novel quantifier construct for referencing time: the "freeze" quantifier binds a variable to the time of the local temporal context. TPTL is both a natural language for specification and a suitable formalism for verification. We present a tableau-based decision procedure and a model-checking algorithm for TPTL. Several generalizations of TPTL are shown to be highly undecidable.
Keywords: real-time systems; clock variables

A really temporal logic - Alur, Rajeev; Henzinger, Thomas A (Journal of the ACM)
We introduce a temporal logic for the specification of real-time systems. Our logic, TPTL, employs a novel quantifier construct for referencing time: the freeze quantifier binds a variable to the time of the local temporal context. TPTL is both a natural language for specification and a suitable formalism for verification. We present a tableau-based decision procedure and a model-checking algorithm for TPTL. Several generalizations of TPTL are shown to be highly undecidable.

The observational power of clocks - Alur, Rajeev; Courcoubetis, Costas; Henzinger, Thomas A (5th International Conference on Concurrency Theory)
We develop a theory of equivalences for timed systems. Two systems are equivalent iff external observers cannot observe differences in their behavior. The notion of equivalence depends, therefore, on the distinguishing power of the observers. The power of an observer to measure time results in untimed, clock, and timed equivalences: an untimed observer cannot measure the time difference between events; a clock observer uses a clock to measure time differences with finite precision; a timed observer is able to measure time differences with arbitrary precision. We show that the distinguishing power of clock observers grows with the number of observers, and approaches, in the limit, the distinguishing power of a timed observer. More precisely, given any equivalence for untimed systems, two timed systems are k-clock congruent, for a nonnegative integer k, iff their compositions with every environment that uses k clocks are untimed equivalent. Both k-clock bisimulation congruence and k-clock trace congruence form strict decidable hierarchies that converge towards the corresponding timed equivalences. Moreover, k-clock bisimulation congruence and k-clock trace congruence provide an adequate and abstract semantics for branching-time and linear-time logics with k clocks. Our results impact on the verification of timed systems in two ways. First, our decision procedure for k-clock bisimulation congruence leads to a new, symbolic, decision procedure for timed bisimilarity. Second, timed trace equivalence is known to be undecidable. If the number of environment clocks is bounded, however, then our decision procedure for k-clock trace congruence allows the verification of timed systems in a trace model.

A determinizable class of timed automata - Alur, Rajeev; Fix, Limor; Henzinger, Thomas A (International Conference on Computer Aided Verification)
We introduce the class of event- recording timed automata (ERA). An event-recording automaton contains, for every event a, a clock that records the time of the last occurrence of a. The class ERA is, on one hand, expressive enough to model (finite) timed transition systems and, on the other hand, determinizable and closed under all boolean operations. As a result, the language inclusion problem is decidable for event-recording automata. We present a translation from timed transition systems to event-recording automata, which leads to an algorithm for checking if two timed transition systems have the same set of timed behaviors. We also consider event-predicting timed automata (EPA), which contain clocks that predict the time of the next occurrence of an event. The class of event-clock automata (ECA), which contain both event-recording and event-predicting clocks, is a suitable specification language for real-time properties. We provide an algorithm for checking if a timed automaton meets a specification that is given as an event-clock automaton.

The algorithmic analysis of hybrid systems - Alur, Rajeev; Courcoubetis, Costas; Henzinger, Thomas A; Ho, Pei; Nicollin, Xavier; Olivero, Alfredo; Sifakis, Joseph; Yovine, Sergio (11th International Conference on Analysis and Optimization of Systems Discrete Event Systems)
We extend the timed-automaton model for real-time systems [AD90] to a formal model for hybrid systems: while the continuous variables of a timed automaton are clocks that measure time, the continuous variables of a hybrid system are governed by arbitrary differential equations. We then adopt the verification methodology for timed automata [ACD90, ACD+92, HNSY92] to analyze hybrid systems: while the verification problem is decidable for timed automata, we obtain semidecision procedures for the class of hybrid systems whose continuous variables change in a piecewise linear fashion.

Regulatory rearrangements and smg-sensitive allels of the C. elegans sex-determining gene tra-1 - Zarkower, David; de Bono, Mario; Aronoff, Rachel; Hodgkin, Jonathan (Developmental Genetics)
The tra-1 gene is the terminal regulator in the sex determination pathway in C. elegans, directing all aspects of somatic sexual differentiation. Recessive loss-of-function (lf) mutations in tra-1 masculinize XX animals (normally somatically female), while dominant gain-of-function mutations feminize XO animals (normally male). Most tra-1 (lf) mutations can be fitted into a simple allelic series of somatic masculinization, but a small number of lf alleles do not fit into this series. Here we show that three of these mutations are associated with DNA rearrangements 5' to the coding region. One allele is an inversion that may be subject to a position effect. We also report the isolation of a new class of tra-1 alleles that are responsive to mutations in the smg system of RNA surveillance. We show that two of these express RNAs of aberrant size. We suggest that the smg-sensitive mutations may identify a carboxy-terminal domain required for negative regulation of tra-1 activity.