TY - JOUR AB - Genetic regulatory networks enable cells to respond to changes in internal and external conditions by dynamically coordinating their gene expression profiles. Our ability to make quantitative measurements in these biochemical circuits has deepened our understanding of what kinds of computations genetic regulatory networks can perform, and with what reliability. These advances have motivated researchers to look for connections between the architecture and function of genetic regulatory networks. Transmitting information between a network's inputs and outputs has been proposed as one such possible measure of function, relevant in certain biological contexts. Here we summarize recent developments in the application of information theory to gene regulatory networks. We first review basic concepts in information theory necessary for understanding recent work. We then discuss the functional complexity of gene regulation, which arises from the molecular nature of the regulatory interactions. We end by reviewing some experiments that support the view that genetic networks responsible for early development of multicellular organisms might be maximizing transmitted 'positional information'. AU - Tkacik, Gasper AU - Walczak, Aleksandra ID - 3374 IS - 15 JF - Journal of Physics: Condensed Matter TI - Information transmission in genetic regulatory networks a review VL - 23 ER - TY - JOUR AB - Tissue surface tension (TST) is an important mechanical property influencing cell sorting and tissue envelopment. The study by Manning et al. (1) reported on a mathematical model describing TST on the basis of the balance between adhesive and tensile properties of the constituent cells. The model predicts that, in high-adhesion cell aggregates, surface cells will be stretched to maintain the same area of cell–cell contact as interior bulk cells, resulting in an elongated and flattened cell shape. The authors (1) observed flat and elongated cells at the surface of high-adhesion zebrafish germ-layer explants, which they argue are undifferentiated stretched germ-layer progenitor cells, and they use this observation as a validation of their model. AU - Krens, Gabriel AU - Möllmert, Stephanie AU - Heisenberg, Carl-Philipp J ID - 3368 IS - 3 JF - PNAS TI - Enveloping cell layer differentiation at the surface of zebrafish germ layer tissue explants VL - 108 ER - TY - JOUR AB - Supertree methods are widely applied and give rise to new conclusions about phylogenies (e.g., Bininda-Emonds et al. 2007). Although several desiderata for supertree methods exist (Wilkinson, Thorley, et al. 2004), only few of them have been studied in greater detail, examples include shape bias (Wilkinson et al. 2005) or pareto properties (Wilkinson et al. 2007). Here I look more closely at two matrix representation methods, matrix representation with compatibility (MRC) and matrix representation with parsimony (MRP). Different null models of random data are studied and the resulting tree shapes are investigated. Thereby I consider unrooted trees and a bias in tree shape is determined by a tree balance measure. The measure for unrooted trees is a modification of a tree balance measure for rooted trees. I observe that depending on the underlying null model of random data, the methods may resolve conflict in favor of more balanced tree shapes. The analyses refer only to trees with the same taxon set, also known as the consensus setting (e.g., Wilkinson et al. 2007), but I will be able to draw conclusions on how to deal with missing data. AU - Kupczok, Anne ID - 3370 IS - 2 JF - Systematic Biology TI - Consequences of different null models on the tree shape bias of supertree methods VL - 60 ER - TY - JOUR AB - Rab3 interacting molecules (RIMs) are highly enriched in the active zones of presynaptic terminals. It is generally thought that they operate as effectors of the small G protein Rab3. Three recent papers, by Han et al. (this issue of Neuron), Deng et al. (this issue of Neuron), and Kaeser et al. (a recent issue of Cell), shed new light on the functional role of RIM in presynaptic terminals. First, RIM tethers Ca2+ channels to active zones. Second, RIM contributes to priming of synaptic vesicles by interacting with another presynaptic protein, Munc13. AU - Pernia-Andrade, Alejandro AU - Jonas, Peter M ID - 3369 IS - 2 JF - Neuron TI - The multiple faces of RIM VL - 69 ER - TY - JOUR AB - Facial branchiomotor neurons (FBMNs) in zebrafish and mouse embryonic hindbrain undergo a characteristic tangential migration from rhombomere (r) 4, where they are born, to r6/7. Cohesion among neuroepithelial cells (NCs) has been suggested to function in FBMN migration by inhibiting FBMNs positioned in the basal neuroepithelium such that they move apically between NCs towards the midline of the neuroepithelium instead of tangentially along the basal side of the neuroepithelium towards r6/7. However, direct experimental evaluation of this hypothesis is still lacking. Here, we have used a combination of biophysical cell adhesion measurements and high-resolution time-lapse microscopy to determine the role of NC cohesion in FBMN migration. We show that reducing NC cohesion by interfering with Cadherin 2 (Cdh2) activity results in FBMNs positioned at the basal side of the neuroepithelium moving apically towards the neural tube midline instead of tangentially towards r6/7. In embryos with strongly reduced NC cohesion, ectopic apical FBMN movement frequently results in fusion of the bilateral FBMN clusters over the apical midline of the neural tube. By contrast, reducing cohesion among FBMNs by interfering with Contactin 2 (Cntn2) expression in these cells has little effect on apical FBMN movement, but reduces the fusion of the bilateral FBMN clusters in embryos with strongly diminished NC cohesion. These data provide direct experimental evidence that NC cohesion functions in tangential FBMN migration by restricting their apical movement. AU - Stockinger, Petra AU - Heisenberg, Carl-Philipp J AU - Maître, Jean-Léon ID - 3396 IS - 21 JF - Development TI - Defective neuroepithelial cell cohesion affects tangential branchiomotor neuron migration in the zebrafish neural tube VL - 138 ER - TY - JOUR AB - Random genetic drift shifts clines in space, alters their width, and distorts their shape. Such random fluctuations complicate inferences from cline width and position. Notably, the effect of genetic drift on the expected shape of the cline is opposite to the naive (but quite common) misinterpretation of classic results on the expected cline. While random drift on average broadens the overall cline in expected allele frequency, it narrows the width of any particular cline. The opposing effects arise because locally, drift drives alleles to fixation—but fluctuations in position widen the expected cline. The effect of genetic drift can be predicted from standardized variance in allele frequencies, averaged across the habitat: 〈F〉. A cline maintained by spatially varying selection (step change) is expected to be narrower by a factor of relative to the cline in the absence of drift. The expected cline is broader by the inverse of this factor. In a tension zone maintained by underdominance, the expected cline width is narrower by about 1 – 〈F〉relative to the width in the absence of drift. Individual clines can differ substantially from the expectation, and we give quantitative predictions for the variance in cline position and width. The predictions apply to clines in almost one-dimensional circumstances such as hybrid zones in rivers, deep valleys, or along a coast line and give a guide to what patterns to expect in two dimensions. AU - Polechova, Jitka AU - Barton, Nicholas H ID - 3394 IS - 1 JF - Genetics TI - Genetic drift widens the expected cline but narrows the expected cline width VL - 189 ER - TY - JOUR AB - What determines the genetic contribution that an individual makes to future generations? With biparental reproduction, each individual leaves a 'pedigree' of descendants, determined by the biparental relationships in the population. The pedigree of an individual constrains the lines of descent of each of its genes. An individual's reproductive value is the expected number of copies of each of its genes that is passed on to distant generations conditional on its pedigree. For the simplest model of biparental reproduction analogous to the Wright-Fisher model, an individual's reproductive value is determined within ~10 generations, independent of population size. Partial selfing and subdivision do not greatly slow this convergence. Our central result is that the probability that a gene will survive is proportional to the reproductive value of the individual that carries it, and that conditional on survival, after a few tens of generations, the distribution of the number of surviving copies is the same for all individuals, whatever their reproductive value. These results can be generalized to the joint distribution of surviving blocks of ancestral genome. Selection on unlinked loci in the genetic background may greatly increase the variance in reproductive value, but the above results nevertheless still hold. The almost linear relationship between survival probability and reproductive value also holds for weakly favored alleles. Thus, the influence of the complex pedigree of descendants on an individual's genetic contribution to the population can be summarized through a single number: its reproductive value. AU - Barton, Nicholas H AU - Etheridge, Alison ID - 3390 IS - 4 JF - Genetics TI - The relation between reproductive value and genetic contribution VL - 188 ER - TY - JOUR AB - Evolutionary biology shares many concepts with statistical physics: both deal with populations, whether of molecules or organisms, and both seek to simplify evolution in very many dimensions. Often, methodologies have undergone parallel and independent development, as with stochastic methods in population genetics. Here, we discuss aspects of population genetics that have embraced methods from physics: non-equilibrium statistical mechanics, travelling waves and Monte-Carlo methods, among others, have been used to study polygenic evolution, rates of adaptation and range expansions. These applications indicate that evolutionary biology can further benefit from interactions with other areas of statistical physics; for example, by following the distribution of paths taken by a population through time AU - de Vladar, Harold AU - Barton, Nicholas H ID - 3391 IS - 8 JF - Trends in Ecology and Evolution TI - The contribution of statistical physics to evolutionary biology VL - 26 ER - TY - JOUR AB - Recent advances in microscopy techniques and biophysical measurements have provided novel insight into the molecular, cellular and biophysical basis of cell adhesion. However, comparably little is known about a core element of cell–cell adhesion—the energy of adhesion at the cell–cell contact. In this review, we discuss approaches to understand the nature and regulation of adhesion energy, and propose strategies to determine adhesion energy between cells in vitro and in vivo. AU - Maître, Jean-Léon AU - Heisenberg, Carl-Philipp J ID - 3397 IS - 5 JF - Current Opinion in Cell Biology TI - The role of adhesion energy in controlling cell-cell contacts VL - 23 ER - TY - JOUR AB - Glutamate is the major excitatory neurotransmitter in the mammalian central nervous system and gates non-selective cation channels. The origins of glutamate receptors are not well understood as they differ structurally and functionally from simple bacterial ligand-gated ion channels. Here we report the discovery of an ionotropic glutamate receptor that combines the typical eukaryotic domain architecture with the 'TXVGYG' signature sequence of the selectivity filter found in K+ channels. This receptor exhibits functional properties intermediate between bacterial and eukaryotic glutamate-gated ion channels, suggesting a link in the evolution of ionotropic glutamate receptors. AU - Janovjak, Harald L AU - Sandoz, Guillaume AU - Isacoff, Ehud ID - 3405 IS - 232 JF - Nature Communications TI - Modern ionotropic glutamate receptor with a K+ selectivity signature sequence VL - 2 ER - TY - JOUR AB - An oriented attachment and growth mechanism allows an accurate control of the size and morphology of Cu2-xS nanocrystals, from spheres and disks to tetradecahedrons and dodecahedrons. The synthesis conditions and the growth mechanism are detailed here. AU - Li, Wenhua AU - Shavel, Alexey AU - Guzman, Roger AU - Rubio Garcia, Javier AU - Flox, Cristina AU - Fan, Jiandong AU - Cadavid, Doris AU - Ibáñez, Maria AU - Arbiol, Jordi AU - Morante, Joan AU - Cabot, Andreu ID - 341 IS - 37 JF - Chemical Communications TI - Morphology evolution of Cu2−xS nanoparticles: from spheres to dodecahedrons VL - 47 ER - TY - JOUR AB - Transcription factors are central to sustaining pluripotency, yet little is known about transcription factor dynamics in defining pluripotency in the early mammalian embryo. Here, we establish a fluorescence decay after photoactivation (FDAP) assay to quantitatively study the kinetic behaviour of Oct4, a key transcription factor controlling pre-implantation development in the mouse embryo. FDAP measurements reveal that each cell in a developing embryo shows one of two distinct Oct4 kinetics, before there are any morphologically distinguishable differences or outward signs of lineage patterning. The differences revealed by FDAP are due to differences in the accessibility of Oct4 to its DNA binding sites in the nucleus. Lineage tracing of the cells in the two distinct sub-populations demonstrates that the Oct4 kinetics predict lineages of the early embryo. Cells with slower Oct4 kinetics are more likely to give rise to the pluripotent cell lineage that contributes to the inner cell mass. Those with faster Oct4 kinetics contribute mostly to the extra-embryonic lineage. Our findings identify Oct4 kinetics, rather than differences in total transcription factor expression levels, as a predictive measure of developmental cell lineage patterning in the early mouse embryo. AU - Plachta, Nicolas AU - Bollenbach, Mark Tobias AU - Pease, Shirley AU - Fraser, Scott AU - Pantazis, Periklis ID - 3429 IS - 2 JF - Nature Cell Biology TI - Oct4 kinetics predict cell lineage patterning in the early mammalian embryo VL - 13 ER - TY - JOUR AB - Cell migration on two-dimensional (2D) substrates follows entirely different rules than cell migration in three-dimensional (3D) environments. This is especially relevant for leukocytes that are able to migrate in the absence of adhesion receptors within the confined geometry of artificial 3D extracellular matrix scaffolds and within the interstitial space in vivo. Here, we describe in detail a simple and economical protocol to visualize dendritic cell migration in 3D collagen scaffolds along chemotactic gradients. This method can be adapted to other cell types and may serve as a physiologically relevant paradigm for the directed locomotion of most amoeboid cells. AU - Sixt, Michael K AU - Lämmermann, Tim ID - 3505 JF - Cell Migration TI - In vitro analysis of chemotactic leukocyte migration in 3D environments VL - 769 ER - TY - JOUR AB - Advanced stages of Scyllarus phyllosoma larvae were collected by demersal trawling during fishery research surveys in the western Mediterranean Sea in 2003–2005. Nucleotide sequence analysis of the mitochondrial 16S rDNA gene allowed the final-stage phyllosoma of Scyllarus arctus to be identified among these larvae. Its morphology is described and illustrated. This constitutes the second complete description of a Scyllaridae phyllosoma with its specific identity being validated by molecular techniques (the first was S. pygmaeus). These results also solved a long lasting taxonomic anomaly of several species assigned to the ancient genus Phyllosoma Leach, 1814. Detailed examination indicated that the final-stage phyllosoma of S. arctus shows closer affinities with the American scyllarid Scyllarus depressus or with the Australian Scyllarus sp. b (sensu Phillips et al., 1981) than to its sympatric species S. pygmaeus. AU - Palero, Ferran AU - Guerao, Guillermo AU - Clark, Paul AU - Abello, Pere ID - 3784 IS - 2 JF - Journal of the Marine Biological Association of the United Kingdom TI - Scyllarus arctus (Crustacea: Decapoda: Scyllaridae) final stage phyllosoma identified by DNA analysis, with morphological description VL - 91 ER - TY - JOUR AB - We bound the difference in length of two curves in terms of their total curvatures and the Fréchet distance. The bound is independent of the dimension of the ambient Euclidean space, it improves upon a bound by Cohen-Steiner and Edelsbrunner, and it generalizes a result by Fáry and Chakerian. AU - Fasy, Brittany Terese ID - 3781 IS - 1-2 JF - Acta Sci. Math. (Szeged) TI - The difference in length of curves in R^n VL - 77 ER - TY - CHAP AB - We address the problem of covering ℝ n with congruent balls, while minimizing the number of balls that contain an average point. Considering the 1-parameter family of lattices defined by stretching or compressing the integer grid in diagonal direction, we give a closed formula for the covering density that depends on the distortion parameter. We observe that our family contains the thinnest lattice coverings in dimensions 2 to 5. We also consider the problem of packing congruent balls in ℝ n , for which we give a closed formula for the packing density as well. Again we observe that our family contains optimal configurations, this time densest packings in dimensions 2 and 3. AU - Edelsbrunner, Herbert AU - Kerber, Michael ED - Calude, Cristian ED - Rozenberg, Grzegorz ED - Salomaa, Arto ID - 3796 T2 - Rainbow of Computer Science TI - Covering and packing with spheres by diagonal distortion in R^n VL - 6570 ER - TY - JOUR AB - In this survey, we compare several languages for specifying Markovian population models such as queuing networks and chemical reaction networks. All these languages — matrix descriptions, stochastic Petri nets, stoichiometric equations, stochastic process algebras, and guarded command models — describe continuous-time Markov chains, but they differ according to important properties, such as compositionality, expressiveness and succinctness, executability, and ease of use. Moreover, they provide different support for checking the well-formedness of a model and for analyzing a model. AU - Henzinger, Thomas A AU - Jobstmann, Barbara AU - Wolf, Verena ID - 3381 IS - 4 JF - IJFCS: International Journal of Foundations of Computer Science TI - Formalisms for specifying Markovian population models VL - 22 ER - TY - JOUR AB - We present a detailed study of the local density of states (LDOS) associated with the surface-state band near a step edge of the strong topological insulator Bi2Te3 and reveal a one-dimensional bound state that runs parallel to the step edge and is bound to it at some characteristic distance. This bound state is clearly observed in the bulk gap region, while it becomes entangled with the oscillations of the warped surface band at high energy, and with the valence-band states near the Dirac point. We obtain excellent fits to theoretical predictions [Alpichshev, 2011] that properly incorporate the three-dimensional nature of the problem to the surface state. Fitting the data at different energies, we can recalculate the LDOS originating from the Dirac band without the contribution of the bulk bands or incoherent tunneling effects. AU - Alpichshev, Zhanybek AU - Analytis, J G AU - Chu, J H AU - Fisher, I R AU - Kapitulnik, A ID - 386 IS - 4 JF - Physical Review B - Condensed Matter and Materials Physics TI - STM imaging of a bound state along a step on the surface of the topological insulator Bi2Te3 VL - 84 ER - TY - JOUR AB - We consider two-player games played in real time on game structures with clocks where the objectives of players are described using parity conditions. The games are concurrent in that at each turn, both players independently propose a time delay and an action, and the action with the shorter delay is chosen. To prevent a player from winning by blocking time, we restrict each player to play strategies that ensure that the player cannot be responsible for causing a zeno run. First, we present an efficient reduction of these games to turn-based (i.e., not concurrent) finite-state (i.e., untimed) parity games. Our reduction improves the best known complexity for solving timed parity games. Moreover, the rich class of algorithms for classical parity games can now be applied to timed parity games. The states of the resulting game are based on clock regions of the original game, and the state space of the finite game is linear in the size of the region graph. Second, we consider two restricted classes of strategies for the player that represents the controller in a real-time synthesis problem, namely, limit-robust and bounded-robust winning strategies. Using a limit-robust winning strategy, the controller cannot choose an exact real-valued time delay but must allow for some nonzero jitter in each of its actions. If there is a given lower bound on the jitter, then the strategy is bounded-robust winning. We show that exact strategies are more powerful than limit-robust strategies, which are more powerful than bounded-robust winning strategies for any bound. For both kinds of robust strategies, we present efficient reductions to standard timed automaton games. These reductions provide algorithms for the synthesis of robust real-time controllers. AU - Chatterjee, Krishnendu AU - Henzinger, Thomas A AU - Prabhu, Vinayak ID - 3315 IS - 4 JF - Logical Methods in Computer Science TI - Timed parity games: Complexity and robustness VL - 7 ER - TY - JOUR AB - The elevation function on a smoothly embedded 2-manifold in R-3 reflects the multiscale topography of cavities and protrusions as local maxima. The function has been useful in identifying coarse docking configurations for protein pairs. Transporting the concept from the smooth to the piecewise linear category, this paper describes an algorithm for finding all local maxima. While its worst-case running time is the same as of the algorithm used in prior work, its performance in practice is orders of magnitudes superior. We cast light on this improvement by relating the running time to the total absolute Gaussian curvature of the 2-manifold. AU - Wang, Bei AU - Edelsbrunner, Herbert AU - Morozov, Dmitriy ID - 3965 IS - 2.2 JF - Journal of Experimental Algorithmics TI - Computing elevation maxima by searching the Gauss sphere VL - 16 ER - TY - JOUR AB - PIN-FORMED (PIN)-dependent auxin transport is essential for plant development and its modulation in response to the environment or endogenous signals. A NON-PHOTOTROPIC HYPOCOTYL 3 (NPH3)-like protein, MACCHI-BOU 4 (MAB4), has been shown to control PIN1 localization during organ formation, but its contribution is limited. The Arabidopsis genome contains four genes, MAB4/ENP/NPY1-LIKE1 (MEL1), MEL2, MEL3 and MEL4, highly homologous to MAB4. Genetic analysis disclosed functional redundancy between MAB4 and MEL genes in regulation of not only organ formation but also of root gravitropism, revealing that NPH3 family proteins have a wider range of functions than previously suspected. Multiple mutants showed severe reduction in PIN abundance and PIN polar localization, leading to defective expression of an auxin responsive marker DR5rev::GFP. Pharmacological analyses and fluorescence recovery after photo-bleaching experiments showed that mel mutations increase PIN2 internalization from the plasma membrane, but affect neither intracellular PIN2 trafficking nor PIN2 lateral diffusion at the plasma membrane. Notably, all MAB4 subfamily proteins show polar localization at the cell periphery in plants. The MAB4 polarity was almost identical to PIN polarity. Our results suggest that the MAB4 subfamily proteins specifically retain PIN proteins in a polarized manner at the plasma membrane, thus controlling directional auxin transport and plant development. AU - Furutani, Masahiko AU - Sakamoto, Norihito AU - Yoshida, Shuhei AU - Kajiwara, Takahito AU - Robert, Hélène S AU - Jirí Friml AU - Tasaka, Masao ID - 3086 IS - 10 JF - Development TI - Polar localized NPH3-like proteins regulate polarity and endocytosis of PIN-FORMED auxin efflux carriers VL - 138 ER - TY - JOUR AB - Endocytosis is a crucial mechanism by which eukaryotic cells internalize extracellular and plasma membrane material, and it is required for a multitude of cellular and developmental processes in unicellular and multicellular organisms. In animals and yeast, the best characterized pathway for endocytosis depends on the function of the vesicle coat protein clathrin. Clathrinmediated endocytosis has recently been demonstrated also in plant cells, but its physiological and developmental roles remain unclear. Here, we assessed the roles of the clathrin-mediated mechanism of endocytosis in plants by genetic means. We interfered with clathrin heavy chain (CHC) function through mutants and dominant-negative approaches in Arabidopsis thaliana and established tools to manipulate clathrin function in a cell type-specific manner. The chc2 single mutants and dominant-negative CHC1 (HUB) transgenic lines were defective in bulk endocytosis as well as in internalization of prominent plasma membrane proteins. Interference with clathrin-mediated endocytosis led to defects in constitutive endocytic recycling of PIN auxin transporters and their polar distribution in embryos and roots. Consistent with this, these lines had altered auxin distribution patterns and associated auxin transport-related phenotypes, such as aberrant embryo patterning, imperfect cotyledon specification, agravitropic growth, and impaired lateral root organogenesis. Together, these data demonstrate a fundamental role for clathrin function in cell polarity, growth, patterning, and organogenesis in plants. AU - Kitakura, Saeko AU - Vanneste, Steffen AU - Robert, Stéphanie AU - Löfke, Christian AU - Teichmann, Thomas AU - Tanaka, Hirokazu AU - Jirí Friml ID - 3087 IS - 5 JF - Plant Cell TI - Clathrin mediates endocytosis and polar distribution of PIN auxin transporters in Arabidopsis VL - 23 ER - TY - JOUR AB - Phototropism is an adaptation response, through which plants grow towards the light. It involves light perception and asymmetric distribution of the plant hormone auxin. Here we identify a crucial part of the mechanism for phototropism, revealing how light perception initiates auxin redistribution that leads to directional growth. We show that light polarizes the cellular localization of the auxin efflux carrier PIN3 in hypocotyl endodermis cells, resulting in changes in auxin distribution and differential growth. In the dark, high expression and activity of the PINOID (PID) kinase correlates with apolar targeting of PIN3 to all cell sides. Following illumination, light represses PINOID transcription and PIN3 is polarized specifically to the inner cell sides by GNOM ARF GTPase GEF (guanine nucleotide exchange factor)-dependent trafficking. Thus, differential trafficking at the shaded and illuminated hypocotyl side aligns PIN3 polarity with the light direction, and presumably redirects auxin flow towards the shaded side, where auxin promotes growth, causing hypocotyls to bend towards the light. Our results imply that PID phosphorylation-dependent recruitment of PIN proteins into distinct trafficking pathways is a mechanism to polarize auxin fluxes in response to different environmental and endogenous cues. AU - Ding, Zhaojun AU - Galván-Ampudia, Carlos S AU - Demarsy, Emilie AU - Łangowski, Łukasz AU - Kleine-Vehn, Jürgen AU - Fan, Yuanwei AU - Morita, Miyo T AU - Tasaka, Masao AU - Fankhauser, Christian AU - Offringa, Remko AU - Jirí Friml ID - 3085 IS - 4 JF - Nature Cell Biology TI - Light-mediated polarization of the PIN3 auxin transporter for the phototropic response in Arabidopsis VL - 13 ER - TY - JOUR AB - A central question in developmental biology concerns the mechanism of generation and maintenance of cell polarity, because these processes are essential for many cellular functions and multicellular development [1]. In plants, cell polarity has an additional role in mediating directional transport of the plant hormone auxin that is crucial for multiple developmental processes [2-4]. In addition, plant cells have a complex extracellular matrix, the cell wall [5, 6], whose role in regulating cellular processes, including cell polarity, is unexplored. We have found that polar distribution of PIN auxin transporters [7] in plant cells is maintained by connections between polar domains at the plasma membrane and the cell wall. Genetic and pharmacological interference with cellulose, the major component of the cell wall, or mechanical interference with the cell wall disrupts these connections and leads to increased lateral diffusion and loss of polar distribution of PIN transporters for the phytohormone auxin. Our results reveal a plant-specific mechanism for cell polarity maintenance and provide a conceptual framework for modulating cell polarity and plant development via endogenous and environmental manipulations of the cellulose-based extracellular matrix. AU - Feraru, Elena AU - Feraru, Mugurel I AU - Kleine-Vehn, Jürgen AU - Martinière, Alexandre AU - Mouille, Grégory AU - Vanneste, Steffen AU - Vernhettes, Samantha AU - Runions, John AU - Jirí Friml ID - 3084 IS - 4 JF - Current Biology TI - PIN polarity maintenance by the cell wall in Arabidopsis VL - 21 ER - TY - JOUR AB - Shoot branching is one of the major determinants of plant architecture. Polar auxin transport in stems is necessary for the control of bud outgrowth by a dominant apex. Here, we show that following decapitation in pea (Pisum sativum L.), the axillary buds establish directional auxin export by subcellular polarization of PIN auxin transporters. Apical auxin application on the decapitated stem prevents this PIN polarization and canalization of laterally applied auxin. These results support a model in which the apical and lateral auxin sources compete for primary channels of auxin transport in the stem to control the outgrowth of axillary buds. AU - Balla, Jozef AU - Kalousek, Petr AU - Reinöhl, Vilém AU - Jirí Friml AU - Procházka, Stanislav ID - 3082 IS - 4 JF - Plant Journal TI - Competitive canalization of PIN dependent auxin flow from axillary buds controls pea bud outgrowth VL - 65 ER - TY - JOUR AU - Robinson, David G AU - Scheuring, David AU - Naramoto, Satoshi AU - Jirí Friml ID - 3083 IS - 3 JF - Plant Cell TI - ARF1 localizes to the golgi and the trans Golgi network VL - 23 ER - TY - JOUR AB - Subcellular trafficking is required for a multitude of functions in eukaryotic cells. It involves regulation of cargo sorting, vesicle formation, trafficking and fusion processes at multiple levels. Adaptor protein (AP) complexes are key regulators of cargo sorting into vesicles in yeast and mammals but their existence and function in plants have not been demonstrated. Here we report the identification of the protein-affected trafficking 4 (pat4) mutant defective in the putative δ subunit of the AP-3 complex. pat4 and pat2, a mutant isolated from the same GFP imaging-based forward genetic screen that lacks a functional putative AP-3 β, as well as dominant negative AP-3 μ transgenic lines display undistinguishable phenotypes characterized by largely normal morphology and development, but strong intracellular accumulation of membrane proteins in aberrant vacuolar structures. All mutants are defective in morphology and function of lytic and protein storage vacuoles (PSVs) but show normal sorting of reserve proteins to PSVs. Immunoprecipitation experiments and genetic studies revealed tight functional and physical associations of putative AP-3 β and AP-3 δ subunits. Furthermore, both proteins are closely linked with putative AP-3 μ and σ subunits and several components of the clathrin and dynamin machineries. Taken together, these results demonstrate that AP complexes, similar to those in other eukaryotes, exist in plants, and that AP-3 plays a specific role in the regulation of biogenesis and function of vacuoles in plant cells. © 2011 IBCB, SIBS, CAS All rights reserved AU - Zwiewka, Marta AU - Feraru, Elena AU - Möller, Barbara AU - Hwang, Inhwan AU - Feraru, Mugurel I AU - Kleine-Vehn, Jürgen AU - Weijers, Dolf AU - Jirí Friml ID - 3101 IS - 12 JF - Cell Research TI - The AP 3 adaptor complex is required for vacuolar function in Arabidopsis VL - 21 ER - TY - JOUR AB - Cell polarity reflected by asymmetric distribution of proteins at the plasma membrane is a fundamental feature of unicellular and multicellular organisms. It remains conceptually unclear how cell polarity is kept in cell wall-encapsulated plant cells. We have used super-resolution and semi-quantitative live-cell imaging in combination with pharmacological, genetic, and computational approaches to reveal insights into the mechanism of cell polarity maintenance in Arabidopsis thaliana. We show that polar-competent PIN transporters for the phytohormone auxin are delivered to the center of polar domains by super-polar recycling. Within the plasma membrane, PINs are recruited into non-mobile membrane clusters and their lateral diffusion is dramatically reduced, which ensures longer polar retention. At the circumventing edges of the polar domain, spatially defined internalization of escaped cargos occurs by clathrin-dependent endocytosis. Computer simulations confirm that the combination of these processes provides a robust mechanism for polarity maintenance in plant cells. Moreover, our study suggests that the regulation of lateral diffusion and spatially defined endocytosis, but not super-polar exocytosis have primary importance for PIN polarity maintenance. AU - Kleine-Vehn, Jürgen AU - Krzysztof Wabnik AU - Martinière, Alexandre AU - Łangowski, Łukasz AU - Willig, Katrin AU - Naramoto, Satoshi AU - Leitner, Johannes AU - Tanaka, Hirokazu AU - Jakobs, Stefan AU - Robert, Stéphanie AU - Luschnig, Christian AU - Govaerts, Willy J AU - Hell, Stefan W AU - Runions, John AU - Jirí Friml ID - 3098 JF - Molecular Systems Biology TI - Recycling, clustering and endocytosis jointly maintain PIN auxin carrier polarity at the plasma membrane VL - 7 ER - TY - JOUR AB - In multicellular organisms, morphogenesis relies on a strict coordination in time and space of cell proliferation and differentiation. In contrast to animals, plant development displays continuous organ formation and adaptive growth responses during their lifespan relying on a tight coordination of cell proliferation. How developmental signals interact with the plant cell-cycle machinery is largely unknown. Here, we characterize plant A2-type cyclins, a small gene family of mitotic cyclins, and show how they contribute to the fine-tuning of local proliferation during plant development. Moreover, the timely repression of CYCA2;3 expression in newly formed guard cells is shown to require the stomatal transcription factors FOUR LIPS/MYB124 and MYB88, providing a direct link between developmental programming and cell-cycle exit in plants. Thus, transcriptional downregulation of CYCA2s represents a critical mechanism to coordinate proliferation during plant development. AU - Vanneste, Steffen AU - Coppens, Frederik AU - Lee, EunKyoung AU - Donner, Tyler J AU - Xie, Zidian AU - Van Isterdael, Gert AU - Dhondt, Stijn AU - De Winter, Freya AU - De Rybel, Bert AU - Vuylsteke, Marnik AU - De Veylder, Lieven AU - Jirí Friml AU - Inzé, Dirk AU - Grotewold, Erich AU - Scarpella, Enrico AU - Sack, Fred AU - Beemster, Gerrit T AU - Beeckman, Tom ID - 3100 IS - 16 JF - EMBO Journal TI - Developmental regulation of CYCA2s contributes to tissue-specific proliferation in Arabidopsis VL - 30 ER - TY - JOUR AB - Endomembrane trafficking relies on the coordination of a highly complex, dynamic network of intracellular vesicles. Understanding the network will require a dissection of cargo and vesicle dynamics at the cellular level in vivo. This is also a key to establishing a link between vesicular networks and their functional roles in development. We used a high-content intracellular screen to discover small molecules targeting endomembrane trafficking in vivo in a complex eukaryote, Arabidopsis thaliana. Tens of thousands of molecules were prescreened and a selected subset was interrogated against a panel of plasma membrane (PM) and other endomembrane compartment markers to identify molecules that altered vesicle trafficking. The extensive image dataset was transformed by a flexible algorithm into a marker-by-phenotype-by-treatment time matrix and revealed groups of molecules that induced similar subcellular fingerprints (clusters). This matrix provides a platform for a systems view of trafficking. Molecules from distinct clusters presented avenues and enabled an entry point to dissect recycling at the PM, vacuolar sorting, and cell-plate maturation. Bioactivity in human cells indicated the value of the approach to identifying small molecules that are active in diverse organisms for biology and drug discovery. AU - Drakakaki, Georgia AU - Robert, Stéphanie AU - Szatmári, Anna-Maria AU - Brown, Michelle Q AU - Nagawa, Shingo AU - Van Damme, Daniël AU - Leonard, Marylin AU - Yang, Zhenbiao AU - Girke, Thomas AU - Schmid, Sandra L AU - Russinova, Eugenia AU - Jirí Friml AU - Raikhel, Natasha V AU - Hicks, Glen R ID - 3099 IS - 43 JF - PNAS TI - Clusters of bioactive compounds target dynamic endomembrane networks in vivo VL - 108 ER - TY - JOUR AB - Root system architecture depends on lateral root (LR) initiation that takes place in a relatively narrow developmental window (DW). Here, we analyzed the role of auxin gradients established along the parent root in defining this DW for LR initiation. Correlations between auxin distribution and response, and spatiotemporal control of LR initiation were analyzed in Arabidopsis thaliana and tomato (Solanum lycopersicum). In both Arabidopsis and tomato roots, a well defined zone, where auxin content and response are minimal, demarcates the position of a DW for founder cell specification and LR initiation. We show that in the zone of auxin minimum pericycle cells have highest probability to become founder cells and that auxin perception via the TIR1/AFB pathway, and polar auxin transport, are essential for the establishment of this zone. Altogether, this study reveals that the same morphogen-like molecule, auxin, can act simultaneously as a morphogenetic trigger of LR founder cell identity and as a gradient-dependent signal defining positioning of the founder cell specification. This auxin minimum zone might represent an important control mechanism ensuring the LR initiation steadiness and the acropetal LR initiation pattern. © 2011 The Authors. New Phytologist © 2011 New Phytologist Trust. AU - Dubrovsky, Joseph G AU - Napsucialy-Mendivil, Selene AU - Duclercq, Jérôme AU - Cheng, Yan AU - Shishkova, Svetlana O AU - Ivanchenko, Maria G AU - Jirí Friml AU - Murphy, Angus S AU - Eva Benková ID - 3095 IS - 4 JF - New Phytologist TI - Auxin minimum defines a developmental window for lateral root initiation VL - 191 ER - TY - JOUR AB - Cytokinin is an important regulator of plant growth and development. In Arabidopsis thaliana, the two-component phosphorelay mediated through a family of histidine kinases and response regulators is recognized as the principal cytokinin signal transduction mechanism activating the complex transcriptional response to control various developmental processes. Here, we identified an alternative mode of cytokinin action that uses endocytic trafficking as a means to direct plant organogenesis. This activity occurs downstream of known cytokinin receptors but through a branch of the cytokinin signaling pathway that does not involve transcriptional regulation. We show that cytokinin regulates endocytic recycling of the auxin efflux carrier PINFORMED1 (PIN1) by redirecting it for lytic degradation in vacuoles. Stimulation of the lytic PIN1 degradation is not a default effect for general downregulation of proteins from plasma membranes, but a specific mechanism to rapidly modulate the auxin distribution in cytokinin-mediated developmental processes. AU - Peter Marhavy AU - Bielach, Agnieszka AU - Abas, Lindy AU - Abuzeineh, Anas AU - Duclercq, Jérôme AU - Tanaka, Hirokazu AU - Pařezová, Markéta AU - Petrášek, Jan AU - Jirí Friml AU - Kleine-Vehn, Jürgen AU - Eva Benková ID - 3097 IS - 4 JF - Developmental Cell TI - Cytokinin modulates endocytic trafficking of PIN1 auxin efflux carrier to control plant organogenesis VL - 21 ER - TY - JOUR AB - Carrier-dependent, intercellular auxin transport is central to the developmental patterning of higher plants (tracheophytes). The evolution of this polar auxin transport might be linked to the translocation of some PIN auxin efflux carriers from their presumably ancestral localization at the endoplasmic reticulum (ER) to the polar domains at the plasma membrane. Here we propose an eventually ancient mechanism of intercellular auxin distribution by ER-localized auxin transporters involving intracellular auxin retention and switch-like release from the ER. The proposed model integrates feedback circuits utilizing the conserved nuclear auxin signaling for the regulation of PIN transcription and a hypothetical ER-based signaling for the regulation of PIN-dependent transport activity at the ER. Computer simulations of the model revealed its plausibility for generating auxin channels and localized auxin maxima highlighting the possibility of this alternative mechanism for polar auxin transport. AU - Wabnik, Krzysztof T AU - Kleine Vehn, Jürgen AU - Govaerts, Willy AU - Friml, Jirí ID - 3096 IS - 9 JF - Trends in Plant Science TI - Prototype cell-to-cell auxin transport mechanism by intracellular auxin compartmentalization VL - 16 ER - TY - JOUR AB - Hippocampal sharp waves (SPWs) and associated fast ("ripple") oscillations (SPW-Rs) in the CA1 region are among the most synchronous physiological patterns in the mammalian brain. Using two-dimensional arrays of electrodes for recording local field potentials and unit discharges in freely moving rats, we studied the emergence of ripple oscillations (140-220 Hz) and compared their origin and cellular-synaptic mechanisms with fast gamma oscillations (90-140 Hz). We show that (1) hippocampal SPW-Rs and fast gamma oscillations are quantitatively distinct patterns but involve the same networks and share similar mechanisms; (2) both the frequency and magnitude of fast oscillations are positively correlated with the magnitude of SPWs; (3) during both ripples and fast gamma oscillations the frequency of network oscillation is higher in CA1 than in CA3; and (4) the emergence of CA3 population bursts, a prerequisite for SPW-Rs, is biased by activity patterns in the dentate gyrus and entorhinal cortex, with the highest probability of ripples associated with an "optimum" level of dentate gamma power. We hypothesize that each hippocampal subnetwork possesses distinct resonant properties, tuned by the magnitude of the excitatory drive. AU - Sullivan, David W AU - Jozsef Csicsvari AU - Mizuseki, Kenji AU - Montgomery, Sean M AU - Diba, Kamran AU - Buzsáki, György ID - 3138 IS - 23 JF - Journal of Neuroscience TI - Relationships between hippocampal sharp waves ripples and fast gamma oscillation Influence of dentate and entorhinal cortical activity VL - 31 ER - TY - JOUR AB - Microinjection of recombinant DNA into zygotic pronuclei has been widely used for producing transgenic mice. However, with this method, the insertion site, integrity, and copy number of the transgene cannot be controlled. Here, we present an integrase-based approach to produce transgenic mice via pronuclear injection, whereby an intact single-copy transgene can be inserted into predetermined chromosomal loci with high efficiency (up to 40%), and faithfully transmitted through generations. We show that neighboring transgenic elements and bacterial DNA within the transgene cause profound silencing and expression variability of the transgenic marker. Removal of these undesirable elements leads to global high-level marker expression from transgenes driven by a ubiquitous promoter. We also obtained faithful marker expression from a tissue-specific promoter. The technique presented here will greatly facilitate murine transgenesis and precise structure/function dissection of mammalian gene function and regulation in vivo. AU - Tasic, Bosiljka AU - Simon Hippenmeyer AU - Wang, Charlene AU - Gamboa, Matthew AU - Zong, Hui AU - Chen-Tsai, Yanru AU - Luo, Liqun ID - 3145 IS - 19 JF - PNAS TI - Site specific integrase mediated transgenesis in mice via pronuclear injection VL - 108 ER - TY - JOUR AB - Regulated adhesion between cells and their environment is critical for normal cell migration. We have identified mutations in a gene encoding the Drosophila hydrogen peroxide (H2O2)-degrading enzyme Jafrac1, which lead to germ cell adhesion defects. During gastrulation, primordial germ cells (PGCs) associate tightly with the invaginating midgut primordium as it enters the embryo; however, in embryos from jafrac1 mutant mothers this association is disrupted, leaving some PGCs trailing on the outside of the embryo. We observed similar phenotypes in embryos from DE-cadherin/shotgun (shg) mutant mothers and were able to rescue the jafrac1 phenotype by increasing DE-cadherin levels. This and our biochemical evidence strongly suggest that Jafrac1-mediated reduction of H2O2 is required to maintain DE-cadherin protein levels in the early embryo. Our results present in vivo evidence of a peroxiredoxin regulating DE-cadherin-mediated adhesion. AU - DeGennaro, Matthew AU - Hurd, Thomas R AU - Daria Siekhaus AU - Biteau, Benoit AU - Jasper, Heinrich AU - Lehmann, Ruth ID - 3154 IS - 2 JF - Developmental Cell TI - Peroxiredoxin stabilization of DE-cadherin promotes primordial germ cell adhesion VL - 20 ER - TY - CONF AB - Tampering attacks are cryptanalytic attacks on the implementation of cryptographic algorithms (e.g., smart cards), where an adversary introduces faults with the hope that the tampered device will reveal secret information. Inspired by the work of Ishai et al. [Eurocrypt'06], we propose a compiler that transforms any circuit into a new circuit with the same functionality, but which is resilient against a well-defined and powerful tampering adversary. More concretely, our transformed circuits remain secure even if the adversary can adaptively tamper with every wire in the circuit as long as the tampering fails with some probability δ>0. This additional requirement is motivated by practical tampering attacks, where it is often difficult to guarantee the success of a specific attack. Formally, we show that a q-query tampering attack against the transformed circuit can be "simulated" with only black-box access to the original circuit and log(q) bits of additional auxiliary information. Thus, if the implemented cryptographic scheme is secure against log(q) bits of leakage, then our implementation is tamper-proof in the above sense. Surprisingly, allowing for this small amount of information leakage allows for much more efficient compilers, which moreover do not require randomness during evaluation. Similar to earlier works our compiler requires small, stateless and computation-independent tamper-proof gadgets. Thus, our result can be interpreted as reducing the problem of shielding arbitrary complex computation to protecting simple components. © 2011 Springer-Verlag. AU - Faust, Sebastian AU - Krzysztof Pietrzak AU - Venturi, Daniele ID - 3239 IS - Part 1 TI - Tamper proof circuits How to trade leakage for tamper resilience VL - 6755 ER - TY - CONF AB - If a cryptographic primitive remains secure even if ℓ bits about the secret key are leaked to the adversary, one would expect that at least one of n independent instantiations of the scheme remains secure given n·ℓ bits of leakage. This intuition has been proven true for schemes satisfying some special information-theoretic properties by Alwen et al. [Eurocrypt'10]. On the negative side, Lewko and Waters [FOCS'10] construct a CPA secure public-key encryption scheme for which this intuition fails. The counterexample of Lewko and Waters leaves open the interesting possibility that for any scheme there exists a constant c>0, such that n fold repetition remains secure against c·n·ℓ bits of leakage. Furthermore, their counterexample requires the n copies of the encryption scheme to share a common reference parameter, leaving open the possibility that the intuition is true for all schemes without common setup. In this work we give a stronger counterexample ruling out these possibilities. We construct a signature scheme such that: 1. a single instantiation remains secure given ℓ = log(k) bits of leakage where k is a security parameter. 2. any polynomial number of independent instantiations can be broken (in the strongest sense of key-recovery) given ℓ′ = poly(k) bits of leakage. Note that ℓ does not depend on the number of instances. The computational assumption underlying our counterexample is that non-interactive computationally sound proofs exist. Moreover, under a stronger (non-standard) assumption about such proofs, our counterexample does not require a common reference parameter. The underlying idea of our counterexample is rather generic and can be applied to other primitives like encryption schemes. © 2011 International Association for Cryptologic Research. AU - Jain, Abhishek AU - Krzysztof Pietrzak ID - 3236 TI - Parallel repetition for leakage resilience amplification revisited VL - 6597 ER - TY - JOUR AB - We present an algorithm to identify individual neural spikes observed on high-density multi-electrode arrays (MEAs). Our method can distinguish large numbers of distinct neural units, even when spikes overlap, and accounts for intrinsic variability of spikes from each unit. As MEAs grow larger, it is important to find spike-identification methods that are scalable, that is, the computational cost of spike fitting should scale well with the number of units observed. Our algorithm accomplishes this goal, and is fast, because it exploits the spatial locality of each unit and the basic biophysics of extracellular signal propagation. Human interaction plays a key role in our method; but effort is minimized and streamlined via a graphical interface. We illustrate our method on data from guinea pig retinal ganglion cells and document its performance on simulated data consisting of spikes added to experimentally measured background noise. We present several tests demonstrating that the algorithm is highly accurate: it exhibits low error rates on fits to synthetic data, low refractory violation rates, good receptive field coverage, and consistency across users. AU - Prentice, Jason S AU - Homann, Jan AU - Simmons, Kristina D AU - Gasper Tkacik AU - Balasubramanian, Vijay AU - Nelson, Philip C ID - 3276 IS - 7 JF - PLoS One TI - Fast, scalable, Bayesian spike identification for multi-electrode arrays VL - 6 ER - TY - CHAP AB - In this paper we present an efficient framework for computation of persis- tent homology of cubical data in arbitrary dimensions. An existing algorithm using simplicial complexes is adapted to the setting of cubical complexes. The proposed approach enables efficient application of persistent homology in domains where the data is naturally given in a cubical form. By avoiding triangulation of the data, we significantly reduce the size of the complex. We also present a data-structure de- signed to compactly store and quickly manipulate cubical complexes. By means of numerical experiments, we show high speed and memory efficiency of our ap- proach. We compare our framework to other available implementations, showing its superiority. Finally, we report performance on selected 3D and 4D data-sets. AU - Wagner, Hubert AU - Chen, Chao AU - Vuçini, Erald ED - Peikert, Ronald ED - Hauser, Helwig ED - Carr, Hamish ED - Fuchs, Raphael ID - 3271 T2 - Topological Methods in Data Analysis and Visualization II TI - Efficient computation of persistent homology for cubical data ER - TY - JOUR AB - Despite much research on the socially parasitic large blue butterflies (genus Maculinea) in the past 40 years, their relationship to their closest relatives, Phengaris, is controversial and the relationships among the remaining genera in the Glaucopsyche section are largely unresolved. The evolutionary history of this butterfly section is particularly important to understand the evolution of life history diversity con- nected to food-plant and host-ant associations in the larval stage. In the present study, we use a combi- nation of four nuclear and two mitochondrial genes to reconstruct the phylogeny of the Glaucopsyche section, and in particular, to study the relationships among and within the Phengaris–Maculinea species. We find a clear pattern between the clades recovered in the Glaucopsyche section phylogeny and their food-plant associations, with only the Phengaris–Maculinea clade utilising more than one plant family. Maculinea is, for the first time, recovered with strong support as a monophyletic group nested within Phengaris, with the closest relative being the rare genus Caerulea. The genus Glaucopsyche is polyphyletic, including the genera Sinia and Iolana. Interestingly, we find evidence for additional potential cryptic spe- cies within the highly endangered Maculinea, which has long been suspected from morphological, ecolog- ical and molecular studies. AU - Vila, Roger AU - Pierce, Naomi E AU - Nash, David R AU - Line Ugelvig ID - 3278 IS - 1 JF - Molecular Phylogenetics and Evolution TI - A phylogenetic revision of the Glaucopsyche section (Lepidoptera: Lycaenidae), with special focus on the Phengaris-Maculinea clade VL - 61 ER - TY - CONF AB - The persistence diagram of a filtered simplicial com- plex is usually computed by reducing the boundary matrix of the complex. We introduce a simple op- timization technique: by processing the simplices of the complex in decreasing dimension, we can “kill” columns (i.e., set them to zero) without reducing them. This technique completely avoids reduction on roughly half of the columns. We demonstrate that this idea significantly improves the running time of the reduction algorithm in practice. We also give an output-sensitive complexity analysis for the new al- gorithm which yields to sub-cubic asymptotic bounds under certain assumptions. AU - Chen, Chao AU - Kerber, Michael ID - 3270 TI - Persistent homology computation with a twist ER - TY - CONF AB - We present a new algorithm for enforcing incompressibility for Smoothed Particle Hydrodynamics (SPH) by preserving uniform density across the domain. We propose a hybrid method that uses a Poisson solve on a coarse grid to enforce a divergence free velocity field, followed by a local density correction of the particles. This avoids typical grid artifacts and maintains the Lagrangian nature of SPH by directly transferring pressures onto particles. Our method can be easily integrated with existing SPH techniques such as the incompressible PCISPH method as well as weakly compressible SPH by adding an additional force term. We show that this hybrid method accelerates convergence towards uniform density and permits a significantly larger time step compared to earlier approaches while producing similar results. We demonstrate our approach in a variety of scenarios with significant pressure gradients such as splashing liquids. AU - Raveendran, Karthik AU - Wojtan, Christopher J AU - Turk, Greg ED - Spencer, Stephen ID - 3298 TI - Hybrid smoothed particle hydrodynamics ER - TY - CONF AB - Animating detailed liquid surfaces has always been a challenge for computer graphics researchers and visual effects artists. Over the past few years, researchers in this field have focused on mesh-based surface tracking to synthesize extremely detailed liquid surfaces as efficiently as possible. This course provides a solid understanding of the steps required to create a fluid simulator with a mesh-based liquid surface. The course begins with an overview of several existing liquid-surface-tracking techniques and the pros and cons of each method. Then it explains how to embed a triangle mesh into a finite-difference-based fluid simulator and describes several methods for allowing the liquid surface to merge together or break apart. The final section showcases the benefits and further applications of a mesh-based liquid surface, highlighting state-of-the-art methods for tracking colors and textures, maintaining liquid volume, preserving small surface features, and simulating realistic surface-tension waves. AU - Wojtan, Christopher J AU - Müller Fischer, Matthias AU - Brochu, Tyson ID - 3297 TI - Liquid simulation with mesh-based surface tracking ER - TY - JOUR AB - Analysis of genomic data requires an efficient way to calculate likelihoods across very large numbers of loci. We describe a general method for finding the distribution of genealogies: we allow migration between demes, splitting of demes [as in the isolation-with-migration (IM) model], and recombination between linked loci. These processes are described by a set of linear recursions for the generating function of branch lengths. Under the infinite-sites model, the probability of any configuration of mutations can be found by differentiating this generating function. Such calculations are feasible for small numbers of sampled genomes: as an example, we show how the generating function can be derived explicitly for three genes under the two-deme IM model. This derivation is done automatically, using Mathematica. Given data from a large number of unlinked and nonrecombining blocks of sequence, these results can be used to find maximum-likelihood estimates of model parameters by tabulating the probabilities of all relevant mutational configurations and then multiplying across loci. The feasibility of the method is demonstrated by applying it to simulated data and to a data set previously analyzed by Wang and Hey (2010) consisting of 26,141 loci sampled from Drosophila simulans and D. melanogaster. Our results suggest that such likelihood calculations are scalable to genomic data as long as the numbers of sampled individuals and mutations per sequence block are small. AU - Lohse, Konrad AU - Harrison, Richard AU - Barton, Nicholas H ID - 3290 IS - 3 JF - Genetics TI - A general method for calculating likelihoods under the coalescent process VL - 189 ER - TY - GEN AB - We study the 3D reconstruction of plant roots from multiple 2D images. To meet the challenge caused by the delicate nature of thin branches, we make three innovations to cope with the sensitivity to image quality and calibration. First, we model the background as a harmonic function to improve the segmentation of the root in each 2D image. Second, we develop the concept of the regularized visual hull which reduces the effect of jittering and refraction by ensuring consistency with one 2D image. Third, we guarantee connectedness through adjustments to the 3D reconstruction that minimize global error. Our software is part of a biological phenotype/genotype study of agricultural root systems. It has been tested on more than 40 plant roots and results are promising in terms of reconstruction quality and efficiency. AU - Zheng, Ying AU - Gu, Steve AU - Edelsbrunner, Herbert AU - Tomasi, Carlo AU - Benfey, Philip ID - 3312 T2 - Proceedings of the IEEE International Conference on Computer Vision TI - Detailed reconstruction of 3D plant root shape ER - TY - CONF AB - Interpreting an image as a function on a compact sub- set of the Euclidean plane, we get its scale-space by diffu- sion, spreading the image over the entire plane. This gener- ates a 1-parameter family of functions alternatively defined as convolutions with a progressively wider Gaussian ker- nel. We prove that the corresponding 1-parameter family of persistence diagrams have norms that go rapidly to zero as time goes to infinity. This result rationalizes experimental observations about scale-space. We hope this will lead to targeted improvements of related computer vision methods. AU - Chen, Chao AU - Edelsbrunner, Herbert ID - 3313 T2 - Proceedings of the IEEE International Conference on Computer Vision TI - Diffusion runs low on persistence fast ER - TY - CHAP AB - Alpha shapes have been conceived in 1981 as an attempt to define the shape of a finite set of point in the plane. Since then, connections to diverse areas in the sciences and engineering have developed, including to pattern recognition, digital shape sampling and processing, and structural molecular biology. This survey begins with a historical account and discusses geometric, algorithmic, topological, and combinatorial aspects of alpha shapes in this sequence. AU - Edelsbrunner, Herbert ED - van de Weygaert, R ED - Vegter, G ED - Ritzerveld, J ED - Icke, V ID - 3311 T2 - Tessellations in the Sciences: Virtues, Techniques and Applications of Geometric Tilings TI - Alpha shapes - a survey ER - TY - CONF AB - Weighted automata map input words to numerical values. Ap- plications of weighted automata include formal verification of quantitative properties, as well as text, speech, and image processing. A weighted au- tomaton is defined with respect to a semiring. For the tropical semiring, the weight of a run is the sum of the weights of the transitions taken along the run, and the value of a word is the minimal weight of an accepting run on it. In the 90’s, Krob studied the decidability of problems on rational series defined with respect to the tropical semiring. Rational series are strongly related to weighted automata, and Krob’s results apply to them. In par- ticular, it follows from Krob’s results that the universality problem (that is, deciding whether the values of all words are below some threshold) is decidable for weighted automata defined with respect to the tropical semir- ing with domain ∪ {∞}, and that the equality problem is undecidable when the domain is ∪ {∞}. In this paper we continue the study of the borders of decidability in weighted automata, describe alternative and direct proofs of the above results, and tighten them further. Unlike the proofs of Krob, which are algebraic in their nature, our proofs stay in the terrain of state machines, and the reduction is from the halting problem of a two-counter machine. This enables us to significantly simplify Krob’s reasoning, make the un- decidability result accessible to the automata-theoretic community, and strengthen it to apply already to a very simple class of automata: all the states are accepting, there are no initial nor final weights, and all the weights on the transitions are from the set {−1, 0, 1}. The fact we work directly with the automata enables us to tighten also the decidability re- sults and to show that the universality problem for weighted automata defined with respect to the tropical semiring with domain ∪ {∞}, and in fact even with domain ≥0 ∪ {∞}, is PSPACE-complete. Our results thus draw a sharper picture about the decidability of decision problems for weighted automata, in both the front of containment vs. universality and the front of the ∪ {∞} vs. the ∪ {∞} domains. AU - Almagor, Shaull AU - Boker, Udi AU - Kupferman, Orna ID - 3326 TI - What’s decidable about weighted automata VL - 6996 ER - TY - CONF AB - We introduce streaming data string transducers that map input data strings to output data strings in a single left-to-right pass in linear time. Data strings are (unbounded) sequences of data values, tagged with symbols from a finite set, over a potentially infinite data do- main that supports only the operations of equality and ordering. The transducer uses a finite set of states, a finite set of variables ranging over the data domain, and a finite set of variables ranging over data strings. At every step, it can make decisions based on the next in- put symbol, updating its state, remembering the input data value in its data variables, and updating data-string variables by concatenat- ing data-string variables and new symbols formed from data vari- ables, while avoiding duplication. We establish that the problems of checking functional equivalence of two streaming transducers, and of checking whether a streaming transducer satisfies pre/post verification conditions specified by streaming acceptors over in- put/output data-strings, are in PSPACE. We identify a class of imperative and a class of functional pro- grams, manipulating lists of data items, which can be effectively translated to streaming data-string transducers. The imperative pro- grams dynamically modify a singly-linked heap by changing next- pointers of heap-nodes and by adding new nodes. The main re- striction specifies how the next-pointers can be used for traversal. We also identify an expressively equivalent fragment of functional programs that traverse a list using syntactically restricted recursive calls. Our results lead to algorithms for assertion checking and for checking functional equivalence of two programs, written possibly in different programming styles, for commonly used routines such as insert, delete, and reverse. AU - Alur, Rajeev AU - Cerny, Pavol ID - 3325 IS - 1 TI - Streaming transducers for algorithmic verification of single pass list processing programs VL - 46 ER -