@inproceedings{2901, abstract = { We introduce the M-modes problem for graphical models: predicting the M label configurations of highest probability that are at the same time local maxima of the probability landscape. M-modes have multiple possible applications: because they are intrinsically diverse, they provide a principled alternative to non-maximum suppression techniques for structured prediction, they can act as codebook vectors for quantizing the configuration space, or they can form component centers for mixture model approximation. We present two algorithms for solving the M-modes problem. The first algorithm solves the problem in polynomial time when the underlying graphical model is a simple chain. The second algorithm solves the problem for junction chains. In synthetic and real dataset, we demonstrate how M-modes can improve the performance of prediction. We also use the generated modes as a tool to understand the topography of the probability distribution of configurations, for example with relation to the training set size and amount of noise in the data. }, author = {Chen, Chao and Kolmogorov, Vladimir and Yan, Zhu and Metaxas, Dimitris and Lampert, Christoph}, location = {Scottsdale, AZ, United States}, pages = {161 -- 169}, publisher = {JMLR}, title = {{Computing the M most probable modes of a graphical model}}, volume = {31}, year = {2013}, } @inproceedings{2906, abstract = {Motivated by an application in cell biology, we describe an extension of the kinetic data structures framework from Delaunay triangulations to fixed-radius alpha complexes. Our algorithm is implemented using CGAL, following the exact geometric computation paradigm. We report on several techniques to accelerate the computation that turn our implementation applicable to the underlying biological problem.}, author = {Kerber, Michael and Edelsbrunner, Herbert}, booktitle = {2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments}, location = {New Orleans, LA, United States}, pages = {70 -- 77}, publisher = {Society of Industrial and Applied Mathematics}, title = {{3D kinetic alpha complexes and their implementation}}, doi = {10.1137/1.9781611972931.6}, year = {2013}, } @inbook{2907, abstract = {Sex and recombination are among the most striking features of the living world, and they play a crucial role in allowing the evolution of complex adaptation. The sharing of genomes through the sexual union of different individuals requires elaborate behavioral and physiological adaptations. At the molecular level, the alignment of two DNA double helices, followed by their precise cutting and rejoining, is an extraordinary feat. Sex and recombination have diverse—and often surprising—evolutionary consequences: distinct sexes, elaborate mating displays, selfish genetic elements, and so on.}, author = {Barton, Nicholas H}, booktitle = {The Princeton Guide to Evolution}, isbn = {9780691149776}, pages = {328 -- 333}, publisher = {Princeton University Press}, title = {{Recombination and sex}}, year = {2013}, } @article{2908, abstract = {Hybridization is an almost inevitable component of speciation, and its study can tell us much about that process. However, hybridization itself may have a negligible influence on the origin of species: on the one hand, universally favoured alleles spread readily across hybrid zones, whilst on the other, spatially heterogeneous selection causes divergence despite gene flow. Thus, narrow hybrid zones or occasional hybridisation may hardly affect the process of divergence.}, author = {Barton, Nicholas H}, journal = {Journal of Evolutionary Biology}, number = {2}, pages = {267 -- 269}, publisher = {Wiley-Blackwell}, title = {{Does hybridisation influence speciation? }}, doi = {10.1111/jeb.12015}, volume = {26}, year = {2013}, } @article{2909, abstract = {We survey a class of models for spatially structured populations which we have called spatial Λ-Fleming–Viot processes. They arise from a flexible framework for modelling in which the key innovation is that random genetic drift is driven by a Poisson point process of spatial ‘events’. We demonstrate how this overcomes some of the obstructions to modelling populations which evolve in two- (and higher-) dimensional spatial continua, how its predictions match phenomena observed in data and how it fits with classical models. Finally we outline some directions for future research.}, author = {Barton, Nicholas H and Etheridge, Alison and Véber, Amandine}, journal = {Journal of Statistical Mechanics Theory and Experiment}, number = {1}, publisher = {IOP Publishing Ltd.}, title = {{Modelling evolution in a spatial continuum}}, doi = {10.1088/1742-5468/2013/01/P01002}, volume = {2013}, year = {2013}, } @article{2910, abstract = {Coalescent simulation has become an indispensable tool in population genetics and many complex evolutionary scenarios have been incorporated into the basic algorithm. Despite many years of intense interest in spatial structure, however, there are no available methods to simulate the ancestry of a sample of genes that occupy a spatial continuum. This is mainly due to the severe technical problems encountered by the classical model of isolation by distance. A recently introduced model solves these technical problems and provides a solid theoretical basis for the study of populations evolving in continuous space. We present a detailed algorithm to simulate the coalescent process in this model, and provide an efficient implementation of a generalised version of this algorithm as a freely available Python module.}, author = {Kelleher, Jerome and Barton, Nicholas H and Etheridge, Alison}, journal = {Bioinformatics}, number = {7}, pages = {955 -- 956}, publisher = {Oxford University Press}, title = {{Coalescent simulation in continuous space}}, doi = {10.1093/bioinformatics/btt067}, volume = {29}, year = {2013}, } @article{2913, abstract = {The ability of an organism to distinguish between various stimuli is limited by the structure and noise in the population code of its sensory neurons. Here we infer a distance measure on the stimulus space directly from the recorded activity of 100 neurons in the salamander retina. In contrast to previously used measures of stimulus similarity, this "neural metric" tells us how distinguishable a pair of stimulus clips is to the retina, based on the similarity between the induced distributions of population responses. We show that the retinal distance strongly deviates from Euclidean, or any static metric, yet has a simple structure: we identify the stimulus features that the neural population is jointly sensitive to, and show the support-vector-machine- like kernel function relating the stimulus and neural response spaces. We show that the non-Euclidean nature of the retinal distance has important consequences for neural decoding.}, author = {Tkacik, Gasper and Granot Atedgi, Einat and Segev, Ronen and Schneidman, Elad}, journal = {Physical Review Letters}, number = {5}, publisher = {American Physical Society}, title = {{Retinal metric: a stimulus distance measure derived from population neural responses}}, doi = {10.1103/PhysRevLett.110.058104}, volume = {110}, year = {2013}, } @article{2914, abstract = {The scale invariance of natural images suggests an analogy to the statistical mechanics of physical systems at a critical point. Here we examine the distribution of pixels in small image patches and show how to construct the corresponding thermodynamics. We find evidence for criticality in a diverging specific heat, which corresponds to large fluctuations in how "surprising" we find individual images, and in the quantitative form of the entropy vs energy. We identify special image configurations as local energy minima and show that average patches within each basin are interpretable as lines and edges in all orientations.}, author = {Stephens, Greg and Mora, Thierry and Tkacik, Gasper and Bialek, William}, journal = {Physical Review Letters}, number = {1}, publisher = {American Physical Society}, title = {{Statistical thermodynamics of natural images}}, doi = {10.1103/PhysRevLett.110.018701}, volume = {110}, year = {2013}, } @article{2918, abstract = {Oriented mitosis is essential during tissue morphogenesis. The Wnt/planar cell polarity (Wnt/PCP) pathway orients mitosis in a number of developmental systems, including dorsal epiblast cell divisions along the animal-vegetal (A-V) axis during zebrafish gastrulation. How Wnt signalling orients the mitotic plane is, however, unknown. Here we show that, in dorsal epiblast cells, anthrax toxin receptor 2a (Antxr2a) accumulates in a polarized cortical cap, which is aligned with the embryonic A-V axis and forecasts the division plane. Filamentous actin (F-actin) also forms an A-V polarized cap, which depends on Wnt/PCP and its effectors RhoA and Rock2. Antxr2a is recruited to the cap by interacting with actin. Antxr2a also interacts with RhoA and together they activate the diaphanous-related formin zDia2. Mechanistically, Antxr2a functions as a Wnt-dependent polarized determinant, which, through the action of RhoA and zDia2, exerts torque on the spindle to align it with the A-V axis. }, author = {Castanon, Irinka and Abrami, Laurence and Holtzer, Laurent and Heisenberg, Carl-Philipp J and Van Der Goot, Françoise and González Gaitán, Marcos}, journal = {Nature Cell Biology}, number = {1}, pages = {28 -- 39}, publisher = {Nature Publishing Group}, title = {{Anthrax toxin receptor 2a controls mitotic spindle positioning}}, doi = {10.1038/ncb2632}, volume = {15}, year = {2013}, } @article{2919, abstract = {The distribution of the phytohormone auxin regulates many aspects of plant development including growth response to gravity. Gravitropic root curvature involves coordinated and asymmetric cell elongation between the lower and upper side of the root, mediated by differential cellular auxin levels. The asymmetry in the auxin distribution is established and maintained by a spatio-temporal regulation of the PIN-FORMED (PIN) auxin transporter activity. We provide novel insights into the complex regulation of PIN abundance and activity during root gravitropism. We show that PIN2 turnover is differentially regulated on the upper and lower side of gravistimulated roots by distinct but partially overlapping auxin feedback mechanisms. In addition to regulating transcription and clathrin-mediated internalization, auxin also controls PIN abundance at the plasma membrane by promoting their vacuolar targeting and degradation. This effect of elevated auxin levels requires the activity of SKP-Cullin-F-box TIR1/AFB (SCF TIR1/AFB)-dependent pathway. Importantly, also suboptimal auxin levels mediate PIN degradation utilizing the same signalling pathway. These feedback mechanisms are functionally important during gravitropic response and ensure fine-tuning of auxin fluxes for maintaining as well as terminating asymmetric growth.}, author = {Baster, Pawel and Robert, Stéphanie and Kleine Vehn, Jürgen and Vanneste, Steffen and Kania, Urszula and Grunewald, Wim and De Rybel, Bert and Beeckman, Tom and Friml, Jirí}, journal = {EMBO Journal}, number = {2}, pages = {260 -- 274}, publisher = {Wiley-Blackwell}, title = {{SCF^TIR1 AFB-auxin signalling regulates PIN vacuolar trafficking and auxin fluxes during root gravitropism}}, doi = {10.1038/emboj.2012.310}, volume = {32}, year = {2013}, } @article{2920, abstract = {Cell polarisation in development is a common and fundamental process underlying embryo patterning and morphogenesis, and has been extensively studied over the past years. Our current knowledge of cell polarisation in development is predominantly based on studies that have analysed polarisation of single cells, such as eggs, or cellular aggregates with a stable polarising interface, such as cultured epithelial cells (St Johnston and Ahringer, 2010). However, in embryonic development, particularly of vertebrates, cell polarisation processes often encompass large numbers of cells that are placed within moving and proliferating tissues, and undergo mesenchymal-to-epithelial transitions with a highly complex spatiotemporal choreography. How such intricate cell polarisation processes in embryonic development are achieved has only started to be analysed. By using live imaging of neurulation in the transparent zebrafish embryo, Buckley et al (2012) now describe a novel polarisation strategy by which cells assemble an apical domain in the part of their cell body that intersects with the midline of the forming neural rod. This mechanism, along with the previously described mirror-symmetric divisions (Tawk et al, 2007), is thought to trigger formation of both neural rod midline and lumen.}, author = {Compagnon, Julien and Heisenberg, Carl-Philipp J}, journal = {EMBO Journal}, number = {1}, pages = {1 -- 3}, publisher = {Wiley-Blackwell}, title = {{Neurulation coordinating cell polarisation and lumen formation}}, doi = {10.1038/emboj.2012.325}, volume = {32}, year = {2013}, } @article{2926, abstract = {To fight infectious diseases, host immune defenses are employed at multiple levels. Sanitary behavior, such as pathogen avoidance and removal, acts as a first line of defense to prevent infection [1] before activation of the physiological immune system. Insect societies have evolved a wide range of collective hygiene measures and intensive health care toward pathogen-exposed group members [2]. One of the most common behaviors is allogrooming, in which nestmates remove infectious particles from the body surfaces of exposed individuals [3]. Here we show that, in invasive garden ants, grooming of fungus-exposed brood is effective beyond the sheer mechanical removal of fungal conidiospores; it also includes chemical disinfection through the application of poison produced by the ants themselves. Formic acid is the main active component of the poison. It inhibits fungal growth of conidiospores remaining on the brood surface after grooming and also those collected in the mouth of the grooming ant. This dual function is achieved by uptake of the poison droplet into the mouth through acidopore self-grooming and subsequent application onto the infectious brood via brood grooming. This extraordinary behavior extends the current understanding of grooming and the establishment of social immunity in insect societies.}, author = {Tragust, Simon and Mitteregger, Barbara and Barone, Vanessa and Konrad, Matthias and Ugelvig, Line V and Cremer, Sylvia}, journal = {Current Biology}, number = {1}, pages = {76 -- 82}, publisher = {Cell Press}, title = {{Ants disinfect fungus-exposed brood by oral uptake and spread of their poison}}, doi = {10.1016/j.cub.2012.11.034}, volume = {23}, year = {2013}, } @article{2939, abstract = {In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any Γ > 0, it returns only those homology classes with persistence at least Γ. Instead of the classical reduction via column operations, our algorithm performs rank computations on submatrices of the boundary matrix. For an arbitrary constant δ ∈ (0, 1), the running time is O (C (1 - δ) Γ R d (n) log n), where C (1 - δ) Γ is the number of homology classes with persistence at least (1 - δ) Γ, n is the total number of simplices in the complex, d its dimension, and R d (n) is the complexity of computing the rank of an n × n matrix with O (d n) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O (C (1 - δ) Γ n 2.376) algorithm, an O (C (1 - δ) Γ n 2.28) Las-Vegas algorithm, or an O (C (1 - δ) Γ n 2 + ε{lunate}) Monte-Carlo algorithm for an arbitrary ε{lunate} > 0. The space complexity of the Monte-Carlo version is bounded by O (d n) = O (n log n).}, author = {Chen, Chao and Kerber, Michael}, journal = {Computational Geometry: Theory and Applications}, number = {4}, pages = {435 -- 447}, publisher = {Elsevier}, title = {{An output sensitive algorithm for persistent homology}}, doi = {10.1016/j.comgeo.2012.02.010}, volume = {46}, year = {2013}, } @inproceedings{2940, abstract = {A chain rule for an entropy notion H(.) states that the entropy H(X) of a variable X decreases by at most l if conditioned on an l-bit string A, i.e., H(X|A)>= H(X)-l. More generally, it satisfies a chain rule for conditional entropy if H(X|Y,A)>= H(X|Y)-l. All natural information theoretic entropy notions we are aware of (like Shannon or min-entropy) satisfy some kind of chain rule for conditional entropy. Moreover, many computational entropy notions (like Yao entropy, unpredictability entropy and several variants of HILL entropy) satisfy the chain rule for conditional entropy, though here not only the quantity decreases by l, but also the quality of the entropy decreases exponentially in l. However, for the standard notion of conditional HILL entropy (the computational equivalent of min-entropy) the existence of such a rule was unknown so far. In this paper, we prove that for conditional HILL entropy no meaningful chain rule exists, assuming the existence of one-way permutations: there exist distributions X,Y,A, where A is a distribution over a single bit, but $H(X|Y)>>H(X|Y,A)$, even if we simultaneously allow for a massive degradation in the quality of the entropy. The idea underlying our construction is based on a surprising connection between the chain rule for HILL entropy and deniable encryption. }, author = {Krenn, Stephan and Pietrzak, Krzysztof Z and Wadia, Akshay}, editor = {Sahai, Amit}, location = {Tokyo, Japan}, pages = {23 -- 39}, publisher = {Springer}, title = {{A counterexample to the chain rule for conditional HILL entropy, and what deniable encryption has to do with it}}, doi = {10.1007/978-3-642-36594-2_2}, volume = {7785}, year = {2013}, } @article{2944, abstract = {We propose a two-step procedure for estimating multiple migration rates in an approximate Bayesian computation (ABC) framework, accounting for global nuisance parameters. The approach is not limited to migration, but generally of interest for inference problems with multiple parameters and a modular structure (e.g. independent sets of demes or loci). We condition on a known, but complex demographic model of a spatially subdivided population, motivated by the reintroduction of Alpine ibex (Capra ibex) into Switzerland. In the first step, the global parameters ancestral mutation rate and male mating skew have been estimated for the whole population in Aeschbacher et al. (Genetics 2012; 192: 1027). In the second step, we estimate in this study the migration rates independently for clusters of demes putatively connected by migration. For large clusters (many migration rates), ABC faces the problem of too many summary statistics. We therefore assess by simulation if estimation per pair of demes is a valid alternative. We find that the trade-off between reduced dimensionality for the pairwise estimation on the one hand and lower accuracy due to the assumption of pairwise independence on the other depends on the number of migration rates to be inferred: the accuracy of the pairwise approach increases with the number of parameters, relative to the joint estimation approach. To distinguish between low and zero migration, we perform ABC-type model comparison between a model with migration and one without. Applying the approach to microsatellite data from Alpine ibex, we find no evidence for substantial gene flow via migration, except for one pair of demes in one direction.}, author = {Aeschbacher, Simon and Futschik, Andreas and Beaumont, Mark}, journal = {Molecular Ecology}, number = {4}, pages = {987 -- 1002}, publisher = {Wiley-Blackwell}, title = {{Approximate Bayesian computation for modular inference problems with many parameters: the example of migration rates. }}, doi = {10.1111/mec.12165}, volume = {22}, year = {2013}, } @inproceedings{2948, abstract = {Many visual datasets are traditionally used to analyze the performance of different learning techniques. The evaluation is usually done within each dataset, therefore it is questionable if such results are a reliable indicator of true generalization ability. We propose here an algorithm to exploit the existing data resources when learning on a new multiclass problem. Our main idea is to identify an image representation that decomposes orthogonally into two subspaces: a part specific to each dataset, and a part generic to, and therefore shared between, all the considered source sets. This allows us to use the generic representation as un-biased reference knowledge for a novel classification task. By casting the method in the multi-view setting, we also make it possible to use different features for different databases. We call the algorithm MUST, Multitask Unaligned Shared knowledge Transfer. Through extensive experiments on five public datasets, we show that MUST consistently improves the cross-datasets generalization performance.}, author = {Tommasi, Tatiana and Quadrianto, Novi and Caputo, Barbara and Lampert, Christoph}, location = {Daejeon, Korea}, pages = {1 -- 15}, publisher = {Springer}, title = {{Beyond dataset bias: Multi-task unaligned shared knowledge transfer}}, doi = {10.1007/978-3-642-37331-2_1}, volume = {7724}, year = {2013}, } @article{3116, abstract = {Multithreaded programs coordinate their interaction through synchronization primitives like mutexes and semaphores, which are managed by an OS-provided resource manager. We propose algorithms for the automatic construction of code-aware resource managers for multithreaded embedded applications. Such managers use knowledge about the structure and resource usage (mutex and semaphore usage) of the threads to guarantee deadlock freedom and progress while managing resources in an efficient way. Our algorithms compute managers as winning strategies in certain infinite games, and produce a compact code description of these strategies. We have implemented the algorithms in the tool Cynthesis. Given a multithreaded program in C, the tool produces C code implementing a code-aware resource manager. We show in experiments that Cynthesis produces compact resource managers within a few minutes on a set of embedded benchmarks with up to 6 threads. © 2012 Springer Science+Business Media, LLC.}, author = {Chatterjee, Krishnendu and De Alfaro, Luca and Faella, Marco and Majumdar, Ritankar and Raman, Vishwanath}, journal = {Formal Methods in System Design}, number = {2}, pages = {142 -- 174}, publisher = {Springer}, title = {{Code aware resource management}}, doi = {10.1007/s10703-012-0170-4}, volume = {42}, year = {2013}, } @article{3261, abstract = {Cells in a developing embryo have no direct way of "measuring" their physical position. Through a variety of processes, however, the expression levels of multiple genes come to be correlated with position, and these expression levels thus form a code for "positional information." We show how to measure this information, in bits, using the gap genes in the Drosophila embryo as an example. Individual genes carry nearly two bits of information, twice as much as expected if the expression patterns consisted only of on/off domains separated by sharp boundaries. Taken together, four gap genes carry enough information to define a cell's location with an error bar of ~1% along the anterior-posterior axis of the embryo. This precision is nearly enough for each cell to have a unique identity, which is the maximum information the system can use, and is nearly constant along the length of the embryo. We argue that this constancy is a signature of optimality in the transmission of information from primary morphogen inputs to the output of the gap gene network.}, author = {Dubuis, Julien and Tkacik, Gasper and Wieschaus, Eric and Gregor, Thomas and Bialek, William}, journal = {PNAS}, number = {41}, pages = {16301 -- 16308}, publisher = {National Academy of Sciences}, title = {{Positional information, in bits}}, doi = {10.1073/pnas.1315642110}, volume = {110}, year = {2013}, } @misc{3321, author = {Quadrianto, Novi and Lampert, Christoph}, booktitle = {Encyclopedia of Systems Biology}, editor = {Dubitzky, Werner and Wolkenhauer, Olaf and Cho, Kwang and Yokota, Hiroki}, pages = {1069 -- 1069}, publisher = {Springer}, title = {{Kernel based learning}}, doi = {10.1007/978-1-4419-9863-7_604}, volume = {3}, year = {2013}, } @article{10895, abstract = {Due to their sessile lifestyles, plants need to deal with the limitations and stresses imposed by the changing environment. Plants cope with these by a remarkable developmental flexibility, which is embedded in their strategy to survive. Plants can adjust their size, shape and number of organs, bend according to gravity and light, and regenerate tissues that were damaged, utilizing a coordinating, intercellular signal, the plant hormone, auxin. Another versatile signal is the cation, Ca2+, which is a crucial second messenger for many rapid cellular processes during responses to a wide range of endogenous and environmental signals, such as hormones, light, drought stress and others. Auxin is a good candidate for one of these Ca2+-activating signals. However, the role of auxin-induced Ca2+ signaling is poorly understood. Here, we will provide an overview of possible developmental and physiological roles, as well as mechanisms underlying the interconnection of Ca2+ and auxin signaling. }, author = {Vanneste, Steffen and Friml, Jiří}, issn = {2223-7747}, journal = {Plants}, keywords = {Plant Science, Ecology, Ecology, Evolution, Behavior and Systematics}, number = {4}, pages = {650--675}, publisher = {MDPI}, title = {{Calcium: The missing link in auxin action}}, doi = {10.3390/plants2040650}, volume = {2}, year = {2013}, }