TY - JOUR AB - The paper presents an algorithm that applies a stack filter simulating the Mean Curvature Motion equation via a finite difference scheme. AU - Mondelli, Marco ID - 6768 JF - Image Processing On Line SN - 2105-1232 TI - A finite difference scheme for the stack filter simulating the MCM VL - 3 ER - TY - CONF AB - Two-player games on graphs are central in many problems in formal verification and program analysis such as synthesis and verification of open systems. In this work, we consider both finite-state game graphs, and recursive game graphs (or pushdown game graphs) that model the control flow of sequential programs with recursion. The objectives we study are multidimensional mean-payoff objectives, where the goal of player 1 is to ensure that the mean-payoff is non-negative in all dimensions. In pushdown games two types of strategies are relevant: (1) global strategies, that depend on the entire global history; and (2) modular strategies, that have only local memory and thus do not depend on the context of invocation. Our main contributions are as follows: (1) We show that finite-state multidimensional mean-payoff games can be solved in polynomial time if the number of dimensions and the maximal absolute value of the weights are fixed; whereas if the number of dimensions is arbitrary, then the problem is known to be coNP-complete. (2) We show that pushdown graphs with multidimensional mean-payoff objectives can be solved in polynomial time. For both (1) and (2) our algorithms are based on hyperplane separation technique. (3) For pushdown games under global strategies both one and multidimensional mean-payoff objectives problems are known to be undecidable, and we show that under modular strategies the multidimensional problem is also undecidable; under modular strategies the one-dimensional problem is NP-complete. We show that if the number of modules, the number of exits, and the maximal absolute value of the weights are fixed, then pushdown games under modular strategies with one-dimensional mean-payoff objectives can be solved in polynomial time, and if either the number of exits or the number of modules is unbounded, then the problem is NP-hard. (4) Finally we show that a fixed parameter tractable algorithm for finite-state multidimensional mean-payoff games or pushdown games under modular strategies with one-dimensional mean-payoff objectives would imply the fixed parameter tractability of parity games. AU - Chatterjee, Krishnendu AU - Velner, Yaron ID - 2329 TI - Hyperplane separation technique for multidimensional mean-payoff games VL - 8052 ER - TY - JOUR AB - Rechargeable lithium–air (O2) batteries are receiving intense interest because their high theoretical specific energy exceeds that of lithium-ion batteries. If the Li–O2 battery is ever to succeed, highly reversible formation/decomposition of Li2O2 must take place at the cathode on cycling. However, carbon, used ubiquitously as the basis of the cathode, decomposes during Li2O2 oxidation on charge and actively promotes electrolyte decomposition on cycling. Replacing carbon with a nanoporous gold cathode, when in contact with a dimethyl sulphoxide-based electrolyte, does seem to demonstrate better stability. However, nanoporous gold is not a suitable cathode; its high mass destroys the key advantage of Li–O2 over Li ion (specific energy), it is too expensive and too difficult to fabricate. Identifying a suitable cathode material for the Li–O2 cell is one of the greatest challenges at present. Here we show that a TiC-based cathode reduces greatly side reactions (arising from the electrolyte and electrode degradation) compared with carbon and exhibits better reversible formation/decomposition of Li2O2 even than nanoporous gold (>98% capacity retention after 100 cycles, compared with 95% for nanoporous gold); it is also four times lighter, of lower cost and easier to fabricate. The stability may originate from the presence of TiO2 (along with some TiOC) on the surface of TiC. In contrast to carbon or nanoporous gold, TiC seems to represent a more viable, stable, cathode for aprotic Li–O2 cells. AU - Ottakam Thotiyl, Muhammed M. AU - Freunberger, Stefan Alexander AU - Peng, Zhangquan AU - Chen, Yuhui AU - Liu, Zheng AU - Bruce, Peter G. ID - 7306 IS - 11 JF - Nature Materials SN - 1476-1122 TI - A stable cathode for the aprotic Li–O2 battery VL - 12 ER - TY - JOUR AB - The non-aqueous Li–air (O2) battery is receiving intense interest because its theoretical specific energy exceeds that of Li-ion batteries. Recharging the Li–O2 battery depends on oxidizing solid lithium peroxide (Li2O2), which is formed on discharge within the porous cathode. However, transporting charge between Li2O2 particles and the solid electrode surface is at best very difficult and leads to voltage polarization on charging, even at modest rates. This is a significant problem facing the non-aqueous Li–O2 battery. Here we show that incorporation of a redox mediator, tetrathiafulvalene (TTF), enables recharging at rates that are impossible for the cell in the absence of the mediator. On charging, TTF is oxidized to TTF+ at the cathode surface; TTF+ in turn oxidizes the solid Li2O2, which results in the regeneration of TTF. The mediator acts as an electron–hole transfer agent that permits efficient oxidation of solid Li2O2. The cell with the mediator demonstrated 100 charge/discharge cycles. AU - Chen, Yuhui AU - Freunberger, Stefan Alexander AU - Peng, Zhangquan AU - Fontaine, Olivier AU - Bruce, Peter G. ID - 7307 IS - 6 JF - Nature Chemistry SN - 1755-4330 TI - Charging a Li–O2 battery using a redox mediator VL - 5 ER - TY - JOUR AB - Casein kinase1 (CK1) plays crucial roles in regulating growth and development via phosphorylating various substrates throughout the eukaryote kingdom. Blue light is crucial for normal growth of both plants and animals, and blue light receptor cryptochrome2 (CRY2) undergoes blue light–dependent phosphorylation and degradation in planta. To study the function of plant CK1s, systematic genetic analysis showed that deficiency of two paralogous Arabidopsis thaliana CK1s, CK1.3 and CK1.4, caused shortened hypocotyls, especially under blue light, while overexpression of either CK1.3 or CK1.4 resulted in the insensitive response to blue light and delayed flowering under long-day conditions. CK1.3 or CK1.4 act dependently on CRY2, and overexpression of CK1.3 or CK1.4 significantly suppresses the hypersensitive response to blue light by CRY2 overexpression. Biochemical studies showed that CK1.3 and CK1.4 directly phosphorylate CRY2 at Ser-587 and Thr-603 in vitro and negatively regulate CRY2 stability in planta, which are stimulated by blue light, further confirming the crucial roles of CK1.3 and CK1.4 in blue light responses through phosphorylating CRY2. Interestingly, expression of CK1.3 and CK1.4 is stimulated by blue light and feedback regulated by CRY2-mediated signaling. These results provide direct evidence for CRY2 phosphorylation and informative clues on the mechanisms of CRY2-mediated light responses. AU - Tan, Shutang AU - Dai, C. AU - Liu, H.-T. AU - Xue, H.-W. ID - 7596 IS - 7 JF - The Plant Cell SN - 1040-4651 TI - Arabidopsis casein kinase1 proteins CK1.3 and CK1.4 phosphorylate cryptochrome2 to regulate blue light signaling VL - 25 ER - TY - JOUR AB - Inositol 1,3,4-trisphosphate 5/6 kinase (ITPK) phosphorylates inositol 1,3,4-trisphosphate to form inositol 1,3,4,5-tetrakisphosphate and inositol 1,3,4,6-tetrakisphosphate which can be finally transferred to inositol hexaphosphate (IP6) and play important roles during plant growth and development. There are 4 putative ITPK members in Arabidopsis. Expression pattern analysis showed that ITPK2 is constitutively expressed in various tissues. A T-DNA knockout mutant of ITPK2 was identified and scanning electron microscopy (SEM) analysis showed that the epidermis structure of seed coat was irregularly formed in seeds of itpk2-1 mutant, resulting in the increased permeability of seed coat to tetrazolium salts. Further analysis by gas chromatography coupled with mass spectrometry of lipid polyester monomers in cell wall confirmed a dramatic decrease in composition of suberin and cutin, which relate to the permeability of seed coat and the formation of which is accompanied with seed coat development. These results indicate that ITPK2 plays an essential role in seed coat development and lipid polyester barrier formation. AU - Tang, Yong AU - Tan, Shutang AU - Xue, Hongwei ID - 7595 IS - 7 JF - Acta Biochimica et Biophysica Sinica SN - 1745-7270 TI - Arabidopsis inositol 1,3,4-trisphosphate 5/6 kinase 2 is required for seed coat development VL - 45 ER - TY - CONF AB - Renaming is a classic distributed coordination task in which a set of processes must pick distinct identifiers from a small namespace. In this paper, we consider the time complexity of this problem when the namespace is linear in the number of participants, a variant known as loose renaming. We give a non-adaptive algorithm with O(log log n) (individual) step complexity, where n is a known upper bound on contention, and an adaptive algorithm with step complexity O((log log k)2), where k is the actual contention in the execution. We also present a variant of the adaptive algorithm which requires O(k log log k) total process steps. All upper bounds hold with high probability against a strong adaptive adversary. We complement the algorithms with an ω(log log n) expected time lower bound on the complexity of randomized renaming using test-and-set operations and linear space. The result is based on a new coupling technique, and is the first to apply to non-adaptive randomized renaming. Since our algorithms use O(n) test-and-set objects, our results provide matching bounds on the cost of loose renaming in this setting. AU - Alistarh, Dan-Adrian AU - Aspnes, James AU - Giakkoupis, George AU - Woelfel, Philipp ID - 765 TI - Randomized loose renaming in O(loglogn) time ER - TY - JOUR AB - The underlying basis of genetic variation in quantitative traits, in terms of the number of causal variants and the size of their effects, is largely unknown in natural populations. The expectation is that complex quantitative trait variation is attributable to many, possibly interacting, causal variants, whose effects may depend upon the sex, age and the environment in which they are expressed. A recently developed methodology in animal breeding derives a value of relatedness among individuals from high‐density genomic marker data, to estimate additive genetic variance within livestock populations. Here, we adapt and test the effectiveness of these methods to partition genetic variation for complex traits across genomic regions within ecological study populations where individuals have varying degrees of relatedness. We then apply this approach for the first time to a natural population and demonstrate that genetic variation in wing length in the great tit (Parus major) reflects contributions from multiple genomic regions. We show that a polygenic additive mode of gene action best describes the patterns observed, and we find no evidence of dosage compensation for the sex chromosome. Our results suggest that most of the genomic regions that influence wing length have the same effects in both sexes. We found a limited amount of genetic variance in males that is attributed to regions that have no effects in females, which could facilitate the sexual dimorphism observed for this trait. Although this exploratory work focuses on one complex trait, the methodology is generally applicable to any trait for any laboratory or wild population, paving the way for investigating sex‐, age‐ and environment‐specific genetic effects and thus the underlying genetic architecture of phenotype in biological study systems. AU - Robinson, Matthew Richard AU - Santure, Anna W. AU - DeCauwer, Isabelle AU - Sheldon, Ben C. AU - Slate, Jon ID - 7745 IS - 15 JF - Molecular Ecology SN - 0962-1083 TI - Partitioning of genetic variation across the genome using multimarker methods in a wild bird population VL - 22 ER - TY - JOUR AB - Clutch size and egg mass are life history traits that have been extensively studied in wild bird populations, as life history theory predicts a negative trade‐off between them, either at the phenotypic or at the genetic level. Here, we analyse the genomic architecture of these heritable traits in a wild great tit (Parus major) population, using three marker‐based approaches – chromosome partitioning, quantitative trait locus (QTL) mapping and a genome‐wide association study (GWAS). The variance explained by each great tit chromosome scales with predicted chromosome size, no location in the genome contains genome‐wide significant QTL, and no individual SNPs are associated with a large proportion of phenotypic variation, all of which may suggest that variation in both traits is due to many loci of small effect, located across the genome. There is no evidence that any regions of the genome contribute significantly to both traits, which combined with a small, nonsignificant negative genetic covariance between the traits, suggests the absence of genetic constraints on the independent evolution of these traits. Our findings support the hypothesis that variation in life history traits in natural populations is likely to be determined by many loci of small effect spread throughout the genome, which are subject to continued input of variation by mutation and migration, although we cannot exclude the possibility of an additional input of major effect genes influencing either trait. AU - Santure, Anna W. AU - De Cauwer, Isabelle AU - Robinson, Matthew Richard AU - Poissant, Jocelyn AU - Sheldon, Ben C. AU - Slate, Jon ID - 7746 IS - 15 JF - Molecular Ecology SN - 0962-1083 TI - Genomic dissection of variation in clutch size and egg mass in a wild great tit (Parus major) population VL - 22 ER - TY - JOUR AB - Acquisition and allocation of resources are central to life‐history theory. However, empirical work typically focuses only on allocation despite the fact that relationships between fitness components may be governed by differences in the ability of individuals to acquire resources across environments. Here, we outline a statistical framework to partition the genetic basis of multivariate plasticity into independent axes of genetic variation, and quantify for the first time, the extent to which specific traits drive multitrait genotype–environment interactions. Our framework generalises to analyses of plasticity, growth and ageing. We apply this approach to a unique, large‐scale, multivariate study of acquisition, allocation and plasticity in the life history of the cricket, Gryllus firmus. We demonstrate that resource acquisition and allocation are genetically correlated, and that plasticity in trade‐offs between allocation to components of fitness is 90% dependent on genetic variance for total resource acquisition. These results suggest that genotype–environment effects for resource acquisition can maintain variation in life‐history components that are typically observed in the wild. AU - Robinson, Matthew Richard AU - Beckerman, Andrew P. ID - 7747 IS - 3 JF - Ecology Letters SN - 1461-023X TI - Quantifying multivariate plasticity: Genetic variation in resource acquisition drives plasticity in resource allocation to components of life history VL - 16 ER -