TY - JOUR AB - We present an algorithm for maintaining the biconnected components of a graph during a sequence of edge insertions and deletions. It requires linear storage and preprocessing time. The amortized running time for insertions and for deletions isO(m 2/3 ), wherem is the number of edges in the graph. Any query of the form ‘Are the verticesu andv biconnected?’ can be answered in timeO(1). This is the first sublinear algorithm for this problem. We can also output all articulation points separating any two vertices efficiently. If the input is a plane graph, the amortized running time for insertions and deletions drops toO(√n logn) and the query time isO(log2 n), wheren is the number of vertices in the graph. The best previously known solution takes timeO(n 2/3 ) per update or query. AU - Henzinger, Monika H ID - 11677 IS - 6 JF - Algorithmica SN - 0178-4617 TI - Fully dynamic biconnectivity in graphs VL - 13 ER - TY - CONF AB - This paper presents an algorithm for the fully dynamic biconnectivity problem whose running time is exponentially faster than all previously known solutions. It is the first dynamic algorithm that answers biconnectivity queries in time O(log/sup 2/n) in a n-node graph and can be updated after an edge insertion or deletion in polylogarithmic time. Our algorithm is a Las-Vegas style randomized algorithm with the update time amortized update time O(log/sup 4/n). Only recently the best deterministic result for this problem was improved to O(/spl radic/nlog/sup 2/n). We also give the first fully dynamic and a novel deletions-only transitive closure (i.e. directed connectivity) algorithms. These are randomized Monte Carlo algorithms. Let n be the number of nodes in the graph and let m/spl circ/ be the average number of edges in the graph during the whole update sequence: The fully dynamic algorithms achieve (1) query time O(n/logn) and update time O(m/spl circ//spl radic/nlog/sup 2/n+n); or (2) query time O(n/logn) and update time O(nm/spl circ//sup /spl mu/-1/)log/sup 2/n=O(nm/spl circ//sup 0.58/log/sup 2/n), where /spl mu/ is the exponent for boolean matrix multiplication (currently /spl mu/=2.38). The deletions-only algorithm answers queries in time O(n/logn). Its amortized update time is O(nlog/sup 2/n). AU - Henzinger, Monika H AU - King, V. ID - 11684 SN - 0272-5428 T2 - Proceedings of IEEE 36th Annual Foundations of Computer Science TI - Fully dynamic biconnectivity and transitive closure ER - TY - CONF AB - This paper presents insertions-only algorithms for maintaining the exact and approximate size of the minimum edge cut and the minimum vertex cut of a graph. The algorithms output the approximate or exact size k in time O(1) or O(log n) and a cut of size k in time linear in its size. The amortized time per insertion is O(1/ε 2) for a (2+ε)-approximation, O((log λ)((log n)/ε)2) for a (1+ε)-approximation, and O(λ log n) for the exact size of the minimum edge cut, where n is the number of nodes in the graph, λ is the size of the minimum cut and ε>0. The (2+ε)-approximation algorithm and the exact algorithm are deterministic, the (1+ε)-approximation algorithm is randomized. The algorithms are optimal in the sense that the time needed for m insertions matches the time needed by the best static algorithm on a m-edge graph. We also present a static 2-approximation algorithm for the size κ of the minimum vertex cut in a graph, which takes time O(n 2 min(√n,κ)). This is a factor of κ faster than the best algorithm for computing the exact size, which takes time O(κ 2 n 2 +κ 3 n 1.5). We give an insertionsonly algorithm for maintaining a (2+ε)-approximation of the minimum vertex cut with amortized insertion time O(n(logκk)/ε). AU - Henzinger, Monika H ID - 11806 SN - 0302-9743 T2 - 22nd International Colloquium on Automata, Languages and Programming TI - Approximating minimum cuts under insertions VL - 944 ER - TY - CONF AB - In this paper, we present sparse certificates for biconnectivity together with algorithms for updating these certificates. We thus obtain fully-dynamic algorithms for biconnectivity in graphs that run in O(√n log n log⌈m/n⌉) amortized time per operation, where m is the number of edges and n is the number of nodes in the graph. This improves upon the results in [11], in which algorithms were presented running in O(√m) amortized time, and solves the open problem to find certificates to speed up biconnectivity, as stated in [2]. AU - Henzinger, Monika H AU - Poutré, Han ID - 11805 SN - 0302-9743 T2 - 3rd Annual European Symposium on Algorithms TI - Certificates and fast algorithms for biconnectivity in fully-dynamic graphs VL - 979 ER - TY - CONF AB - We present a model with restricted randomness for edge updates in dynamic graph algorithms and a general technique for analyzing the expected running time of an update operation. This model is able to capture the average case in many applications, since (1) it allows restrictions on the set of edges which can be used for insertions and (2) the type (insertion or deletion) of each update operation is arbitrary, i.e., not random. We use our technique to analyze existing and new dynamic algorithms for maximum cardinality matching, minimum spanning forest, connectivity, 2-edge connectivity, k-edge connectivity, k-vertex connectivity, and bipartiteness. Given a random graph G with mo edges and n vertices and a sequence of 1 update operations such that the graph contains rni edges after operation i, the expected time for performing the updates for any 1 is O(1 logn + n xi=, l/fii) in the case of minimum spanning forests, connectivity, 2- edge connectivity, and bipartiteness. The expected time per update operation is O(n) in the case of maximum matching. For k-edge and k-vertex connectivity we also give improved bounds. Additionally we give an insertions-only algorithm for maximum cardinality matching with worst-case O(n) amortized time per insertion. AU - Alberts, David AU - Henzinger, Monika H ID - 11928 SN - 0898713498 T2 - 6th Annual ACM-SIAM Symposium on Discrete Algorithms TI - Average case analysis of dynamic graph algorithms ER - TY - JOUR AB - Transhydrogenase from beef-heart mitochondria was solubilised with Triton X-100 and purified by column chromatography. The detergent-dispersed enzyme catalysed the reduction of acetylpyridine adenine dinucleotide (AcPdAD+) by NADH, but only in the presence of NADP+. Experiments showed that this reaction was cyclic; NADP(H), whilst remaining bound to the enzyme, was alternately reduced by NADH and oxidised by AcPdAD+. A period of incubation of the enzyme with NADPH at pH 6.0 led to inhibition of the simple transhydrogenation reaction between AcPdAD+ and NADPH. However, after such treatment, transhydrogenase acquired the ability to catalyse the (NADPH-dependent) reduction of AcPdAD+ by NADH. It is suggested that this is a similar cycle to the one described above. Evidently, the binding affinity for NADP+ increases as a consequence of the inhibition process resulting from prolonged incubation with NADPH. The pH dependences of simple and cyclic transhydrogenation reactions are described. Though more complex than those in Escherichia coli transhydrogenase, they are consistent with the view [Hutton, M., Day, J.M., Bizouarn, T. and Jackson, J.B. (1994) Eur. J. Biochem. 219, 1041–10511] that, also in the mitochondrial enzyme, binding the release of NADP+ and NADP are accompanied by binding and release of a proton. The enzyme was successfully reconstituted into liposomes by a cholate dilution procedure. The proteoliposomes catalysed cyclic NADPH-dependent reduction of AcPdAD+ by NADH only when they were tightly coupled. However, they catalysed cyclic NADP+-dependent reduction of AcPdAD+ by NADH only when they were uncoupled eg. by addition of carbonylcyanide-p-trifluoromethoxyphenyl hydrazone. These observations are evidence that the proton binding and release which accompany NADP+ binding and release, respectively, take place on the inside of the vesicle, and that they are components of the electrogenic processes of the enzyme. AU - Sazanov, Leonid A AU - Jackson, Baz ID - 1943 IS - 3 JF - Biochimica et Biophysica Acta - Bioenergetics SN - 0005-2728 TI - Cyclic reactions catalysed by detergent-dispersed and reconstituted transhydrogenase from beef heart mitochondria; implications for the mechanism of proton translocation VL - 1231 ER - TY - CHAP AB - Auxins play a crucial role in the regulation of spatial and temporal aspects of plant growth and development1. As well as being required for the division, enlargement and differentiation of individual plant cells, auxins also function as signals between cells, tissues and organs. In this way they contribute to the coordination and integration of growth and development in the whole plant and to physiological responses of plants to environmental cues (63). At the individual cell level, fast changes or pulses in hormone concentration may function to initiate or to terminate a developmental process. In contrast, the maintenance of a stable concentration of the hormone (homeostasis) may be necessary to maintain the progress of a developmental event that has already been initiated. AU - Morris, David AU - Friml, Jirí AU - Zažímalová, Eva ED - Davies, Peter ID - 2465 SN - 978-1-4020-2684-3 T2 - Plant Hormones: Biosynthesis, Signal Transduction, Action! TI - Auxin transport ER - TY - JOUR AB - The distribution of mRNAs for metabotropic glutamate receptors, mGluR4 and mGluR7, which are highly sensitive for L-2-amino-4-phosphonobutyrate (L- AP4), was examined in the central nervous system of the rat by in situ hybridization. In general, the hybridization signals of mGluR7 mRNA were more widely distributed than those of mGluR4 mRNA, and differential expression of mGluR4 mRNA and mGluR7 mRNA was clearly indicated in some brain regions. Intense or moderate expression of mGluR4 mRNA was detected in the granule cells of the olfactory bulb and cerebellum, whereas no significant expression of mGluR7 mRNA was found in these cells. In other neurons or regions where mGluR7 mRNA was intensely or moderately expressed, no significant expression of mGluR4 mRNA was observed. Such were the mitral and tufted cells of the olfactory bulb; anterior olfactory nucleus; neocortical regions; cingulate cortex; retrosplenial cortex; piriform cortex; perirhinal cortex; CA1; CA3; granule cells of the dentate gyrus; superficial layers of the subicular cortex; deep layers of the entorhinal, parasubicular, and presubicular cortices; ventral part of the lateral septal nucleus; septohippocampal nucleus; triangular septal nucleus; nuclei of the diagonal band; bed nucleus of the stria terminalis; ventral pallidum; claustrum; amygdaloid nuclei other than the intercalated nuclei; preoptic region; hypothalamic nuclei other than the medial mammillary nucleus; ventral lateral geniculate nucleus; locus coeruleus; Purkinje cells; many nuclei of the lower brainstem other than the superior colliculus, periaqueductal gray, interpeduncular nucleus, pontine nuclei, and dorsal cochlear nucleus; and dorsal horn of the spinal cord. Both mGluR4 mRNA and mGluR7 mRNA were moderately or intensely expressed in the olfactory tubercle, superficial layers of the entorhinal cortex, CA4, septofimbrial nucleus, intercalated nuclei of the amygdala, medial mammillary nucleus, many thalamic nuclei, and pontine nuclei. Intense expression of both mGluR4 mRNA and mGluR7 mRNA was further detected in the trigeminal ganglion and dorsal root ganglia, whereas no significant expression of them was found in the pterygopalatine ganglion and superior cervical ganglion. The results indicate differential roles of the L-AP4-sensitive metabotropic glutamate receptors in the glutamatergic nervous system. AU - Ohishi, Hitoshi AU - Akazawa, Chihiro AU - Shigemoto, Ryuichi AU - Nakanishi, Shigetada AU - Mizuno, Noboru ID - 2491 IS - 4 JF - Journal of Comparative Neurology SN - 0021-9967 TI - Distributions of the mRNAs for L-2-amino-4-phosphonobutyrate-sensitive metabotropic glutamate receptors, mGluR4 and mGluR7, in the rat brain VL - 360 ER - TY - JOUR AB - Taking advantage of the restricted expression of metabotropic glutamate receptor subtype 6 (mGIuR6) in retinal ON bipolar cells, we generated knockout mice lacking mGIuR6 expression. The homozygous mutant mice showed a loss of ON responses but unchanged OFF responses to light. The mutant mice displayed no obvious changes in retinal cell organization nor in the projection of optic fibers to the brain. Furthermore, the mGIuR6-deficient mice showed visual behavioral responses to light stimulation as examined by shuttle box avoidance behavior experiments using light exposure as a conditioned stimulus. The results demonstrate that mGIuR6 is essential in synaptic transmission to the ON bipolar cell and that the OFF response provides an important means for transmitting visual information. AU - Masu, Masayuki AU - Iwakabe, Hideki AU - Tagawa, Yoshiaki AU - Miyoshi, Tomomitsu AU - Yamashita, Masayuki AU - Fukuda, Yutaka AU - Sasaki, Hitoshi AU - Hiroi, Kano AU - Nakamura, Yasuhisa AU - Shigemoto, Ryuichi AU - Takada, Masahiko AU - Nakamura, Kenji AU - Nakao, Kazuki AU - Katsuki, Motoya AU - Nakanishi, Shigetada ID - 2559 IS - 5 JF - Cell SN - 0092-8674 TI - Specific deficit of the ON response in visual transmission by targeted disruption of the mGIuR6 gene VL - 80 ER - TY - JOUR AB - Brain areas involved in the genesis and control of daily rhythms receive a prominent neural input that contains the neurotransmitter substance P (SP), a peptide putatively involved in the synchronization of circadian rhythms by environmental light. We investigated the localization of receptors to SP in the suprachiasmatic nucleus of the hypothalamus (SCN) and in the intergeniculate leaflet of the thalamus (IGL) of the rat and hamster using in situ hybridization histochemistry and immunohistochemistry. Consistently with that previously described in the rat, a neuronal population distributed along the lateral margin and at the dorso-latero-caudal aspect of the hamster SCN expresses moderately the mRNA encoding the SP receptor. In both rat and hamster, immunohistochemical data confirm the previous finding and reveal an almost complete absence of SP receptors in the ventral part of the SCN, which receives a direct projection from the retina. In the IGL of both species, numerous neurons prominently express the mRNA encoding the SP receptor. The immunostaining shows a high density of SP receptors on perikarya and dendrites throughout the nucleus. A dense staining is also observed on individual cells and processes bordering the lumen of blood vessels in the SCN and IGL. AU - Mick, Gérard AU - Shigemoto, Ryuichi AU - Kitahama, Kunio ID - 2558 IS - 2 JF - Comptes Rendus de l'Academie des Sciences - Series III SN - 0764-4469 TI - Localization of substance P receptors in central neural structures controlling daily rhythms in nocturnal rodents VL - 318 ER - TY - JOUR AB - An antibody which recognizes specifically a metabotropic glutamate receptor, mGluR7, was produced by using a trpE fusion protein containing a C-terminal sequence of rat mGluR7. Neuropil in laminae I and II of the dorsal horn of the rat, as well as many neuronal cell bodies in the dorsal root ganglion, showed mGluR7-like immunoreactivity; the immunoreactivity in neuropil was seen in axon terminals, which were filled with round synaptic vesicles and constituted axodendritic and axosomatic asymmetric synapses. The mGluR7-like immunoreactivity in laminae I and II in the dorsal horn was reduced after dorsal rhizotomy. The results indicate that some axon terminals of the primary afferent fibers to laminae I and II of the dorsal horn are provided with mGluR7. AU - Ohishi, Hitoshi AU - Nomura, Sakashi AU - Ding, Yu AU - Shigemoto, Ryuichi AU - Wada, Eiki AU - Kinoshita, Ayae AU - Li, Jin AU - Neki, Akio AU - Nakanishi, Shigetada AU - Mizuno, Noboru ID - 2561 IS - 1-2 JF - Neuroscience Letters SN - 0304-3940 TI - Presynaptic localization of a metabotropic glutamate receptor, mGluR7, in the primary afferent neurons: An immunohistochemical study in the rat VL - 202 ER - TY - JOUR AB - Chemical irritation of the urinary bladder with formalin in the rat induced c-fos protein-like immunoreactivity in more than 80% of substance P receptor-like immunoreactive (SPR-LI) neurons of the dorsal commissural nucleus, sacral parasympathetic nucleus and lamina I in the 6th lumbar and 1st sacral cord segments. These neurons with SPR-LI may receive noxious information from the urinary bladder through the primary afferent fibers with substance P. AU - Lü, Yan AU - Jin, Shan AU - Xu, Tian AU - Qin, Bing AU - Li, Ji AU - Ding, Yu AU - Shigemoto, Ryuichi AU - Mizuno, Noboru ID - 2560 IS - 2 JF - Neuroscience Letters SN - 0304-3940 TI - Expression of c-fos protein in substance P receptor-like immunoreactive neurons in response to noxious stimuli on the urinary bladder: an observation in the lumbosacral cord segments of the rat VL - 198 ER - TY - JOUR AB - By using substance P receptor (SPR) immunofluorescence histochemistry combined with fluorescent retrograde labeling, SPR-like immunoreactive (SPR-LI) neurons sending their axons to the lateral parabrachial region were observed in the lumbar spinal cord of the rat. After injection of Fluoro-Gold into the lateral parabrachial region, retrogradely labeled neurons with SPR-LI were seen frequently in lamina I and the lateral spinal nucleus, and occasionally in laminae IV and V, with a predominantly contralateral distribution. Some of these neurons, especially those in lamina I, may convey nociceptive information to the lateral parabrachial region. AU - Ding, Yu AU - Takada, Masahiko AU - Shigemoto, Ryuichi AU - Mizuno, Noboru ID - 2556 IS - 2 JF - Brain Research SN - 0006-8993 TI - Spinoparabrachial tract neurons showing substance P receptor-like immunoreactivity in the lumbar spinal cord of the rat VL - 674 ER - TY - JOUR AB - By means of substance P receptor (SPR) immunofluorescence histochemistry combined with Fluoro-Gold fluorescent retrograde labeling, SPR-like immunoreactive neurons in the caudal subnucleus of the spinal trigeminal nucleus of the rat were observed to send their axons to the nucleus of Kolliker-Fuse and ventrolateral part of the lateral parabrachial nucleus bilaterally with a clear ipsilateral dominance. These neurons were distributed mainly in lamina I, and additionally in lamina III. AU - Ding, Yu AU - Takada, Masahiko AU - Shigemoto, Ryuichi AU - Mizuno, Noboru ID - 2563 IS - 4 JF - Neuroscience Research SN - 0168-0102 TI - Trigeminoparabrachial projection neurons showing substance P receptor-like immunoreactivity in the rat VL - 23 ER - TY - CONF AB - We study the generalizations of the well-known Lieb-Thirring inequality for the magnetic Schrödinger operator with a nonconstant magnetic field. We use stochastic methods to prove estimates on the moments of the negative eigenvalues. AU - Erdös, László ID - 2712 TI - Magnetic Lieb-Thirring inequalities and stochastic oscillatory integrals VL - 78 ER - TY - JOUR AB - We study the generalizations of the well-known Lieb-Thirring inequality for the magnetic Schrödinger operator with nonconstant magnetic field. Our main result is the naturally expected magnetic Lieb-Thirring estimate on the moments of the negative eigenvalues for a certain class of magnetic fields (including even some unbounded ones). We develop a localization technique in path space of the stochastic Feynman-Kac representation of the heat kernel which effectively estimates the oscillatory effect due to the magnetic phase factor. AU - Erdös, László ID - 2724 IS - 3 JF - Communications in Mathematical Physics SN - 0010-3616 TI - Magnetic Lieb-Thirring inequalities VL - 170 ER - TY - CHAP AB - The study of gene expression and regulation in the central nervous system (CNS) is a daunting task because of the diversity of neuronal phenotypes and the complexity of many protein classes. Molecular cloning revealed the presence of a large number of different protein families in the CNS, each comprising several members. Ligand-gated ion channels may serve as an example to illustrate this point (for review, see Unwin, 1993). Heterologous expression combined with electrophysiological analysis suggests that ligand-gated channels are multimeric proteins with functional properties depending on the subunit composition. Very little is known, however, about how the functional properties of the recombinant and native receptors relate to each other. Thus, it is of eminent importance to elucidate the subunit expression profile in different types of neurons in the CNS and to correlate this with the functional properties of the native receptors. AU - Monyer, Hannah AU - Jonas, Peter M ED - Sakmann, Bert ED - Neher, Erwin ID - 3454 SN - 978-0-306-44870-6 T2 - Single-channel recording TI - Polymerase chain reaction analysis of ion channel expression in single neurons of brain slices ER - TY - CHAP AB - At a synapse, the transmitter is stored in synaptic vesicles and is released into the synaptic cleft almost instantaneously upon fusion of these vesicles with the presynaptic membrane. Subsequently, the transmitter diffuses to ligand-gated ion channels in the postsynaptic density, binds to them, and thereby causes channel activation. Unfortunately, we have estimates neither of the exact amount of transmitter in the synaptic vesicle nor of the concentration in the synaptic cleft reaching the postsynaptic receptors, and in some cases even the identity of the transmitter is unknown. These questions may be addressed by modeling of release and diffusion. Such a theoretical approach, however, is based on several assumptions, some of which lack experimental evidence. AU - Jonas, Peter M ED - Sakmann, Bert ED - Neher, Erwin ID - 3455 SN - 978-0-306-44870-6 T2 - Single-channel recording TI - Fast application of agonists to isolated membrane patches ER - TY - JOUR AU - Jonas, Peter M AU - Burnashev, Nail ID - 3461 IS - 5 JF - Neuron SN - 0896-6273 TI - Molecular mechanisms controlling calcium entry through AMPA-type glutamate receptor channels VL - 15 ER - TY - JOUR AB - 1. Properties of dendritic glutamate receptor (GluR) channels were investigated using fast application of glutamate to outside-out membrane patches isolated from the apical dendrites of CA3 and CA1 pyramidal neurons in rat hippocampal slices. CA3 patches were formed (15-76 μm from the soma) in the region of messy fibre (MF) synapses, and CA1 patches (25-174 μm from the soma) in the region of Schaffer collateral (SC) innervation. 2. Dual-component responses consisting of a rapidly rising and decaying component followed by a second, substantially slower, component were elicited by 1 ms pulses of 1 mM glutamate in the presence of 10 μM glycine and absence of external Mg2+. The fast component was selectively blocked by 2-5 μM 6-cyano-7-nitroquinoxaline-2,3-dione (CNQX) and the slow component by 30 μM D-2-amino-5-phosphonopentanoic acid (D-AP5), suggesting that the fast and slow components were mediated by the GluR channels of the L-α-amino-3-hydroxy-5-methyl-4-isoxazolepropionate (AMPA) and NMDA type, respectively. The peak amplitude ratio of the NMDA to AMPA receptor-mediated components varied between 0.03 and 0.62 in patches from both CA3 and CA1 dendrites. Patches lacking either component were rarely observed. 3. The peak current-voltage (I-V) relationship of the fast component was almost linear, whereas the I-V relationship of the slow component showed a region of negative slope in the presence of 1 mM external Mg2+. The reversal potential for both components was close to 0 mV. 4. Kainate-preferring GluR channels did not contribute appreciably to the response to glutamate. The responses to 100 ms pulses of 1 mM glutamate were mimicked by application of 1 mM AMPA, whereas 1 mM kainate produced much smaller, weakly desensitizing currents. This suggests that the fast component is primarily mediated by the action of glutamate on AMPA-preferring receptors. 5. The mean elementary conductance of AMPA receptor channels was about 10 pS, as estimated by non-stationary fluctuation analysis. The permeability of these channels to Ca2+ was low (~5% of the permeability to Cs+). 6. The elementary conductance of NMDA receptor channels was larger, with a main conductance state of about 45 pS. These channels were 3.6 times more permeable to Ca2+ than to Cs+. 7. AMPA receptor-mediated currents activated rapidly in response to 1 ms pulses of 1 mM glutamate and deactivated with a predominant, fast time constant and a smaller, slower component (τ1≃2 ms, τ2≃8 ms, contributing ~80 and ~20% to the total decay amplitude, respectively). Desensitization of the current during a 100 ms pulse was best fitted by two time constants (τ1≃10 ms, ~60%; τ2≃34 ms, ~40%). 8. NMDA receptor-mediated currents in response to 1 ms pulses of 1 mM glutamate activated and deactivated much more slowly than AMPA receptor-mediated currents. The time course could be described by a single exponential rising phase (τ≃7 ms) followed by a double exponential decay (τ1≃200 ms, ~80%; τ2≃1-3 s, ~20%). 9. Mg2+ blocked the NMDA component in a voltage-dependent manner, with a half-maximal inhibitory concentration (IC50) of 21 μM at -80 mV. At physiological Mg2+ concentrations, block of the NMDA component could be rapidly relieved with voltage jumps from negative to positive potentials. Block of the current upon return to negative potentials occurred almost instantaneously. 10. Zn2+ also selectively-blocked the NMDA receptor-mediated current with an IC50 of 22 μM, but this block differed from that of Mg2+ in that it showed little voltage dependence. Rapid application of Zn2+ together with glutamate produced partial block of the current. More block was observed if Zn2+ and glutamate were co-applied when NMDA receptor channels were already open. 11. The functional properties of dendritic GluRs were similar to those found at the soma. Knowledge of these properties facilitated simulations investigating the contribution of coactivated AMPA and NMDA receptors to synaptic depolarization and Ca2+ entry into dendritic spines. Because of its slow deactivation, the NMDA receptor-mediated current contributes substantially to depolarization and Ca2+ entry and is susceptible to modulation over a period of seconds, either by backpropagating action potentials or by the release of Zn2+ from presynaptic boutons. AU - Spruston, Nelson AU - Jonas, Peter M AU - Sakmann, Bert ID - 3478 IS - Pt 2 JF - Journal of Physiology SN - 0022-3751 TI - Dendritic glutamate receptor channels in rat hippocampal CA3 and CA1 pyramidal neurons VL - 482 ER - TY - CONF AB - Common geometric models for proteins and other molecules are the space filling diagram, the solvent accessible surface, and the molecular surface. We describe software that computes metric properties of these models, including volume and surface area. It also measures voids or empty space enclosed by the protein, and it keeps track of surface area contributions of individual atoms. The software is based on 3-dimensional alpha complexes and on inclusion-exclusion formulas with terms derived from the simplices in this complex. AU - Edelsbrunner, Herbert AU - Facello, Michael AU - Fu, Ping AU - Liang, Jie ID - 3551 SN - 0-8186-6930-6 T2 - Proceedings of the 28th Annual Hawaii International Conference on System Sciences TI - Measuring proteins and voids in proteins ER - TY - CONF AB - The concept of an α-shape of a finite set of points in R^d, with weights, is defined and illustrated. An α-shape is a polytope which is not necessarily convex nor connected and can be derived from the (weighted) Delaunay triangulation of the point set, with a parameter controlling the desired level of detail. The set of all α values leads to a descrete family of shapes capturing the intuitive notion of ``crude'' versus ``fine'' shapes of a point set. Software that computes such shapes in R^2 and R^3 is available via anonymous ftp from: ftp://ftp.ncsa.uiuc.edu/Visualization/Alpha-shape/ AU - Akkiraju, Nataraj AU - Edelsbrunner, Herbert AU - Facello, Michael AU - Fu, Ping AU - Mücke, Ernst AU - Varela, Carlos ID - 3552 TI - Alpha shapes: definition and software ER - TY - JOUR AB - Observations on the means, variances, and covariances of quantitative traits across hybrid zones can give information similar to that from Mendelian markers. In addition, they can identify particular traits through which the cline is maintained. We describe a survey of six traits across the hybrid zone between Bombina bombina and Bombina variegata (Amphibia: Discoglossidae) near Pescenica in Croatia. We obtained laboratory measuments of the belly pattern, skin thickness, mating call, skeletal form, egg size, and the developmental time of tadpoles. Although offspring from hybrid populations showed no evidence of reduced viability, a third of the F1 families failed completely, irrespective of the direction of the cross. All traits differed significantly between the taxa. Clines in belly pattern, skin thickness, mating call, and skeletal form were closely concordant with clines in four diagnostic enzyme loci. However, the cline in developmental time was displaced towards bombina, and the cline in egg size was displaced towards variegata. This discordance could be because the traits are not inherited additively or because they are subject to different selection pressures. We favor the latter explanation in the case of developmental time. We show that moderate selection acting directly on a trait suffices to shift its position; rather stronger selection is needed to change its width appreciably. Within hybrid populations, there are significant associations among quantitative traits, and between traits and enzymes. Phenotypic variances also increase in hybrid populations. These observations can be explained by linkage disequilibria among the underlying loci. However, the average magnitude of the covariance between traits is about half that expected from the linkage disequilibria between enzyme loci. The discrepancy is not readily explained by nonadditive gene action. This puzzle is now unresolved and calls for further investigation. AU - Nürnberger, Beate AU - Barton, Nicholas H AU - Maccallum, Catriona AU - Gilchrist, Jason AU - Appleby, Michael ID - 3636 IS - 6 JF - Evolution SN - 0014-3820 TI - Natural selection on quantitative traits in the Bombina hybrid zone VL - 49 ER - TY - JOUR AB - Hybridizing taxa remain distinct for two main reasons. Natural selection acts against hybrids either because of their incompatible genome, or because of differential adaptation of the pure types across an environmental gradient. Here, we provide experimental evidence that the location of the Bombina (Anura: Discoglossidae) hybrid zone in Croatia is, at least in part, determined by differential adaptation. B. bombina typically breeds in permanent water in the lowland, whereas B. variegata reproduces in puddles at higher elevations. In a reciprocal translocation, pure bombina and variegata tadpoles were introduced in equal proportions into lowland pond enclosures and upland puddles. After three weeks, variegata exceeded bombina in survival and growth in both habitats. The effect was most pronounced in puddles, where the few surviving bombina tadpoles had hardly grown at all. In comparison to variegata, the smaller hatchlings of bombina grew relatively faster in ponds, but remained smaller in absolute terms. Nevertheless, B. bombina appears better adapted to ponds than to puddles. The mechanisms by which variegata is excluded from ponds remain to be demonstrated. These data show that habitat dependent selection prevents the invasion of bombina tadpole traits into the variegata gene pool. Given the strong linkage disequilibria in hybrid populations, differential selection on tadpoles may be sufficient to maintain the integrity of the two gene pools. AU - Maccallum, Catriona AU - Nürnberger, Beate AU - Barton, Nicholas H ID - 3637 IS - 1359 JF - Proceedings of the Royal Society of London Series B Biological Sciences SN - 0962-8452 TI - Experimental evidence for habitat dependent selection in a Bombina hybrid zone VL - 260 ER - TY - JOUR AB - A general representation of multilocus selection is extended to allow recombination to depend on genotype. The equations simplify if modifier alleles have small effects on recombination. The evolution of such modifiers only depends on how they alter recombination between the selected loci, and does not involve dominance in modifier effects. The net selection on modifiers can be found explicitly if epistasis is weak relative to recombination. This analysis shows that recombination can be favoured in two ways: because it impedes the response to epistasis which fluctuates in sign, or because it facilitates the response to directional selection. The first mechanism is implausible, because epistasis must change sign over periods of a few generations: faster or slower fluctuations favour reduced recombination. The second mechanism requires weak negative epistasis between favourable alleles, which may either be increasing, or held in check by mutation. The selection (si) on recombination modifiers depends on the reduction in additive variance of log (fitness) due to linkage disequilibria (υ1 < 0), and on non-additive variance in log (fitness) (V′2, V′3,.. epistasis between 2, 3.. loci). For unlinked loci and pairwise epistasis, si = − (υ1 + 4V2/3)δr, where δr is the average increase in recombination caused by the modifier. The approximations are checked against exact calculations for three loci, and against Charlesworth's analyses of mutation/selection balance (1990), and directional selection (1993). The analysis demonstrates a general relation between selection on recombination and observable components of fitness variation, which is open to experimental test. AU - Barton, Nicholas H ID - 3639 IS - 2 JF - Genetical Research SN - 0016-6723 TI - A general model for the evolution of recombination VL - 65 ER - TY - JOUR AB - Any sample of genes traces back to a single common ancestor. Each gene also has other properties: its sequence, its geographic location and the phenotype and fitness of the organism that carries it. With sexual reproduction, different genes have different genealogies, which gives us much more information, but also greatly complicates population genetic analysis. We review the close relation between the distribution of genealogies and the classic theory of identity by descent in spatially structured populations, and develop a simple diffusion approximation to the distribution of coalescence times in a homogeneous two-dimensional habitat. This shows that when neighbourhood size is large (as in most populations) only a small fraction of pairs of genes are closely related, and only this fraction gives information about current rates of gene flow. The increase of spatial dispersion with lineage age is thus a poor estimator of gene flow. The bulk of the genealogy depends on the long-term history of the population; we discuss ways of inferring this history from the concordance between genealogies across loci. AU - Barton, Nicholas H AU - Wilson, I ID - 3638 IS - 1327 JF - Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences SN - 0962-8436 TI - Genealogies and geography VL - 349 ER - TY - JOUR AB - Let S be a set of n points in ℝd . A set W is a weak ε-net for (convex ranges of)S if, for any T⊆S containing εn points, the convex hull of T intersects W. We show the existence of weak ε-nets of size {Mathematical expression}, where β2=0, β3=1, and βd ≈0.149·2d-1(d-1)!, improving a previous bound of Alon et al. Such a net can be computed effectively. We also consider two special cases: when S is a planar point set in convex position, we prove the existence of a net of size O((1/ε) log1.6(1/ε)). In the case where S consists of the vertices of a regular polygon, we use an argument from hyperbolic geometry to exhibit an optimal net of size O(1/ε), which improves a previous bound of Capoyleas. AU - Chazelle, Bernard AU - Edelsbrunner, Herbert AU - Grigni, Michelangelo AU - Guibas, Leonidas AU - Sharir, Micha AU - Welzl, Emo ID - 4035 IS - 1 JF - Discrete & Computational Geometry SN - 0179-5376 TI - Improved bounds on weak ε-nets for convex sets VL - 13 ER - TY - CONF AB - Any arbitrary polyhedron P contained as a subset within Rd can be written as algebraic sum of simple terms, each an integer multiple of the intersection of d or fewer half-spaces defined by facets of P. P can be non-convex and can have holes of any kind. Among the consequences of this result are a short boolean formula for P, a fast parallel algorithm for point classification, and a new proof of the Gram-Sommerville angle relation. AU - Edelsbrunner, Herbert ID - 4034 SN - 0272-5428 T2 - Proceedings of IEEE 36th Annual Foundations of Computer Science TI - Algebraic decomposition of non-convex polyhedra ER - TY - JOUR AU - Ransom, D. AU - Brownlie, Alison AU - Haffter, Pascal AU - Odenthal, Jörg AU - Kelsh, Robert AU - Brand, Michael AU - Furutani Seiki, Makoto AU - Granato, Michael AU - Hammerschmidt, Matthias AU - Heisenberg, Carl-Philipp J AU - Jiang, Yunjin AU - Kane, David AU - Mullins, Mary AU - Van Eden, Fredericus AU - Warga, Rachel AU - Nüsslein Volhard, Christiane AU - Zon, L. ID - 4153 IS - 10 JF - Blood SN - 0006-4971 TI - Hematopoietic mutants identified in a saturation screen of the zebrafish genome VL - 86 ER - TY - JOUR AB - 1. Glutamate receptor (GluR) channels were studied in basket cells in the dentate gyrus of rat hippocampal slices. Basket cells were identified by their location, dendritic morphology and high frequency of action potentials generated during sustained current injection. 2. Dual-component currents were activated by fast application of glutamate to outside-out membrane patches isolated from basket cell somata (10 μM glycine, no external Mg2+). The fast component was selectively blocked by 6-cyano-7-nitroquinoxaline-2,3-dione (CNQX), the slow component by D-2-amino-5-phosphonopentanoic acid (D-AP5). This suggests that the two components were mediated by α-amino-3-hydroxy-5-methyl-4-isoxazolepropionate receptor (AMPAR)/kainate receptor and N-methyl-D-aspartate receptor (NMDAR) channels, respectively. The mean ratio of the peak current of the NMDAR component to that of the AMPAR/kainate receptor component was 0.22 (1 ms pulses of 10 mM glutamate). 3. The AMPAR/kainate receptor component, which was studied in isolation in the presence of D-AP5, was identified as AMPAR mediated on the basis of the preferential activation by AMPA as compared with kainate, the weak desensitization of kainate-activated currents, the cross-desensitization between AMPA and kainate, and the reduction of desensitization by cyclothiazide. 4. Deactivation of basket cell AMPARs following 1 ms pulses of glutamate occurred with a time constant (τ) of 1.2 ± 0.1 ms (mean ± S.E.M.). During 100 ms glutamate pulses, AMPARs desensitized with a τ of 3.7 ± 0.2 ms. 5. The peak current-voltage (I-V) relation of AMPAR-mediated currents in Na+-rich extracellular solution showed a reversal potential of -4.0 ± 2.6 mV and was characterized by a doubly rectifying shape. The conductance of single AMPAR channels was estimated as 22.6 ± 1.6 pS using non-stationary fluctuation analysis. AMPARs expressed in hippocampal basket cells mere highly Ca2+ permeable (P(Ca)/P(K) = 1.79). 6. NMDARs in hippocampal basket cells were studied in isolation in the presence of CNQX. Deactivation of NMDARs activated by glutamate pulses occurred bi-exponentially with mean τ values of 266 ± 23 ms (76%) and 2620 ± 383 ms (24%). 7. The peak I-V relation of the NMDAR-mediated component in Na+-rich extracellular solution showed a reversal potential of 1.5 ± 0.6 mV and a region of negative slope at negative membrane potentials in the presence of external Mg2+, due to voltage-dependent block by these ions. The conductance of single NMDAR channels in the main open state was 50.2 ± 1.8 pS. NMDARs in hippocampal basket cells were highly permeable to Ca2+ (P(Ca)/P(K) = 6.68). 8. AMPARs in hippocampal basket cells are characterized by about threefold faster kinetics and twentyfold higher Ca2+ permeability than AMPARs in hippocampal granule or pyramidal cells. Simulations show that the Ca2+ influx through basket cell AMPARs is comparable to that through NMDARs at negative membrane potentials with physiological concentrations of Ca2+ and Mg2+. This suggests a dual pathway of synaptically mediated Ca2+ entry into interneurones. AU - Koh, Duk AU - Geiger, Jörg AU - Jonas, Peter M AU - Sakmann, Bert ID - 3479 IS - Pt 2 JF - Journal of Physiology SN - 0022-3751 TI - Ca(2+)-permeable AMPA and NMDA receptor channels in basket cells of rat hippocampal dentate gyrus VL - 485 ER - TY - JOUR AB - 1. The influence of intracellular factors on current rectification of different subtypes of native α-amino-3-hydroxy-5-methyl-4-isoxazolepropionate receptors (AMPARs) was studied in rat brain slices by combining fast application of glutamate with patch pipette perfusion. 2. The peak current-voltage (I-V) relation of the AMPARs expressed in Bergmann glial cells of cerebellum and dentate gyrus (DG) basket cells of hippocampus was weakly rectifying in outside-out patches and nystatin-perforated vesicles, but showed a doubly rectifying shape with a region of reduced slope between 0 and +40 mV in nucleated patches. The I-V relation of AMPARs expressed in hippocampal CA3 pyramidal neurones was linear in all recording configurations. 3. Intracellular application of 2.5 μM spermine, a naturally occurring polyamine, blocked outward currents in outside-oat patches from Bergmann glial cells and DG basket cells in a voltage-dependent manner, generating I-V relations with a doubly rectifying shape which were similar to those recorded in nucleated patches. AMPARs in CA3 pyramidal cell patches were unaffected by 25 μM spermine. 4. The half-maximal blocking concentration of spermine at +40 mV was 0.3 μM in Bergmann glial cell patches and 1.5 μM in DG basket cell patches, whereas it was much higher (≥ 100 μM) for CA3 pyramidal. cell patches. Spermidine also affected current rectification, but with lower affinity. The block of outward current by polyamines following voltage jumps developed within < 0.5 ms. 5. We conclude that current rectification, rather than being an intrinsic property of the Ca2+ permeable AMPAR channel, is generated by polyamine block. AU - Koh, Duk AU - Burnashev, Nail AU - Jonas, Peter M ID - 3481 IS - Pt 2 JF - Journal of Physiology SN - 0022-3751 TI - Block of native Ca(2+)-permeable AMPA receptors in rat brain by intracellular polyamines generates double rectification VL - 486 ER - TY - JOUR AB - Recording of glutamate-activated currents in membrane patches was combine with RT-PCR-mediated AMPA receptor (AMPAR) subunit mRNA analysis in single identified cells of rat brain slices. Analysis of AMPARs in principal neurons end interneurons of hippocampus and neocortex and in auditory relay neurons and Bergmann glial cells indicates that the GluR-B subunit in its flip version determines formation of receptors with relatively slow gating, whereas the GluR-D subunit promotes assembly of more rapidly gated receptors. The relation between Ca 2+ permeability of AMPAR channels and the relative GluR-B mRNA abundance is consistent with the dominance of this subunit in determining the Ca 2+ permeability of native receptors. The results suggest that differential expression of GluR-B and GluR-D subunit genes, as well as splicing end editing of their mRNAs, account for the differences in gating and Ca 2+ permeability of native AMPAR channels. AU - Geiger, Jörg AU - Melcher, Thorsten AU - Koh, Duk AU - Sakmann, Bert AU - Seeburg, Peter AU - Jonas, Peter M AU - Monyer, Hannah ID - 3480 IS - 1 JF - Neuron SN - 0896-6273 TI - Relative abundance of subunit mRNAs determines gating and Ca(2+) permeability of AMPA receptors in principal neurons and interneurons in rat CNS VL - 15 ER - TY - GEN AU - Kirkpatrick, Mark AU - Barton, Nicholas H ID - 3597 SN - 0028-0836 T2 - Nature TI - Déjà vu all over again VL - 377 ER - TY - JOUR AB - The probability of fixation of a favorable mutation is reduced if selection at other loci causes inherited variation in fitness. A general method for calculating the fixation probability of an allele that can find itself in a variety of genetic backgrounds is applied to find the effect of substitutions, fluctuating polymorphisms, and deleterious mutations in a large population. With loose linkage, r, the effects depend on the additive genetic variance in relative fitness, var(W), and act by reducing effective population size by (N/Ne) = 1 + var(W)/2r2. However, tightly linked loci can have a substantial effect not predictable from Ne. Linked deleterious mutations reduce the fixation probability of weakly favored alleles by exp (-2U/R), where U is the total mutation rate and R is the map length in Morgans. Substitutions can cause a greater reduction: an allele with advantage s < scrit = (pi 2/6) loge (S/s) [var(W)/R] is very unlikely to be fixed. (S is the advantage of the substitution impeding fixation.) Fluctuating polymorphisms at many (n) linked loci can also have a substantial effect, reducing fixation probability by exp [square root of 2Kn var(W)/R] [K = -1/E((u-u)2/uv) depending on the frequencies (u,v) at the selected polymorphisms]. Hitchhiking due to all three kinds of selection may substantially impede adaptation that depends on weakly favored alleles. AU - Barton, Nicholas H ID - 3640 IS - 2 JF - Genetics SN - 0016-6731 TI - Linkage and the limits to natural selection VL - 140 ER - TY - JOUR AB - Efficient algorithms are described for computing topological, combinatorial, and metric properties of the union of finitely many spherical balls in R(d) These algorithms are based on a simplicial complex dual to a decomposition of the union of balls using Voronoi cells, and on short inclusion-exclusion formulas derived from this complex. The algorithms are most relevant in R(3) where unions of finitely many balls are commonly used as models of molecules. AU - Edelsbrunner, Herbert ID - 4028 IS - 1 JF - Discrete & Computational Geometry SN - 0179-5376 TI - The union of balls and its dual shape VL - 13 ER - TY - JOUR AB - A general and direct method for computing the Betti numbers of a finite simplicial complex in Bd is given. This method is complete for d less than or equal to 3, where versions of this method run in time O(n alpha(n)) and O(n), n the number of simplices. An implementation of the algorithm is applied to alpha shapes, which is a novel geometric modeling tool. AU - Delfinado, Cecil AU - Edelsbrunner, Herbert ID - 4029 IS - 7 JF - Computer Aided Geometric Design SN - 0167-8396 TI - An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere VL - 12 ER - TY - JOUR AB - The F5 (2n = 34) and FM2 (2n = 44-46) chromosome races of the Sceloporus grammicus complex form a parapatric hybrid zone in the Mexican state of Hidalgo, characterized by steep concordant clines among three diagnostic chromosome markers across a straight-line distance of about 2 km. Here, we show that this zone is actually structured into local patches in which hybridization extends over an extremely irregular front. The distribution of hybrid-index (HI) scores across the transect reveals some hybridization at almost all localities mapped in a central 7 km x 3 km area. Pooling the central samples produces both a strong heterozygote deficit for all diagnostic markers and strong linkage disequilibria between all pairwise combinations of these (unlinked) markers. Moreover, a highly significant association exists between the habitat on which each individual was caught and its karyotype (F5 chromosomes are more likely to be found on oak). Analysis of genotype frequencies over a range of spatial scales shows that there is no significant heterozygote deficit or habitat association within local areas of less than about 200 m; however, there is significant linkage disequilibrium over the smallest scales (R = D (pquv)1/2 = 0.29, support limits, 0.18-0.36) over 100 m. These patterns suggest that lizards mate and choose habitats randomly within local patches. This conclusion is supported by mark-recapture estimates of dispersal (≈ 80 m in a generation) and by inference of matings from embryo and maternal karyotypes. Closer examination of the two-dimensional pattern reveals a convoluted cline for all three markers, with a width of 830 m (support limits 770 m-930 m). This cline width, combined with the strength of local linkage disequilibrium, implies a dispersal rate of σ = 160 m in a generation and an effective selection pressure of 30% on each chromosome marker. The proportion of inviable embryos is greater in females from the center of the hybrid zone; this is caused by effects associated with both karyotype and location. The hybrid zone is likely to be maintained by selection against chromosomal heterozygotes, by other kinds of selection against hybrids, and by selection adapting the chromosome races to different habitats. The structure of the contact may be caused by both random drift and by selection in relation to habitat. AU - Sites, Jack AU - Barton, Nicholas H AU - Reed, Kent ID - 4297 IS - 1 JF - Evolution SN - 0014-3820 TI - The genetic structure of a mosaic hybrid zone between two chromosome races of the Sceloporus grammicus complex (Sauria, Phrynosomatidae) in central Mexico VL - 49 ER - TY - JOUR AB - Three replicate lines of Drosophila melanogaster were cultured at each of two temperatures (16.5⚬C and 25⚬C) in population cages for 4 yr. The lifespans of both sexes and the fecundity and fertility of the females were then measured at both experimental temperatures. The characters showed evidence of adaptation; flies of both sexes from each selection regime showed higher longevity, and females showed higher fecundity and fertility, than flies from the other selection regime when they were tested at the experimental temperature at which they had evolved. Calculation of intrinsic rates of increase under different assumptions about the rate of population increase showed that the difference between the lines from the two selection regimes became less the higher the rate of population increase, because the lines were more similar in early adulthood than they were later. Despite the increased adaptation of the low-temperature lines to the low temperature, like the high temperature lines they produced progeny at a higher rate at the higher temperature. The lines may have independently evolved adaptations to their respective thermal regimes during the experiment, or there may have been a trade-off between adaptation to the two temperatures, or mutation pressure may have lowered adaptation to the temperature that the flies no longer encountered. AU - Partridge, Linda AU - Barrie, Brian AU - Barton, Nicholas H AU - Fowler, Kevin AU - French, Vernon ID - 4296 IS - 3 JF - Evolution SN - 0014-3820 TI - Rapid laboratory evolution of adult life history traits in Drosophila melanogaster in response to temperature VL - 49 ER - TY - JOUR AU - Barton, Nicholas H ID - 4298 IS - 6 JF - Evolution SN - 1558-5646 TI - Appendix to "A simulation study of multilocus clines" by S J E Baird VL - 49 ER - TY - THES AB - Hybrid systems are real-time systems that react to both discrete and continuous activities (such as analog signals, time, temperature, and speed). Typical examples of hybrid systems are embedded systems, timing-based communication protocols, and digital circuits at the transistor level. Due to the rapid development of microprocessor technology, hybrid systems directly control much of what we depend on in our daily lives. Consequently, the formal specification and verification of hybrid systems has become an active area of research. This dissertation presents the first general framework for the formal specification and verification of hybrid systems, as well as the first hybrid-system analysis tool--HyTech. The framework consists of a graphical finite-state-machine-like language for modeling hybrid systems, a temporal logic for modeling the requirements of hybrid systems, and a computer procedure that verifies modeled hybrid systems against modeled requirements. The tool HyTech is the implementation of the framework using C++ and Mathematica. More specifically, our hybrid-system modeling language, Hybrid Automata, is an extension of timed automata with discrete and continuous variables whose dynamics are governed by differential equations. Our requirement modeling language, ICTL, is a branching-time temporal logic, and is an extension of TCTL with stop-watch variables. Our verification procedure is a symbolic model-checking procedure that verifies linear hybrid automata against ICTL formulas. To make HyTech more efficient and effective, we use model-checking strategies and abstract operators that can expedite the verification process. To enable HyTech to verify nonlinear hybrid automata, we introduce two translations from nonlinear hybrid automata to linear hybrid automata. We have applied HyTech to analyze more than 30 hybrid-system benchmarks. In this dissertation, we present the application of HyTech to three nontrivial hybrid systems taken from the literature. AU - Ho, Pei ID - 4428 TI - Automatic analysis of hybrid systems ER - TY - CONF AB - Hybrid systems model discrete programs that are embedded in continuous environments. Model-checking tools are available for the analysis of linear hybrid systems, whose continuous variables are bounded by piecewise-linear trajectories. Most embedded programs, however, operate in nonlinear environments. We present, analyze, and apply two algorithms for translating nonlinear hybrid systems into linear hybrid systems. The clock translation replaces nonlinear variables by clock variables; the rate translation approximates nonlinear variables by piecewise-linear envelopes. Both translations are sound for reachability; that is, if we establish a safety property of the translated linear system, we may conclude that the original nonlinear system satisfies the property. The clock translation is also complete for reachability; that is, the original system and the translated system satisfy the same safety properties. The two translations apply to incomparable classes of nonlinear hybrid systems. From the clock translation we obtain a new decidability result for hybrid systems. With the help of Hytech, a symbolic model checker for linear hybrid systems, we automatically verify a nonlinear railroad gate control program using the clock translation, and a nonlinear temperature control program using the rate translation. AU - Henzinger, Thomas A AU - Ho, Pei ID - 4450 SN - 9783540494133 T2 - 7th International Conference on Computer Aided Verification TI - Algorithmic analysis of nonlinear hybrid systems VL - 939 ER - TY - CONF AB - We report on several abstract interpretation strategies that are designed to improve the performance of HyTech, a symbolic model checker for linear hybrid systems. We (1) simultaneously compute the target region from different directions, (2) conservatively approximate the target region by dropping constraints, and (3) iteratively refine the approximation until sufficient precision is obtained. We consider the standard abstract convex-hull operator and a novel abstract extrapolation operator. AU - Henzinger, Thomas A AU - Ho, Pei ED - Panos, Antsaklis ED - Kohn, Wolf ED - Nerode, Anil ED - Sastry, Shankar ID - 4448 SN - 9783540604723 T2 - 3rd International Hybrid Systems Workshop TI - A note on abstract-interpretation strategies for hybrid automata VL - 999 ER - TY - CONF AB - This paper is addressed to potential users of HyTech, the Cornell Hybrid Technology Tool, an automatic tool for analyzing hybrid systems. We review the formal technologies that have been incorporated into HyTech, and we illustrate the use of HyTech with three nontrivial case studies. AU - Henzinger, Thomas A AU - Ho, Pei ED - Panos, Antsaklis ED - Kohn, Wolf ED - Nerode, Anil ED - Sastry, Shankar ID - 4447 SN - 9783540683346 T2 - 4th International Hybrid Systems Workshop TI - HyTech: The Cornell Hybrid Technology Tool VL - 999 ER - TY - CONF AB - HyTech is a tool for the automated analysis of embedded systems. This document, designed for the first-time user of HyTech, guides the reader through the underlying system model, and through the input language for describing and analyzing systems. The guide gives several examples of usage, and some hints for gaining maximal computational efficiency from the tool. The version of HyTech described in this guide was released in August 1995, and is available through anonymous ftp from ftp.cs.cornell.edu in the directory pub/tah/HyTech, and through the World-Wide Web via HyTech's home page http:/www.cs.cornell.edu/Info/People/tah/hytech.html. AU - Henzinger, Thomas A AU - Ho, Pei AU - Wong Toi, Howard ID - 4497 SN - 9783540606307 T2 - 1st International Workshop on Tools and Algorithms for the Construction and Analysis of Systems TI - A user guide to HyTech VL - 1019 ER - TY - CONF AB - We describe a new implementation of HYTECH, a symbolic model checker for hybrid systems. Given a parametric description of an embedded system as a collection of communicating automata, HYTECH automatically computes the conditions on the parameters under which the system satisfies its safety and timing requirements. While the original HYTECH prototype was based on the symbolic algebra tool Mathematica, the new implementation is written in C++ and builds on geometric algorithms instead of formula manipulation. The new HYTECH offers a cleaner and more expressive input language, greater portability, superior performance (typically two to three orders of magnitude), and new features such as diagnostic error-trace generation. We illustrate the effectiveness of the new implementation by applying HYTECH to the automatic parametric analysis of the generic railroad crossing benchmark problem and to an active structure control algorithm AU - Henzinger, Thomas A AU - Ho, Pei AU - Wong Toi, Howard ID - 4499 SN - 0818673370 T2 - Proceedings 16th IEEE Real-Time Systems Symposium TI - HyTech: The next generation ER - TY - CONF AB - We present algorithms for computing similarity relations of labeled graphs. Similarity relations have applications for the refinement and verification of reactive systems. For finite graphs, we present an O(mn) algorithm for computing the similarity relation of a graph with n vertices and m edges (assuming m⩾n). For effectively presented infinite graphs, we present a symbolic similarity-checking procedure that terminates if a finite similarity relation exists. We show that 2D rectangular automata, which model discrete reactive systems with continuous environments, define effectively presented infinite graphs with finite similarity relations. It follows that the refinement problem and the ∀CTL* model-checking problem are decidable for 2D rectangular automata AU - Henzinger, Monika H AU - Henzinger, Thomas A AU - Kopke, Peter ID - 4498 SN - 0272-5428 T2 - Proceedings of IEEE 36th Annual Foundations of Computer Science TI - Computing simulations on finite and infinite graphs ER - TY - CONF AB - Hybrid automata model systems with both digital and analog components, such as embedded control programs. Many verification tasks for such programs can be expressed as reachability problems for hybrid automata. By improving on previous decidability and undecidability results, we identify the precise boundary between decidability and undecidability of the reachability problem for hybrid automata. On the positive side, we give an (optimal) PSPACE reachability algorithm for the case of initialized rectangular automata, where all analog variables follow trajectories within piecewise-linear envelopes and are reinitialized whenever the envelope changes. Our algorithm is based on the construction of a timed automaton that contains all reachability information about a given initialized rectangular automaton. The translation has practical significance for verification, because it guarantees the termination of symbolic procedures for the reachability analysis of initialized rectangular automata. The translation also preserves the omega-languages of initialized rectangular automata with bounded nondeterminism. On the negative side, we show that several slight generalizations of initialized rectangular automata lead to an undecidable reachability problem. In particular, we prove that the reachability problem is undecidable for timed automata augmented with a single stopwatch. AU - Henzinger, Thomas A AU - Kopke, Peter AU - Puri, Anuj AU - Varaiya, P. ID - 4502 SN - 9780897917186 T2 - Proceedings of the 27th annual ACM symposium on Theory of computing TI - What's decidable about hybrid automata? ER - TY - CONF AB - We investigate the expressive power of timing restrictions on labeled transition systems. In particular, we show how constraints on clock variables together with a uniform liveness condition—the divergence of time—can express Büchi, Muller, Streett, Rabin, and weak and strong fairness conditions on a given labeled transition system. We then consider the effect, on both timed and time-abstract expressiveness, of varying the following parameters: time domain (discrete or dense), number of clocks, number of states, and size of constants used in timing restrictions. AU - Henzinger, Thomas A AU - Kopke, Peter AU - Wong Toi, Howard ID - 4500 SN - 9783540600848 T2 - 22nd International Colloquium on Automata, Languages and Programming TI - The expressive power of clocks VL - 944 ER - TY - CONF AB - The analysis, verification, and control of hybrid automata with finite bisimulations can be reduced to finite-state problems. We advocate a time-abstract, phase-based methodology for checking if a given hybrid automaton has a finite bisimulation. First, we factor the automaton into two components, a boolean automaton with a discrete dynamics on the finite state space B m and a euclidean automaton with a continuous dynamics on the infinite state space n . Second, we investigate the phase portrait of the euclidean component. In this fashion, we obtain new decidability results for hybrid systems as well as new, uniform proofs of known decidability results. AU - Henzinger, Thomas A ID - 4518 SN - 9783540600848 T2 - 22nd International Colloquium on Automata, Languages and Programming TI - Hybrid automata with finite bisimulations VL - 944 ER - TY - CONF AB - We argue that the standard constraints on liveness conditions in nonblocking trace models—machine closure for closed systems, and receptiveness for open systems—are unnecessarily weak and complex, and that liveness should, instead, be specified by augmenting transition systems with acceptance conditions that satisfy a locality constraint. First, locality implies machine closure and receptiveness, and thus permits the composition and modular verification of live transition systems. Second, while machine closure and receptiveness are based on infinite games, locality is based on repeated finite games, and thus easier to check. Third, no expressive power is lost by the restriction to local liveness conditions. We illustrate the appeal of local liveness using the model of Fair Reactive Systems, a nonblocking trace model of communicating processes. AU - Alur, Rajeev AU - Henzinger, Thomas A ID - 4587 SN - 978-3-540-60045-9 T2 - 7th International Conference on Computer Aided Verification TI - Local liveness for compositional modeling of fair reactive systems VL - 939 ER - TY - JOUR AB - We present a general framework for the formal specification and algorithmic analysis of hybrid systems. A hybrid system consists of a discrete program with an analog environment. We model hybrid systems as finite automata equipped with variables that evolve continuously with time according to dynamical laws. For verification purposes, we restrict ourselves to linear hybrid systems, where all variables follow piecewise-linear trajectories. We provide decidability and undecidability results for classes of linear hybrid systems, and we show that standard program-analysis techniques can be adapted to linear hybrid systems. In particular, we consider symbolic model-checking and minimization procedures that are based on the reachability analysis of an infinite state space. The procedures iteratively compute state sets that are definable as unions of convex polyhedra in multidimensional real space. We also present approximation techniques for dealing with systems for which the iterative procedures do not converge. AU - Alur, Rajeev AU - Courcoubetis, Costas AU - Halbwachs, Nicolas AU - Henzinger, Thomas A AU - Ho, Pei AU - Nicollin, Xavier AU - Olivero, Alfredo AU - Sifakis, Joseph AU - Yovine, Sergio ID - 4613 IS - 1 JF - Theoretical Computer Science SN - 0304-3975 TI - The algorithmic analysis of hybrid systems VL - 138 ER - TY - JOUR AB - The tra-1 gene is the terminal global selector of somatic sex in Caenorhabditis elegans: High tra-1 activity elicits female somatic development while low tra-1 activity elicits male development. Previous genetic studies defined a cascade of negatively interacting genes that regulates tra-1 activity in response to the primary sex-determining signal. Here, we investigate the last step in this regulatory cascade, by studying rare gain-of-function (gf) mutations of tra-1 that direct female somatic development irrespective of the upstream sex-determining signal. These mutations appear to abolish negative regulation of tra-1 in male tissues. We identify the lesions associated with 29 of these mutations and find that all affect a short stretch of amino acid residues present in both protein products of the tra-1 gene. Twenty-six alleles are associated with single nonconservative amino acid substitutions. Two alleles affect tra-1 RNA splicing and generate messages that omit part or all of the exon encoding this short stretch. These results suggest that sexual regulation of tra-1 is achieved post-translationally, by an inhibitory protein-protein interaction. The amino acid stretch altered by the tra-1(gf) mutations may define a site of interaction for negative regulators of tra-1. The stretch includes a potential phosphorylation site for glycogen synthase kinase 3 and may be conserved in the human gene GLI3, a homolog of tra-1 identified previously. AU - de Bono, Mario AU - Zarkower, D. AU - Hodgkin, J. ID - 6162 IS - 2 JF - Genes and Development SN - 08909369 TI - Dominant feminizing mutations implicate protein-protein interactions as the main mode of regulation of the nematode sex-determining gene tra-1 VL - 9 ER -