TY - GEN AB - It is widely accepted that the hippocampus plays a major role in learning and memory. The mossy fiber synapse between granule cells in the dentate gyrus and pyramidal neurons in the CA3 region is a key component of the hippocampal trisynaptic circuit. Recent work, partially based on direct presynaptic patch-clamp recordings from hippocampal mossy fiber boutons, sheds light on the mechanisms of synaptic transmission and plasticity at mossy fiber synapses. A high Na(+) channel density in mossy fiber boutons leads to a large amplitude of the presynaptic action potential. Together with the fast gating of presynaptic Ca(2+) channels, this generates a large and brief presynaptic Ca(2+) influx, which can trigger transmitter release with high efficiency and temporal precision. The large number of release sites, the large size of the releasable pool of vesicles, and the huge extent of presynaptic plasticity confer unique strength to this synapse, suggesting a large impact onto the CA3 pyramidal cell network under specific behavioral conditions. The characteristic properties of the hippocampal mossy fiber synapse may be important for pattern separation and information storage in the dentate gyrus-CA3 cell network. AU - Bischofberger, Joseph AU - Engel, Dominique AU - Frotscher, Michael AU - Peter Jonas ID - 3463 IS - 3 T2 - Pflugers Archiv : European Journal of Physiology TI - Timing and efficacy of transmitter release at mossy fiber synapses in the hippocampal network. (Review) VL - 453 ER - TY - CONF AB - We study infinite stochastic games played by n-players on a finite graph with goals specified by sets of infinite traces. The games are concurrent (each player simultaneously and independently chooses an action at each round), stochastic (the next state is determined by a probability distribution depending on the current state and the chosen actions), infinite (the game continues for an infinite number of rounds), nonzero-sum (the players’ goals are not necessarily conflicting), and undiscounted. We show that if each player has an upward-closed objective, then there exists an ε-Nash equilibrium in memoryless strategies, for every ε>0; and exact Nash equilibria need not exist. Upward-closure of an objective means that if a set Z of infinitely repeating states is winning, then all supersets of Z of infinitely repeating states are also winning. Memoryless strategies are strategies that are independent of history of plays and depend only on the current state. We also study the complexity of finding values (payoff profile) of an ε-Nash equilibrium. We show that the values of an ε-Nash equilibrium in nonzero-sum concurrent games with upward-closed objectives for all players can be computed by computing ε-Nash equilibrium values of nonzero-sum concurrent games with reachability objectives for all players and a polynomial procedure. As a consequence we establish that values of an ε-Nash equilibrium can be computed in TFNP (total functional NP), and hence in EXPTIME. AU - Krishnendu Chatterjee ID - 3499 TI - Nash equilibrium for upward-closed objectives VL - 4207 ER - TY - CONF AB - The classical algorithm for solving Bu ̈chi games requires time O(n · m) for game graphs with n states and m edges. For game graphs with constant outdegree, the best known algorithm has running time O(n2/logn). We present two new algorithms for Bu ̈chi games. First, we give an algorithm that performs at most O(m) more work than the classical algorithm, but runs in time O(n) on infinitely many graphs of constant outdegree on which the classical algorithm requires time O(n2). Second, we give an algorithm with running time O(n · m · log δ(n)/ log n), where 1 ≤ δ(n) ≤ n is the outdegree of the game graph. Note that this algorithm performs asymptotically better than the classical algorithm if δ(n) = O(log n). AU - Krishnendu Chatterjee AU - Thomas Henzinger AU - Piterman, Nir ID - 3500 TI - Algorithms for Büchi Games ER - TY - GEN AB - Embodiments automatically generate an accurate network of watertight NURBS patches from polygonal models of objects while automatically detecting and preserving character lines thereon. These embodiments generate from an initial triangulation of the surface, a hierarchy of progressively coarser triangulations of the surface by performing a sequence of edge contractions using a greedy algorithm that selects edge contractions by their numerical properties. Operations are also performed to connect the triangulations in the hierarchy using homeomorphisms that preserve the topology of the initial triangulation in the coarsest triangulation. A desired quadrangulation of the surface can then be generated by homeomorphically mapping edges of a coarsest triangulation in the hierarchy back to the initial triangulation. This quadrangulation is topologically consistent with the initial triangulation and is defined by a plurality of quadrangular patches. These quadrangular patches are linked together by a (U, V) mesh that is guaranteed to be continuous at patch boundaries. A grid is then preferably fit to each of the quadrangles in the resulting quadrangulation by decomposing each of the quadrangles into k.sup.2 smaller quadrangles. A watertight NURBS model may be generated from the resulting quadrangulation. AU - Edelsbrunner, Herbert AU - Fu, Ping AU - Nekhayev, Dmitry AU - Facello, Michael AU - Williams, Steven ID - 3510 TI - Method, apparatus and computer program products for automatically generating NURBS models of triangulated surfaces using homeomorphism ER - TY - GEN AB - Methods, apparatus and computer program products provide efficient techniques for designing and printing shells of hearing-aid devices with a high degree of quality assurance and reliability and with a reduced number of manual and time consuming production steps and operations. These techniques also preferably provide hearing-aid shells having internal volumes that can approach a maximum allowable ratio of internal volume relative to external volume. These high internal volumes facilitate the inclusion of hearing-aid electrical components having higher degrees of functionality and/or the use of smaller and less conspicuous hearing-aid shells. A preferred method includes operations to generate a watertight digital model of a hearing-aid shell by thickening a three-dimensional digital model of a shell surface in a manner that eliminates self-intersections and results in a thickened model having an internal volume that is a high percentage of an external volume of the model. AU - Fu, Ping AU - Nekhayev, Dmitry AU - Edelsbrunner, Herbert ID - 3511 TI - Manufacturing methods and systems for rapid production of hearing-aid shells ER - TY - GEN AB - Methods, apparatus and computer program products provide efficient techniques for reconstructing surfaces from data point sets. These techniques include reconstructing surfaces from sets of scanned data points that have preferably undergone preprocessing operations to improve their quality by, for example, reducing noise and removing outliers. These techniques include reconstructing a dense and locally two-dimensionally distributed 3D point set (e.g., point cloud) by merging stars in two-dimensional weighted Delaunay triangulations within estimated tangent planes. The techniques include determining a plurality of stars from a plurality of points p.sub.i in a 3D point set S that at least partially describes the 3D surface, by projecting the plurality of points p.sub.i onto planes T.sub.i that are each estimated to be tangent about a respective one of the plurality of points p.sub.i. The plurality of stars are then merged into a digital model of the 3D surface. AU - Fletcher, Yates AU - Gloth, Tobias AU - Edelsbrunner, Herbert AU - Fu, Ping ID - 3512 TI - Method, apparatus and computer products that reconstruct surfaces from data points ER - TY - JOUR AB - The functional organization of the basal ganglia ( BG) is often defined according to one of two opposing schemes. The first proposes multiple, essentially independent channels of information processing. The second posits convergence and lateral integration of striatal channels at the level of the globus pallidus ( GP). We tested the hypothesis that these proposed aspects of functional connectivity within the striatopallidal axis are dynamic and related to brain state. Local field potentials ( LFPs) were simultaneously recorded from multiple sites in striatum and GP in anesthetized rats during slow-wave activity( SWA) and during global activation evoked by sensory stimulation. Functional connectivity was inferred from comparative analyses of the internuclear and intranuclear coherence between bipolar derivations of LFPs. During prominent SWA, as shown in the electrocorticogram and local field potentials in the basal ganglia, intranuclear coherence, and, thus, lateral functional connectivity within striatum or globus pallidus was relatively weak. Furthermore, the temporal coupling of LFPs recorded across these two nuclei involved functional convergence at the level of GP. Global activation, indicated by a loss of SWA, was accompanied by a rapid functional reorganization of the striatopallidal axis. Prominent lateral functional connectivity developed within GP and, to a significantly more constrained spatial extent, striatum. Additionally, functional convergence on GP was no longer apparent, despite increased internuclear coherence. These data demonstrate that functional connectivity within the BG is highly dynamic and suggest that the relative expression of organizational principles, such as parallel, independent processing channels, striatopallidal convergence, and lateral integration within BG nuclei, is dependent on brain state. AU - Magill,Peter J AU - Pogosyan,Alek AU - Sharott,Andrew AU - Jozsef Csicsvari AU - Bolam, John Paul AU - Brown,Peter ID - 3545 IS - 23 JF - Journal of Neuroscience TI - Changes in functional connectivity within the rat striatopallidal axis during global brain activation in vivo VL - 26 ER - TY - CONF AB - Persistent homology is the mathematical core of recent work on shape, including reconstruction, recognition, and matching. Its per- tinent information is encapsulated by a pairing of the critical values of a function, visualized by points forming a diagram in the plane. The original algorithm in [10] computes the pairs from an ordering of the simplices in a triangulation and takes worst-case time cubic in the number of simplices. The main result of this paper is an algorithm that maintains the pairing in worst-case linear time per transposition in the ordering. A side-effect of the algorithm’s anal- ysis is an elementary proof of the stability of persistence diagrams [7] in the special case of piecewise-linear functions. We use the algorithm to compute 1-parameter families of diagrams which we apply to the study of protein folding trajectories. AU - Cohen-Steiner, David AU - Herbert Edelsbrunner AU - Morozov, Dmitriy ID - 3559 TI - Vines and vineyards by updating persistence in linear time ER - TY - CONF AB - We continue the study of topological persistence [5] by investigat- ing the problem of simplifying a function f in a way that removes topological noise as determined by its persistence diagram [2]. To state our results, we call a function g an ε-simplification of another function f if ∥f − g∥∞ ≤ ε, and the persistence diagrams of g are the same as those of f except all points within L1-distance at most ε from the diagonal have been removed. We prove that for func- tions f on a 2-manifold such ε-simplification exists, and we give an algorithm to construct them in the piecewise linear case. AU - Herbert Edelsbrunner AU - Morozov, Dmitriy AU - Pascucci, Valerio ID - 3560 TI - Persistence-sensitive simplification of functions on 2-manifolds ER - TY - GEN AU - Pemberton, Josephine M AU - Swanson, Graeme M AU - Nicholas Barton AU - Livingstone, Suzanne R AU - Senn, Helen V ID - 3594 IS - 9 T2 - Deer TI - Hybridisation between red and sika deer in Scotland VL - 13 ER - TY - JOUR AB - Bombina bombina and B. variegata are two anciently diverged toad taxa that have adapted to different breeding habitats yet hybridize freely in zones of overlap where their parapatric distributions meet. Here, we report on a joint genetic and ecological analysis of a hybrid zone in the vicinity of Stryi in western Ukraine. We used five unlinked allozyme loci, two nuclear single nucleotide polymorphisms and a mitochondrial DNA haplotype as genetic markers. Parallel allele frequency clines with a sharp central step occur across a sharp ecotone, where transitions in aquatic habitat, elevation, and terrestrial vegetation coincide. The width of the hybrid zone, estimated as the inverse of the maximum gradient in allele frequency, is 2.3 km. This is the smallest of four estimates derived from different clinal transects across Europe. We argue that the narrow cline near Stryi is mainly due to a combination of habitat distribution and habitat preference. Adult toads show a preference for either ponds (B. bombina) or puddles (B. variegata), which is known to affect the distribution of genotypes within the hybrid zones. At Stryi, it should cause a reduction of the dispersal rate across the ecotone and thus narrow the cline. A detailed comparison of all five intensively studied Bombina transects lends support to the hypothesis that habitat distribution plus habitat preference can jointly affect the structure of hybrid zones and, ultimately, the resulting barriers to gene flow between differentiated gene pools. This study also represents a resampling of an area that was last studied more than 70 years ago. Our allele-frequency clines largely coincide with those that were described then on the basis of morphological variation. However, we found asymmetrical introgression of B. variegata genes into B. bombina territory along the bank of a river. AU - Yanchukov, Alexey AU - Hofman, Sebastian AU - Szymura, Jacek M AU - Mezhzherin, Sergey V AU - Morozov-Leonov, Sviatoslav AU - Nicholas Barton AU - Nürnberger, Beate ID - 3609 IS - 3 JF - Evolution; International Journal of Organic Evolution TI - Hybridization of Bombina bombina and B. variegata (Anura, Discoglossidae) at a sharp ecotone in western Ukraine: comparisons across transects and over time VL - 60 ER - TY - JOUR AB - We study the evolution of inversions that capture locally adapted alleles when two populations are exchanging migrants or hybridizing. By suppressing recombination between the loci, a new inversion can spread. Neither drift nor coadaptation between the alleles (epistasis) is needed, so this local adaptation mechanism may apply to a broader range of genetic and demographic situations than alternative hypotheses that have been widely discussed. The mechanism can explain many features observed in inversion systems. It will drive an inversion to high frequency if there is no countervailing force, which could explain fixed differences observed between populations and species. An inversion can be stabilized at an intermediate frequency if it also happens to capture one or more deleterious recessive mutations, which could explain polymorphisms that are common in some species. This polymorphism can cycle in frequency with the changing selective advantage of the locally favored alleles. The mechanism can establish underdominant inversions that decrease heterokaryotype fitness by several percent if the cause of fitness loss is structural, while if the cause is genic there is no limit to the strength of underdominance that can result. The mechanism is expected to cause loci responsible for adaptive species-specific differences to map to inversions, as seen in recent QTL studies. We discuss data that support the hypothesis, review other mechanisms for inversion evolution, and suggest possible tests. AU - Kirkpatrick, Mark AU - Nicholas Barton ID - 3608 IS - 1 JF - Genetics TI - Chromosome inversions, local adaptation, and speciation VL - 173 ER - TY - JOUR AB - For a model of diallelic loci with arbitrary epistasis, Barton and Turelli [2004. Effects of genetic drift on variance components under a general model of epistasis. Evolution 58, 2111–2132] gave results for variances among and within replicate lines obtained by inbreeding without selection. Here, we discuss the relation between their population genetic methods and classical quantitative genetic arguments. In particular, we consider the case of no dominance using classical identity by descent arguments, which generalizes their results from two alleles to multiple alleles. To clarify the connections between the alternative methods, we obtain the same results using an intermediate method, which explicitly identifies the statistical effects of sets of loci. We also discuss the effects of population bottlenecks on covariances among relatives. AU - Hill, William G AU - Nicholas Barton AU - Turelli, Michael ID - 3610 IS - 1 JF - Theoretical Population Biology TI - Prediction of effects of genetic drift on variance components under a general model of epistasis VL - 70 ER - TY - CONF AB - This paper describes a new system for "Finding Satellite Tracks” in astronomical images based on the modern geometric approach. There is an increasing need of using methods with solid mathematical and statistical foundation in astronomical image processing. Where the computational methods are serving in all disciplines of science, they are becoming popular in the field of astronomy as well. Currently different computational systems are required to be numerically optimized before to get applied on astronomical images. So at present there is no single system which solves the problems of astronomers using computational methods based on modern approaches. The system "Finding Satellite Tracks” is based on geometric matching method "Recognition by Adaptive Subdivision of Transformation Space (RAST)". AU - Ali,Haider AU - Christoph Lampert AU - Breuel,Thomas M ID - 3679 TI - Satellite tracks removal in astronomical images VL - 4225 ER - TY - CONF AB - We propose a video retrieval framework based on a novel combination of spatiograms and the Jensen-Shannon divergence, and validate its performance in two quantitative experiments on TRECVID BBC Rushes data. In the first experiment, color-based methods are tested by grouping redundant shots in an unsupervised clustering. Results of the second experiment show that motion-based spatiograms make a promising fast, compressed-domain descriptor for the detection of interview scenes. AU - Ulges, Adrian AU - Christoph Lampert AU - Keysers,Daniel ID - 3677 TI - Spatiogram-based shot distances for video retrieval ER - TY - CONF AB - The detection of counterfeit in printed documents is currently based mainly on built-in security features or on human expertise. We propose a classification system that supports non-expert users to distinguish original documents from PC-made forgeries by analyzing the printing technique used. Each letter in a document is classified using a support vector machine that has been trained to distinguish laser from inkjet printouts. A color-coded visualization helps the user to interpret the per-letter classification results AU - Christoph Lampert AU - Mei,Lin AU - Breuel,Thomas M ID - 3680 TI - Printing technique classification for document counterfeit detection VL - 1 ER - TY - JOUR AB - We give an analytical and geometrical treatment of what it means to separate a Gaussian kernel along arbitrary axes in Ropfn, and we present a separation scheme that allows us to efficiently implement anisotropic Gaussian convolution filters for data of arbitrary dimensionality. Based on our previous analysis we show that this scheme is optimal with regard to the number of memory accesses and interpolation operations needed. The proposed method relies on nonorthogonal convolution axes and works completely in image space. Thus, it avoids the need for a fast Fourier transform (FFT)-subroutine. Depending on the accuracy and speed requirements, different interpolation schemes and methods to implement the one-dimensional Gaussian (finite impulse response and infinite impulse response) can be integrated. Special emphasis is put on analyzing the performance and accuracy of the new method. In particular, we show that without any special optimization of the source code, it can perform anisotropic Gaussian filtering faster than methods relying on the FFT. AU - Christoph Lampert AU - Wirjadi,Oliver ID - 3695 IS - 11 JF - IEEE Transactions on Image Processing (TIP) TI - An optimal non-orthogonal separation of the anisotropic Gaussian convolution filter VL - 15 ER - TY - CONF AB - Gaussian filtering in one, two or three dimensions is among the most commonly needed tasks in signal and image processing. Finite impulse response filters in the time domain with Gaussian masks are easy to implement in either floating or fixed point arithmetic, because Gaussian kernels are strictly positive and bounded. But these implementations are slow for large images or kernels. With the recursive IIR-filters and FFT-based methods, there are at least two alternative methods to perform Gaussian filtering in a faster way, but so far they are only applicable when floating-point hardware is available. In this paper, a fixed-point implementation of recursive Gaussian filtering is discussed and applied to isotropic and anisotropic image filtering by making use of a non-orthogonal separation scheme of the Gaussian filter. AU - Christoph Lampert AU - Wirjadi,Oliver ID - 3693 TI - Anisotropic Gaussian filtering using fixed point arithmetic ER - TY - CONF AU - Keysers,Daniel AU - Christoph Lampert AU - Breuel,Thomas M ID - 3692 TI - Color image dequantization by constrained diffusion VL - 6058 ER - TY - JOUR AB - Measuring the visco-elastic properties of biological macromolecules constitutes an important step towards the understanding of dynamic biological processes, such as cell adhesion, muscle function, or plant cell wall stability. Force spectroscopy techniques based on the atomic force microscope (AFM) are increasingly used to study the complex visco-elastic response of (bio-)molecules on a single-molecule level. These experiments either require that the AFM cantilever is actively oscillated or that the molecule is clamped at constant force to monitor thermal cantilever motion. Here we demonstrate that the visco-elasticity of single bio-molecules can readily be extracted from the Brownian cantilever motion during conventional force-extension measurements. It is shown that the characteristics of the cantilever determine the signal-to-noise (S/N) ratio and time resolution. Using a small cantilever, the visco-elastic properties of single dextran molecules were resolved with a time resolution of 8.3 ms. The presented approach can be directly applied to probe the dynamic response of complex bio-molecular systems or proteins in force-extension experiments. AU - Bippes, Christian A AU - Humphris, Andrew D AU - Stark, Martin AU - Mueller, Daniel J AU - Harald Janovjak ID - 3729 IS - 3 JF - European Biophysics Journal TI - Direct measurement of single-molecule visco-elasticity in atomic force microscope force-extension experiments VL - 35 ER - TY - JOUR AB - Mechanical unfolding of single bacteriorhodopsins from a membrane bilayer is studied using molecular dynamics simulations. The initial conformation of the lipid membrane is determined through all-atom simulations and then its coarse-grained representation is used in the studies of stretching. A Go-like model with a realistic contact map and with Lennard–Jones contact interactions is applied to model the protein–membrane system. The model qualitatively reproduces the experimentally observed differences between force-extension patterns obtained on bacteriorhodopsin at different temperatures and predicts a lack of symmetry in the choice of the terminus to pull by. It also illustrates the decisive role of the interactions of the protein with the membrane in determining the force pattern and thus the stability of transmembrane proteins. AU - Cieplak, Marek AU - Filipek, Sławomir AU - Harald Janovjak AU - Krzysko, Krystiana A ID - 3728 IS - 4 JF - Biochimica et Biophysica Acta (BBA) - Biomembranes TI - Pulling single bacteriorhodopsin out of a membrane: Comparison of simulation and experiment VL - 1758 ER - TY - CHAP AU - Harald Janovjak AU - Mueller, Daniel J ID - 3722 T2 - Bioanalytik TI - Rastersondenmikroskopie ER - TY - JOUR AB - A primitive example of adaptation in gene expression is the balance between the rate of synthesis and degradation of cellular RNA, which allows rapid responses to environmental signals. Here, we investigate how multidrug efflux pump systems mediate the dynamics of a simple drug-inducible system in response to a steady level of inducer. Using fluorescence correlation spectroscopy, we measured in real time within a single bacterium the transcription activity at the RNA level of the acrAB-TolC multidrug efflux pump system. When cells are exposed to constant level of anhydrotetracycline inducer and are adsorbed onto a poly-L-lysine-coated surface, we found that the acrAB-TolC promoter is steadily active. We also monitored the activity of the tet promoter to characterize the effect of this efflux system on the dynamics of drug-inducible transcription. We found that the transcriptional response of the tet promoter to a steady level of aTc rises and then falls back to its preinduction level. The rate of RNA degradation was constant throughout the transcriptional pulse, indicating that the modulation of intracellular inducer concentration alone can produce this pulsating response. Single-cell experiments together with numerical simulations suggest that such pulsating response in drug-inducible genetic systems is a property emerging from the dependence of drug-inducible transcription on multidrug efflux systems. AU - Le,Thuc T. AU - Emonet,Thierry AU - Harlepp, Sébastien AU - Calin Guet AU - Cluzel,Philippe ID - 3755 IS - 9 JF - Biophysical Journal TI - Dynamical determinants of drug-inducible gene expression in a single bacterium VL - 90 ER - TY - CONF AB - Control of physical simulation has become a popular topic in the field of computer graphics. Keyframe control has been applied to simulations of rigid bodies, smoke, liquid, flocks, and finite element-based elastic bodies. In this paper, we create a framework for controlling systems of interacting particles -- paying special attention to simulations of cloth and flocking behavior. We introduce a novel integrator-swapping approximation in order to apply the adjoint method to linearized implicit schemes appropriate for cloth simulation. This allows the control of cloth while avoiding computationally infeasible derivative calculations. Meanwhile, flocking control using the adjoint method is significantly more efficient than currently-used methods for constraining group behaviors, allowing the controlled simulation of greater numbers of agents in fewer optimization iterations. AU - Wojtan, Christopher J AU - Mucha, Peter AU - Turk, Greg ID - 3758 TI - Keyframe control of complex particle systems using the adjoint method ER - TY - JOUR AB - Rigorous analysis of synaptic transmission in the central nervous system requires access to presynaptic terminals. However, cortical terminals have been largely inaccessible to presynaptic patch-clamp recording, due to their small size. Using improved patch-clamp techniques in brain slices, we recorded from mossy fiber terminals in the CA3 region of the hippocampus, which have a diameter of 2-5 microm. The major steps of improvement were the enhanced visibility provided by high-numerical aperture objectives and infrared illumination, the development of vibratomes with minimal vertical blade vibrations and the use of sucrose-based solutions for storage and cutting. Based on these improvements, we describe a protocol that allows us to routinely record from hippocampal mossy fiber boutons. Presynaptic recordings can be obtained in slices from both rats and mice. Presynaptic recordings can be also obtained in slices from transgenic mice in which terminals are labeled with enhanced green fluorescent protein. AU - Bischofberger, Josef AU - Engel, Dominique AU - Li, Liyi AU - Geiger, Jörg R AU - Peter Jonas ID - 3818 IS - 4 JF - Nature Protocols TI - Patch-clamp recording from mossy fiber terminals in hippocampal slices VL - 1 ER - TY - CONF AB - We consider two-player infinite games played on graphs. The games are concurrent, in that at each state the players choose their moves simultaneously and independently, and stochastic, in that the moves determine a probability distribution for the successor state. The value of a game is the maximal probability with which a player can guarantee the satisfaction of her objective. We show that the values of concurrent games with w-regular objectives expressed as parity conditions can be decided in NP boolean AND coNP. This result substantially improves the best known previous bound of 3EXPTIME. It also shows that the full class of concurrent parity games is no harder than the special case of turn-based stochastic reachability games, for which NP boolean AND coNP is the best known bound. While the previous, more restricted NP boolean AND coNP results for graph games relied on the existence of particularly simple (pure memoryless) optimal strategies, in concurrent games with parity objectives optimal strategies may not exist, and epsilon-optimal strategies (which achieve the value of the game within a parameter epsilon > 0) require in general both randomization and infinite memory. Hence our proof must rely on a more detailed analysis of strategies and, in addition to the main result, yields two results that are interesting on their own. First, we show that there exist epsilon-optimal strategies that in the limit coincide with memoryless strategies; this parallels the celebrated result of Mertens-Neyman for concurrent games with limit-average objectives. Second, we complete the characterization of the memory requirements for epsilon-optimal strategies for concurrent games with parity conditions, by showing that memoryless strategies suffice for epsilon-optimality for coBachi conditions. AU - Krishnendu Chatterjee AU - de Alfaro, Luca AU - Thomas Henzinger ID - 3890 TI - The complexity of quantitative concurrent parity games ER - TY - CONF AB - We study observation-based strategies for two-player turn-based games on graphs with omega-regular objectives. An observation-based strategy relies on imperfect information about the history of a play, namely, on the past sequence of observations. Such games occur in the synthesis of a controller that does not see the private state of the plant. Our main results are twofold. First, we give a fixed-point algorithm for computing the set of states from which a player can win with a deterministic observation-based strategy for any omega-regular objective. The fixed point is computed in the lattice of antichains of state sets. This algorithm has the advantages of being directed by the objective and of avoiding an explicit subset construction on the game graph. Second, we give an algorithm for computing the set of states from which a player can win with probability 1 with a randomized observation-based strategy for a Buchi objective. This set is of interest because in the absence of perfect information, randomized strategies are more powerful than deterministic ones. We show that our algorithms are optimal by proving matching lower bounds. AU - Krishnendu Chatterjee AU - Doyen, Laurent AU - Thomas Henzinger AU - Raskin, Jean-François ID - 3889 TI - Algorithms for omega-regular games with imperfect information VL - 4207 ER - TY - CONF AB - We study infinite stochastic games played by two-players over a finite state space, with objectives specified by sets of infinite traces. The games are concurrent (players make moves simultaneously and independently), stochastic (the next state is determined by a probability distribution that depends on the current state and chosen moves of the players) and infinite (proceeds for infinite number of rounds). The analysis of concurrent stochastic games can be classified into: quantitative analysis, analyzing the optimum value of the game; and qualitative analysis, analyzing the set of states with optimum value 1. We consider concurrent games with tail objectives, i.e., objectives that are independent of the finite-prefix of traces, and show that the class of tail objectives are strictly richer than the omega-regular objectives. We develop new proof techniques to extend several properties of concurrent games with omega-regular objectives to concurrent games with tail objectives. We prove the positive limit-one property for tail objectives, that states for all concurrent games if the optimum value for a player is positive for a tail objective Phi at some state, then there is a state where the optimum value is 1 for Phi, for the player. We also show that the optimum values of zero-sum (strictly conflicting objectives) games with tail objectives can be related to equilibrium values of nonzero-sum (not strictly conflicting objectives) games with simpler reachability objectives. A consequence of our analysis presents a polynomial time reduction of the quantitative analysis of tail objectives to the qualitative analysis for the sub-class of one-player stochastic games (Markov decision processes). AU - Krishnendu Chatterjee ID - 3891 TI - Concurrent games with tail objectives VL - 4207 ER - TY - CONF AB - A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with omega-regular winning conditions specified as Rabin or Streett objectives. These games are NP-complete and coNP-complete, respectively. The value of the game for a player at a state s given an objective Phi is the maximal probability with which the player can guarantee the satisfaction of Phi from s. We present a strategy-improvement algorithm to compute values in stochastic Rabin games, where an improvement step involves solving Markov decision processes (MDPs) and nonstochastic Rabin games. The algorithm also computes values for stochastic Streett games but does not directly yield an optimal strategy for Streett objectives. We then show how to obtain an optimal strategy for Streett objectives by solving certain nonstochastic Streett games. AU - Krishnendu Chatterjee AU - Thomas Henzinger ID - 3888 TI - Strategy improvement for stochastic Rabin and Streett games VL - 4137 ER - TY - JOUR AB - It is commonly believed that both the average length and the frequency of microsatellites correlate with genome size. We have estimated the frequency and the average length for 69 perfect dinucleotide microsatellites in an insect with an exceptionally large genome: Chorthippus biguttulus (Orthoptera, Acrididae). Dinucleotide microsatellites are not more frequent in C. biguttulus, but repeat arrays are 1.4 to 2 times longer than in other insect species. The average repeat number in C. biguttulus lies in the range of higher vertebrates. Natural populations are highly variable. At least 30 alleles per locus were found and the expected heterozygosity is above 0.95 at all three loci studied. In contrast, the observed heterozygosity is much lower (≤0.51), which could be caused by long null alleles. AU - Ustinova, Jana AU - Achmann, Roland AU - Cremer, Sylvia AU - Mayer, Frieder ID - 3908 IS - 2 JF - Journal of Molecular Evolution TI - Long repeats in a huge gemome: microsatellite loci in the grasshopper Chorthippus biguttulus VL - 62 ER - TY - JOUR AB - T cells develop in the thymus in a highly specialized cellular and extracellular microenvironment. The basement membrane molecule, laminin-5 (LN-5), is predominantly found in the medulla of the human thymic lobules. Using high-resolution light microscopy, we show here that LN-5 is localized in a bi-membranous conduit-like structure, together with other typical basement membrane components including collagen type IV, nidogen and perlecan. Other interstitial matrix components, such as fibrillin-1 or -2, tenascin-C or fibrillar collagen types, were also associated with these structures. Three-dimensional (3D) confocal microscopy suggested a tubular structure, whereas immunoelectron and transmission electron microscopy showed that the core of these tubes contained fibrillar collagens enwrapped by the LN-5-containing membrane. These medullary conduits are surrounded by thymic epithelial cells, which in vitro were found to bind LN-5, but also fibrillin and tenascin-C. Dendritic cells were also detected in close vicinity to the conduits. Both of these stromal cell types express major histocompatibility complex (MHC) class II molecules capable of antigen presentation. The conduits are connected to blood vessels but, with an average diameter of 2 mum, they are too small to transport cells. However, evidence is provided that smaller molecules such as a 10 kDa dextran, but not large molecules (>500 kDa), can be transported in the conduits. These results clearly demonstrate that a conduit system, which is also known from secondary lymphatic organs such as lymph nodes and spleen, is present in the medulla of the human thymus, and that it might serve to transport small blood-borne molecules or chemokines to defined locations within the medulla. AU - Drumea-Mirancea, Mihaela AU - Wessels, Johannes T AU - Müller, Claudia A AU - Essl, Mike AU - Eble, Johannes A AU - Tolosa, Eva AU - Koch, Manuel AU - Reinhardt, Dieter P AU - Michael Sixt AU - Sorokin, Lydia AU - Stierhof, York-Dieter AU - Schwarz, Heinz AU - Klein, Gerd ID - 3934 IS - Pt 7 JF - Journal of Cell Science TI - Characterization of a conduit system containing laminin-5 in the human thymus: a potential transport system for small molecules VL - 119 ER - TY - JOUR AB - Integrins regulate cell behavior through the assembly of multiprotein complexes at the site of cell adhesion. Parvins are components of such a multiprotein complex. They consist of three members (alpha-, beta-, and gamma-parvin), form a functional complex with integrin-linked kinase (ILK) and PINCH, and link integrins to the actin cytoskeleton. Whereas alpha- and beta-parvins are widely expressed, gamma-parvin has been reported to be expressed in hematopoietic organs. In the present study, we report the expression pattern of the parvins in hematopoietic cells and the phenotypic analysis of gamma-parvin-deficient mice. Whereas alpha-parvin is not expressed in hematopoietic cells, beta-parvin is only found in myeloid cells and gamma-parvin is present in both cells of the myeloid and lymphoid lineages, where it binds ILK. Surprisingly, loss of gamma-parvin expression had no effect on blood cell differentiation, proliferation, and survival and no consequence for the T-cell-dependent antibody response and lymphocyte and dendritic cell migration. These data indicate that despite the high expression of gamma-parvin in hematopoietic cells it must play a more subtle role for blood cell homeostasis. AU - Chu, Haiyan AU - Thievessen, Ingo AU - Michael Sixt AU - Lämmermann, Tim AU - Waisman, Ari AU - Braun, Attila AU - Noegel, Angelika A AU - Fässler, Reinhard ID - 3935 IS - 5 JF - Molecular and Cellular Biology TI - γ-Parvin is dispensable for hematopoiesis, leukocyte trafficking, and T-cell-dependent antibody response VL - 26 ER - TY - JOUR AB - At least eight of the twelve known members of the beta1 integrin family are expressed on hematopoietic cells. Among these, the VCAM-1 receptor alpha4beta1 has received most attention as a main factor mediating firm adhesion to the endothelium during blood cell extravasation. Therapeutic trials are ongoing into the use of antibodies and small molecule inhibitors to target this interaction and hence obtain anti-inflammatory effects. However, extravasation is only one possible process that is mediated by beta1 integrins and there is evidence that they also mediate leukocyte retention and positioning in the tissue, lymphocyte activation and possibly migration within the interstitium. Genetic mouse models where integrins are selectively deleted on blood cells have been used to investigate these functions and further studies will be invaluable to critically evaluate therapeutic trials. AU - Michael Sixt AU - Bauer, Martina AU - Lämmermann, Tim AU - Fässler, Reinhard ID - 3936 IS - 5 JF - Current Opinion in Cell Biology TI - β1 integrins: zip codes and signaling relay for blood cells VL - 18 ER - TY - JOUR AB - Wnt11 is a key signal, determining cell polarization and migration during vertebrate gastrulation. It is known that Wnt11 functionally interacts with several signaling components, the homologues of which control planar cell polarity in Drosophila melanogaster. Although in D. melanogaster these components are thought to polarize cells by asymmetrically localizing at the plasma membrane, it is not yet clear whether their subcellular localization plays a similarly important role in vertebrates. We show that in zebrafish embryonic cells, Wnt11 locally functions at the plasma membrane by accumulating its receptor, Frizzled 7, on adjacent sites of cell contacts. Wnt11-induced Frizzled 7 accumulations recruit the intracellular Wnt signaling mediator Dishevelled, as well as Wnt11 itself, and locally increase cell contact persistence. This increase in cell contact persistence is mediated by the local interaction of Wnt11, Frizzled 7, and the atypical cadherin Flamingo at the plasma membrane, and it does not require the activity of further downstream effectors of Wnt11 signaling, such as RhoA and Rok2. We propose that Wnt11, by interacting with Frizzled 7 and Flamingo, modulates local cell contact persistence to coordinate cell movements during gastrulation. AU - Witzel, Sabine AU - Zimyanin, Vitaly AU - Carreira Barbosa, Filipa AU - Tada, Masazumi AU - Heisenberg, Carl-Philipp J ID - 4140 IS - 5 JF - Journal of Cell Biology TI - Wnt11 controls cell contact persistence by local accumulation of Frizzled 7 at the plasma membrane VL - 175 ER - TY - JOUR AB - The detection of microRNAs (miRNAs) at single-cell resolution is important for studying the role of these posttranscriptional regulators. Here, we use a dual-fluorescent green fluorescent protein (GFP)-reporter/monomeric red fluorescent protein (mRFP)-sensor (DFRS) plasmid, injected into zebrafish blastomeres or electroporated into defined tissues of mouse embryos in utero or ex utero, to monitor the dynamics of specific miRNAs in individual live cells. This approach reveals, for example, that in the developing mouse central nervous system,, miR-124a is expressed not only in postmitotic neurons but also in neuronal progenitor cells. Collectively, our results demonstrate that acute administration of DFRS plasmids.offers an alternative to previous in situ hybridization and transgenic approaches and allows the monitoring of miRNA appearance and disappearance in defined cell lineages during vertebrate development. AU - Tonelli, Davide AU - Calegari, Frederico AU - Fei, Ji AU - Nomura, Tadashi AU - Osumi, Noriko AU - Heisenberg, Carl-Philipp J AU - Huttner, Wieland ID - 4145 IS - 6 JF - Biotechniques TI - Single-cell detection of microRNAs in developing vertebrate embryos after acute administration of a dual-fluorescence reporter/sensor plasmid VL - 41 ER - TY - JOUR AB - During vertebrate gastrulation, a well-orchestrated series of morphogenetic changes leads to the formation of the three germ layers: the ectoderm, mesoderm and endoderm. The analysis of gene expression patterns during gastrulation has been central to the identification of genes involved in germ layer formation. However, many proteins are regulated on a translational or post-translational level and are thus undetectable by gene expression analysis. Therefore, we developed a 2D-gel-based comparative proteomic approach to target proteins involved in germ layer morphogenesis during zebrafish gastrulation. Proteomes of ectodermal and mesendodermal progenitor cells were compared and 35 significantly regulated proteins were identified by mass spectrometry, including several proteins with predicted functions in cytoskeletal organization. A comparison of our proteomic results with data obtained in an accompanying microarray-based gene expression analysis revealed no significant overlap, confirming the complementary nature of proteomics and transcriptomics. The regulation of ezrin2, which was identified based on a reduction in spot intensity in mesendodermal cells, was independently validated. Furthermore, we show that ezrin2 is activated by phosphorylation in mesendodermal cells and is required for proper germ layer morphogenesis. We demonstrate the feasibility of proteomics in zebrafish, concluding that proteomics is a valuable tool for analysis of early development. AU - Link, Vinzenz AU - Carvalho, Lara AU - Castanon, Irinka AU - Stockinger, Petra AU - Shevchenko, Andrej AU - Heisenberg, Carl-Philipp J ID - 4176 IS - 10 JF - Journal of Cell Science TI - Identification of regulators of germ layer morphogenesis using proteomics in zebrafish VL - 119 ER - TY - JOUR AB - Background: Zebrafish (D. rerio) has become a powerful and widely used model system for the analysis of vertebrate embryogenesis and organ development. While genetic methods are readily available in zebrafish, protocols for two dimensional (2D) gel electrophoresis and proteomics have yet to be developed. Results: As a prerequisite to carry out proteomic experiments with early zebrafish embryos, we developed a method to efficiently remove the yolk from large batches of embryos. This method enabled high resolution 2D gel electrophoresis and improved Western blotting considerably. Here, we provide detailed protocols for proteomics in zebrafish from sample preparation to mass spectrometry (MS), including a comparison of databases for MS identification of zebrafish proteins. Conclusion: The provided protocols for proteomic analysis of early embryos enable research to be taken in novel directions in embryogenesis. AU - Link, Vinzenz AU - Shevchenko, Andrej AU - Heisenberg, Carl-Philipp J ID - 4173 JF - BMC Developmental Biology TI - Proteomics of early zebrafish embryos VL - 6 ER - TY - JOUR AB - Detailed reconstruction of the spatiotemporal history of embryonic cells is key to understanding tissue formation processes but is often complicated by the large number of cells involved, particularly so in vertebrates. Through a combination of high-resolution time-lapse lineage tracing and antibody staining, we have analyzed the movement of mesencephalic and metencephalic cell populations in the early zebrafish embryo. To facilitate the analysis of our cell tracking data, we have created TracePilot, a software tool that allows interactive manipulation and visualization of tracking data. We demonstrate its utility by showing novel visualizations of cell movement in the developing zebrafish brain. TracePilot (http://www.mpi-cbg.de/tracepilot) is Java-based, available free of charge, and has a program structure that allows the incorporation of additional analysis tools. AU - Langenberg, Tobias AU - Dracz, Tadeusz AU - Oates, Andrew AU - Heisenberg, Carl-Philipp J AU - Brand, Michael ID - 4178 IS - 4 JF - Developmental Dynamics TI - Analysis and visualization of cell movement in the developing zebrafish brain VL - 235 ER - TY - JOUR AB - Epithelial morphogenesis depends on coordinated changes in cell shape, a process that is still poorly understood. During zebrafish epiboly and Drosophila dorsal closure, cell-shape changes at the epithelial margin are of critical importance. Here evidence is provided for a conserved mechanism of local actin and myosin 2 recruitment during theses events. It was found that during epiboly of the zebrafish embryo, the movement of the outer epithelium (enveloping layer) over the yolk cell surface involves the constriction of marginal cells. This process depends on the recruitment of actin and myosin 2 within the yolk cytoplasm along the margin of the enveloping layer. Actin and myosin 2 recruitment within the yolk cytoplasm requires the Ste20-like kinase Msn1, an orthologue of Drosophila Misshapen. Similarly, in Drosophila, actin and myosin 2 localization and cell constriction at the margin of the epidermis mediate dorsal closure and are controlled by Misshapen. Thus, this study has characterized a conserved mechanism underlying coordinated cell-shape changes during epithelial morphogenesis. AU - Köppen, Mathias AU - Fernández, Beatriz AU - Carvalho, Lara AU - Jacinto, António AU - Heisenberg, Carl-Philipp J ID - 4184 IS - 14 JF - Development TI - Coordinated cell-shape changes control epithelial movement in zebrafish and Drosophila VL - 133 ER - TY - JOUR AB - The molecular and cellular mechanisms governing cell motility and directed migration in response to the chemokine SDF-1 are largely unknown. Here, we demonstrate that zebrafish primordial germ cells whose migration is guided by SDF-1 generate bleb-like protrusions that are powered by cytoplasmic flow. Protrusions are formed at sites of higher levels of free calcium where activation of myosin contraction occurs. Separation of the acto-myosin cortex from the plasma membrane at these sites is followed by a flow of cytoplasm into the forming bleb. We propose that polarized activation of the receptor CXCR4 leads to a rise in free calcium that in turn activates myosin contraction in the part of the cell responding to higher levels of the ligand SDF-1. The biased formation of new protrusions in a particular region of the cell in response to SDF-1 defines the leading edge and the direction of cell migration. AU - Blaser, Heiko AU - Reichman Fried, Michal AU - Castanon, Irinka AU - Dumstrei, Karin AU - Marlow, Florence AU - Kawakami, Koichi AU - Solnica Krezel, Lilianna AU - Heisenberg, Carl-Philipp J AU - Raz, Erez ID - 4218 IS - 5 JF - Developmental Cell TI - Migration of zebrafish primordial germ cells: A role for myosin contraction and cytoplasmic flow VL - 11 ER - TY - JOUR AB - The growth function of populations is central in biomathematics. The main dogma is the existence of density-dependence mechanisms, which can be modelled with distinct functional forms that depend on the size of the Population. One important class of regulatory functions is the theta-logistic, which generalizes the logistic equation. Using this model as a motivation, this paper introduces a simple dynamical reformulation that generalizes many growth functions. The reformulation consists of two equations, one for population size, and one for the growth rate. Furthermore, the model shows that although population is density-dependent, the dynamics of the growth rate does not depend either on population size, nor on the carrying capacity. Actually, the growth equation is uncoupled from the population size equation, and the model has only two parameters, a Malthusian parameter rho and a competition coefficient theta. Distinct sign combinations of these parameters reproduce not only the family of theta-logistics, but also the van Bertalanffy, Gompertz and Potential Growth equations, among other possibilities. It is also shown that, except for two critical points, there is a general size-scaling relation that includes those appearing in the most important allometric theories, including the recently proposed Metabolic Theory of Ecology. With this model, several issues of general interest are discussed such as the growth of animal population, extinctions, cell growth and allometry, and the effect of environment over a population. (c) 2005 Elsevier Ltd. All rights reserved. AU - de Vladar, Harold ID - 4237 IS - 2 JF - Journal of Theoretical Biology TI - Density-dependence as a size-independent regulatory mechanism VL - 238 ER - TY - JOUR AU - Harold Vladar AU - González,J. A ID - 4235 JF - Journal of Theoretical Biology TI - Dynamic response of cancer under the influence of immunological activity and therapy ER - TY - JOUR AB - In finite populations, genetic drift generates interference between selected loci, causing advantageous alleles to be found more often on different chromosomes than on the same chromosome, which reduces the rate of adaptation. This “Hill–Robertson effect” generates indirect selection to increase recombination rates. We present a new method to quantify the strength of this selection. Our model represents a new beneficial allele (A) entering a population as a single copy, while another beneficial allele (B) is sweeping at another locus. A third locus affects the recombination rate between selected loci. Using a branching process model, we calculate the probability distribution of the number of copies of A on the different genetic backgrounds, after it is established but while it is still rare. Then, we use a deterministic model to express the change in frequency of the recombination modifier, due to hitchhiking, as A goes to fixation. We show that this method can give good estimates of selection for recombination. Moreover, it shows that recombination is selected through two different effects: it increases the fixation probability of new alleles, and it accelerates selective sweeps. The relative importance of these two effects depends on the relative times of occurrence of the beneficial alleles. AU - Roze, Denis AU - Nicholas Barton ID - 4248 IS - 3 JF - Genetics TI - The Hill-Robertson effect and the evolution of recombination VL - 173 ER - TY - GEN AB - A recent analysis has shown that divergence between human and chimpanzee varies greatly across the genome. Although this is consistent with ‘hybridisation’ between the diverging human and chimp lineages, such observations can be explained more simply by the null model of allopatric speciation. AU - Nicholas Barton ID - 4250 IS - 16 T2 - Current Biology TI - Evolutionary Biology: How did the human species form? VL - 16 ER - TY - CONF AU - Thomas Wies AU - Kuncak, Viktor AU - Lam,Patrick AU - Podelski,Andreas AU - Rinard,Martin ID - 4359 TI - Field Constraint Analysis ER - TY - CONF AU - Maler, Oded AU - Dejan Nickovic AU - Pnueli,Amir ID - 4373 TI - Real Time Temporal Logic: Past, Present, Future ER - TY - CONF AU - Maler, Oded AU - Dejan Nickovic AU - Pnueli,Amir ID - 4374 TI - From MITL to Timed Automata ER - TY - CONF AB - We propose and evaluate a new algorithm for checking the universality of nondeterministic finite automata. In contrast to the standard algorithm, which uses the subset construction to explicitly determinize the automaton, we keep the determinization step implicit. Our algorithm computes the least fixed point of a monotone function on the lattice of antichains of state sets. We evaluate the performance of our algorithm experimentally using the random automaton model recently proposed by Tabakov and Vardi. We show that on the difficult instances of this probabilistic model, the antichain algorithm outperforms the standard one by several orders of magnitude. We also show how variations of the antichain method can be used for solving the language-inclusion problem for nondeterministic finite automata, and the emptiness problem for alternating finite automata. AU - De Wulf, Martin AU - Doyen, Laurent AU - Thomas Henzinger AU - Raskin, Jean-François ID - 4406 TI - Antichains: A new algorithm for checking universality of finite automata VL - 4144 ER - TY - CONF AU - Alur, Rajeev AU - Pavol Cerny AU - Zdancewic,Steve ID - 4401 TI - Preserving Secrecy Under Refinement ER - TY - CONF AB - The synthesis of reactive systems requires the solution of two-player games on graphs with ω-regular objectives. When the objective is specified by a linear temporal logic formula or nondeterministic Büchi automaton, then previous algorithms for solving the game require the construction of an equivalent deterministic automaton. However, determinization for automata on infinite words is extremely complicated, and current implementations fail to produce deterministic automata even for relatively small inputs. We show how to construct, from a given nondeterministic Büchi automaton, an equivalent nondeterministic parity automaton that is good for solving games with objective . The main insight is that a nondeterministic automaton is good for solving games if it fairly simulates the equivalent deterministic automaton. In this way, we omit the determinization step in game solving and reactive synthesis. The fact that our automata are nondeterministic makes them surprisingly simple, amenable to symbolic implementation, and allows an incremental search for winning strategies. AU - Thomas Henzinger AU - Piterman, Nir ID - 4437 TI - Solving games without determinization VL - 4207 ER -