@article{1145, abstract = {Auxin directs plant ontogenesis via differential accumulation within tissues depending largely on the activity of PIN proteins that mediate auxin efflux from cells and its directional cell-to-cell transport. Regardless of the developmental importance of PINs, the structure of these transporters is poorly characterized. Here, we present experimental data concerning protein topology of plasma membrane-localized PINs. Utilizing approaches based on pH-dependent quenching of fluorescent reporters combined with immunolocalization techniques, we mapped the membrane topology of PINs and further cross-validated our results using available topology modeling software. We delineated the topology of PIN1 with two transmembrane (TM) bundles of five α-helices linked by a large intracellular loop and a C-terminus positioned outside the cytoplasm. Using constraints derived from our experimental data, we also provide an updated position of helical regions generating a verisimilitude model of PIN1. Since the canonical long PINs show a high degree of conservation in TM domains and auxin transport capacity has been demonstrated for Arabidopsis representatives of this group, this empirically enhanced topological model of PIN1 will be an important starting point for further studies on PIN structure–function relationships. In addition, we have established protocols that can be used to probe the topology of other plasma membrane proteins in plants. © 2016 The Authors}, author = {Nodzyński, Tomasz and Vanneste, Steffen and Zwiewka, Marta and Pernisová, Markéta and Hejátko, Jan and Friml, Jirí}, journal = {Molecular Plant}, number = {11}, pages = {1504 -- 1519}, publisher = {Cell Press}, title = {{Enquiry into the topology of plasma membrane localized PIN auxin transport components}}, doi = {10.1016/j.molp.2016.08.010}, volume = {9}, year = {2016}, } @article{1147, abstract = {Apical dominance is one of the fundamental developmental phenomena in plant biology, which determines the overall architecture of aerial plant parts. Here we show apex decapitation activated competition for dominance in adjacent upper and lower axillary buds. A two-nodal-bud pea (Pisum sativum L.) was used as a model system to monitor and assess auxin flow, auxin transport channels, and dormancy and initiation status of axillary buds. Auxin flow was manipulated by lateral stem wounds or chemically by auxin efflux inhibitors 2,3,5-triiodobenzoic acid (TIBA), 1-N-naphtylphtalamic acid (NPA), or protein synthesis inhibitor cycloheximide (CHX) treatments, which served to interfere with axillary bud competition. Redirecting auxin flow to different points influenced which bud formed the outgrowing and dominant shoot. The obtained results proved that competition between upper and lower axillary buds as secondary auxin sources is based on the same auxin canalization principle that operates between the shoot apex and axillary bud. © The Author(s) 2016.}, author = {Balla, Jozef and Medved'Ová, Zuzana and Kalousek, Petr and Matiješčuková, Natálie and Friml, Jirí and Reinöhl, Vilém and Procházka, Stanislav}, journal = {Scientific Reports}, publisher = {Nature Publishing Group}, title = {{Auxin flow mediated competition between axillary buds to restore apical dominance}}, doi = {10.1038/srep35955}, volume = {6}, year = {2016}, } @article{1148, abstract = {Continuous-time Markov chain (CTMC) models have become a central tool for understanding the dynamics of complex reaction networks and the importance of stochasticity in the underlying biochemical processes. When such models are employed to answer questions in applications, in order to ensure that the model provides a sufficiently accurate representation of the real system, it is of vital importance that the model parameters are inferred from real measured data. This, however, is often a formidable task and all of the existing methods fail in one case or the other, usually because the underlying CTMC model is high-dimensional and computationally difficult to analyze. The parameter inference methods that tend to scale best in the dimension of the CTMC are based on so-called moment closure approximations. However, there exists a large number of different moment closure approximations and it is typically hard to say a priori which of the approximations is the most suitable for the inference procedure. Here, we propose a moment-based parameter inference method that automatically chooses the most appropriate moment closure method. Accordingly, contrary to existing methods, the user is not required to be experienced in moment closure techniques. In addition to that, our method adaptively changes the approximation during the parameter inference to ensure that always the best approximation is used, even in cases where different approximations are best in different regions of the parameter space. © 2016 Elsevier Ireland Ltd}, author = {Schilling, Christian and Bogomolov, Sergiy and Henzinger, Thomas A and Podelski, Andreas and Ruess, Jakob}, journal = {Biosystems}, pages = {15 -- 25}, publisher = {Elsevier}, title = {{Adaptive moment closure for parameter inference of biochemical reaction networks}}, doi = {10.1016/j.biosystems.2016.07.005}, volume = {149}, year = {2016}, } @article{1149, abstract = {We study the usefulness of two most prominent publicly available rigorous ODE integrators: one provided by the CAPD group (capd.ii.uj.edu.pl), the other based on the COSY Infinity project (cosyinfinity.org). Both integrators are capable of handling entire sets of initial conditions and provide tight rigorous outer enclosures of the images under a time-T map. We conduct extensive benchmark computations using the well-known Lorenz system, and compare the computation time against the final accuracy achieved. We also discuss the effect of a few technical parameters, such as the order of the numerical integration method, the value of T, and the phase space resolution. We conclude that COSY may provide more precise results due to its ability of avoiding the variable dependency problem. However, the overall cost of computations conducted using CAPD is typically lower, especially when intervals of parameters are involved. Moreover, access to COSY is limited (registration required) and the rigorous ODE integrators are not publicly available, while CAPD is an open source free software project. Therefore, we recommend the latter integrator for this kind of computations. Nevertheless, proper choice of the various integration parameters turns out to be of even greater importance than the choice of the integrator itself. © 2016 IMACS. Published by Elsevier B.V. All rights reserved.}, author = {Miyaji, Tomoyuki and Pilarczyk, Pawel and Gameiro, Marcio and Kokubu, Hiroshi and Mischaikow, Konstantin}, journal = {Applied Numerical Mathematics}, pages = {34 -- 47}, publisher = {Elsevier}, title = {{A study of rigorous ODE integrators for multi scale set oriented computations}}, doi = {10.1016/j.apnum.2016.04.005}, volume = {107}, year = {2016}, } @article{1150, abstract = {When neutrophils infiltrate a site of inflammation, they have to stop at the right place to exert their effector function. In this issue of Developmental Cell, Wang et al. (2016) show that neutrophils sense reactive oxygen species via the TRPM2 channel to arrest migration at their target site. © 2016 Elsevier Inc.}, author = {Renkawitz, Jörg and Sixt, Michael K}, journal = {Developmental Cell}, number = {5}, pages = {448 -- 450}, publisher = {Cell Press}, title = {{A Radical Break Restraining Neutrophil Migration}}, doi = {10.1016/j.devcel.2016.08.017}, volume = {38}, year = {2016}, } @article{1151, abstract = {Tissue patterning in multicellular organisms is the output of precise spatio–temporal regulation of gene expression coupled with changes in hormone dynamics. In plants, the hormone auxin regulates growth and development at every stage of a plant’s life cycle. Auxin signaling occurs through binding of the auxin molecule to a TIR1/AFB F-box ubiquitin ligase, allowing interaction with Aux/IAA transcriptional repressor proteins. These are subsequently ubiquitinated and degraded via the 26S proteasome, leading to derepression of auxin response factors (ARFs). How auxin is able to elicit such a diverse range of developmental responses through a single signaling module has not yet been resolved. Here we present an alternative auxin-sensing mechanism in which the ARF ARF3/ETTIN controls gene expression through interactions with process-specific transcription factors. This noncanonical hormonesensing mechanism exhibits strong preference for the naturally occurring auxin indole 3-acetic acid (IAA) and is important for coordinating growth and patterning in diverse developmental contexts such as gynoecium morphogenesis, lateral root emergence, ovule development, and primary branch formation. Disrupting this IAA-sensing ability induces morphological aberrations with consequences for plant fitness. Therefore, our findings introduce a novel transcription factor-based mechanism of hormone perception in plants. © 2016 Simonini et al.}, author = {Simonini, Sara and Deb, Joyita and Moubayidin, Laila and Stephenson, Pauline and Valluru, Manoj and Freire Rios, Alejandra and Sorefan, Karim and Weijers, Dolf and Friml, Jirí and Östergaard, Lars}, journal = {Genes and Development}, number = {20}, pages = {2286 -- 2296}, publisher = {Cold Spring Harbor Laboratory Press}, title = {{A noncanonical auxin sensing mechanism is required for organ morphogenesis in arabidopsis}}, doi = {10.1101/gad.285361.116}, volume = {30}, year = {2016}, } @article{1153, abstract = {Differential cell growth enables flexible organ bending in the presence of environmental signals such as light or gravity. A prominent example of the developmental processes based on differential cell growth is the formation of the apical hook that protects the fragile shoot apical meristem when it breaks through the soil during germination. Here, we combined in silico and in vivo approaches to identify a minimal mechanism producing auxin gradient-guided differential growth during the establishment of the apical hook in the model plant Arabidopsis thaliana. Computer simulation models based on experimental data demonstrate that asymmetric expression of the PIN-FORMED auxin efflux carrier at the concave (inner) versus convex (outer) side of the hook suffices to establish an auxin maximum in the epidermis at the concave side of the apical hook. Furthermore, we propose a mechanism that translates this maximum into differential growth, and thus curvature, of the apical hook. Through a combination of experimental and in silico computational approaches, we have identified the individual contributions of differential cell elongation and proliferation to defining the apical hook and reveal the role of auxin-ethylene crosstalk in balancing these two processes. © 2016 American Society of Plant Biologists. All rights reserved.}, author = {Žádníková, Petra and Wabnik, Krzysztof T and Abuzeineh, Anas and Gallemí, Marçal and Van Der Straeten, Dominique and Smith, Richard and Inze, Dirk and Friml, Jirí and Prusinkiewicz, Przemysław and Benková, Eva}, journal = {Plant Cell}, number = {10}, pages = {2464 -- 2477}, publisher = {American Society of Plant Biologists}, title = {{A model of differential growth guided apical hook formation in plants}}, doi = {10.1105/tpc.15.00569}, volume = {28}, year = {2016}, } @article{1154, abstract = {Cellular locomotion is a central hallmark of eukaryotic life. It is governed by cell-extrinsic molecular factors, which can either emerge in the soluble phase or as immobilized, often adhesive ligands. To encode for direction, every cue must be present as a spatial or temporal gradient. Here, we developed a microfluidic chamber that allows measurement of cell migration in combined response to surface immobilized and soluble molecular gradients. As a proof of principle we study the response of dendritic cells to their major guidance cues, chemokines. The majority of data on chemokine gradient sensing is based on in vitro studies employing soluble gradients. Despite evidence suggesting that in vivo chemokines are often immobilized to sugar residues, limited information is available how cells respond to immobilized chemokines. We tracked migration of dendritic cells towards immobilized gradients of the chemokine CCL21 and varying superimposed soluble gradients of CCL19. Differential migratory patterns illustrate the potential of our setup to quantitatively study the competitive response to both types of gradients. Beyond chemokines our approach is broadly applicable to alternative systems of chemo- and haptotaxis such as cells migrating along gradients of adhesion receptor ligands vs. any soluble cue. }, author = {Schwarz, Jan and Bierbaum, Veronika and Merrin, Jack and Frank, Tino and Hauschild, Robert and Bollenbach, Mark Tobias and Tay, Savaş and Sixt, Michael K and Mehling, Matthias}, journal = {Scientific Reports}, publisher = {Nature Publishing Group}, title = {{A microfluidic device for measuring cell migration towards substrate bound and soluble chemokine gradients}}, doi = {10.1038/srep36440}, volume = {6}, year = {2016}, } @article{1156, abstract = {Let k, n, and r be positive integers with k < n and r≤⌊nk⌋. We determine the facets of the r-stable n, k-hypersimplex. As a result, it turns out that the r-stable n, k-hypersimplex has exactly 2n facets for every r<⌊nk⌋. We then utilize the equations of the facets to study when the r-stable hypersimplex is Gorenstein. For every k > 0 we identify an infinite collection of Gorenstein r-stable hypersimplices, consequently expanding the collection of r-stable hypersimplices known to have unimodal Ehrhart δ-vectors.}, author = {Hibi, Takayugi and Liam Solus}, journal = {Annals of Combinatorics}, number = {4}, pages = {815 -- 829}, publisher = {Springer}, title = {{Facets of the r-stable (n, k)-hypersimplex}}, doi = {10.1007/s00026-016-0325-x}, volume = {20}, year = {2016}, } @article{1157, abstract = {We consider sample covariance matrices of the form Q = ( σ1/2X)(σ1/2X)∗, where the sample X is an M ×N random matrix whose entries are real independent random variables with variance 1/N and whereσ is an M × M positive-definite deterministic matrix. We analyze the asymptotic fluctuations of the largest rescaled eigenvalue of Q when both M and N tend to infinity with N/M →d ϵ (0,∞). For a large class of populations σ in the sub-critical regime, we show that the distribution of the largest rescaled eigenvalue of Q is given by the type-1 Tracy-Widom distribution under the additional assumptions that (1) either the entries of X are i.i.d. Gaussians or (2) that σ is diagonal and that the entries of X have a sub-exponential decay.}, author = {Lee, Ji and Schnelli, Kevin}, journal = {Annals of Applied Probability}, number = {6}, pages = {3786 -- 3839}, publisher = {Institute of Mathematical Statistics}, title = {{Tracy-widom distribution for the largest eigenvalue of real sample covariance matrices with general population}}, doi = {10.1214/16-AAP1193}, volume = {26}, year = {2016}, } @article{11574, abstract = {We present new results from the widest narrow-band survey search for Lyα emitters at z = 5.7, just after reionization. We survey a total of 7 deg2 spread over the COSMOS, UDS and SA22 fields. We find over 11 000 line emitters, out of which 514 are robust Lyα candidates at z = 5.7 within a volume of 6.3 × 106 Mpc3. Our Lyα emitters span a wide range in Lyα luminosities, from faint to bright (LLyα ∼ 1042.5–44 erg s−1) and rest-frame equivalent widths (EW0 ∼ 25–1000 Å) in a single, homogeneous data set. By combining all our fields, we find that the faint end slope of the z = 5.7 Lyα luminosity function is very steep, with α=−2.3+0.4−0.3⁠. We also present an updated z = 6.6 Lyα luminosity function, based on comparable volumes and obtained with the same methods, which we directly compare with that at z = 5.7. We find a significant decline of the number density of faint Lyα emitters from z = 5.7 to 6.6 (by 0.5 ± 0.1 dex), but no evolution at the bright end/no evolution in L*. Faint Lyα emitters at z = 6.6 show much more extended haloes than those at z = 5.7, suggesting that neutral Hydrogen plays an important role, increasing the scattering and leading to observations missing faint Lyα emission within the epoch of reionization. Altogether, our results suggest that we are observing patchy reionization which happens first around the brightest Lyα emitters, allowing the number densities of those sources to remain unaffected by the increase of neutral Hydrogen fraction from z ∼ 5 to 7.}, author = {Santos, Sérgio and Sobral, David and Matthee, Jorryt J}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: high-redshift, galaxies: luminosity function, mass function, cosmology: observations, dark ages, reionization, first stars}, number = {2}, pages = {1678--1691}, publisher = {Oxford University Press}, title = {{The Lyα luminosity function at z= 5.7–6.6 and the steep drop of the faint end: Implications for reionization}}, doi = {10.1093/mnras/stw2076}, volume = {463}, year = {2016}, } @article{11575, abstract = {We investigate correlations between different physical properties of star-forming galaxies in the ‘Evolution and Assembly of GaLaxies and their Environments’ (EAGLE) cosmological hydrodynamical simulation suite over the redshift range 0 ≤ z ≤ 4.5. A principal component analysis reveals that neutral gas fraction (fgas,neutral), stellar mass (Mstellar) and star formation rate (SFR) account for most of the variance seen in the population, with galaxies tracing a two-dimensional, nearly flat, surface in the three-dimensional space of fgas, neutral–Mstellar–SFR with little scatter. The location of this plane varies little with redshift, whereas galaxies themselves move along the plane as their fgas, neutral and SFR drop with redshift. The positions of galaxies along the plane are highly correlated with gas metallicity. The metallicity can therefore be robustly predicted from fgas, neutral, or from the Mstellar and SFR. We argue that the appearance of this ‘Fundamental Plane of star formation’ is a consequence of self-regulation, with the plane's curvature set by the dependence of the SFR on gas density and metallicity. We analyse a large compilation of observations spanning the redshift range 0 ≲ z ≲ 3, and find that such a plane is also present in the data. The properties of the observed Fundamental Plane of star formation are in good agreement with EAGLE's predictions.}, author = {Lagos, Claudia del P. and Theuns, Tom and Schaye, Joop and Furlong, Michelle and Bower, Richard G. and Schaller, Matthieu and Crain, Robert A. and Trayford, James W. and Matthee, Jorryt J}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics stars: formation, ISM: evolution, galaxies: evolution, galaxies: formation, galaxies: ISM}, number = {3}, pages = {2632--2650}, publisher = {Oxford University Press}, title = {{The Fundamental Plane of star formation in galaxies revealed by the EAGLE hydrodynamical simulations}}, doi = {10.1093/mnras/stw717}, volume = {459}, year = {2016}, } @article{11576, abstract = {We use new near-infrared spectroscopic observations to investigate the nature and evolution of the most luminous Hα emitters at z ∼ 0.8–2.23, which evolve strongly in number density over this period, and compare them to more typical Hα emitters. We study 59 luminous Hα emitters with LHα > L∗Hα⁠, roughly equally split per redshift slice at z ∼ 0.8, 1.47 and 2.23 from the HiZELS and CF-HiZELS surveys. We find that, overall, 30 ± 8 per cent are active galactic nuclei [AGNs; 80 ± 30 per cent of these AGNs are broad-line AGNs, BL-AGNs], and we find little to no evolution in the AGN fraction with redshift, within the errors. However, the AGN fraction increases strongly with Hα luminosity and correlates best with LHα/L∗Hα(z)⁠. While LHα ≤ L∗Hα(z) Hα emitters are largely dominated by star-forming galaxies (>80 per cent), the most luminous Hα emitters (⁠LHα>10L∗Hα(z)⁠) at any cosmic time are essentially all BL-AGN. Using our AGN-decontaminated sample of luminous star-forming galaxies, and integrating down to a fixed Hα luminosity, we find a factor of ∼1300 evolution in the star formation rate density from z = 0 to 2.23. This is much stronger than the evolution from typical Hα star-forming galaxies and in line with the evolution seen for constant luminosity cuts used to select ‘ultraluminous’ infrared galaxies and/or sub-millimetre galaxies. By taking into account the evolution in the typical Hα luminosity, we show that the most strongly star-forming Hα-selected galaxies at any epoch (⁠LHα>L∗Hα(z)⁠) contribute the same fractional amount of ≈15 per cent to the total star formation rate density, at least up to z = 2.23.}, author = {Sobral, David and Kohn, Saul A. and Best, Philip N. and Smail, Ian and Harrison, Chris M. and Stott, John and Calhau, João and Matthee, Jorryt J}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: evolution, galaxies: high-redshift, cosmology: observations}, number = {2}, pages = {1739--1752}, publisher = {Oxford University Press}, title = {{The most luminous H α emitters at z ∼ 0.8–2.23 from HiZELS: Evolution of AGN and star-forming galaxies}}, doi = {10.1093/mnras/stw022}, volume = {457}, year = {2016}, } @article{11578, abstract = {We present the first results from our CAlibrating LYMan α with Hα (CALYMHA) pilot survey at the Isaac Newton Telescope. We measure Lyα emission for 488 Hα selected galaxies at z = 2.23 from High-z Emission Line Survey in the COSMOS and UDS fields with a specially designed narrow-band filter (λc = 3918 Å, Δλ = 52 Å). We find 17 dual Hα-Lyα emitters [fLyα > 5 × 10−17 erg s−1 cm−2, of which five are X-ray active galactic nuclei (AGN)]. For star-forming galaxies, we find a range of Lyα escape fractions (fesc, measured with 3 arcsec apertures) from 2 to 30 per cent. These galaxies have masses from 3 × 108 M⊙ to 1011 M⊙ and dust attenuations E(B − V) = 0–0.5. Using stacking, we measure a median escape fraction of 1.6 ± 0.5 per cent (4.0 ± 1.0 per cent without correcting Hα for dust), but show that this depends on galaxy properties. The stacked fesc tends to decrease with increasing star formation rate and dust attenuation. However, at the highest masses and dust attenuations, we detect individual galaxies with fesc much higher than the typical values from stacking, indicating significant scatter in the values of fesc. Relations between fesc and UV slope are bimodal, with high fesc for either the bluest or reddest galaxies. We speculate that this bimodality and large scatter in the values of fesc is due to additional physical mechanisms such as outflows facilitating fesc for dusty/massive systems. Lyα is significantly more extended than Hα and the UV. fesc continues to increase up to at least 20 kpc (3σ, 40 kpc [2σ]) for typical star-forming galaxies and thus the aperture is the most important predictor of fesc.}, author = {Matthee, Jorryt J and Sobral, David and Oteo, Iván and Best, Philip and Smail, Ian and Röttgering, Huub and Paulino-Afonso, Ana}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: evolution, galaxies: high-redshift, galaxies: ISM}, number = {1}, pages = {449--467}, publisher = {Oxford University Press}, title = {{The CALYMHA survey: Lyα escape fraction and its dependence on galaxy properties at z = 2.23}}, doi = {10.1093/mnras/stw322}, volume = {458}, year = {2016}, } @article{1158, abstract = {Speciation results from the progressive accumulation of mutations that decrease the probability of mating between parental populations or reduce the fitness of hybrids—the so-called species barriers. The speciation genomic literature, however, is mainly a collection of case studies, each with its own approach and specificities, such that a global view of the gradual process of evolution from one to two species is currently lacking. Of primary importance is the prevalence of gene flow between diverging entities, which is central in most species concepts and has been widely discussed in recent years. Here, we explore the continuum of speciation thanks to a comparative analysis of genomic data from 61 pairs of populations/species of animals with variable levels of divergence. Gene flow between diverging gene pools is assessed under an approximate Bayesian computation (ABC) framework. We show that the intermediate "grey zone" of speciation, in which taxonomy is often controversial, spans from 0.5% to 2% of net synonymous divergence, irrespective of species life history traits or ecology. Thanks to appropriate modeling of among-locus variation in genetic drift and introgression rate, we clarify the status of the majority of ambiguous cases and uncover a number of cryptic species. Our analysis also reveals the high incidence in animals of semi-isolated species (when some but not all loci are affected by barriers to gene flow) and highlights the intrinsic difficulty, both statistical and conceptual, of delineating species in the grey zone of speciation.}, author = {Roux, Camille and Fraisse, Christelle and Romiguier, Jonathan and Anciaux, Youann and Galtier, Nicolas and Bierne, Nicolas}, journal = {PLoS Biology}, number = {12}, publisher = {Public Library of Science}, title = {{Shedding light on the grey zone of speciation along a continuum of genomic divergence}}, doi = {10.1371/journal.pbio.2000234}, volume = {14}, year = {2016}, } @inproceedings{1164, abstract = {A drawing of a graph G is radial if the vertices of G are placed on concentric circles C1, … , Ck with common center c, and edges are drawn radially: every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. A pair of edges e and f in a graph is independent if e and f do not share a vertex. We show that a graph G is radial planar if G has a radial drawing in which every two independent edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the strong Hanani-Tutte theorem for radial planarity. This characterization yields a very simple algorithm for radial planarity testing.}, author = {Fulek, Radoslav and Pelsmajer, Michael and Schaefer, Marcus}, location = {Athens, Greece}, pages = {468 -- 481}, publisher = {Springer}, title = {{Hanani-Tutte for radial planarity II}}, doi = {10.1007/978-3-319-50106-2_36}, volume = {9801}, year = {2016}, } @inproceedings{1165, abstract = {We show that c-planarity is solvable in quadratic time for flat clustered graphs with three clusters if the combinatorial embedding of the underlying graph is fixed. In simpler graph-theoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2-sphere, our algorithm decides if we can augment G by adding edges without creating an edge-crossing so that in the resulting spherical graph the vertices of each part induce a connected sub-graph. We proceed by a reduction to the problem of testing the existence of a perfect matching in planar bipartite graphs. We formulate our result in a slightly more general setting of cyclic clustered graphs, i.e., the simple graph obtained by contracting each cluster, where we disregard loops and multi-edges, is a cycle.}, author = {Fulek, Radoslav}, location = {Athens, Greece}, pages = {94 -- 106}, publisher = {Springer}, title = {{C-planarity of embedded cyclic c-graphs}}, doi = {10.1007/978-3-319-50106-2_8}, volume = {9801 }, year = {2016}, } @inproceedings{1166, abstract = {POMDPs are standard models for probabilistic planning problems, where an agent interacts with an uncertain environment. We study the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a policy to ensure that the target set is reached with probability 1 (almost-surely). While in general the problem is EXPTIMEcomplete, in many practical cases policies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. In this work, we first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach. © 2016, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.}, author = {Chatterjee, Krishnendu and Chmelik, Martin and Davies, Jessica}, booktitle = {Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence}, location = {Phoenix, AZ, USA}, pages = {3225 -- 3232}, publisher = {AAAI Press}, title = {{A symbolic SAT based algorithm for almost sure reachability with small strategies in pomdps}}, volume = {2016}, year = {2016}, } @article{1167, abstract = {Evolutionary pathways describe trajectories of biological evolution in the space of different variants of organisms (genotypes). The probability of existence and the number of evolutionary pathways that lead from a given genotype to a better-adapted genotype are important measures of accessibility of local fitness optima and the reproducibility of evolution. Both quantities have been studied in simple mathematical models where genotypes are represented as binary sequences of two types of basic units, and the network of permitted mutations between the genotypes is a hypercube graph. However, it is unclear how these results translate to the biologically relevant case in which genotypes are represented by sequences of more than two units, for example four nucleotides (DNA) or 20 amino acids (proteins), and the mutational graph is not the hypercube. Here we investigate accessibility of the best-adapted genotype in the general case of K > 2 units. Using computer generated and experimental fitness landscapes we show that accessibility of the global fitness maximum increases with K and can be much higher than for binary sequences. The increase in accessibility comes from the increase in the number of indirect trajectories exploited by evolution for higher K. As one of the consequences, the fraction of genotypes that are accessible increases by three orders of magnitude when the number of units K increases from 2 to 16 for landscapes of size N ∼ 106genotypes. This suggests that evolution can follow many different trajectories on such landscapes and the reconstruction of evolutionary pathways from experimental data might be an extremely difficult task.}, author = {Zagórski, Marcin P and Burda, Zdzisław and Wacław, Bartłomiej}, journal = {PLoS Computational Biology}, number = {12}, publisher = {Public Library of Science}, title = {{Beyond the hypercube evolutionary accessibility of fitness landscapes with realistic mutational networks}}, doi = {10.1371/journal.pcbi.1005218}, volume = {12}, year = {2016}, } @article{1170, abstract = {The increasing complexity of dynamic models in systems and synthetic biology poses computational challenges especially for the identification of model parameters. While modularization of the corresponding optimization problems could help reduce the “curse of dimensionality,” abundant feedback and crosstalk mechanisms prohibit a simple decomposition of most biomolecular networks into subnetworks, or modules. Drawing on ideas from network modularization and multiple-shooting optimization, we present here a modular parameter identification approach that explicitly allows for such interdependencies. Interfaces between our modules are given by the experimentally measured molecular species. This definition allows deriving good (initial) estimates for the inter-module communication directly from the experimental data. Given these estimates, the states and parameter sensitivities of different modules can be integrated independently. To achieve consistency between modules, we iteratively adjust the estimates for inter-module communication while optimizing the parameters. After convergence to an optimal parameter set---but not during earlier iterations---the intermodule communication as well as the individual modules\' state dynamics agree with the dynamics of the nonmodularized network. Our modular parameter identification approach allows for easy parallelization; it can reduce the computational complexity for larger networks and decrease the probability to converge to suboptimal local minima. We demonstrate the algorithm\'s performance in parameter estimation for two biomolecular networks, a synthetic genetic oscillator and a mammalian signaling pathway.}, author = {Lang, Moritz and Stelling, Jörg}, journal = {SIAM Journal on Scientific Computing}, number = {6}, pages = {B988 -- B1008}, publisher = {Society for Industrial and Applied Mathematics }, title = {{Modular parameter identification of biomolecular networks}}, doi = {10.1137/15M103306X}, volume = {38}, year = {2016}, }