@misc{5395, abstract = {We study observation-based strategies for partially-observable Markov decision processes (POMDPs) with omega-regular objectives. An observation-based strategy relies on partial information about the history of a play, namely, on the past sequence of observa- tions. We consider the qualitative analysis problem: given a POMDP with an omega-regular objective, whether there is an observation-based strategy to achieve the objective with probability 1 (almost-sure winning), or with positive probability (positive winning). Our main results are twofold. First, we present a complete picture of the computational complexity of the qualitative analysis of POMDPs with parity objectives (a canonical form to express omega-regular objectives) and its subclasses. Our contribution consists in establishing several upper and lower bounds that were not known in literature. Second, we present optimal bounds (matching upper and lower bounds) on the memory required by pure and randomized observation-based strategies for the qualitative analysis of POMDPs with parity objectives and its subclasses.}, author = {Chatterjee, Krishnendu and Doyen, Laurent and Henzinger, Thomas A}, issn = {2664-1690}, pages = {20}, publisher = {IST Austria}, title = {{Qualitative analysis of partially-observable Markov decision processes}}, doi = {10.15479/AT:IST-2009-0001}, year = {2009}, } @article{599, abstract = {The human CDK8 subcomplex (CDK8, cyclin C, Med12, and Med13) negatively regulates transcription in ways not completely defined; past studies suggested CDK8 kinase activity was required for its repressive function. Using a reconstituted transcription system together with recombinant or endogenous CDK8 subcomplexes, we demonstrate that, in fact, Med12 and Med13 are critical for subcomplex-dependent repression, whereas CDK8 kinase activity is not. A hallmark of activated transcription is efficient reinitiation from promoter-bound scaffold complexes that recruit a series of pol II enzymes to the gene. Notably, the CDK8 submodule strongly represses even reinitiation events, suggesting a means to fine tune transcript levels. Structural and biochemical studies confirm the CDK8 submodule binds the Mediator leg/tail domain via the Med13 subunit, and this submodule-Mediator association precludes pol II recruitment. Collectively, these results reveal the CDK8 subcomplex functions as a simple switch that controls the Mediator-pol II interaction to help regulate transcription initiation and reinitiation events. As Mediator is generally required for expression of protein-coding genes, this may reflect a common mechanism by which activated transcription is shut down in human cells.}, author = {Knuesel, Matthew and Meyer, Krista and Bernecky, Carrie A and Taatjes, Dylan}, journal = {Genes and Development}, number = {4}, pages = {439 -- 451}, publisher = {Cold Spring Harbor Laboratory Press}, title = {{The human CDK8 subcomplex is a molecular switch that controls Mediator coactivator function}}, doi = {10.1101/gad.1767009}, volume = {23}, year = {2009}, } @article{6144, abstract = {Behaviours evolve by iterations of natural selection, but we have few insights into the molecular and neural mechanisms involved. Here we show that some Caenorhabditis elegans wild strains switch between two foraging behaviours in response to subtle changes in ambient oxygen. This finely tuned switch is conferred by a naturally variable hexacoordinated globin, GLB-5. GLB-5 acts with the atypical soluble guanylate cyclases1,2,3, which are a different type of oxygen binding protein, to tune the dynamic range of oxygen-sensing neurons close to atmospheric (21%) concentrations. Calcium imaging indicates that one group of these neurons is activated when oxygen rises towards 21%, and is inhibited as oxygen drops below 21%. The soluble guanylate cyclase GCY-35 is required for high oxygen to activate the neurons; GLB-5 provides inhibitory input when oxygen decreases below 21%. Together, these oxygen binding proteins tune neuronal and behavioural responses to a narrow oxygen concentration range close to atmospheric levels. The effect of the glb-5 gene on oxygen sensing and foraging is modified by the naturally variable neuropeptide receptor npr-1 (refs 4, 5), providing insights into how polygenic variation reshapes neural circuit function.}, author = {Persson, Annelie and Gross, Einav and Laurent, Patrick and Busch, Karl Emanuel and Bretes, Hugo and de Bono, Mario}, issn = {0028-0836}, journal = {Nature}, number = {7241}, pages = {1030--1033}, publisher = {Springer Nature}, title = {{Natural variation in a neural globin tunes oxygen sensing in wild Caenorhabditis elegans}}, doi = {10.1038/nature07820}, volume = {458}, year = {2009}, } @article{6145, author = {Cohen, Merav and Reale, Vincenzina and Olofsson, Birgitta and Knights, Andrew and Evans, Peter and de Bono, Mario}, issn = {1550-4131}, journal = {Cell Metabolism}, number = {4}, pages = {375--385}, publisher = {Elsevier}, title = {{Coordinated regulation of foraging and metabolism in C. elegans by RFamide neuropeptide signaling}}, doi = {10.1016/j.cmet.2009.02.003}, volume = {9}, year = {2009}, } @article{1983, abstract = {During many cellular processes such as cell division, polarization and motility, the plasma membrane does not only represent a passive physical barrier, but also provides a highly dynamic platform for the interplay between lipids, membrane binding proteins and cytoskeletal elements. Even though many regulators of these interactions are known, their mutual interdependence appears to be highly complex and difficult to study in a living cell. Over the past few years, in vitro studies on membrane-cytoskeleton interactions using biomimetic membranes turned out to be extremely helpful to get better mechanistic insight into the dynamics of these processes. In this review, we discuss some of the recent developments using in vitro assays to dissect the role of the players involved: lipids in the membrane, proteins binding to membranes and proteins binding to membrane proteins. We also summarize advantages and disadvantages of supported lipid bilayers as model membrane.}, author = {Martin Loose and Schwille, Petra }, journal = {Journal of Structural Biology}, number = {1}, pages = {143 -- 151}, publisher = {Academic Press}, title = {{Biomimetic membrane systems to study cellular organization}}, doi = {10.1016/j.jsb.2009.03.016}, volume = {168}, year = {2009}, } @article{1984, abstract = {In animal and plant cells, mitotic chromatin locally generates microtubules that self-organize into a mitotic spindle, and its dimensions and bipolar symmetry are essential for accurate chromosome segregation. By immobilizing microscopic chromatin-coated beads on slide surfaces using a microprinting technique, we have examined the effect of chromatin on the dimensions and symmetry of spindles in Xenopus laevis cytoplasmic extracts. While circular spots with diameters around 14-18 μm trigger bipolar spindle formation, larger spots generate an incorrect number of poles. We also examined lines of chromatin with various dimensions. Their length determined the number of poles that formed, with a 6 × 18 μm rectangular patch generating normal spindle morphology. Around longer lines, multiple poles formed and the structures were disorganized. While lines thinner than 10 μm generated symmetric structures, thicker lines induced the formation of asymmetric structures where all microtubules are on the same side of the line. Our results show that chromatin defines spindle shape and orientation. For a video summary of this article, see the PaperFlick file available with the online Supplemental Data.}, author = {Dinarina, Ana and Pugieux, Céline and Corral, Maria M and Martin Loose and Spatz, Joachim P and Karsenti, Éric and Nédélec, François J}, journal = {Cell}, number = {3}, pages = {502 -- 513}, publisher = {Cell Press}, title = {{Chromatin shapes the mitotic spindle}}, doi = {10.1016/j.cell.2009.05.027}, volume = {138}, year = {2009}, } @article{2067, author = {Beatriz Vicoso and Charlesworth, Brian}, journal = {Genetics}, number = {4}, pages = {1699 -- 1701}, publisher = {Genetics Society of America}, title = {{Recombination rates may affect the ratio of X to autosomal noncoding polymorphism in African populations of Drosophila melanogaster}}, doi = {10.1534/genetics.108.098004}, volume = {181}, year = {2009}, } @article{2068, abstract = {In Drosophila, there is a consistent deficit of male-biased genes on the X chromosome. It has been suggested that male-biased genes may evolve from initially unbiased genes as a result of increased expression levels in males. If transcription rates are limited, a large increase in expression in the testis may be harder to achieve for single-copy X-linked genes than for autosomal genes, because they are already hypertranscribed due to dosage compensation. This hypothesis predicts that the larger the increase in expression required to make a male-biased gene, the lower the chance of this being achievable if it is located on the X chromosome. Consequently, highly expressed male-biased genes should be located on the X chromosome less often than lowly expressed male-biased genes. This pattern is observed in our analysis of publicly available data, where microarray data or EST data are used to detect male-biased genes in D. melanogaster and to measure their expression levels. This is consistent with the idea that limitations in transcription rates may prevent male-biased genes from accumulating on the X chromosome.}, author = {Beatriz Vicoso and Charlesworth, Brian}, journal = {Journal of Molecular Evolution}, number = {5}, pages = {576 -- 583}, publisher = {Springer}, title = {{The deficit of male-biased genes on the D. melanogaster X chromosome is expression-dependent: A consequence of dosage compensation?}}, doi = {10.1007/s00239-009-9235-4}, volume = {68}, year = {2009}, } @article{2069, abstract = {Current models of X-linked and autosomal evolutionary rates often assume that the effective population size of the X chromosome (NeX) is equal to three-quarters of the autosomal population size (NeA). However, polymorphism studies of Drosophila melanogaster and D. simulans suggest that there are often significant deviations from this value. We have computed fixation rates of beneficial and deleterious mutations at X-linked and autosomal sites when this occurs. We find that NeX/NeA is a crucial parameter for the rates of evolution of X-linked sites compared to autosomal sites. Faster-X evolution due to the fixation of beneficial mutations can occur under a much wider range of levels of dominance when NeX/N eA > 3/4. We also examined various parameters that are known to influence the rates of evolution at X-linked and autosomal sites, such as different mutation rates in males and females and mutations that are sexually antagonistic, to determine which cases can lead to faster-X evolution. We show that, when the rate of nonsynonymous evolution is normalized by the rate of neutral evolution, a sex difference in mutation rate has no influence on the conditions for faster-X evolution.}, author = {Beatriz Vicoso and Charlesworth, Brian}, journal = {Evolution}, number = {9}, pages = {2413 -- 2426}, publisher = {Wiley-Blackwell}, title = {{Effective population size and the faster-X effect: An extended model}}, doi = {10.1111/j.1558-5646.2009.00719.x}, volume = {63}, year = {2009}, } @article{2070, abstract = {In many eukaryotic organisms, gender is determined by a pair of heteromorphic sex chromosomes. Degeneration of the non-recombining Y chromosome is a general facet of sex chromosome evolution. Selective pressure to restore expression levels of X-linked genes relative to autosomes accompanies Y-chromosome degeneration, thus driving the evolution of dosage compensation mechanisms. This review focuses on evolutionary aspects of dosage compensation, in light of recent advances in comparative and functional genomics that have substantially increased our understanding of the molecular mechanisms of dosage compensation and how it evolved. We review processes involved in sex chromosome evolution, and discuss the dynamic interaction between Y degeneration and the acquisition of dosage compensation. We compare mechanisms of dosage compensation and the origin of dosage compensation genes between different taxa and comment on sex chromosomes that apparently lack compensation mechanisms. Finally, we discuss how dosage compensation systems can also influence the evolution of well-established sex chromosomes.}, author = {Beatriz Vicoso and Bachtrog, Doris}, journal = {Chromosome Research}, number = {5}, pages = {585 -- 602}, publisher = {Springer}, title = {{Progress and prospects toward our understanding of the evolution of dosage compensation}}, doi = {10.1007/s10577-009-9053-y}, volume = {17}, year = {2009}, } @article{1038, abstract = {One possible way to produce ultra-cold, high-phase-space-density quantum gases of molecules in the rovibronic ground state is given by molecule association from quantum-degenerate atomic gases on a Feshbach resonance and subsequent coherent optical multi-photon transfer into the rovibronic ground state. In ultra-cold samples of Cs2 molecules, we observe two-photon dark resonances that connect the intermediate rovibrational level |v=73,J=2 with the rovibrational ground state |v=0,J=0 of the singlet X 1 ∑ g + ground-state potential. For precise dark resonance spectroscopy we exploit the fact that it is possible to efficiently populate the level |v=73,J=2 by two-photon transfer from the dissociation threshold with the stimulated Raman adiabatic passage (STIRAP) technique. We find that at least one of the two-photon resonances is sufficiently strong to allow future implementation of coherent STIRAP transfer of a molecular quantum gas to the rovibrational ground state |v=0,J=0.}, author = {Mark, Manfred and Danzl, Johann G and Haller, Elmar and Gustavsson, Mattias and Bouloufa, Nadia and Dulieu, Olivier and Salami, Houssam and Bergeman, Thomas and Ritsch, Helmut and Hart, Russell and Nägerl, Hanns}, journal = {Applied Physics B: Lasers and Optics}, number = {2}, pages = {219 -- 225}, publisher = {Springer}, title = {{Dark resonances for ground-state transfer of molecular quantum gases}}, doi = {10.1007/s00340-009-3407-1}, volume = {95}, year = {2009}, } @article{1040, abstract = {Ultracold atomic physics offers myriad possibilities to study strongly correlated many-body systems in lower dimensions. Typically, only ground-state phases are accessible. Using a tunable quantum gas of bosonic cesium atoms, we realized and controlled in one-dimensional geometry a highly excited quantum phase that is stabilized in the presence of attractive interactions by maintaining and strengthening quantum correlations across a confinement-induced resonance. We diagnosed the crossover from repulsive to attractive interactions in terms of the stiffness and energy of the system. Our results open up the experimental study of metastable, excited, many-body phases with strong correlations and their dynamical properties.}, author = {Haller, Elmar and Gustavsson, Mattias and Mark, Manfred and Danzl, Johann G and Hart, Russell and Pupillo, Guido and Nägerl, Hanns}, journal = {Science}, number = {5945}, pages = {1224 -- 1227}, publisher = {American Association for the Advancement of Science}, title = {{Realization of an excited, strongly correlated quantum gas Phase}}, doi = {10.1126/science.1175850}, volume = {325}, year = {2009}, } @article{1041, abstract = {We demonstrate efficient transfer of ultracold molecules into a deeply bound rovibrational level of the singlet ground state potential in the presence of an optical lattice. The overall molecule creation efficiency is 25%, and the transfer efficiency to the rovibrational level |v = 73, J = 2) is above 80%. We find that the molecules in |v = 73, J = 2) are trapped in the optical lattice, and that the lifetime in the lattice is limited by optical excitation by the lattice light. The molecule trapping time for a lattice depth of 15 atomic recoil energies is about 20 ms. We determine the trapping frequency by the lattice phase and amplitude modulation technique. It will now be possible to transfer the molecules to the rovibrational ground state |v = 0, J = 0) in the presence of the optical lattice.}, author = {Danzl, Johann G and Mark, Manfred and Haller, Elmar and Gustavsson, Mattias and Hart, Russell and Liem, Andreas and Zellmer, Holger and Nägerl, Hanns}, journal = {New Journal of Physics}, publisher = {IOP Publishing Ltd.}, title = {{Deeply bound ultracold molecules in an optical lattice}}, doi = {10.1088/1367-2630/11/5/055036}, volume = {11}, year = {2009}, } @article{1043, abstract = {One possibility for the creation of ultracold, high phase space density quantum gases of molecules in the rovibronic ground state relies on first associating weakly-bound molecules from quantum-degenerate atomic gases on a Feshbach resonance and then transferring the molecules via several steps of coherent two-photon stimulated Raman adiabatic passage (STIRAP) into the rovibronic ground state. Here, in ultracold samples of Cs2 Feshbach molecules produced out of ultracold samples of Cs atoms, we observe several optical transitions to deeply-bound rovibrational levels of the excited 0 u+ molecular potentials with high resolution. At least one of these transitions, although rather weak, allows efficient STIRAP transfer into the deeply-bound vibrational level v = 73> of the singlet X 1Σg+ ground state potential, as recently demonstrated (J. G. Danzl, E. Haller, M. Gustavsson, M. J. Mark, R. Hart, N. Bouloufa, O. Dulieu, H. Ritsch, and H.-C. Nägerl, Science, 2008, 321, 1062). From this level, the rovibrational ground state v = 0, J = 0> can be reached with one more transfer step. In total, our results show that coherent ground state transfer for Cs2 is possible using a maximum of two successive two-photon STIRAP processes or one single four-photon STIRAP process.}, author = {Danzl, Johann G and Mark, Manfred and Haller, Elmar and Gustavsson, Mattias and Bouloufa, Nadia and Dulieu, Olivier and Ritsch, Helmut and Hart, Russell and Nägerl, Hanns}, journal = {Faraday Discussions}, pages = {283 -- 295}, publisher = {Royal Society of Chemistry}, title = {{Precision molecular spectroscopy for ground state transfer of molecular quantum gases}}, doi = {10.1039/b820542f}, volume = {142}, year = {2009}, } @article{3197, abstract = {The problem of obtaining the maximum a posteriori estimate of a general discrete Markov random field (i.e., a Markov random field defined using a discrete set of labels) is known to be NP-hard. However, due to its central importance in many applications, several approximation algorithms have been proposed in the literature. In this paper, we present an analysis of three such algorithms based on convex relaxations: (i) LP-S: the linear programming (LP) relaxation proposed by Schlesinger (1976) for a special case and independently in Chekuri et al. (2001), Koster et al. (1998), and Wainwright et al. (2005) for the general case; (ii) QP-RL: the quadratic programming (QP) relaxation of Ravikumar and Lafferty (2006); and (iii) SOCP-MS: the second order cone programming (SOCP) relaxation first proposed by Muramatsu and Suzuki (2003) for two label problems and later extended by Kumar et al. (2006) for a general label set. We show that the SOCP-MS and the QP-RL relaxations are equivalent. Furthermore, we prove that despite the flexibility in the form of the constraints/objective function offered by QP and SOCP, the LP-S relaxation strictly dominates (i.e., provides a better approximation than) QP-RL and SOCP-MS. We generalize these results by defining a large class of SOCP (and equivalent QP) relaxations which is dominated by the LP-S relaxation. Based on these results we propose some novel SOCP relaxations which define constraints using random variables that form cycles or cliques in the graphical model representation of the random field. Using some examples we show that the new SOCP relaxations strictly dominate the previous approaches.}, author = {Kumar, M Pawan and Vladimir Kolmogorov and Torr, Philip H}, journal = {Journal of Machine Learning Research}, pages = {71 -- 106}, publisher = {Microtome Publishing}, title = {{An analysis of convex relaxations for MAP estimation of discrete MRFs}}, volume = {10}, year = {2009}, } @inproceedings{3199, abstract = {Many interactive image segmentation approaches use an objective function which includes appearance models as an unknown variable. Since the resulting optimization problem is NP-hard the segmentation and appearance are typically optimized separately, in an EM-style fashion. One contribution of this paper is to express the objective function purely in terms of the unknown segmentation, using higher-order cliques. This formulation reveals an interesting bias of the model towards balanced segmentations. Furthermore, it enables us to develop a new dual decomposition optimization procedure, which provides additionally a lower bound. Hence, we are able to improve on existing optimizers, and verify that for a considerable number of real world examples we even achieve global optimality. This is important since we are able, for the first time, to analyze the deficiencies of the model. Another contribution is to establish a property of a particular dual decomposition approach which involves convex functions depending on foreground area. As a consequence, we show that the optimal decomposition for our problem can be computed efficiently via a parametric maxflow algorithm.}, author = {Vicente, Sara and Vladimir Kolmogorov and Rother, Carsten}, pages = {755 -- 762}, publisher = {IEEE}, title = {{Joint optimization of segmentation and appearance models}}, doi = {10.1109/ICCV.2009.5459287}, year = {2009}, } @article{3200, abstract = {Motivated by various applications to computer vision, we consider the convex cost tension problem, which is the dual of the convex cost flow problem. In this paper, we first propose a primal algorithm for computing an optimal solution of the problem. Our primal algorithm iteratively updates primal variables by solving associated minimum cut problems. We show that the time complexity of the primal algorithm is O (K {dot operator} T (n, m)), where K is the range of primal variables and T (n, m) is the time needed to compute a minimum cut in a graph with n nodes and m edges. We then develop an improved version of the primal algorithm, called the primal-dual algorithm, by making good use of dual variables in addition to primal variables. Although its time complexity is the same as that of the primal algorithm, we can expect a better performance in practice. We finally consider an application to a computer vision problem called the panoramic image stitching.}, author = {Vladimir Kolmogorov and Shioura, Akiyoshi}, journal = {Discrete Optimization}, number = {4}, pages = {378 -- 393}, publisher = {Elsevier}, title = {{New algorithms for convex cost tension problem with application to computer vision}}, doi = {10.1016/j.disopt.2009.04.006}, volume = {6}, year = {2009}, } @inproceedings{3203, abstract = {In recent years the Markov Random Field (MRF) has become the de facto probabilistic model for low-level vision applications. However, in a maximum a posteriori (MAP) framework, MRFs inherently encourage delta function marginal statistics. By contrast, many low-level vision problems have heavy tailed marginal statistics, making the MRF model unsuitable. In this paper we introduce a more general Marginal Probability Field (MPF), of which the MRF is a special, linear case, and show that convex energy MPFs can be used to encourage arbitrary marginal statistics. We introduce a flexible, extensible framework for effectively optimizing the resulting NP-hard MAP problem, based around dual-decomposition and a modified mincost flow algorithm, and which achieves global optimality in some instances. We use a range of applications, including image denoising and texture synthesis, to demonstrate the benefits of this class of MPF over MRFs.}, author = {Woodford, Oliver J and Rother, Carsten and Vladimir Kolmogorov}, pages = {2319 -- 2326}, publisher = {IEEE}, title = {{A global perspective on MAP inference for low level vision}}, doi = {10.1109/ICCV.2009.5459434}, year = {2009}, } @inproceedings{3230, abstract = {We present a new approach to the design of IND-CCA2 secure hybrid encryption schemes in the standard model. Our approach provides an efficient generic transformation from 1-universal to 2-universal hash proof systems. The transformation involves a randomness extractor based on a 4-wise independent hash function as the key derivation function. Our methodology can be instantiated with efficient schemes based on standard intractability assumptions such as Decisional Diffie-Hellman, Quadratic Residuosity, and Paillier's Decisional Composite Residuosity. Interestingly, our framework also allows to prove IND-CCA2 security of a hybrid version of 1991's Damgård's ElGamal public-key encryption scheme under the DDH assumption. }, author = {Kiltz, Eike and Krzysztof Pietrzak and Stam, Martijn and Yung, Moti}, pages = {590 -- 609}, publisher = {Springer}, title = {{A new randomness extraction paradigm for hybrid encryption}}, doi = {10.1007/978-3-642-01001-9_34}, volume = {5479}, year = {2009}, } @inproceedings{3231, abstract = {We investigate the security of "padding-based" encryption schemes in the standard model. This class contains all public-key encryption schemes where the encryption algorithm first applies some invertible public transformation to the message (the "padding"), followed by a trapdoor permutation. In particular, this class contains OAEP and its variants. Our main result is a black-box impossibility result showing that one cannot prove any such padding-based scheme chosen-ciphertext secure even assuming the existence of ideal trapdoor permutations. The latter is a strong ideal abstraction of trapdoor permutations which inherits all security properties of uniform random permutations. }, author = {Kiltz, Eike and Krzysztof Pietrzak}, pages = {389 -- 406}, publisher = {Springer}, title = {{On the security of padding based encryption schemes Why We cannot prove OAEP secure in the standard model}}, doi = {10.1007/978-3-642-01001-9_23}, volume = {5479}, year = {2009}, }