@article{11893, abstract = {We present fully dynamic algorithms for maintaining the biconnected components in general and plane graphs. A fully dynamic algorithm maintains a graph during a sequence of insertions and deletions of edges or isolated vertices. Let m be the number of edges and n be the number of vertices in a graph. The time per operation of the best deterministic algorithms is 𝑂(𝑛√) in general graphs and O(log n) in plane graphs for fully dynamic connectivity and O(min m2/3 ,n}) in general graphs and 𝑂(𝑛√) in plane graphs for fully dynamic biconnectivity. We improve the later running times to 𝑂(𝑚logđ‘›â€Ÿâ€Ÿâ€Ÿâ€Ÿâ€Ÿâ€Ÿâ€Ÿâˆš) in general graphs and O(log 2n ) in plane graphs. Our algorithm for general graphscan also find the biconnected components of all vertices in time O(n).}, author = {Henzinger, Monika H}, issn = {1095-7111}, journal = {SIAM Journal on Computing}, number = {6}, pages = {1761--1815}, publisher = {Society for Industrial & Applied Mathematics}, title = {{Improved data structures for fully dynamic biconnectivity}}, doi = {10.1137/s0097539794263907}, volume = {29}, year = {2000}, } @article{12925, abstract = {Normal function of organs and cells is tightly linked to the cytoarchitecture. Control of the cell volume is therefore vital for the organism. A widely established strategy of cells to counteract swelling is the activation of chloride and potassium channels, which leads to a net efflux of salt followed by water - a process termed regulatory volume decrease. Since there is evidence for swelling-dependent chloride channels (IClswell) being activated also during pathological processes, the identification of the molecular entity underlying IClswell is of utmost importance. Several proteins are discussed as the channel forming IClswell, i.e. phospholemman, p-glycoprotein, CLC-3 and ICln. In this review we would like to focus on the properties of ICln, a protein cloned from a Madin Darby canine kidney (MDCK) cell library whose expression in Xenopus laevis oocytes resulted in a nucleotide sensitive outwardly rectifying chloride current closely resembling the biophysical properties of IClswell.}, author = {FĂŒrst, Johannes and Jakab, Martin and König, Matthias and Ritter, Markus and Gschwentner, Martin and Rudzki, Jakob and Danzl, Johann G and Mayer, Michael and Burtscher, Carmen M. and Schirmer, Julia and Maier, Brigitte and Nairz, Manfred and Chwatal, Sabine and Paulmichl, Markus}, issn = {1015-8987}, journal = {Cellular Physiology and Biochemistry}, keywords = {Physiology}, number = {5-6}, pages = {329--334}, publisher = {S. Karger AG}, title = {{Structure and Function of the Ion Channel ICln}}, doi = {10.1159/000016374}, volume = {10}, year = {2000}, } @article{3489, abstract = {We have examined factors that determine the strength and dynamics of GABAergic synapses between interneurons [dentate gyrus basket cells (BCs)] and principal neurons [dentate gyrus granule cells (GCs)] using paired recordings in rat hippocampal slices at 34°C. Unitary IPSCs recorded from BC–GC pairs in high intracellular Cl− concentration showed a fast rise and a biexponential decay, with mean time constants of 2 and 9 msec. The mean quantal conductance change, determined directly at reduced extracellular Ca2+/Mg2+concentration ratios, was 1.7 nS. Quantal release at the BC–GC synapse occurred with short delay and was highly synchronized. Analysis of IPSC peak amplitudes and numbers of failures by multiple probability compound binomial analysis indicated that synaptic transmission at the BC–GC synapse involves three to seven release sites, each of which releases transmitter with high probability (∌0.5 in 2 mMCa2+/1 mM Mg2+). Unitary BC–GC IPSCs showed paired-pulse depression (PPD); maximal depression, measured for 10 msec intervals, was 37%, and recovery from depression occurred with a time constant of 2 sec. Paired-pulse depression was mainly presynaptic in origin but appeared to be independent of previous release. Synaptic transmission at the BC–GC synapse showed frequency-dependent depression, with half-maximal decrease at 5 Hz after a series of 1000 presynaptic action potentials. The relative stability of transmission at the BC–GC synapse is consistent with a model in which an activity-dependent gating mechanism reduces release probability and thereby prevents depletion of the releasable pool of synaptic vesicles. Thus several mechanisms converge on the generation of powerful and sustained transmission at interneuron–principal neuron synapses in hippocampal circuits.}, author = {Kraushaar, Udo and Jonas, Peter M}, issn = {0270-6474}, journal = {Journal of Neuroscience}, number = {15}, pages = {5594 -- 5607}, publisher = {Society for Neuroscience}, title = {{Efficacy and stability of quantal GABA release at a hippocampal interneuron-principal neuron synapse}}, doi = {10.1523/JNEUROSCI.20-15-05594.2000}, volume = {20}, year = {2000}, } @article{3490, abstract = {Long-term depression (LTD) is a form of synaptic plasticity that can be induced either by low-frequency stimulation of presynaptic fibers or in an associative manner by asynchronous pairing of presynaptic and postsynaptic activity. We investigated the induction mechanisms of associative LTD in CA1 pyramidal neurons of the hippocampus using whole-cell patch-clamp recordings and Ca2+ imaging in acute brain slices. Asynchronous pairing of postsynaptic action potentials with EPSPs evoked with a delay of 20 msec induced a robust, long-lasting depression of the EPSP amplitude to 43%. Unlike LTD induced by low-frequency stimulation, associative LTD was resistant to the application of D-AP-5, indicating that it is independent of NMDA receptors. In contrast, associative LTD was inhibited by (S)-α-methyl-4-carboxyphenyl-glycine, indicating the involvement of metabotropic glutamate receptors. Furthermore, associative LTD is dependent on the activation of voltage-gated Ca2+ channels by postsynaptic action potentials. Both nifedipine, an L-type Ca2+ channel antagonist, and ω-conotoxin GVIA, a selective N-type channel blocker, abolished the induction of associative LTD. 8-hydroxy-2-dipropylaminotetralin (OH-DPAT), a 5-HT(1A) receptor agonist, inhibited postsynaptic Ca2+ influx through N-type Ca2+ channels, without affecting presynaptic transmitter release. OH-DPAT also inhibited the induction of associative LTD, suggesting that the involvement of N-type channels makes synaptic plasticity accessible to modulation by neurotransmitters. Thus, the modulation of N-type Ca2+ channels provides a gain control for synaptic depression in hippocampal pyramidal neurons.}, author = {Normann, Claus and Peckys, Diana and Schulze, Christian and Walden, Jörg and Jonas, Peter M and Bischofberger, Joseph}, issn = {0270-6474}, journal = {Journal of Neuroscience}, number = {22}, pages = {8290 -- 8297}, publisher = {Society for Neuroscience}, title = {{Associative long-term depression in the hippocampus is dependent on postsynaptic N-type Ca(2+) channels}}, doi = {10.1523/JNEUROSCI.20-22-08290.2000}, volume = {20}, year = {2000}, } @article{3491, abstract = {Fast and reliable activation of inhibitory interneurons is critical for the stability of cortical neuronal networks. Active conductances in dendrites may facilitate interneuron activation, but direct experimental evidence was unavailable. Patch-clamp recordings from dendrites of hippocampal oriens- alveus interneurons revealed high densities of voltage-gated sodium and potassium ion channels. Simultaneous recordings from dendrites and somata suggested that action potential initiation occurs preferentially in the axon with long threshold stimuli, but can be shifted to somatodendritic sites when brief stimuli are applied. After initiation, action potentials propagate over the somatodendritic domain with constant amplitude, high velocity, and reliability, even during high-frequency trains.}, author = {Martina, Marco and Vida, Imre and Jonas, Peter M}, issn = {0036-8075}, journal = {Science}, number = {5451}, pages = {295 -- 300}, publisher = {American Association for the Advancement of Science}, title = {{Distal initiation and active propagation of action potentials in interneuron dendrites}}, doi = {10.1126/science.287.5451.295}, volume = {287}, year = {2000}, } @article{3492, abstract = {Analysis of presynaptic determinants of synaptic strength has been difficult at cortical synapses, mainly due to the lack of direct access to presynaptic elements. Here we report patch-clamp recordings from mossy fiber boutons (MFBs) in rat hippocampal slices. The presynaptic action potential is very short during low-frequency stimulation but is prolonged up to 3-fold during high-frequency stimulation. Voltage-gated K+ channels in MFBs inactivate rapidly but recover from inactivation very slowly, suggesting that cumulative K+ channel inactivation mediates activity-dependent spike broadening. Prolongation of the presynaptic voltage waveform leads to an increase in the number of Ca2+ ions entering the terminal per action potential and to a consecutive potentiation of evoked excitatory postsynaptic currents at MFB-CA3 pyramidal cell synapses. Thus, inactivation of presynaptic K+ channels contributes to the control of efficacy of a glutamatergic synapse in the cortex.}, author = {Geiger, Jörg and Jonas, Peter M}, issn = {0896-6273}, journal = {Neuron}, number = {3}, pages = {927 -- 939}, publisher = {Elsevier}, title = {{Dynamic control of presynaptic Ca(2+) inflow by fast-inactivating K+ channels in hippocampal mossy fiber boutons}}, doi = {10.1016/S0896-6273(00)00164-1}, volume = {28}, year = {2000}, } @article{3532, abstract = {Multichannel tetrode array recording in awake behaving animals provides a powerful method to record the activity of large numbers of neurons. The power of this method could be extended if further information concerning the intracellular state of the neurons could be extracted from the extracellularly recorded signals. Toward this end, we have simultaneously recorded intracellular and extracellular signals from hippocampal CA1 pyramidal cells and interneurons in the anesthetized rat. We found that several intracellular parameters can be deduced from extracellular spike waveforms. The width of the intracellular action potential is defined precisely by distinct points on the extracellular spike. Amplitude changes of the intracellular action potential are reflected by changes in the amplitude of the initial negative phase of the extracellular spike, and these amplitude changes are dependent on the state of the network. In addition, intracellular recordings from dendrites with simultaneous extracellular recordings from the soma indicate that, on average, action potentials are initiated in the perisomatic region and propagate to the dendrites at 1.68 m/s. Finally we determined that a tetrode in hippocampal area CA1 theoretically should be able to record electrical signals from similar to 1,000 neurons. Of these, 60-100 neurons should generate spikes of sufficient amplitude to be detectable from the noise and to allow for their separation using current spatial clustering methods. This theoretical maximum is in contrast to the approximately six units that are usually detected per tetrode. From this, we conclude that a large percentage of hippocampal CA1 pyramidal cells are silent in any given behavioral condition.}, author = {Henze, Darrell and Borhegyi, Zsolt and Csicsvari, Jozsef L and Mamiya, Akira and Harris, Kenneth and BuzsĂĄki, György}, issn = {0022-3077}, journal = {Journal of Neurophysiology}, number = {1}, pages = {390 -- 400}, publisher = {American Physiological Society}, title = {{Intracellular features predicted by extracellular recordings in the hippocampus in vivo}}, doi = {10.1152/jn.2000.84.1.390}, volume = {84}, year = {2000}, } @article{3542, abstract = {Transfer of neuronal patterns from the CA3 to CA1 region was studied by simultaneous recording of neuronal ensembles in the behaving rat. A nonlinear interaction among pyramidal neurons was observed during sharp wave (SPW)-related population bursts, with stronger synchrony associated with more widespread spatial coherence. SPW bursts emerged in the CA3a-b subregions and spread to CA3c before invading the CA1 area. Synchronous discharge of >10% of the CA3 within a 100 ms window was required to exert a detectable influence on CA1 pyramidal cells. Activity of some CA3 pyramidal neurons differentially predicted the ripple-related discharge of circumscribed groups of CA1 pyramidal cells. We suggest that, in SPW behavioral state, the coherent discharge of a small group of CA3 cells is the primary cause of spiking activity in CA1 pyramidal neurons.}, author = {Csicsvari, Jozsef L and Hirase, Hajima and Mamiya, Akira and BuzsĂĄki, György}, issn = {0896-6273}, journal = {Neuron}, number = {2}, pages = {585 -- 594}, publisher = {Elsevier}, title = {{Ensemble patterns of hippocampal CA3-CA1 neurons during sharp wave-associated population events}}, doi = {10.1016/S0896-6273(00)00135-5}, volume = {28}, year = {2000}, } @article{3548, abstract = {Simultaneous recording from large numbers of neurons is a prerequisite for understanding their cooperative behavior. Various recording techniques and spike separation methods are being used toward this goal. However, the error rates involved in spike separation have not yet been quantified. We studied the separation reliability of “tetrode” (4-wire electrode) recorded spikes by monitoring simultaneously from the same cell intracellularly with a glass pipette and extracellularly with a tetrode. With manual spike sorting, we found a trade-off between Type I and Type II errors, with errors typically ranging from 0 to 30% depending on the amplitude and firing pattern of the cell, the similarity of the waveshapes of neighboring neurons, and the experience of the operator. Performance using only a single wire was markedly lower, indicating the advantages of multiple-site monitoring techniques over single-wire recordings. For tetrode recordings, error rates were increased by burst activity and during periods of cellular synchrony. The lowest possible separation error rates were estimated by a search for the best ellipsoidal cluster shape. Human operator performance was significantly below the estimated optimum. Investigation of error distributions indicated that suboptimal performance was caused by inability of the operators to mark cluster boundaries accurately in a high-dimensional feature space. We therefore hypothesized that automatic spike-sorting algorithms have the potential to significantly lower error rates. Implementation of a semi-automatic classification system confirms this suggestion, reducing errors close to the estimated optimum, in the range 0-8%.}, author = {Harris, Kenneth and Henze, Darrell and Csicsvari, Jozsef L and Hirase, Hajima and BuzsĂĄki, György}, issn = {0022-3077}, journal = {Journal of Neurophysiology}, number = {1}, pages = {401 -- 414}, publisher = {American Physiological Society}, title = {{Accuracy of tetrode spike separation as determined by simultaneous intracellular and extracellular measurements}}, doi = {10.1152/jn.2000.84.1.401}, volume = {84}, year = {2000}, } @inproceedings{3555, abstract = {A sliver is a tetrahedron whose four vertices lie close to a plane and whose perpendicular projection to that plane is a convex quadrilateral with no short edge. Slivers are both undesirable and ubiquitous in 3-dimensional Delaunay triangulations. Even when the point-set is well-spaced, slivers may result. This paper shows that such a point set permits a small perturbation whose Delaunay triangulation contains no slivers. It also gives deterministic algorithms that compute the perturbation of n points in time O(n log n) with one processor and in time O(log n) with O(n) processors.}, author = {Edelsbrunner, Herbert and Li, Xiang and Miller, Gary and Stathopoulos, Andreas and Talmor, Dafna and Teng, Shang and Üngör, Alper and Walkington, Noel}, booktitle = {Proceedings of the 32nd annual ACM symposium on Theory of computing}, isbn = {9781581131840}, location = {Portland, OR, USA}, pages = {273 -- 277}, publisher = {ACM}, title = {{Smoothing and cleaning up slivers}}, doi = {10.1145/335305.335338}, year = {2000}, } @inbook{3572, abstract = {Allzulange wurde die spielhafte BeschĂ€ftigung als Gegensatz zu ernsthafter Arbeit gesehen. Dieser Artikel propagiert die spielerische Untersuchung von Kreis- und Kugelmengen. Gleichzeitig belegt er die nutzbare Anwendung von elementaren Einsichten in der Molekularbiologie und allgemeiner in der Beschreibung von Form und Verformung.}, author = {Edelsbrunner, Herbert}, booktitle = {Zur Kunst des formalen Denkens}, isbn = {3851653580}, pages = {153 -- 171}, publisher = {Passagen Verlag}, title = {{Spielereien mit Kreisen und Kugeln. Zum Thema Form und Verformung}}, year = {2000}, } @article{3583, abstract = {The Delaunay triangulation of a finite point set is a central theme in computational geometry. It finds its major application in the generation of meshes used in the simulation of physical processes. This paper connects the predominantly combinatorial work in classical computational geometry with the numerical interest in mesh generation. It focuses on the two- and three-dimensional case and covers results obtained during the twentieth century.}, author = {Edelsbrunner, Herbert}, journal = {Acta Numerica}, pages = {133 -- 213}, publisher = {Cambridge University Press}, title = {{Triangulations and meshes in computational geometry}}, doi = {10.1017/S0962492900001331}, volume = {9}, year = {2000}, } @article{3623, abstract = {We present the theoretical background to a new method for measuring genetic variation for total fitness in Drosophila. The method allows heterozygous effects on total fitness of whole wild-type chromosomes to be measured under normal demography with overlapping generations. The wild-type chromosomes are competed against two balancer chromosomes (B1, B2, say), providing a standard genotype B1/B2 against which variation in the fitness effects of the wild-type chromosomes can be assessed. Fitness can be assessed in two ways: (i) at equilibrium of all three chromosomes under heterozygote advantage, and (ii) during displacement of one balancer by the other. Equilibrium with all three chromosomes present will be achieved only if the wild-type homozygote is not too fit, and if the fitnesses of the three heterozygotes are not too unequal. These conditions were not satisfied for any of a sample of 12 lethal-bearing chromosomes isolated from a random-bred laboratory population of Drosophila. At equilibrium, genotypic frequencies show low sensitivity to changes in genotypic fitness. Furthermore, where all four genotypes are viable and fertile, supplementary information from cages with only two chromosomes present and from direct measurements of pre-adult viability are required to estimate fitnesses from frequencies. The invasion method has the advantages of a greater sensitivity and of not requiring further data to estimate fitnesses if the wild-type homozygote is fertile. However, it requires that multiple samples be taken as the invasion progresses. In a discrete generation model, generation time influences fitness estimates from this method and is difficult to estimate accurately from the data. A full age-structured model can also be applied to the data from both types of experiment. For the invasion method, this gives fitness estimates close to those from the discrete generation model.}, author = {Barton, Nicholas H and Patridge, Linda}, issn = {0016-6723}, journal = {Genetical Research}, number = {3}, pages = {297 -- 314}, publisher = {Cambridge University Press}, title = {{Measuring fitness by means of balancer chromosomes}}, doi = {10.1017/S0016672399004346}, volume = {75}, year = {2000}, } @article{3624, abstract = {The state of a diploid population segregating for two alleles at each of n loci is described by 22(n) genotype frequencies, or equivalently, by allele frequencies and by multilocus moments or cumulants of various orders. These measures of linkage disequilibrium cannot usually be determined, both because one cannot tell whether a gene came from the maternal or paternal gamete, and because such a large number of parameters cannot be estimated even from large samples. Simplifying assumptions must therefore be made. This paper sets out methods for estimating multilocus genotype frequencies which are appropriate for unlinked neutral loci, and for populations that are ultimately derived by mixing of two source populations. In such a hybrid population, all multilocus associations depend primarily on the number of loci involved that derive from the maternal genome, and the number derived from the paternal genome Allele frequencies may differ across loci, and the contribution of each locus to multilocus associations may be scaled by the difference in allele frequency between source populations for that locus (ÎŽp ≀ 1). For example, the cumulant describing the association between genes i, j, k from the maternal genome, and genes i, l from the paternal genome is K(tJ,k,iλ*), = ÎŽp(i)/2 ÎŽp(J) ÎŽp(k) ÎŽp(l) Îș3,2. The state of the population is described by n allele frequencies; n divergences, ÎŽp; and by a symmetric matrix of cumulants, Îș(J,K) (J = 0 ,..., n, K = 0 ,..., n). Expressions for these cumulants under short- and long-range migration are given. Two methods for estimating the cumulants are described: a simple method based on multivariate moments, and a maximum likelihood procedure, which uses the Metropolis algorithm. Both methods perform well when tested against simulations with two or four loci.}, author = {Barton, Nicholas H}, issn = {0018-067X}, journal = {Heredity}, number = {3}, pages = {373 -- 389}, publisher = {Nature Publishing Group}, title = {{Estimating multilocus linkage disequilibria}}, doi = {10.1046/j.1365-2540.2000.00683.x}, volume = {84}, year = {2000}, } @article{3798, abstract = {Glutamate is the main excitatory transmitter in the mammalian CNS, mediating fast synaptic transmission primarily by activation of AMPA-type glutamate receptor channels. Both synaptic structure and a cell-specific molecular switch in the AMPA receptor subunit expression are involved in the regulation of the synaptic signaling time course.}, author = {Jonas, Peter M}, issn = {1548-9213}, journal = {Physiology}, number = {2}, pages = {83 -- 89}, publisher = {American Physiological Society}, title = {{The time course of signaling at central glutamatergic synapses}}, doi = {10.1152/physiologyonline.2000.15.2.83}, volume = {15}, year = {2000}, } @article{3923, author = {Cremer, Sylvia}, issn = {0179-6372}, journal = {Futura: the Journal of the Boehringer Ingelheim Fonds}, number = {1}, pages = {68 -- 71}, publisher = {Hippokrates}, title = {{Paternity analysis with AFLPs in Cardiocondyla ants}}, volume = {15}, year = {2000}, } @article{4004, abstract = {In this paper we introduce the abacus model of a simplex and use it to subdivide a d-simplex into k(d) d-simplices all of the same volume and shape characteristics. The construction is an extension of the subdivision method of Freudenthal [3] and has been used by Goodman and Peters [4] to design smooth manifolds.}, author = {Edelsbrunner, Herbert and Grayson, Daniel}, issn = {0179-5376}, journal = {Discrete & Computational Geometry}, number = {4}, pages = {707 -- 719}, publisher = {Springer}, title = {{Edgewise subdivision of a simplex}}, doi = {10.1007/s004540010063}, volume = {24}, year = {2000}, } @inproceedings{4008, abstract = {We formalize a notion of topological simplification within the framework of a filtration, which is the history of a growing complex. We classify a topological change that happens during growth as either a feature or noise depending on its life-time or persistence within the filtration. We give fast algorithms for computing persistence and experimental evidence for their speed and utility.}, author = {Edelsbrunner, Herbert and Letscher, David and Zomorodian, Afra}, booktitle = {Proceedings 41st Annual Symposium on Foundations of Computer Science}, isbn = {0769508502}, location = {Washington, DC, United States}, pages = {454 -- 463}, publisher = {IEEE}, title = {{Topological persistance and simplification}}, doi = {10.1109/SFCS.2000.892133}, year = {2000}, } @article{4009, abstract = {We study the maintenance of a simplicial grid or complex under changing density requirements. The proposed method works in any fixed dimension and generates grids by projecting cross-sections of a monotone simplicial complex that lives in one dimension higher than the grid. The density of the grid is adapted by locally moving the cross-section up or down along the extra dimension.}, author = {Edelsbrunner, Herbert and Waupotitsch, Roman}, issn = {0218-1959}, journal = {International Journal of Computational Geometry and Applications}, number = {3}, pages = {267 -- 284}, publisher = {World Scientific Publishing}, title = {{Adaptive simplicial grids from cross-sections of monotone complexes}}, doi = {10.1142/S0218195900000164}, volume = {10}, year = {2000}, } @article{4010, abstract = {A sliver is a tetrahedron whose four vertices lie close to a plane and whose orthogonal projection to that plane is a convex quadrilateral with no short edge. Slivers are notoriously common in 3-dimensional Delaunay triangulations even for well-spaced point sets. We show that, if the Delaunay triangulation has the ratio property introduced in Miller et al. [1995], then there is an assignment of weights so the weighted Delaunay triangulation contains no slivers. We also give an algorithm to compute such a weight assignment.}, author = {Cheng, Siu and Dey, Tamal and Edelsbrunner, Herbert and Facello, Michael and Teng, Shang}, issn = {0004-5411}, journal = {Journal of the ACM}, number = {5}, pages = {883 -- 904}, publisher = {ACM}, title = {{Sliver exudation}}, doi = {10.1145/355483.355487}, volume = {47}, year = {2000}, }