TY - JOUR AB - A complete mitochondrial (mt) genome sequence was reconstructed from a 38,000 year-old Neandertal individual with 8341 mtDNA sequences identified among 4.8 Gb of DNA generated from ∼0.3 g of bone. Analysis of the assembled sequence unequivocally establishes that the Neandertal mtDNA falls outside the variation of extant human mtDNAs, and allows an estimate of the divergence date between the two mtDNA lineages of 660,000 ± 140,000 years. Of the 13 proteins encoded in the mtDNA, subunit 2 of cytochrome c oxidase of the mitochondrial electron transport chain has experienced the largest number of amino acid substitutions in human ancestors since the separation from Neandertals. There is evidence that purifying selection in the Neandertal mtDNA was reduced compared with other primate lineages, suggesting that the effective population size of Neandertals was small. AU - Green, Richard E AU - Malaspinas, Anna-Sapfo AU - Krause, Johannes AU - Briggs, Adrian W AU - Johnson, Philip L AU - Caroline Uhler AU - Meyer, Matthias AU - Good, Jeffrey M AU - Maricic, Tomislav AU - Stenzel, Udo AU - Prüfer, Kay AU - Siebauer, Michael F AU - Burbano, Hernän A AU - Ronan, Michael T AU - Rothberg, Jonathan M AU - Egholm, Michael AU - Rudan, Pavao AU - Brajković, Dejana AU - Kućan, Željko AU - Gušić, Ivan AU - Wikström, Mårten K AU - Laakkonen, Liisa J AU - Kelso, Janet F AU - Slatkin, Montgomery AU - Pääbo, Svante H ID - 3307 JF - Cell TI - A complete neandertal mitochondrial genome sequence determined by highhhroughput sequencing VL - 134 ER - TY - JOUR AB - We develop a new method for estimating effective population sizes, Ne, and selection coefficients, s, from time-series data of allele frequencies sampled from a single diallelic locus. The method is based on calculating transition probabilities, using a numerical solution of the diffusion process, and assuming independent binomial sampling from this diffusion process at each time point. We apply the method in two example applications. First, we estimate selection coefficients acting on the CCR5-Δ32 mutation on the basis of published samples of contemporary and ancient human DNA. We show that the data are compatible with the assumption of s = 0, although moderate amounts of selection acting on this mutation cannot be excluded. In our second example, we estimate the selection coefficient acting on a mutation segregating in an experimental phage population. We show that the selection coefficient acting on this mutation is ~0.43. AU - Jonathan Bollback AU - York, Thomas L AU - Nielsen, Rasmus ID - 3435 IS - 1 JF - Genetics TI - Estimation of 2Nes From Temporal Allele Frequency Data VL - 179 ER - TY - JOUR AB - Temporal coding is a means of representing information by the time, as opposed to the rate, at which neurons fire. Evidence of temporal coding in the hippocampus comes from place cells, whose spike times relative to theta oscillations reflect a rat's position while running along stereotyped trajectories. This arises from the backwards shift in cell firing relative to local theta oscillations (phase precession). Here we demonstrate phase precession during place-field crossings in an open-field foraging task. This produced spike sequences in each theta cycle that disambiguate the rat's trajectory through two-dimensional space and can be used to predict movement direction. Furthermore, position and movement direction were maximally predicted from firing in the early and late portions of the theta cycle, respectively. This represents the first direct evidence of a combined representation of position, trajectory and heading in the hippocampus, organized on a fine temporal scale by theta oscillations. AU - Huxter,John R AU - Senior,Timothy J AU - Allen, Kevin AU - Jozsef Csicsvari ID - 3516 IS - 5 JF - Nature Neuroscience TI - Theta phase-specific codes for two-dimensional position, trajectory and heading in the hippocampus VL - 11 ER - TY - JOUR AB - In the cerebral cortex, GABAergic interneurons are often regarded as fast-spiking cells. We have identified a type of slow-spiking interneuron that offers distinct contributions to network activity. “Ivy” cells, named after their dense and fine axons innervating mostly basal and oblique pyramidal cell dendrites, are more numerous than the parvalbumin-expressing basket, bistratified, or axo-axonic cells. Ivy cells express nitric oxide synthase, neuropeptide Y, and high levels of GABA(A) receptor alpha 1 subunit; they discharge at a low frequency with wide spikes in vivo, yet are distinctively phase-locked to behaviorally relevant network rhythms including theta, gamma, and ripple oscillations. Paired recordings in vitro showed that Ivy cells receive depressing EPSPs from pyramidal cells, which in turn receive slowly rising and decaying inhibitory input from Ivy cells. In contrast to fast-spiking interneurons operating with millisecond precision, the highly abundant Ivy cells express presynaptically acting neuromodulators and regulate the excitability of pyramidal cell dendrites through slowly rising and decaying GABAergic inputs. AU - Fuentealba,Pablo AU - Begum,Rahima AU - Capogna,Marco AU - Jinno,Shozo AU - Marton,Laszlo F AU - Jozsef Csicsvari AU - Thomson,Alex AU - Somogyi, Péter AU - Klausberger,Thomas ID - 3530 IS - 6 JF - Neuron TI - Ivy cells: A population of nitric-oxide-producing, slow-spiking GABAergic neurons and their involvement in hippocampal network activity VL - 57 ER - TY - JOUR AB - In the subthalamic nucleus (STN) of Parkinson's disease (PD) patients, a pronounced synchronization of oscillatory activity at beta frequencies (15-30 Hz) accompanies movement difficulties. Abnormal beta oscillations and motor symptoms are concomitantly and acutely suppressed by dopaminergic therapies, suggesting that these inappropriate rhythms might also emerge acutely from disrupted dopamine transmission. The neural basis of these abnormal beta oscillations is unclear, and how they might compromise information processing, or how they arise, is unknown. Using a 6-hydroxydopamine-lesioned rodent model of PD, we demonstrate that beta oscillations are inappropriately exaggerated, compared with controls, in a brain-state-dependent manner after chronic dopamine loss. Exaggerated beta oscillations are expressed at the levels of single neurons and small neuronal ensembles, and are focally present and spatially distributed within STN. They are also expressed in synchronous population activities, as evinced by oscillatory local field potentials, in STN and cortex. Excessively synchronized beta oscillations reduce the information coding capacity of STN neuronal ensembles, which may contribute to parkinsonian motor impairment. Acute disruption of dopamine transmission in control animals with antagonists of D-1/D-2 receptors did not exaggerate STN or cortical beta oscillations. Moreover, beta oscillations were not exaggerated until several days after 6-hydroxydopamine injections. Thus, contrary to predictions, abnormally amplified beta oscillations in cortico-STN circuits do not result simply from an acute absence of dopamine receptor stimulation, but are instead delayed sequelae of chronic dopamine depletion. Targeting the plastic processes underlying the delayed emergence of pathological beta oscillations after continuing dopaminergic dysfunction may offer considerable therapeutic promise. AU - Mallet,Nicolas AU - Pogosyan,Alek AU - Sharott,Andrew AU - Jozsef Csicsvari AU - Bolam, John Paul AU - Brown,Peter AU - Magill,Peter J ID - 3544 IS - 18 JF - Journal of Neuroscience TI - Disrupted dopamine transmission and the emergence of exaggerated beta oscillations in subthalamic nucleus and cerebral cortex VL - 28 ER - TY - CHAP AU - Biasotti, Silvia AU - Attali, Dominique AU - Boissonnat, Jean-Daniel AU - Herbert Edelsbrunner AU - Elber, Gershon AU - Mortara, Michela AU - Sanniti di Baja, Gabriella AU - Spagnuolo, Michela AU - Tanase, Mirela AU - Veltkam, Remco ID - 3577 T2 - Shape Analysis and Structuring TI - Skeletal structures ER - TY - JOUR AB - The controlled internalization of membrane receptors and lipids is crucial for cells to control signaling pathways and interact with their environment. During clathrin-mediated endocytosis, membrane constituents are transported via endocytic vesicles into early endosomes, from which they are further distributed within the cell. The small guanosine triphosphatase (GTPase) Rab5 is both required and sufficient for the formation of these early endosomes and can be used to experimentally address endocytic processes. Recent evidence shows that endocytic turnover of E-cadherin regulates the migration of mesendodermal cells during zebrafish gastrulation by modulating their adhesive interactions with neighboring cells. This in turn leads to effective and synchronized movement within the embryo. In this review, we discuss techniques to manipulate E-cadherin endocytosis by morpholino-mediated knockdown of rab5 during zebrafish gastrulation. We describe the use of antibodies specifically directed against zebrafish E-cadherin to detect its intracellular localization and of in situ hybridization and primary cell culture to reveal patterns of cell migration and adhesion, respectively AU - Ulrich, Florian AU - Heisenberg, Carl-Philipp J ID - 3591 JF - Methods in Molecular Biology TI - Probing E-cadherin endocytosis by morpholino-mediated Rab5 knock-down in zebrafish. VL - 440 ER - TY - CONF AB - In this paper, adaptive formation control and bio-inspired optimization are jointly addressed for a cluster-based satellite wireless sensor network in which there are multiple satellites flying in formation (MSFF) in the presence of unknown disturbances. The full nonlinear dynamics model describing the relative positioning of the MSFF system is used to develop an adaptive formation controller. First, the original nonlinear system is transformed into a linear controllable system with aperturbation term by invoking the input-output feedback linearization technique. Second, by using the integral feedback design scheme, the adaptive formation controller is presented for improving the steady-state performance of the MSFF system in the presence of unknown disturbances. Third, as a currently popular bio-inspired algorithm, PSO (particle swarm optimizer) is employed to minimize the total energy consumption under the required quality of service by jointly optimizing the transmission power and rate for each satellite. Simulation results are provided to demonstrate the effectiveness of the adaptive formation controller and the PSO-based optimization for saving the total communication energy. AU - Yang, Erfu AU - Erdogan, Ahmet T AU - Arslan, Tughrul AU - Nicholas Barton ID - 3599 TI - Adaptive formation control and bio-inspired optimization of a cluster-based satellite wireless sensor network ER - TY - CONF AB - Kernel canonical correlation analysis (KCCA) is a dimensionality reduction technique for paired data. By finding directions that maximize correlation, KCCA learns representations that are more closely tied to the underlying semantics of the data rather than noise. However, meaningful directions are not only those that have high correlation to another modality, but also those that capture the manifold structure of the data. We propose a method that is simultaneously able to find highly correlated directions that are also located on high variance directions along the data manifold. This is achieved by the use of semi-supervised Laplacian regularization of KCCA. We show experimentally that Laplacian regularized training improves class separation over KCCA with only Tikhonov regularization, while causing no degradation in the correlation between modalities. We propose a model selection criterion based on the Hilbert-Schmidt norm of the semi-supervised Laplacian regularized cross-covariance operator, which we compute in closed form. AU - Blaschko,Matthew B AU - Christoph Lampert AU - Gretton,Arthur ID - 3698 IS - Part 1 TI - Semi-supervised Laplacian regularization of kernel canonical correlation analysis VL - 5211 ER - TY - CONF AB - Distributed Denial of Service (DDoS) attacks are today the most destabilizing factor in the global internet and there is a strong need for sophisticated solutions. We introduce a formal statistical framework and derive a Bayes optimal packet classifier from it. Our proposed practical algorithm "Adaptive History-Based IP Filtering" (AHIF) mitigates DDoS attacks near the victim and outperforms existing methods by at least 32% in terms of collateral damage. Furthermore, it adjusts to the strength of an ongoing attack and ensures availability of the attacked server. In contrast to other adaptive solutions, firewall rulesets used to resist an attack can be precalculated before an attack takes place. This ensures an immediate response in a DDoS emergency. For evaluation, simulated DDoS attacks and two real-world user traffic datasets are used. AU - Goldstein,Markus AU - Christoph Lampert AU - Reif,Matthias AU - Stahl,Armin AU - Breuel,Thomas M ID - 3694 TI - Bayes optimal DDoS mitigation by adaptive history-based IP filtering ER - TY - CONF AB - We present a new technique for structured prediction that works in a hybrid generative/discriminative way, using a one-class support vector machine to model the joint probability of (input, output)-pairs in a joint reproducing kernel Hilbert space. Compared to discriminative techniques, like conditional random fields or structured output SVMs?, the proposed method has the advantage that its training time depends only on the number of training examples, not on the size of the label space. Due to its generative aspect, it is also very tolerant against ambiguous, incomplete or incorrect labels. Experiments on realistic data show that our method works efficiently and robustly in situations that discriminative techniques have problems with or that are computationally infeasible for them. AU - Christoph Lampert AU - Blaschko,Matthew B ID - 3706 TI - Joint kernel support estimation for structured prediction ER - TY - CONF AB - We present a new method for spectral clustering with paired data based on kernel canonical correlation analysis, called correlational spectral clustering. Paired data are common in real world data sources, such as images with text captions. Traditional spectral clustering algorithms either assume that data can be represented by a single similarity measure, or by co-occurrence matrices that are then used in biclustering. In contrast, the proposed method uses separate similarity measures for each data representation, and allows for projection of previously unseen data that are only observed in one representation (e.g. images but not text). We show that this algorithm generalizes traditional spectral clustering algorithms and show consistent empirical improvement over spectral clustering on a variety of datasets of images with associated text. AU - Blaschko,Matthew B AU - Christoph Lampert ID - 3712 TI - Correlational spectral clustering ER - TY - CHAP AB - Single-molecule atomic force microscopy (AFM) provides novel ways to characterize the structure-function relationship of native membrane proteins. High-resolution AFM topographs allow observing the structure of single proteins at sub-nanometer resolution as well as their conformational changes, oligomeric state, molecular dynamics and assembly. We will review these feasibilities illustrating examples of membrane proteins in native and reconstituted membranes. Classification of individual topographs of single proteins allows understanding the principles of motions of their extrinsic domains, to learn about their local structural flexibilities and to find the entropy minima of certain conformations. Combined with the visualization of functionally related conformational changes these insights allow understanding why certain flexibilities are required for the protein to function and how structurally flexible regions allow certain conformational changes. Complementary to AFM imaging, single-molecule force spectroscopy (SMFS) experiments detect molecular interactions established within and between membrane proteins. The sensitivity of this method makes it possible to measure interactions that stabilize secondary structures such as transmembrane α-helices, polypeptide loops and segments within. Changes in temperature or protein-protein assembly do not change the locations of stable structural segments, but influence their stability established by collective molecular interactions. Such changes alter the probability of proteins to choose a certain unfolding pathway. Recent examples have elucidated unfolding and refolding pathways of membrane proteins as well as their energy landscapes. AU - Engel, Andreas AU - Harald Janovjak AU - Fotiadis, Dimtrios AU - Kedrov, Alexej AU - Cisneros, David AU - Mueller, Daniel J ID - 3726 T2 - Single Molecules and Nanotechnology TI - Single-molecule microscopy and force spectroscopy of membrane proteins VL - 12 ER - TY - JOUR AB - Changes in a cell's external or internal conditions are usually reflected in the concentrations of the relevant transcription factors. These proteins in turn modulate the expression levels of the genes under their control and sometimes need to perform nontrivial computations that integrate several inputs and affect multiple genes. At the same time, the activities of the regulated genes would fluctuate even if the inputs were held fixed, as a consequence of the intrinsic noise in the system, and such noise must fundamentally limit the reliability of any genetic computation. Here we use information theory to formalize the notion of information transmission in simple genetic regulatory elements in the presence of physically realistic noise sources. The dependence of this "channel capacity" on noise parameters, cooperativity and cost of making signaling molecules is explored systematically. We find that, in the range of parameters probed by recent in vivo measurements, capacities higher than one bit should be achievable. It is of course generally accepted that gene regulatory elements must, in order to function properly, have a capacity of at least one bit. The central point of our analysis is the demonstration that simple physical models of noisy gene transcription, with realistic parameters, can indeed achieve this capacity: it was not self-evident that this should be so. We also demonstrate that capacities significantly greater than one bit are possible, so that transcriptional regulation need not be limited to simple "on-off" components. The question whether real systems actually exploit this richer possibility is beyond the scope of this investigation. AU - Gasper Tkacik AU - Callan,Curtis G AU - Bialek, William S ID - 3739 IS - 1 JF - Physical Review E Statistical Nonlinear and Soft Matter Physics TI - Information capacity of genetic regulatory elements VL - 78 ER - TY - JOUR AB - In the simplest view of transcriptional regulation, the expression of a gene is turned on or off by changes in the concentration of a transcription factor (TF). We use recent data on noise levels in gene expression to show that it should be possible to transmit much more than just one regulatory bit. Realizing this optimal information capacity would require that the dynamic range of TF concentrations used by the cell, the input/output relation of the regulatory module, and the noise in gene expression satisfy certain matching relations, which we derive. These results provide parameter-free, quantitative predictions connecting independently measurable quantities. Although we have considered only the simplified problem of a single gene responding to a single TF, we find that these predictions are in surprisingly good agreement with recent experiments on the Bicoid/Hunchback system in the early Drosophila embryo and that this system achieves approximately 90% of its theoretical maximum information transmission. AU - Gasper Tkacik AU - Callan,Curtis G AU - Bialek, William S ID - 3740 IS - 34 JF - PNAS TI - Information flow and optimization in transcriptional regulation VL - 105 ER - TY - JOUR AB - It is widely acknowledged that detailed timing of action potentials is used to encode information, for example, in auditory pathways; however, the computational tools required to analyze encoding through timing are still in their infancy. We present a simple example of encoding, based on a recent model of time-frequency analysis, in which units fire action potentials when a certain condition is met, but the timing of the action potential depends also on other features of the stimulus. We show that, as a result, spike-triggered averages are smoothed so much that they do not represent the true features of the encoding. Inspired by this example, we present a simple method, differential reverse correlations, that can separate an analysis of what causes a neuron to spike, and what controls its timing. We analyze with this method the leaky integrate-and-fire neuron and show the method accurately reconstructs the model's kernel. AU - Gasper Tkacik AU - Magnasco, Marcelo O ID - 3744 IS - 1-2 JF - Biosystems TI - Decoding spike timing: The differential reverse-correlation method VL - 93 ER - TY - JOUR AB - We introduce a method for efficiently animating a wide range of deformable materials. We combine a high resolution surface mesh with a tetrahedral finite element simulator that makes use of frequent re-meshing. This combination allows for fast and detailed simulations of complex elastic and plastic behavior. We significantly expand the range of physical parameters that can be simulated with a single technique, and the results are free from common artifacts such as volume-loss, smoothing, popping, and the absence of thin features like strands and sheets. Our decision to couple a high resolution surface with low-resolution physics leads to efficient simulation and detailed surface features, and our approach to creating the tetrahedral mesh leads to an order-of-magnitude speedup over previous techniques in the time spent re-meshing. We compute masses, collisions, and surface tension forces on the scale of the fine mesh, which helps avoid visual artifacts due to the differing mesh resolutions. The result is a method that can simulate a large array of different material behaviors with high resolution features in a short amount of time. AU - Wojtan, Christopher J AU - Turk, Greg ID - 3760 IS - 3 JF - ACM Transactions on Graphics TI - Fast viscoelastic behavior with thin features VL - 27 ER - TY - JOUR AB - Fast-spiking parvalbumin-expressing basket cells (BCs) represent a major type of inhibitory interneuron in the hippocampus. These cells inhibit principal cells in a temporally precise manner and are involved in the generation of network oscillations. Although BCs show a unique expression profile of Ca(2+)-permeable receptors, Ca(2+)-binding proteins and Ca(2+)-dependent signalling molecules, physiological Ca(2+) signalling in these interneurons has not been investigated. To study action potential (AP)-induced dendritic Ca(2+) influx and buffering, we combined whole-cell patch-clamp recordings with ratiometric Ca(2+) imaging from the proximal apical dendrites of rigorously identified BCs in acute slices, using the high-affinity Ca(2+) indicator fura-2 or the low-affinity dye fura-FF. Single APs evoked dendritic Ca(2+) transients with small amplitude. Bursts of APs evoked Ca(2+) transients with amplitudes that increased linearly with AP number. Analysis of Ca(2+) transients under steady-state conditions with different fura-2 concentrations and during loading with 200 microm fura-2 indicated that the endogenous Ca(2+)-binding ratio was approximately 200 (kappa(S) = 202 +/- 26 for the loading experiments). The peak amplitude of the Ca(2+) transients measured directly with 100 microm fura-FF was 39 nm AP(-1). At approximately 23 degrees C, the decay time constant of the Ca(2+) transients was 390 ms, corresponding to an extrusion rate of approximately 600 s(-1). At 34 degrees C, the decay time constant was 203 ms and the corresponding extrusion rate was approximately 1100 s(-1). At both temperatures, continuous theta-burst activity with three to five APs per theta cycle, as occurs in vivo during exploration, led to a moderate increase in the global Ca(2+) concentration that was proportional to AP number, whereas more intense stimulation was required to reach micromolar Ca(2+) concentrations and to shift Ca(2+) signalling into a non-linear regime. In conclusion, dentate gyrus BCs show a high endogenous Ca(2+)-binding ratio, a small AP-induced dendritic Ca(2+) influx, and a relatively slow Ca(2+) extrusion. These specific buffering properties of BCs will sharpen the time course of local Ca(2+) signals, while prolonging the decay of global Ca(2+) signals. AU - Aponte, Yexica AU - Bischofberger, Josef AU - Peter Jonas ID - 3825 IS - 8 JF - Journal of Physiology TI - Efficient Ca(2+) buffering in fast-spiking basket cells of rat hippocampus VL - 586 ER - TY - JOUR AB - Dentate gyrus granule cells transmit action potentials (APs) along their unmyelinated mossy fibre axons to the CA3 region. Although the initiation and propagation of APs are fundamental steps during neural computation, little is known about the site of AP initiation and the speed of propagation in mossy fibre axons. To address these questions, we performed simultaneous somatic and axonal whole-cell recordings from granule cells in acute hippocampal slices of adult mice at approximately 23 degrees C. Injection of short current pulses or synaptic stimulation evoked axonal and somatic APs with similar amplitudes. By contrast, the time course was significantly different, as axonal APs had a higher maximal rate of rise (464 +/- 30 V s(-1) in the axon versus 297 +/- 12 V s(-1) in the soma, mean +/- s.e.m.). Furthermore, analysis of latencies between the axonal and somatic signals showed that APs were initiated in the proximal axon at approximately 20-30 mum distance from the soma, and propagated orthodromically with a velocity of 0.24 m s(-1). Qualitatively similar results were obtained at a recording temperature of approximately 34 degrees C. Modelling of AP propagation in detailed cable models of granule cells suggested that a approximately 4 times higher Na(+) channel density ( approximately 1000 pS mum(-2)) in the axon might account for both the higher rate of rise of axonal APs and the robust AP initiation in the proximal mossy fibre axon. This may be of critical importance to separate dendritic integration of thousands of synaptic inputs from the generation and transmission of a common AP output. AU - Schmidt-Hieber, Christoph AU - Peter Jonas AU - Bischofberger, Josef ID - 3822 IS - 7 JF - Journal of Physiology TI - Action potential initiation and propagation in hippocampal mossy fibre axons VL - 586 ER - TY - JOUR AB - It is generally thought that transmitter release at mammalian central synapses is triggered by Ca2+ microdomains, implying loose coupling between presynaptic Ca2+ channels and Ca2+ sensors of exocytosis. Here we show that Ca2+ channel subunit immunoreactivity is highly concentrated in the active zone of GABAergic presynaptic terminals of putative parvalbumin-containing basket cells in the hippocampus. Paired recording combined with presynaptic patch pipette perfusion revealed that GABA release at basket cell-granule cell synapses is sensitive to millimolar concentrations of the fast Ca2+ chelator BAPTA but insensitive to the slow Ca2+ chelator EGTA. These results show that Ca2+ source and Ca2+ sensor are tightly coupled at this synapse, with distances in the range of 10-20 nm. Models of Ca2+ inflow-exocytosis coupling further reveal that the tightness of coupling increases efficacy, speed, and temporal precision of transmitter release. Thus, tight coupling contributes to fast feedforward and feedback inhibition in the hippocampal network. AU - Bucurenciu, Iancu AU - Kulik, Ákos AU - Schwaller, Beat AU - Frotscher, Michael AU - Peter Jonas ID - 3824 IS - 4 JF - Neuron TI - Nanodomain coupling between Ca(2+) channels and Ca2+ sensors promotes fast and efficient transmitter release at a cortical GABAergic synapse VL - 57 ER - TY - JOUR AB - Two studies in this issue of Neuron (Kwon and Castillo and Rebola et al.) show that the mossy fiber-CA3 pyramidal neuron synapse, a hippocampal synapse well known for its presynaptic plasticity, exhibits a novel form of long-term potentiation of NMDAR-mediated currents, which is induced and expressed postsynaptically. AU - Kerr, Angharad M AU - Peter Jonas ID - 3823 IS - 1 JF - Neuron TI - The two sides of hippocampal mossy fiber plasticity (Review) VL - 57 ER - TY - CONF AB - We consider imperfect-information parity games in which strategies rely on observations that provide imperfect information about the history of a play. To solve such games, i.e., to determine the winning regions of players and corresponding winning strategies, one can use the subset construction to build an equivalent perfect-information game. Recently, an algorithm that avoids the inefficient subset construction has been proposed. The algorithm performs a fixed-point computation in a lattice of antichains, thus maintaining a succinct representation of state sets. However, this representation does not allow to recover winning strategies. In this paper, we build on the antichain approach to develop an algorithm for constructing the winning strategies in parity games of imperfect information. We have implemented this algorithm as a prototype. To our knowledge, this is the first implementation of a procedure for solving imperfect-information parity games on graphs. AU - Berwanger, Dietmar AU - Krishnendu Chatterjee AU - Doyen, Laurent AU - Thomas Henzinger AU - Raje, Sangram ID - 3880 TI - Strategy construction for parity games with imperfect information VL - 5201 ER - TY - JOUR AB - Background The invasive garden ant, Lasius neglectus, is the most recently detected pest ant and the first known invasive ant able to become established and thrive in the temperate regions of Eurasia. In this study, we aim to reconstruct the invasion history of this ant in Europe analysing 14 populations with three complementary approaches: genetic microsatellite analysis, chemical analysis of cuticular hydrocarbon profiles and behavioural observations of aggression behaviour. We evaluate the relative informative power of the three methodological approaches and estimate both the number of independent introduction events from a yet unknown native range somewhere in the Black Sea area, and the invasive potential of the existing introduced populations. Results Three clusters of genetically similar populations were detected, and all but one population had a similar chemical profile. Aggression between populations could be predicted from their genetic and chemical distance, and two major clusters of non-aggressive groups of populations were found. However, populations of L. neglectus did not separate into clear supercolonial associations, as is typical for other invasive ants. Conclusion The three methodological approaches gave consistent and complementary results. All joint evidence supports the inference that the 14 introduced populations of L. neglectus in Europe likely arose from only very few independent introductions from the native range, and that new infestations were typically started through introductions from other invasive populations. This indicates that existing introduced populations have a very high invasive potential when the ants are inadvertently spread by human transport. AU - Ugelvig, Line V AU - Drijfhout, Falko AU - Kronauer, Daniel AU - Boomsma, Jacobus AU - Pedersen, Jes AU - Cremer, Sylvia ID - 3903 IS - 11 JF - BMC Biology TI - The introduction history of invasive garden ants in Europe: integrating genetic, chemical and behavioural approaches VL - 6 ER - TY - JOUR AB - Winged and wingless males coexist in the ant Cardiocondyla obscurior. Wingless (“ergatoid”) males never leave their maternal colony and fight remorselessly among each other for the access to emerging females. The peaceful winged males disperse after about 10 days, but beforehand also mate in the nest. In the first 5 days of their life, winged males perform a chemical female mimicry that protects them against attack and even makes them sexually attractive to ergatoid males. When older, the chemical profile of winged males no longer matches that of virgin females; nevertheless, they are still tolerated, which so far has been puzzling. Contrasting this general pattern, we have identified a single aberrant colony in which all winged males were attacked and killed by the ergatoid males. A comparative analysis of the morphology and chemical profile of these untypical attacked winged males and the tolerated males from several normal colonies revealed that normal old males are still performing some chemical mimicry to the virgin queens, though less perfect than in their young ages. The anomalous attacked winged males, on the other hand, had a very different odour to the females. Our study thus exemplifies that the analysis of rare malfunctioning can add valuable insight on functioning under normal conditions and allows the conclusion that older winged males from normal colonies of the ant C. obscurior are guarded through an imperfect chemical female mimicry, still close enough to protect against attacks by the wingless fighters yet dissimilar enough not to elicit their sexual interest. AU - Cremer, Sylvia AU - D'Ettorre, Patrizia AU - Drijfhout, Falko AU - Sledge, Matthew AU - Turillazzi, Stefano AU - Heinze, Jürgen ID - 3905 IS - 11 JF - Naturwissenschaften TI - Imperfect chemical female mimicry in males of the ant Cardiocondyla obscurior VL - 95 ER - TY - JOUR AB - Wingless males of the ant genus Cardiocondyla engage in fatal fighting for access to female sexual nestmates. Older, heavily sclerotized males are usually capable of eliminating all younger rivals, whose cuticle is still soft. In Cardiocondyla sp. A, this type of local mate competition (LMC) has turned the standard pattern of brood production of social insects upside down, in that mother queens in multi-queen colonies produce extremely long-lived sons very early in the life cycle of the colony. Here, we investigated the emergence pattern of sexuals in two species with LMC, in which males are much less long-lived. Queens of Cardiocondyla obscurior and Cardiocondyla minutior reared their first sons significantly earlier in multi-queen than in single-queen societies. In addition, first female sexuals also emerged earlier in multi-queen colonies, so that early males had mating opportunities. Hence, the timing of sexual production appears to be well predicted by evolutionary theory, in particular by local mate and queen–queen competition. AU - Suefuji, Masaki AU - Cremer, Sylvia AU - Oettler, Jan AU - Heinze, Jürgen ID - 3907 IS - 6 JF - Biology Letters TI - Queen number influences the timing of the sexual production in colonies of Cardiocondyla ants VL - 4 ER - TY - JOUR AU - Cremer, Sylvia AU - Ugelvig, Line V AU - Drijfhout, Falko AU - Schlick Steiner, Birgit AU - Steiner, Florian AU - Seifert, Bernhard AU - Hughes, David AU - Schulz, Andreas AU - Petersen, Klaus AU - Konrad, Heino AU - Stauffer, Christian AU - Kiran, Kadri AU - Espadaler, Xavier AU - D'Ettorre, Patrizia AU - Aktaç, Nihat AU - Eilenberg, Jørgen AU - Jones, Graeme AU - Nash, David AU - Pedersen, Jes AU - Boomsma, Jacobus ID - 3906 IS - 12 JF - PLoS One TI - The evolution of invasiveness in garden ants VL - 3 ER - TY - JOUR AB - The priming of a T cell results from its physical interaction with a dendritic cell (DC) that presents the cognate antigenic peptide. The success rate of such interactions is extremely low, because the precursor frequency of a naive T cell recognizing a specific antigen is in the range of 1:10(5)-10(6). To make this principle practicable, encounter frequencies between DCs and T cells are maximized within lymph nodes (LNs) that are compact immunological projections of the peripheral tissue they drain. But LNs are more than passive meeting places for DCs that immigrated from the tissue and lymphocytes that recirculated via the blood. The microanatomy of the LN stroma actively organizes the cellular encounters by providing preformed migration tracks that create dynamic but highly ordered movement patterns. LN architecture further acts as a sophisticated filtration system that sieves the incoming interstitial fluid at different levels and guarantees that immunologically relevant antigens are loaded on DCs or B cells while inert substances are channeled back into the blood circulation. This review focuses on the non-hematopoietic infrastructure of the lymph node. We describe the association between fibroblastic reticular cell, conduit, DC, and T cell as the essential functional unit of the T-cell cortex. AU - Lämmermann, Tim AU - Sixt, Michael K ID - 3939 IS - 1 JF - Immunological Reviews TI - The microanatomy of T-cell responses VL - 221 ER - TY - JOUR AB - Until recently little information was available on the molecular details of the extracellular matrix (ECM) of secondary lymphoid tissues. There is now growing evidence that these ECMs are unique structures, combining characteristics of basement membranes and interstitial or fibrillar matrices, resulting in scaffolds that are strong and highly flexible and, in certain secondary lymphoid compartments, also forming conduit networks for rapid fluid transport. This review will address the structural characteristics of the ECM of the murine spleen and its potential role as an organizer of immune cell compartments, with reference to the lymph node where relevant. AU - Lokmic, Zerina AU - Lämmermann, Tim AU - Michael Sixt AU - Cardell, Susanna AU - Hallmann, Rupert AU - Sorokin, Lydia ID - 3940 IS - 1 JF - Seminars in Immunology TI - The extracellular matrix of the spleen as a potential organizer of immune cell compartments VL - 20 ER - TY - JOUR AB - While genome-wide gene expression data are generated at an increasing rate, the repertoire of approaches for pattern discovery in these data is still limited. Identifying subtle patterns of interest in large amounts of data (tens of thousands of profiles) associated with a certain level of noise remains a challenge. A microarray time series was recently generated to study the transcriptional program of the mouse segmentation clock, a biological oscillator associated with the periodic formation of the segments of the body axis. A method related to Fourier analysis, the Lomb-Scargle periodogram, was used to detect periodic profiles in the dataset, leading to the identification of a novel set of cyclic genes associated with the segmentation clock. Here, we applied to the same microarray time series dataset four distinct mathematical methods to identify significant patterns in gene expression profiles. These methods are called: Phase consistency, Address reduction, Cyclohedron test and Stable persistence, and are based on different conceptual frameworks that are either hypothesis- or data-driven. Some of the methods, unlike Fourier transforms, are not dependent on the assumption of periodicity of the pattern of interest. Remarkably, these methods identified blindly the expression profiles of known cyclic genes as the most significant patterns in the dataset. Many candidate genes predicted by more than one approach appeared to be true positive cyclic genes and will be of particular interest for future research. In addition, these methods predicted novel candidate cyclic genes that were consistent with previous biological knowledge and experimental validation in mouse embryos. Our results demonstrate the utility of these novel pattern detection strategies, notably for detection of periodic profiles, and suggest that combining several distinct mathematical approaches to analyze microarray datasets is a valuable strategy for identifying genes that exhibit novel, interesting transcriptional patterns. AU - Dequéant, Mary-Lee AU - Ahnert, Sebastian AU - Herbert Edelsbrunner AU - Fink, Thomas M AU - Glynn, Earl F AU - Hattem, Gaye AU - Kudlicki, Andrzej AU - Mileyko, Yuriy AU - Morton, Jason AU - Mushegian, Arcady R AU - Pachter, Lior AU - Rowicka, Maga AU - Shiu, Anne AU - Sturmfels, Bernd AU - Pourquie, Olivier ID - 3970 IS - 8 JF - PLoS One TI - Comparison of pattern detection methods in microarray time series of the segmentation clock VL - 3 ER - TY - JOUR AB - The Reeb graph is a useful tool in visualizing real-valued data obtained from computational simulations of physical processes. We characterize the evolution of the Reeb graph of a time-varying continuous function defined in three-dimensional space. We show how to maintain the Reeb graph over time and compress the entire sequence of Reeb graphs into a single, partially persistent data structure, and augment this data structure with Betti numbers to describe the topology of level sets and with path seeds to assist in the fast extraction of level sets for visualization. AU - Herbert Edelsbrunner AU - Harer, John AU - Mascarenhas, Ajith AU - Pascucci, Valerio AU - Snoeyink, Jack ID - 3971 IS - 3 JF - Computational Geometry: Theory and Applications TI - Time-varying Reeb graphs for continuous space-time data VL - 41 ER - TY - CHAP AB - Persistent homology is an algebraic tool for measuring topological features of shapes and functions. It casts the multi-scale organization we frequently observe in nature into a mathematical formalism. Here we give a record of the short history of persistent homology and present its basic concepts. Besides the mathematics we focus on algorithms and mention the various connections to applications, including to biomolecules, biological networks, data analysis, and geometric modeling. AU - Herbert Edelsbrunner AU - Harer, John ID - 3969 T2 - Surveys on Discrete and Computational Geometry: Twenty Years Later TI - Persistent homology - a survey ER - TY - JOUR AB - The zyxin-related LPP protein is localized at focal adhesions and cell-cell contacts and is involved in the regulation of smooth muscle cell migration. A known interaction partner of LPP in human is the tumor suppressor protein SCRIB. Knocking down scrib expression c uring zebrafish embryonic development results in defects of convergence and extension (C&amp;E) movements, which occur during gastrulation and mediate elongation of the anterior-posterior body axis. Mediolateral cell polarization underlying C&amp;E is regulated by a noncanonical Writ signaling pathway constituting the vertebrate planar cell polarity (PCP) pathway. Here, we investigated the role of Lpp during early zebrafish development. We show that morpholino knockdown of Ipp results in defects of C&amp;E, phenocopying noncanonical Wnt signaling mutants. Time-lapse analysis associates the defective dorsal convergence movements with a reduced ability to migrate along straight paths. In addition, expression of Lpp is significantly reduced in Wnt11 morphants and in embryos overexpressing Wnt11 or a dominant-negative form of Rho kinase 2, which is a downstream effector of Wnt11, Suggesting that Lpp expression is dependent on noncanonical Wnt signaling. Finally, we demonstrate that Lpp interacts with the PCP protein Scrib in zebrafish, and that Lpp and Scrib cooperate for the mediation of C&amp;E. (C) 2008 Elsevier Inc. All rights reserved. AU - Vervenne, Hilke AU - Crombez, Koen AU - Lambaerts, Kathleen AU - Carvalho, Lara AU - Köppen, Mathias AU - Heisenberg, Carl-Philipp J AU - Van De Ven, Wim AU - Petit, Marleen ID - 4141 IS - 1 JF - Developmental Biology TI - Lpp is involved in Wnt/PCP signaling and acts together with Scrib to mediate convergence and extension movements during zebrafish gastrulation VL - 320 ER - TY - JOUR AB - Handedness of the vertebrate body plan critically depends on transient embryonic structures/ organs that generate cilia-dependent leftward fluid flow within constrained extracellular environments. Although the function of ciliated organs in laterality determination has been extensively studied, how they are formed during embryogenesis is still poorly understood. Here we show that Kupffer's vesicle (KV), the zebrafish organ of laterality, arises from a surface epithelium previously thought to adopt exclusively extra-embryonic fates. Live multi-photon confocal imaging reveals that surface epithelial cells undergo Nodal/TGF beta signalling-dependent ingression at the dorsal germ ring margin prior to gastrulation, to give rise to dorsal forerunner cells (DFCs), the precursors of KV. DFCs then migrate attached to the overlying surface epithelium and rearrange into rosette-like epithelial structures at the end of gastrulation. During early somitogenesis, these epithelial rosettes coalesce into a single rosette that differentiates into the KV with a ciliated lumen at its apical centre. Our results provide novel insights into the morphogenetic transformations that shape the laterality organ in zebrafish and suggest a conserved progenitor role of the surface epithelium during laterality organ formation in vertebrates. AU - Oteíza, Pablo AU - Köppen, Mathias AU - Concha, Miguel AU - Heisenberg, Carl-Philipp J ID - 4161 IS - 16 JF - Development TI - Origin and shaping of the laterality organ in zebrafish VL - 135 ER - TY - JOUR AB - During vertebrate gastrulation, cells forming the prechordal plate undergo directed migration as a cohesive cluster. Recent studies revealed that E-cadherin-mediated coherence between these cells plays an important role in effective anterior migration, and that platelet-derived growth factor (Pdgf) appears to act as a guidance cue in this process. However, the mechanisms underlying this process at the individual cell level remain poorly understood. We have identified miles apart (mil) as a suppressor of defective anterior migration of the prospective prechordal plate in silberblick (slb)/wnt11 mutant embryos, in which E-cadherin-mediated coherence of cell movement is reduced. mil encodes Edg5, a sphingosine-1-phosphate (S1P) receptor belonging to a family of five G-protein-coupled receptors (S1PRs). S1P is a lipid signalling molecule that has been implicated in regulating cytoskeletal rearrangements, cell motility and cell adhesion in a variety of cell types. We examined the roles of Mil in anterior migration of prechordal plate progenitor cells and found that, in slb embryos injected with mil-MO, cells migrate with increased motility but decreased directionality, without restoring the coherence of cell migration. This indicates that prechordal plate progenitor cells can migrate effectively as individuals, as well as in a coherent cluster of cells. Moreover, we demonstrate that Mil regulates cell motility and polarisation through Pdgf and its intracellular effecter PI3K, but modulates cell coherence independently of the Pdgf/PI3K pathway, thus co-ordinating cell motility and coherence. These results suggest that the net migration of prechordal plate progenitors is determined by different parameters, including motility, persistence and coherence. AU - Kai, Masatake AU - Heisenberg, Carl-Philipp J AU - Tada, Masazumi ID - 4190 IS - 18 JF - Development TI - Sphingosine-1-phosphate receptors regulate individual cell behaviours underlying the directed migration of prechordal plate progenitor cells during zebrafish gastrulation VL - 135 ER - TY - CONF AB - Model checking software transactional memories (STMs) is difficult because of the unbounded number, length, and delay of concurrent transactions and the unbounded size of the memory. We show that, under certain conditions, the verification problem can be reduced to a finite-state problem, and we illustrate the use of the method by proving the correctness of several STMs, including two-phase locking, DSTM, TL2, and optimistic concurrency control. The safety properties we consider include strict serializability and opacity; the liveness properties include obstruction freedom, livelock freedom, and wait freedom. Our main contribution lies in the structure of the proofs, which are largely automated and not restricted to the STMs mentioned above. In a first step we show that every STM that enjoys certain structural properties either violates a safety or liveness requirement on some program with two threads and two shared variables, or satisfies the requirement on all programs. In the second step we use a model checker to prove the requirement for the STM applied to a most general program with two threads and two variables. In the safety case, the model checker constructs a simulation relation between two carefully constructed finite-state transition systems, one representing the given STM applied to a most general program, and the other representing a most liberal safe STM applied to the same program. In the liveness case, the model checker analyzes fairness conditions on the given STM transition system. AU - Guerraoui, Rachid AU - Thomas Henzinger AU - Jobstmann, Barbara AU - Vasu Singh ID - 4384 TI - Model checking transactional memories ER - TY - CONF AB - We introduce the notion of permissiveness in transactional memories (TM). Intuitively, a TM is permissive if it never aborts a transaction when it need not. More specifically, a TM is permissive with respect to a safety property p if the TM accepts every history that satisfies p. Permissiveness, like safety and liveness, can be used as a metric to compare TMs. We illustrate that it is impractical to achieve permissiveness deterministically, and then show how randomization can be used to achieve permissiveness efficiently. We introduce Adaptive Validation STM (AVSTM), which is probabilistically permissive with respect to opacity; that is, every opaque history is accepted by AVSTM with positive probability. Moreover, AVSTM guarantees lock freedom. Owing to its permissiveness, AVSTM outperforms other STMs by up to 40% in read dominated workloads in high contention scenarios. But, in low contention scenarios, the book-keeping done by AVSTM to achieve permissiveness makes AVSTM, on average, 20-30% worse than existing STMs. AU - Guerraoui, Rachid AU - Thomas Henzinger AU - Vasu Singh ID - 4386 TI - Permissiveness in transactional memories VL - 5218 ER - TY - CONF AB - Software transactional memory (STM) offers a disciplined concurrent programming model for exploiting the parallelism of modern processor architectures. This paper presents the first deterministic specification automata for strict serializability and opacity in STMs. Using an antichain-based tool, we show our deterministic specifications to be equivalent to more intuitive, nondeterministic specification automata (which are too large to be determinized automatically). Using deterministic specification automata, we obtain a complete verification tool for STMs. We also show how to model and verify contention management within STMs. We automatically check the opacity of popular STM algorithms, such as TL2 and DSTM, with a universal contention manager. The universal contention manager is nondeterministic and establishes correctness for all possible contention management schemes. AU - Guerraoui, Rachid AU - Thomas Henzinger AU - Vasu Singh ID - 4387 TI - Completeness and nondeterminism in model checking transactional memories VL - 5201 ER - TY - CONF AU - Beyer, Dirk AU - Damien Zufferey AU - Majumdar, Ritankar S ID - 4397 TI - CSIsat: Interpolation for LA+EUF ER - TY - CONF AU - Aviv,Adam J. AU - Pavol Cerny AU - Clark,Sandy AU - Cronin,Eric AU - Shah,Gaurav AU - Sherr,Micah AU - Blaze,Matt ID - 4400 TI - Security Evaluation of ES&S Voting Machines and Election Management System ER - TY - THES AB - Models of timed systems must incorporate not only the sequence of system events, but the timings of these events as well to capture the real-time aspects of physical systems. Timed automata are models of real-time systems in which states consist of discrete locations and values for real-time clocks. The presence of real-time clocks leads to an uncountable state space. This thesis studies verification problems on timed automata in a game theoretic framework. For untimed systems, two systems are close if every sequence of events of one system is also observable in the second system. For timed systems, the difference in timings of the two corresponding sequences is also of importance. We propose the notion of bisimulation distance which quantifies timing differences; if the bisimulation distance between two systems is epsilon, then (a) every sequence of events of one system has a corresponding matching sequence in the other, and (b) the timings of matching events in between the two corresponding traces do not differ by more than epsilon. We show that we can compute the bisimulation distance between two timed automata to within any desired degree of accuracy. We also show that the timed verification logic TCTL is robust with respect to our notion of quantitative bisimilarity, in particular, if a system satisfies a formula, then every close system satisfies a close formula. Timed games are used for distinguishing between the actions of several agents, typically a controller and an environment. The controller must achieve its objective against all possible choices of the environment. The modeling of the passage of time leads to the presence of zeno executions, and corresponding unrealizable strategies of the controller which may achieve objectives by blocking time. We disallow such unreasonable strategies by restricting all agents to use only receptive strategies --strategies which while not being required to ensure time divergence by any agent, are such that no agent is responsible for blocking time. Time divergence is guaranteed when all players use receptive strategies. We show that timed automaton games with receptive strategies can be solved by a reduction to finite state turn based game graphs. We define the logic timed alternating-time temporal logic for verification of timed automaton games and show that the logic can be model checked in EXPTIME. We also show that the minimum time required by an agent to reach a desired location, and the maximum time an agent can stay safe within a set of locations, against all possible actions of its adversaries are both computable. We next study the memory requirements of winning strategies for timed automaton games. We prove that finite memory strategies suffice for safety objectives, and that winning strategies for reachability objectives may require infinite memory in general. We introduce randomized strategies in which an agent can propose a probabilistic distribution of moves and show that finite memory randomized strategies suffice for all omega-regular objectives. We also show that while randomization helps in simplifying winning strategies, and thus allows the construction of simpler controllers, it does not help a player in winning at more states, and thus does not allow the construction of more powerful controllers. Finally we study robust winning strategies in timed games. In a physical system, a controller may propose an action together with a time delay, but the action cannot be assumed to be executed at the exact proposed time delay. We present robust strategies which incorporate such jitters and show that the set of states from which an agent can win robustly is computable. AU - Prabhu, Vinayak ID - 4409 TI - Games for the verification of timed systems ER - TY - THES AB - Many computing applications, especially those in safety critical embedded systems, require highly predictable timing properties. However, time is often not present in the prevailing computing and networking abstractions. In fact, most advances in computer architecture, software, and networking favor average-case performance over timing predictability. This thesis studies several methods for the design of concurrent and/or distributed embedded systems with precise timing guarantees. The focus is on flexible and compositional methods for programming and verification of the timing properties. The presented methods together with related formalisms cover two levels of design: (1) Programming language/model level. We propose the distributed variant of Giotto, a coordination programming language with an explicit temporal semantics—the logical execution time (LET) semantics. The LET of a task is an interval of time that specifies the time instants at which task inputs and outputs become available (task release and termination instants). The LET of a task is always non-zero. This allows us to communicate values across the network without changing the timing information of the task, and without introducing nondeterminism. We show how this methodology supports distributed code generation for distributed real-time systems. The method gives up some performance in favor of composability and predictability. We characterize the tradeoff by comparing the LET semantics with the semantics used in Simulink. (2) Abstract task graph level. We study interface-based design and verification of applications represented with task graphs. We consider task sequence graphs with general event models, and cyclic graphs with periodic event models with jitter and phase. Here an interface of a component exposes time and resource constraints of the component. Together with interfaces we formally define interface composition operations and the refinement relation. For efficient and flexible composability checking two properties are important: incremental design and independent refinement. According to the incremental design property the composition of interfaces can be performed in any order, even if interfaces for some components are not known. The refinement relation is defined such that in a design we can always substitute a refined interface for an abstract one. We show that the framework supports independent refinement, i.e., the refinement relation is preserved under composition operations. AU - Matic, Slobodan ID - 4415 TI - Compositionality in deterministic real-time embedded systems ER - TY - CONF AB - We describe Valigator, a software tool for imperative program verification that efficiently combines symbolic computation and automated reasoning in a uniform framework. The system offers support for automatically generating and proving verification conditions and, most importantly, for automatically inferring loop invariants and bound assertions by means of symbolic summation, Gröbner basis computation, and quantifier elimination. We present general principles of the implementation and illustrate them on examples. AU - Thomas Henzinger AU - Hottelier, Thibaud AU - Kovács, Laura ID - 4452 TI - Valigator: A verification tool with bound and invariant generation VL - 5330 ER - TY - JOUR AB - I discuss two main challenges in embedded systems design: the challenge to build predictable systems, and that to build robust systems. I suggest how predictability can be formalized as a form of determinism, and robustness as a form of continuity. AU - Thomas Henzinger ID - 4509 IS - 1881 JF - Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences TI - Two challenges in embedded systems design: Predictability and robustness VL - 366 ER - TY - THES AB - Complex requirements, time-to-market pressure and regulatory constraints have made the designing of embedded systems extremely challenging. This is evident by the increase in effort and expenditure for design of safety-driven real-time control-dominated applications like automotive and avionic controllers. Design processes are often challenged by lack of proper programming tools for specifying and verifying critical requirements (e.g. timing and reliability) of such applications. Platform based design, an approach for designing embedded systems, addresses the above concerns by separating requirement from architecture. The requirement specifies the intended behavior of an application while the architecture specifies the guarantees (e.g. execution speed, failure rate etc). An implementation, a mapping of the requirement on the architecture, is then analyzed for correctness. The orthogonalization of concerns makes the specification and analyses simpler. An effective use of such design methodology has been proposed in Logical Execution Time (LET) model of real-time tasks. The model separates the timing requirements (specified by release and termination instances of a task) from the architecture guarantees (specified by worst-case execution time of the task). This dissertation proposes a coordination language, Hierarchical Timing Language (HTL), that captures the timing and reliability requirements of real-time applications. An implementation of the program on an architecture is then analyzed to check whether desired timing and reliability requirements are met or not. The core framework extends the LET model by accounting for reliability and refinement. The reliability model separates the reliability requirements of tasks from the reliability guarantees of the architecture. The requirement expresses the desired long-term reliability while the architecture provides a short-term reliability guarantee (e.g. failure rate for each iteration). The analysis checks if the short-term guarantee ensures the desired long-term reliability. The refinement model allows replacing a task by another task during program execution. Refinement preserves schedulability and reliability, i.e., if a refined task is schedulable and reliable for an implementation, then the refining task is also schedulable and reliable for the implementation. Refinement helps in concise specification without overloading analysis. The work presents the formal model, the analyses (both with and without refinement), and a compiler for HTL programs. The compiler checks composition and refinement constraints, performs schedulability and reliability analyses, and generates code for implementation of an HTL program on a virtual machine. Three real-time controllers, one each from automatic control, automotive control and avionic control, are used to illustrate the steps in modeling and analyzing HTL programs. AU - Ghosal, Arkadeb ID - 4524 TI - A hierarchical coordination language for reliable real-time tasks ER - TY - CONF AB - The search for proof and the search for counterexamples (bugs) are complementary activities that need to be pursued concurrently in order to maximize the practical success rate of verification tools.While this is well-understood in safety verification, the current focus of liveness verification has been almost exclusively on the search for termination proofs. A counterexample to termination is an infinite programexecution. In this paper, we propose a method to search for such counterexamples. The search proceeds in two phases. We first dynamically enumerate lasso-shaped candidate paths for counterexamples, and then statically prove their feasibility. We illustrate the utility of our nontermination prover, called TNT, on several nontrivial examples, some of which require bit-level reasoning about integer representations. AU - Ashutosh Gupta AU - Thomas Henzinger AU - Majumdar, Ritankar S AU - Rybalchenko, Andrey AU - Xu, Ru-Gang ID - 4521 TI - Proving non-termination ER - TY - CONF AB - We introduce bounded asynchrony, a notion of concurrency tailored to the modeling of biological cell-cell interactions. Bounded asynchrony is the result of a scheduler that bounds the number of steps that one process gets ahead of other processes; this allows the components of a system to move independently while keeping them coupled. Bounded asynchrony accurately reproduces the experimental observations made about certain cell-cell interactions: its constrained nondeterminism captures the variability observed in cells that, although equally potent, assume distinct fates. Real-life cells are not “scheduled”, but we show that distributed real-time behavior can lead to component interactions that are observationally equivalent to bounded asynchrony; this provides a possible mechanistic explanation for the phenomena observed during cell fate specification. We use model checking to determine cell fates. The nondeterminism of bounded asynchrony causes state explosion during model checking, but partial-order methods are not directly applicable. We present a new algorithm that reduces the number of states that need to be explored: our optimization takes advantage of the bounded-asynchronous progress and the spatially local interactions of components that model cells. We compare our own communication-based reduction with partial-order reduction (on a restricted form of bounded asynchrony) and experiments illustrate that our algorithm leads to significant savings. AU - Fisher, Jasmin AU - Thomas Henzinger AU - Maria Mateescu AU - Piterman, Nir ID - 4527 TI - Bounded asynchrony: Concurrency for modeling cell-cell interactions VL - 5054 ER - TY - JOUR AB - We consider the equivalence problem for labeled Markov chains (LMCs), where each state is labeled with an observation. Two LMCs are equivalent if every finite sequence of observations has the same probability of occurrence in the two LMCs. We show that equivalence can be decided in polynomial time, using a reduction to the equivalence problem for probabilistic automata, which is known to be solvable in polynomial time. We provide an alternative algorithm to solve the equivalence problem, which is based on a new definition of bisimulation for probabilistic automata. We also extend the technique to decide the equivalence of weighted probabilistic automata. AU - Doyen, Laurent AU - Thomas Henzinger AU - Raskin, Jean-François ID - 4532 IS - 3 JF - International Journal of Foundations of Computer Science TI - Equivalence of labeled Markov chains VL - 19 ER - TY - CONF AB - Interface theories have been proposed to support incremental design and independent implementability. Incremental design means that the compatibility checking of interfaces can proceed for partial system descriptions, without knowing the interfaces of all components. Independent implementability means that compatible interfaces can be refined separately, maintaining compatibility. We show that these interface theories provide no formal support for component reuse, meaning that the same component cannot be used to implement several different interfaces in a design. We add a new operation to interface theories in order to support such reuse. For example, different interfaces for the same component may refer to different aspects such as functionality, timing, and power consumption. We give both stateless and stateful examples for interface theories with component reuse. To illustrate component reuse in interface-based design, we show how the stateful theory provides a natural framework for specifying and refining PCI bus clients. AU - Doyen, Laurent AU - Thomas Henzinger AU - Jobstmann, Barbara AU - Tatjana Petrov ID - 4533 TI - Interface theories with component reuse ER - TY - JOUR AB - A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with ω-regular winning conditions specified as parity objectives, and mean-payoff (or limit-average) objectives. These games lie in NP ∩ coNP. We present a polynomial-time Turing reduction of stochastic parity games to stochastic mean-payoff games. AU - Krishnendu Chatterjee AU - Thomas Henzinger ID - 4534 IS - 1 JF - Information Processing Letters TI - Reduction of stochastic parity to stochastic mean-payoff games VL - 106 ER - TY - CONF AB - We propose the notion of logical reliability for real-time program tasks that interact through periodically updated program variables. We describe a reliability analysis that checks if the given short-term (e.g., single-period) reliability of a program variable update in an implementation is sufficient to meet the logical reliability requirement (of the program variable) in the long run. We then present a notion of design by refinement where a task can be refined by another task that writes to program variables with less logical reliability. The resulting analysis can be combined with an incremental schedulability analysis for interacting real-time tasks proposed earlier for the Hierarchical Timing Language (HTL), a coordination language for distributed real-time systems. We implemented a logical-reliability-enhanced prototype of the compiler and runtime infrastructure for HTL. AU - Krishnendu Chatterjee AU - Ghosal, Arkadeb AU - Thomas Henzinger AU - Iercan, Daniel AU - Kirsch, Christoph M AU - Pinello, Claudio AU - Sangiovanni-Vincentelli, Alberto ID - 4546 TI - Logical reliability of interacting real-time tasks ER - TY - JOUR AB - The value of a finite-state two-player zero-sum stochastic game with limit-average payoff can be approximated to within ε in time exponential in a polynomial in the size of the game times polynomial in logarithmic in 1/ε, for all ε > 0. AU - Krishnendu Chatterjee AU - Majumdar, Ritankar S AU - Thomas Henzinger ID - 4548 IS - 2 JF - International Journal of Game Theory TI - Stochastic limit-average games are in EXPTIME VL - 37 ER - TY - CONF AB - We present and evaluate a framework and tool for combining multiple program analyses which allows the dynamic (on-line) adjustment of the precision of each analysis depending on the accumulated results. For example, the explicit tracking of the values of a variable may be switched off in favor of a predicate abstraction when and where the number of different variable values that have been encountered has exceeded a specified threshold. The method is evaluated on verifying the SSH client/server software and shows significant gains compared with predicate abstraction-based model checking. AU - Beyer, Dirk AU - Thomas Henzinger AU - Théoduloz, Grégory ID - 4568 TI - Program analysis with dynamic change of precision ER - TY - JOUR AB - We have detected a spin-dependent displacement perpendicular to the refractive index gradient for photons passing through an air-glass interface. The effect is the photonic version of the spin Hall effect in electronic systems, indicating the universality of the effect for particles of different nature. Treating the effect as a weak measurement of the spin projection of the photons, we used a preselection and postselection technique on the spin state to enhance the original displacement by nearly four orders of magnitude, attaining sensitivity to displacements of ∼1 angstrom. The spin Hall effect can be used for manipulating photonic angular momentum states, and the measurement technique holds promise for precision metrology. AU - Onur Hosten AU - Kwiat, Paul ID - 581 IS - 5864 JF - Science TI - Observation of the spin hall effect of light via weak measurements VL - 319 ER - TY - CONF AB - Using “quantum weak-measurements” as a coherent enhancement technique for small signals, we have measured the recently proposed “spin Hall effect” of light at an air-glass interface, and are working on the smoothly varying refractive-index case. AU - Hosten, Onur AU - Kwiat, Paul ID - 584 SN - 21622701 TI - Spin hall effect of light via weak measurements: Sharp and smooth index variations ER - TY - JOUR AB - Homeostasis of internal carbon dioxide (CO2) and oxygen (O2) levels is fundamental to all animals. Here we examine the CO2 response of the nematode Caenorhabditis elegans. This species inhabits rotting material, which typically has a broad CO2 concentration range. We show that well fed C. elegans avoid CO2 levels above 0.5%. Animals can respond to both absolute CO2 concentrations and changes in CO2 levels within seconds. Responses to CO2 do not reflect avoidance of acid pH but appear to define a new sensory response. Sensation of CO2 is promoted by the cGMP-gated ion channel subunits TAX-2 and TAX-4, but other pathways are also important. Robust CO2 avoidance in well fed animals requires inhibition of the DAF-16 forkhead transcription factor by the insulin-like receptor DAF-2. Starvation, which activates DAF-16, strongly suppresses CO2 avoidance. Exposure to hypoxia (<1% O2) also suppresses CO2 avoidance via activation of the hypoxia-inducible transcription factor HIF-1. The npr-1 215V allele of the naturally polymorphic neuropeptide receptor npr-1, besides inhibiting avoidance of high ambient O2 in feeding C. elegans, also promotes avoidance of high CO2. C. elegans integrates competing O2 and CO2 sensory inputs so that one response dominates. Food and allelic variation at NPR-1 regulate which response prevails. Our results suggest that multiple sensory inputs are coordinated by C. elegans to generate different coherent foraging strategies. AU - Bretscher, A. J. AU - Busch, K. E. AU - de Bono, Mario ID - 6146 IS - 23 JF - Proceedings of the National Academy of Sciences SN - 0027-8424 TI - A carbon dioxide avoidance behavior is integrated with responses to ambient oxygen and food in Caenorhabditis elegans VL - 105 ER - TY - JOUR AU - Kammenga, Jan E. AU - Phillips, Patrick C. AU - de Bono, Mario AU - Doroszuk, Agnieszka ID - 6148 IS - 4 JF - Trends in Genetics SN - 0168-9525 TI - Beyond induced mutants: using worms to study natural variation in genetic pathways VL - 24 ER - TY - JOUR AU - Olofsson, Birgitta AU - de Bono, Mario ID - 6149 IS - 5 JF - Current Biology SN - 0960-9822 TI - Sleep: dozy worms and sleepy flies VL - 18 ER - TY - JOUR AB - Cell interaction phenomena in polymer electrolyte fuel cell stacks that arise from imbalance between adjacent cells are investigated in detail experimentally and theoretically. A specialized two-cell stack with advanced localized diagnostics was developed and used to analyze the mechanism and effect of cell-to-cell coupling as a result of operationally relevant variations in reactant feed flow. Contributions to overall and local voltage changes with respect to uniformly operated cells are scrutinized. Unequal operation of the cells causes in-plane current in the bipolar plate to redistribute current and result in inhomogeneous polarization. Both increasing and decreasing polarization along the air-flow path reduces cell power as compared to isopotential operation. A two-dimensional model based on a commercial computational fluid dynamics code is used to back and extend the experimental results to more general cases. Furthermore, the experimental setup presented allowed for the first time to perform simultaneous localized electrochemical impedance spectroscopy beyond the single-cell level. The mechanism of mutual cell interaction on local and integral spectra is revealed. Results show that virtually identical operation of the cells is essential to obtain meaningful integral spectra. AU - Freunberger, Stefan Alexander AU - Schneider, Ingo A. AU - Sui, Pang-Chieh AU - Wokaun, Alexander AU - Djilali, Nedjib AU - Büchi, Felix N. ID - 7321 IS - 7 JF - Journal of The Electrochemical Society SN - 0013-4651 TI - Cell interaction phenomena in polymer electrolyte fuel cell stacks VL - 155 ER - TY - JOUR AB - A comparative, experimental diffusivity study of gas diffusion layer (GDL) materials for polymer electrolyte fuel cells (PEFC) is presented for the first time. The GDL plays an important role for electrochemical losses due to gas transport limitations at high current densities. Characterization and optimization of these layers is therefore essential to improve power density. A recently developed method which allows for fast diffusimetry is applied and data compared to the literature values. Measurements are made as a function of direction and compression and the effect of different binder structures and hydrophobic treatments on effective diffusivities are discussed. A better understanding of the results is gained by including novel GDL cross-section images and a meaningful unit cell model for the interpretation of the data. The diffusivity data is valuable for GDL manufacturers and future PEFC models. The study reveals that a binder–fiber ratio larger than 50% has a negative impact on the effective diffusion properties. The hydrophobic treatment which is necessary to improve the water management can impede diffusion and thus reduce the power density. Furthermore binder has an isotropic effect while compression pronounces the in-plane orientation of the fibers. AU - Flückiger, Reto AU - Freunberger, Stefan Alexander AU - Kramer, Denis AU - Wokaun, Alexander AU - Scherer, Günther G. AU - Büchi, Felix N. ID - 7320 IS - 2 JF - Electrochimica Acta SN - 0013-4686 TI - Anisotropic, effective diffusivity of porous gas diffusion layer materials for PEFC VL - 54 ER - TY - JOUR AB - The gas diffusion layers (GDLs) of a membrane electrode assembly (MEA) serve as link between flow field and porous electrode within a polymer electrolyte fuel cell. Beside ensuring sufficient electrical and thermal contact between the whole electrode area and the flow field, these typically 200–400 μm thick porous structures enable the access of educts to the electrode area which would be occluded by the flow field lands if the flow field is directly attached to the electrode. Hence, the characterisation of properties pertaining to mass transport of educts and products through these structures is indispensable whilst examining the contribution of the GDLs to the overall electrochemical characteristics of a MEA. A fast and cost effective method to measure the effective diffusivity of a GDL is presented. Electrochemical impedance spectroscopy is applied to measure the effective ionic conductivity of an electrolyte-soaked GDL. Taking advantage of the analogy between Ficks and Ohms law, this provides a measure for the effective diffusivity. The method is described in detail, including experimental as well as theoretical aspects, and selected results, highlighting the anisotropy and dependence on the degree of compression, are shown. Moreover, a two-dimensional model consisting of regularly spaced ellipses is developed to represent the porous structure of the GDL, and by using conformal maps, the agreement between this model and experiment with respect to the sensitivity of the effective diffusivity towards compression is shown. AU - Kramer, Denis AU - Freunberger, Stefan Alexander AU - Flückiger, Reto AU - Schneider, Ingo A. AU - Wokaun, Alexander AU - Büchi, Felix N. AU - Scherer, Günther G. ID - 7322 IS - 1 JF - Journal of Electroanalytical Chemistry SN - 1572-6657 TI - Electrochemical diffusimetry of fuel cell gas diffusion layers VL - 612 ER - TY - CONF AB - The propagation of single cell performance losses to adjacent cells in a polymer electrolyte fuel cell stack is studied by means of local current density measurements in a two cell stack. In this stack, the working conditions of adjacent cells can be controlled independently in order to deliberately change the performance of one cell (inducing cell) and study the coupling effects to the adjacent cell (response cell), while keeping the working conditions of the later one unchanged. The experiments have shown that changes in the current density distribution caused by lowering of the air stoichiometry in the inducing cell cause changes in the current density distribution of the response cell in the order of 60% of the change of the inducing cell, even when the air stoichiometry of the response cell is kept constant. The losses in cell voltage of the inducing cell cause losses in cell voltage of the response cell in a magnitude between 30 and 50%. AU - Santis, Marco AU - Freunberger, Stefan Alexander AU - Papra, Matthias AU - Büchi, Felix N. ID - 7425 SN - 0791837645 T2 - 3rd International Conference on Fuel Cell Science, Engineering and Technology TI - Experimental investigation of the propagation of local current density variations to adjacent cells in PEFC stacks ER - TY - CONF AB - This paper addresses the following question: what is the minimum-sized synchronous window needed to solve consensus in an otherwise asynchronous system? In answer to this question, we present the first optimally-resilient algorithm ASAP that solves consensus as soon as possible in an eventually synchronous system, i.e., a system that from some time GST onwards, delivers messages in a timely fashion. ASAP guarantees that, in an execution with at most f failures, every process decides no later than round GST + f + 2, which is optimal. AU - Alistarh, Dan-Adrian AU - Gilbert, Seth AU - Guerraoui, Rachid AU - Travers, Corentin ID - 753 TI - How to solve consensus in the smallest window of synchrony VL - 5218 LNCS ER - TY - JOUR AU - Robinson, Matthew Richard AU - Pilkington, Jill G. AU - Clutton-Brock, Tim H. AU - Pemberton, Josephine M. AU - Kruuk, Loeske. E.B. ID - 7752 IS - 10 JF - Current Biology SN - 0960-9822 TI - Environmental heterogeneity generates fluctuating selection on a secondary sexual trait VL - 18 ER - TY - JOUR AB - Mutation rate varies greatly between nucleotide sites of the human genome and depends both on the global genomic location and the local sequence context of a site. In particular, CpG context elevates the mutation rate by an order of magnitude. Mutations also vary widely in their effect on the molecular function, phenotype, and fitness. Independence of the probability of occurrence of a new mutation's effect has been a fundamental premise in genetics. However, highly mutable contexts may be preserved by negative selection at important sites but destroyed by mutation at sites under no selection. Thus, there may be a positive correlation between the rate of mutations at a nucleotide site and the magnitude of their effect on fitness. We studied the impact of CpG context on the rate of human-chimpanzee divergence and on intrahuman nucleotide diversity at non-synonymous coding sites. We compared nucleotides that occupy identical positions within codons of identical amino acids and only differ by being within versus outside CpG context. Nucleotides within CpG context are under a stronger negative selection, as revealed by their lower, proportionally to the mutation rate, rate of evolution and nucleotide diversity. In particular, the probability of fixation of a non-synonymous transition at a CpG site is two times lower than at a CpG site. Thus, sites with different mutation rates are not necessarily selectively equivalent. This suggests that the mutation rate may complement sequence conservation as a characteristic predictive of functional importance of nucleotide sites. AU - Schmidt, Steffen AU - Gerasimova, Anna AU - Fyodor Kondrashov AU - Adzuhbei, Ivan A AU - Kondrashov, Alexey S AU - Sunyaev, Shamil R ID - 844 IS - 11 JF - PLoS Genetics TI - Hypermutable non-synonymous sites are under stronger negative selection VL - 4 ER - TY - JOUR AB - The copK gene is localized on the pMOL30 plasmid of Cupriavidus metallidurans CH34 within the complex cop cluster of genes, for which 21 genes have been identified. The expression of the corresponding periplasmic CopK protein is strongly upregulated in the presence of copper, leading to a high periplasmic accumulation. The structure and metal-binding properties of CopK were investigated by NMR and mass spectrometry. The protein is dimeric in the apo state with a dissociation constant in the range of 10- 5 M estimated from analytical ultracentrifugation. Mass spectrometry revealed that CopK has two high-affinity Cu(I)-binding sites per monomer with different Cu(I) affinities. Binding of Cu(II) was observed but appeared to be non-specific. The solution structure of apo-CopK revealed an all-β fold formed of two β-sheets in perpendicular orientation with an unstructured C-terminal tail. The dimer interface is formed by the surface of the C-terminal β-sheet. Binding of the first Cu(I)-ion induces a major structural modification involving dissociation of the dimeric apo-protein. Backbone chemical shifts determined for the 1Cu(I)-bound form confirm the conservation of the N-terminal β-sheet, while the last strand of the C-terminal sheet appears in slow conformational exchange. We hypothesize that the partial disruption of the C-terminal β-sheet is related to dimer dissociation. NH-exchange data acquired on the apo-protein are consistent with a lower thermodynamic stability of the C-terminal sheet. CopK contains seven methionine residues, five of which appear highly conserved. Chemical shift data suggest implication of two or three methionines (Met54, Met38, Met28) in the first Cu(I) site. Addition of a second Cu(I) ion further increases protein plasticity. Comparison of the structural and metal-binding properties of CopK with other periplasmic copper-binding proteins reveals two conserved features within these functionally related proteins: the all-β fold and the methionine-rich Cu(I)-binding site. AU - Bersch, Beate AU - Favier, Adrien AU - Schanda, Paul AU - van Aelst, Sébastien AU - Vallaeys, Tatiana AU - Covès, Jacques AU - Mergeay, Max AU - Wattiez, Ruddy ID - 8481 IS - 2 JF - Journal of Molecular Biology KW - Molecular Biology SN - 0022-2836 TI - Molecular structure and metal-binding properties of the periplasmic CopK protein expressed in Cupriavidus metallidurans CH34 during copper challenge VL - 380 ER - TY - JOUR AB - The KIX domain of the transcription co-activator CBP is a three-helix bundle protein that folds via rapid accumulation of an intermediate state, followed by a slower folding phase. Recent NMR relaxation dispersion studies revealed the presence of a low-populated (excited) state of KIX that exists in equilibrium with the natively folded form under non-denaturing conditions, and likely represents the equilibrium analog of the folding intermediate. Here, we combine amide hydrogen/deuterium exchange measurements using rapid NMR data acquisition techniques with backbone 15N and 13C relaxation dispersion experiments to further investigate the equilibrium folding of the KIX domain. Residual structure within the folding intermediate is detected by both methods, and their combination enables reliable quantification of the amount of persistent residual structure. Three well-defined folding subunits are found, which display variable stability and correspond closely to the individual helices in the native state. While two of the three helices (α2 and α3) are partially formed in the folding intermediate (to ∼ 50% and ∼ 80%, respectively, at 20 °C), the third helix is disordered. The observed helical content within the excited state exceeds the helical propensities predicted for the corresponding peptide regions, suggesting that the two helices are weakly mutually stabilized, while methyl 13C relaxation dispersion data indicate that a defined packing arrangement is unlikely. Temperature-dependent experiments reveal that the largest enthalpy and entropy changes along the folding reaction occur during the final transition from the intermediate to the native state. Our experimental data are consistent with a folding mechanism where helices α2 and α3 form rapidly, although to different extents, while helix α1 consolidates only as folding proceeds to complete the native state-structure. AU - Schanda, Paul AU - Brutscher, Bernhard AU - Konrat, Robert AU - Tollinger, Martin ID - 8480 IS - 4 JF - Journal of Molecular Biology KW - Molecular Biology SN - 0022-2836 TI - Folding of the KIX domain: Characterization of the equilibrium analog of a folding intermediate using 15N/13C relaxation dispersion and fast 1H/2H amide exchange NMR spectroscopy VL - 380 ER - TY - JOUR AB - The SOFAST-HMQC experiment [P. Schanda, B. Brutscher, Very fast two-dimensional NMR spectroscopy for real-time investigation of dynamic events in proteins on the time scale of seconds, J. Am. Chem. Soc. 127 (2005) 8014–8015] allows recording two-dimensional correlation spectra of macromolecules such as proteins in only a few seconds acquisition time. To achieve the highest possible sensitivity, SOFAST-HMQC experiments are preferably performed on high-field NMR spectrometers equipped with cryogenically cooled probes. The duty cycle of over 80% in fast-pulsing SOFAST-HMQC experiments, however, may cause problems when using a cryogenic probe. Here we introduce SE-IPAP-SOFAST-HMQC, a new pulse sequence that provides comparable sensitivity to standard SOFAST-HMQC, while avoiding heteronuclear decoupling during 1H detection, and thus significantly reducing the radiofrequency load of the probe during the experiment. The experiment is also attractive for fast and sensitive measurement of heteronuclear one-bond spin coupling constants. AU - Kern, Thomas AU - Schanda, Paul AU - Brutscher, Bernhard ID - 8482 IS - 2 JF - Journal of Magnetic Resonance KW - Nuclear and High Energy Physics KW - Biophysics KW - Biochemistry KW - Condensed Matter Physics SN - 1090-7807 TI - Sensitivity-enhanced IPAP-SOFAST-HMQC for fast-pulsing 2D NMR with reduced radiofrequency load VL - 190 ER - TY - JOUR AB - DNA methylation is an ancient process found in all domains of life. Although the enzymes that mediate methylation have remained highly conserved, DNA methylation has been adapted for a variety of uses throughout evolution, including defense against transposable elements and control of gene expression. Defects in DNA methylation are linked to human diseases, including cancer. Methylation has been lost several times in the course of animal and fungal evolution, thus limiting the opportunity for study in common model organisms. In the past decade, plants have emerged as a premier model system for genetic dissection of DNA methylation. A recent combination of plant genetics with powerful genomic approaches has led to a number of exciting discoveries and promises many more. AU - Zilberman, Daniel ID - 9537 IS - 5 JF - Current Opinion in Plant Biology SN - 1369-5266 TI - The evolving functions of DNA methylation VL - 11 ER - TY - JOUR AB - We give many examples of applying Bogoliubov's forest formula to iterative solutions of various nonlinear equations. The same formula describes an extremely wide class of objects, from an ordinary quadratic equation to renormalization in quantum field theory. AU - Morozov, Alexei Y AU - Maksym Serbyn ID - 965 IS - 2 JF - Theoretical and Mathematical Physics TI - Nonlinear algebra and Bogoliubov's recursion VL - 154 ER - TY - JOUR AB - In this paper, using the ideas of Bessi and Mather, we present a simple mechanical system exhibiting Arnold diffusion. This system of a particle in a small periodic potential can be also interpreted as ray propagation in a periodic optical medium with a near-constant index of refraction. Arnold diffusion in this context manifests itself as an arbitrary finite change of direction for nearly constant index of refraction. AU - Kaloshin, Vadim AU - Levi, Mark ID - 8510 IS - 3 JF - Bulletin of the American Mathematical Society KW - Applied Mathematics KW - General Mathematics SN - 0273-0979 TI - An example of Arnold diffusion for near-integrable Hamiltonians VL - 45 ER - TY - JOUR AB - The goal of this paper is to present to nonspecialists what is perhaps the simplest possible geometrical picture explaining the mechanism of Arnold diffusion. We choose to speak of a specific model—that of geometric rays in a periodic optical medium. This model is equivalent to that of a particle in a periodic potential in ${\mathbb R}^{n}$ with energy prescribed and to the geodesic flow in a Riemannian metric on ${\mathbb R}^{n} $. AU - Kaloshin, Vadim AU - Levi, Mark ID - 8509 IS - 4 JF - SIAM Review KW - Theoretical Computer Science KW - Applied Mathematics KW - Computational Mathematics SN - 0036-1445 TI - Geometry of Arnold diffusion VL - 50 ER - TY - JOUR AB - Background. The arginine vasopressin V1a receptor (V1aR) modulates social cognition and behavior in a wide variety of species. Variation in a repetitive microsatellite element in the 5′ flanking region of the V1aR gene (AVPR1A) in rodents has been associated with variation in brain V1aR expression and in social behavior. In humans, the 5′ flanking region of AVPR1A contains a tandem duplication of two ∼350 bp, microsatellite-containing elements located approximately 3.5 kb upstream of the transcription start site. The first block, referred to as DupA, contains a polymorphic (GT) 25microsatellite; the second block, DupB, has a complex (CT) 4-(TT)-(CT)8-(GT)24polymorphic motif, known as RS3. Polymorphisms in RS3 have been associated with variation in sociobehavioral traits in humans, including autism spectrum disorders. Thus, evolution of these regions may have contributed to variation in social behavior in primates. We examined the structure of these regions in six ape, six monkey, and one prosimian species. Results. Both tandem repeat blocks are present upstream of the AVPR1A coding region in five of the ape species we investigated, while monkeys have only one copy of this region. As in humans, the microsatellites within DupA and DupB are polymorphic in many primate species. Furthermore, both single (lacking DupB) and duplicated alleles (containing both DupA and DupB) are present in chimpanzee (Pan troglodytes) populations with allele frequencies of 0.795 and 0.205 for the single and duplicated alleles, respectively, based on the analysis of 47 wild-caught individuals. Finally, a phylogenetic reconstruction suggests two alternate evolutionary histories for this locus. Conclusion. There is no obvious relationship between the presence of the RS3 duplication and social organization in primates. However, polymorphisms identified in some species may be useful in future genetic association studies. In particular, the presence of both single and duplicated alleles in chimpanzees provides a unique opportunity to assess the functional role of this duplication in contributing to variation in social behavior in primates. While our initial studies show no signs of directional selection on this locus in chimps, pharmacological and genetic association studies support a potential role for this region in influencing V1aR expression and social behavior. AU - Donaldson, Zoe R AU - Fyodor Kondrashov AU - Putnam, Andrea S AU - Bai, Yaohui AU - Stoinski, Tara S AU - Hammock, Elizabeth A AU - Young, Larry ID - 895 IS - 1 JF - BMC Evolutionary Biology TI - Evolution of a behavior-linked microsatellite-containing element in the 5′ flanking region of the primate AVPR1A gene VL - 8 ER - TY - JOUR AB - The most common form of protein-coding gene overlap in eukaryotes is a simple nested structure, whereby one gene is embedded in an intron of another. Analysis of nested protein-coding genes in vertebrates, fruit flies and nematodes revealed substantially higher rates of evolutionary gains than losses. The accumulation of nested gene structures could not be attributed to any obvious functional relationships between the genes involved and represents an increase of the organizational complexity of animal genomes via a neutral process. AU - Assis, Raquel AU - Kondrashov, Alexey S AU - Koonin, Eugene V AU - Fyodor Kondrashov ID - 907 IS - 10 JF - Trends in Genetics TI - Nested genes and increasing organizational complexity of metazoan genomes VL - 24 ER - TY - JOUR AB - Eukaryotic chromatin is separated into functional domains differentiated by posttranslational histone modifications, histone variants, and DNA methylation1–6. Methylation is associated with repression of transcriptional initiation in plants and animals, and is frequently found in transposable elements. Proper methylation patterns are critical for eukaryotic development4,5, and aberrant methylation-induced silencing of tumor suppressor genes is a common feature of human cancer7. In contrast to methylation, the histone variant H2A.Z is preferentially deposited by the Swr1 ATPase complex near 5′ ends of genes where it promotes transcriptional competence8–20. How DNA methylation and H2A.Z influence transcription remains largely unknown. Here we show that in the plant Arabidopsis thaliana, regions of DNA methylation are quantitatively deficient in H2A.Z. Exclusion of H2A.Z is seen at sites of DNA methylation in the bodies of actively transcribed genes and in methylated transposons. Mutation of the MET1 DNA methyltransferase, which causes both losses and gains of DNA methylation4,5, engenders opposite changes in H2A.Z deposition, while mutation of the PIE1 subunit of the Swr1 complex that deposits H2A.Z17 leads to genome-wide hypermethylation. Our findings indicate that DNA methylation can influence chromatin structure and effect gene silencing by excluding H2A.Z, and that H2A.Z protects genes from DNA methylation. AU - Zilberman, Daniel AU - Coleman-Derr, Devin AU - Ballinger, Tracy AU - Henikoff, Steven ID - 9457 IS - 7218 JF - Nature KW - Multidisciplinary SN - 0028-0836 TI - Histone H2A.Z and DNA methylation are mutually antagonistic chromatin marks VL - 456 ER - TY - JOUR AB - Supraspheres (SS) composed of hundreds to thousands of metal nanoparticles (NPs) and crosslinked by dithiol linkers are assembled into larger structures, which are subsequently converted into nanoporous metals (NMs). Conversion is achieved by heating which removes organic molecules stabilizing the NPs and allows for NP fusion. Heating of SS solutions leads to NMs of overall macroscopic dimensions; localized radiation using collimated electron beam is used to prepare metallized surface micropatterns. Depending on the composition of supraspherical precursors, nanoporous materials composed of up to three metals can be obtained. Strategies for controlling pore size and nanoscale surface roughness of these materials are discussed. AU - Klajn, Rafal AU - Gray, Timothy P. AU - Wesson, Paul J. AU - Myers, Benjamin D. AU - Dravid, Vinayak P. AU - Smoukov, Stoyan K. AU - Grzybowski, Bartosz A. ID - 13423 IS - 18 JF - Advanced Functional Materials KW - Electrochemistry KW - Condensed Matter Physics KW - Biomaterials KW - Electronic KW - Optical and Magnetic Materials SN - 1616-301X TI - Bulk synthesis and surface patterning of nanoporous metals and alloys from supraspherical nanoparticle aggregates VL - 18 ER - TY - JOUR AB - Make like a leaf: The synthesis and characterization of a family of “flowerlike” Au/Fe3O4 nanoparticles is described, whereby Fe3O4 “leaves” adhere to a gold core (see image). The size and numbers of iron oxide domains can be adjusted flexibly by changing the proportion of the starting materials and the reaction time. AU - Wei, Yanhu AU - Klajn, Rafal AU - Pinchuk, Anatoliy O. AU - Grzybowski, Bartosz A. ID - 13422 IS - 10 JF - Small KW - Biomaterials KW - Biotechnology KW - General Materials Science KW - General Chemistry SN - 1613-6810 TI - Synthesis, shape control, and optical properties of hybrid Au/Fe3O4 “nanoflowers” VL - 4 ER - TY - JOUR AU - Barton, Nicholas H ID - 517 IS - 5-6 JF - Genetics Research TI - Identity and coalescence in structured populations: A commentary on 'Inbreeding coefficients and coalescence times' by Montgomery Slatkin VL - 89 ER - TY - JOUR AB - We explore the rich internal structure of Cs2 Feshbach molecules. Pure ultracold molecular samples are prepared in a CO2 -laser trap, and a multitude of weakly bound states is populated by elaborate magnetic-field ramping techniques. Our methods use different Feshbach resonances as input ports and various internal level crossings for controlled state transfer. We populate higher partial-wave states of up to eight units of rotational angular momentum (l -wave states). We investigate the molecular structure by measurements of the magnetic moments for various states. Avoided level crossings between different molecular states are characterized through the changes in magnetic moment and by a Landau-Zener tunneling method. Based on microwave spectroscopy, we present a precise measurement of the magnetic-field-dependent binding energy of the weakly bound s -wave state that is responsible for the large background scattering length of Cs. This state is of particular interest because of its quantum-halo character. AU - Mark, Michael AU - Ferlaino, Francesca AU - Knoop, Steven AU - Danzl, Johann G AU - Kraemer, Tobias AU - Chin, Cheng AU - Nägerl, Hanns AU - Grimm, Rudolf ID - 1035 IS - 4 JF - Physical Review A - Atomic, Molecular, and Optical Physics TI - Spectroscopy of ultracold trapped cesium Feshbach molecules VL - 76 ER - TY - JOUR AB - The metazoan nuclear envelope (NE) breaks down and re-forms during each cell cycle. Nuclear pore complexes (NPCs), which allow nucleocytoplasmic transport during interphase, assemble into the re-forming NE at the end of mitosis. Using in vitro NE assembly, we show that the vertebrate homologue of MEL-28 (maternal effect lethal), a recently discovered NE component in Caenorhabditis elegans, functions in postmitotic NPC assembly. MEL-28 interacts with the Nup107–160 complex (Nup for nucleoporin), an important building block of the NPC, and is essential for the recruitment of the Nup107–160 complex to chromatin. We suggest that MEL-28 acts as a seeding point for NPC assembly. AU - Franz, Cerstin AU - Walczak, Rudolf AU - Yavuz, Sevil AU - Santarella, Rachel AU - Gentzel, Marc AU - Askjaer, Peter AU - Galy, Vincent AU - HETZER, Martin W AU - Mattaj, Iain W AU - Antonin, Wolfram ID - 11116 IS - 2 JF - EMBO reports KW - Genetics KW - Molecular Biology KW - Biochemistry SN - 1469-221X TI - MEL‐28/ELYS is required for the recruitment of nucleoporins to chromatin and postmitotic nuclear pore complex assembly VL - 8 ER - TY - JOUR AB - The formation of the nuclear envelope (NE) around chromatin is a major membrane-remodelling event that occurs during cell division of metazoa. It is unclear whether the nuclear membrane reforms by the fusion of NE fragments or if it re-emerges from an intact tubular network of the endoplasmic reticulum (ER). Here, we show that NE formation and expansion requires a tubular ER network and occurs efficiently in the presence of the membrane fusion inhibitor GTPγS. Chromatin recruitment of membranes, which is initiated by tubule-end binding, followed by the formation, expansion and sealing of flat membrane sheets, is mediated by DNA-binding proteins residing in the ER. Thus, chromatin plays an active role in reshaping of the ER during NE formation. AU - Anderson, Daniel J. AU - HETZER, Martin W ID - 11115 IS - 10 JF - Nature Cell Biology KW - Cell Biology SN - 1465-7392 TI - Nuclear envelope formation by chromatin-mediated reorganization of the endoplasmic reticulum VL - 9 ER - TY - JOUR AB - About 20% of the world's population uses the Web, and a large majority thereof uses Web search engines to find information. As a result, many Web researchers are devoting much effort to improving the speed and capability of search technology. AU - Henzinger, Monika H ID - 11884 IS - 5837 JF - Science SN - 0036-8075 TI - Search technologies for the internet VL - 317 ER - TY - CONF AB - How much can smart combinatorial algorithms improve web search engines? To address this question we will describe three algorithms that have had a positive impact on web search engines: The PageRank algorithm, algorithms for finding near-duplicate web pages, and algorithms for index server loadbalancing. AU - Henzinger, Monika H ID - 11924 SN - 9780898716245 T2 - 18th Annual ACM-SIAM Symposium on Discrete Algorithms TI - Combinatorial algorithms for web search engines: three success stories ER - TY - JOUR AB - A 671 nm diode laser with a mode-hop-free tuning range of 40 GHz is described. This long tuning range is achieved by simultaneously ramping the external cavity length with the laser injection current. The laser output pointing remains fixed, independent of its frequency because of the cover slip cavity design. This system is simple, economical, robust, and easy to use for spectroscopy, as we demonstrate with lithium vapor and lithium atom beam experiments. AU - Carr, Adra AU - Serchest, Yancey AU - Waitukaitis, Scott R AU - Perreault, John AU - Lonij, Vincent AU - Cronin, Alexander ID - 128 IS - 10 JF - Review of Scientific Instruments TI - Cover slip external cavity diode laser VL - 78 ER - TY - JOUR AB - In flies, the large tangential cells of the lobula plate represent an important processing center for visual navigation based on optic flow. Although the visual response properties of these cells have been well studied in blowflies, information on their synaptic organization is mostly lacking. Here we study the distribution of presynaptic release and postsynaptic inhibitory sites in the same set of cells in Drosophila melanogaster. By making use of transgenic tools and immunohistochemistry, our results suggest that HS and VS cells of Drosophila express γ-aminobutyric acid (GABA) receptors in their dendritic region within the lobula plate, thus being postsynaptic to inhibitory input there. At their axon terminals in the protocerebrum, both cell types express synaptobrevin, suggesting the presence of presynaptic specializations there. HS- and VS-cell terminals additionally show evidence for postsynaptic GABAergic input, superimposed on this synaptic polarity. Our findings are in line with the general circuit for visual motion detection and receptive field properties as postulated from electrophysiological and optical recordings in blowflies, suggesting a similar functional organization of lobula plate tangential cells in the two species. AU - Raghu, Shamprasad V AU - Maximilian Jösch AU - Borst, Alexander AU - Reiff, Dierk F ID - 1297 IS - 4 JF - Journal of Comparative Neurology TI - Synaptic organization of lobula plate tangential cells in Drosophila: γ-aminobutyric acid receptors and chemical release sites VL - 502 ER - TY - CHAP AB - This book contains research articles on Diophantine Geometry, written by participants of a research program held at the Ennio De Giorgi Mathematical Research Center in Pisa, Italy, during the period April – July 2005. The authors are eminent experts in the field. Several subfields of the main topic are presented; the volume thus is particularly useful to get a broad overview of recent research developments. AU - Browning, Timothy D AU - Heath Brown, Roger ED - Zannier, Umberto ID - 167 T2 - Diophantine Geometry TI - Simultaneous equal sums of three powers VL - 4 ER - TY - JOUR AB - The authors investigate the composition profile of SiGe islands after capping with Si to form quantum dots, using a two step etching procedure and atomic force microscopy. Initially, the Si capping layers are removed by etching selectively Si over Ge and then the composition of the disclosed islands is addressed by selectively etching Ge over Si. For samples grown at 580 °C the authors show that even when overgrowth leads to a flat Si surface and the islands undergo strong morphological changes, a Ge-rich core region is still preserved in the dot. At high growth and overgrowth temperatures (740 °C), the experiments show that the newly formed base of the buried islands is more Si rich than their top. Furthermore, the authors find that for the growth conditions used, no lateral motion takes place during capping. AU - Georgios Katsaros AU - Stoffel, Mathieu AU - Rastelli, Armando AU - Schmidt, Oliver G AU - Kern, Klaus AU - Tersoff, Jerry ID - 1750 IS - 1 JF - Applied Physics Letters TI - Three-dimensional isocompositional profiles of buried SiGeSi (001) islands VL - 91 ER - TY - JOUR AB - In quantum information science, the phase of a wave function plays an important role in encoding information. Although most experiments in this field rely on dynamic effects to manipulate this information, an alternative approach is to use geometric phase, which has been argued to have potential fault tolerance. We demonstrated the controlled accumulation of a geometric phase, Berry's phase, in a superconducting qubit; we manipulated the qubit geometrically by means of microwave radiation and observed the accumulated phase in an interference experiment. We found excellent agreement with Berry's predictions and also observed a geometry-dependent contribution to dephasing. AU - Leek, Peter J AU - Johannes Fink AU - Blais, Alexandre AU - Bianchetti, R AU - Göppl, M AU - Gambetta, Jay M AU - Schuster, David I AU - Frunzio, Luigi AU - Schoelkopf, Robert J AU - Wallraff, Andreas ID - 1762 IS - 5858 JF - Science TI - Observation of Berry's phase in a solid-state qubit VL - 318 ER - TY - JOUR AB - Intrinsically photosensitive melanopsin-containing retinal ganglion cells (ipRGCs) control important physiological processes, including the circadian rhythm, the pupillary reflex, and the suppression of locomotor behavior (reviewed in [1]). ipRGCs are also activated by classical photoreceptors, the rods and cones, through local retinal circuits [2, 3]. ipRGCs can be transsynaptically labeled through the pupillary-reflex circuit with the derivatives of the Bartha strain of the alphaherpesvirus pseudorabies virus(PRV) [4, 5] that express GFP [6-12]. Bartha-strain derivatives spread only in the retrograde direction [13]. There is evidence that infected cells function normally for a while during GFP expression [7]. Here we combine transsynaptic PRV labeling, two-photon laser microscopy, and electrophysiological techniques to trace the local circuit of different ipRGC subtypes in the mouse retina and record light-evoked activity from the transsynaptically labeled ganglion cells. First, we show that ipRGCs are connected by monostratified amacrine cells that provide strong inhibition from classical-photoreceptor-driven circuits. Second, we show evidence that dopaminergic interplexiform cells are synaptically connected to ipRGCs. The latter finding provides a circuitry link between light-dark adaptation and ipRGC function. AU - Viney, Tim J AU - Bálint, Kamill AU - Hillier, Dániel AU - Sandra Siegert AU - Boldogköi, Zsolt S AU - Enquist, Lynn W AU - Meister, Markus AU - Cepko, Constance L AU - Roska, Botond M ID - 1797 IS - 11 JF - Current Biology TI - Local retinal circuits of melanopsin-containing ganglion cells identified by transsynaptic viral tracing VL - 17 ER - TY - JOUR AB - Respiratory complex I (NADH:ubiquinone oxidoreductase) is an L-shaped multisubunit protein assembly consisting of a hydrophobic membrane arm and a hydrophilic peripheral arm. It catalyses the transfer of two electrons from NADH to quinone coupled to the translocation of four protons across the membrane. Although we have solved recently the crystal structure of the peripheral arm, the structure of the complete enzyme and the coupling mechanism are not yet known. The membrane domain of Escherichia coli complex I consists of seven different subunits with total molecular mass of 258 kDa. It is significantly more stable than the whole enzyme, which allowed us to obtain well-ordered two-dimensional crystals of the domain, belonging to the space group p22121. Comparison of the projection map of negatively stained crystals with previously published low-resolution structures indicated that the characteristic curved shape of the membrane domain is remarkably well conserved between bacterial and mitochondrial enzymes, helping us to interpret projection maps in the context of the intact complex. Two pronounced stain-excluding densities at the distal end of the membrane domain are likely to represent the two large antiporter-like subunits NuoL and NuoM. Cryo-electron microscopy on frozen-hydrated crystals allowed us to calculate a projection map at 8 Å resolution. About 60 transmembrane α-helices, both perpendicular to the membrane plane and tilted, are present within one membrane domain, which is consistent with secondary structure predictions. A possible binding site and access channel for quinone are found at the interface with the peripheral arm. Tentative assignment of individual subunits to the features of the map has been made. The location of subunits NuoL and NuoM at substantial distance from the peripheral arm, which contains all the redox centres of the complex, indicates that conformational changes are likely to play a role in the mechanism of coupling between electron transfer and proton pumping. AU - Baranova, Ekaterina A AU - Holt, Peter J AU - Leonid Sazanov ID - 1965 IS - 1 JF - Journal of Molecular Biology TI - Projection structure of the membrane domain of Escherichia coli respiratory Complex I at 8 Å resolution VL - 366 ER - TY - JOUR AB - Respiratory complex I catalyses the transfer of electrons from NADH to quinone coupled to the translocation of protons across the membrane. The mechanism of coupling and the structure of the complete enzyme are not known. The membrane domain of the complex contains three similar antiporter-like subunits NuoL/M/N, probably involved in proton pumping. We have previously shown that subunits NuoL/M can be removed from the rest of the complex, suggesting their location at the distal end of the membrane domain. Here, using electron microscopy and single particle analysis, we show that subunits NuoL and M jointly occupy a distal half of the membrane domain, separated by about 10 nm from the interface with the peripheral arm. This indicates that coupling mechanism of complex I is likely to involve long range conformational changes. AU - Baranova, Ekaterina A AU - Morgan, David J AU - Leonid Sazanov ID - 1969 IS - 2 SPEC. ISS. JF - Journal of Structural Biology TI - Single particle analysis confirms distal location of subunits NuoL and NuoM in Escherichia coli complex I VL - 159 ER - TY - JOUR AB - Complex I of respiratory chains plays a central role in cellular energy production. Mutations in its subunits lead to many human neurodegenerative diseases. Recently, a first atomic structure of the hydrophilic domain of complex I from Thermus thermophilus was determined. This domain represents a catalytic core of the enzyme. It consists of eight different subunits, contains all the redox centers, and comprises more than half of the entire complex. In this review, novel mechanistic implications of the structure are discussed, and the effects of many known mutations of complex I subunits are interpreted in a structural context. AU - Leonid Sazanov ID - 1964 IS - 9 JF - Biochemistry TI - Respiratory complex I: Mechanistic and structural insights provided by the crystal structure of the hydrophilic domain VL - 46 ER - TY - CONF AB - We present a novel multi-scale representation and acquisition method for the animation of high-resolution facial geometry and wrinkles. We first acquire a static scan of the face including reflectance data at the highest possible quality. We then augment a traditional marker-based facial motion-capture system by two synchronized video cameras to track expression wrinkles. The resulting model consists of high-resolution geometry, motion-capture data, and expression wrinkles in 2D parametric form. This combination represents the facial shape and its salient features at multiple scales. During motion synthesis the motion-capture data deforms the high-resolution geometry using a linear shell-based mesh-deformation method. The wrinkle geometry is added to the facial base mesh using nonlinear energy optimization. We present the results of our approach for performance replay as well as for wrinkle editing. AU - Bernd Bickel AU - Botsch, Mario AU - Angst, Roland AU - Matusik, Wojciech AU - Otaduy, Miguel A AU - Pfister, Hanspeter AU - Groß, Markus S ID - 2091 TI - Multi scale capture of facial geometry and motion ER - TY - JOUR AB - We present a novel multi-scale representation and acquisition method for the animation of high-resolution facial geometry and wrinkles. We first acquire a static scan of the face including reflectance data at the highest possible quality. We then augment a traditional marker-based facial motion-capture system by two synchronized video cameras to track expression wrinkles. The resulting model consists of high-resolution geometry, motion-capture data, and expression wrinkles in 2D parametric form. This combination represents the facial shape and its salient features at multiple scales. During motion synthesis the motion-capture data deforms the high-resolution geometry using a linear shell-based mesh-deformation method. The wrinkle geometry is added to the facial base mesh using nonlinear energy optimization. We present the results of our approach for performance replay as well as for wrinkle editing. AU - Bernd Bickel AU - Botsch, Mario AU - Angst, Roland AU - Matusik, Wojciech AU - Otaduy, Miguel A AU - Pfister, Hanspeter AU - Groß, Markus S ID - 2093 IS - 3 JF - ACM Transactions on Graphics TI - Multi scale capture of facial geometry and motion VL - 26 ER - TY - JOUR AB - We introduce a new appearance-modeling paradigm for synthesizing the internal structure of a 3D model from photographs of a few cross-sections of a real object. When the internal surfaces of the 3D model are revealed as it is cut, carved, or simply clipped, we synthesize their texture from the input photographs. Our texture synthesis algorithm is best classified as a morphing technique, which efficiently outputs the texture attributes of each surface point on demand. For determining source points and their weights in the morphing algorithm, we propose an interpolation domain based on BSP trees that naturally resembles planar splitting of real objects. In the context of the interpolation domain, we define efficient warping and morphing operations that allow for real-time synthesis of textures. Overall, our modeling paradigm, together with its realization through our texture morphing algorithm, allow users to author 3D models that reveal highly realistic internal surfaces in a variety of artistic flavors. AU - Pietroni, Nico AU - Otaduy, Miguel A AU - Bernd Bickel AU - Ganovelli, Fabio AU - Groß, Markus S ID - 2092 IS - 3 JF - Computer Graphics Forum TI - Texturing internal surfaces from a few cross-sections VL - 26 ER - TY - JOUR AB - We extend to infinite dimensions an explicit formula of Chill, Fašangová, Metafune, and Pallara for the optimal angle of analyticity of analytic Ornstein-Uhlenbeck semigroups. The main ingredient is an abstract representation of the Ornstein-Uhlenbeck operator in divergence form. AU - Jan Maas AU - van Neerven, Jan M ID - 2118 IS - 3 JF - Archiv der Mathematik TI - On analytic Ornstein-Uhlenbeck semigroups in infinite dimensions VL - 89 ER - TY - JOUR AB - We use the x-ray absorption fine structure spectroscopy at Nb K edge to reveal the local atomic structure of KxNa1−xNbO3 (PSN) solid solutions. The study is performed over the temperature range 10–1023K for six different x values. We show that only the combined analysis of extended x-ray absorption fine structure and preedge fine structure provides complete and reliable information about the local structure of NbO6 octahedra. Such extensive treatment of the experimental data shows that the local structure of PSN could be described within the spherical model proposed earlier as a hypothesis for perovskite-type ferroelectric zirconates. We reveal that the Nb atoms are localized near their average positions on the sphere surfaces for all temperatures and x values. With regard to previous results we point out the features of microscopic structure common for PSN and perovskite-type zirconates. AU - Mikhail Lemeshko AU - Nazarenko, Elena S AU - Gonchar, A.A AU - Reznichenko, Larisa A AU - Nedoseykina, Tatiana I AU - Novakovich, Alexander A AU - Mathon, Olivier AU - Joly, Yves AU - Vedrinskiǐ, Rostislav V ID - 2135 JF - Physical Review B - Condensed Matter and Materials Physics TI - EXAFS studies of the local atomic structure of the lead-free piezoelectric ceramics KxNa1−xNbO3 over the temperature range 10–1023K VL - 76 ER - TY - JOUR AB - Local atomic structure of the piezoelectric ceramics KxNa 1-xNbO3 (x≤0.00, 0.05, 0.30, 0.40, 0.50 and 0.65) is studied in all phase regions (10 K-1023 K) using Nb K-edge extended X-ray absorption fine-structure (EXAFS) spectroscopy. We have shown the validity of a new spherical model for phase transitions on the basis of both fitting of EXAFS signal in the R-space and differential EXAFS analysis. Within this model the Nb atoms are located on the surfaces of small spheres of constant radii surrounding centers of NbO6 octahedrons in all phases. The distribution of the Nb atom on this surface changes during phase transitions. Besides, the analysis of local structure reveals that the geometry of NbO6 octahedra does not depend on the x value at each temperature, whereas the octahedra rotation angles do. AU - Mikhail Lemeshko AU - Nazarenko, Elena S AU - Gonchar, Anastasia A AU - Reznichenko, Larisa A AU - Mathon, Olivier AU - Joly, Yves AU - Vedrinskiǐ, Rostislav V ID - 2143 IS - 2 JF - EPL TI - Phase transitions in lead-free piezoelectric ceramics: Study of local atomic structure VL - 77 ER - TY - JOUR AB - We use the x-ray absorption fine structure spectroscopy at Nb K edge to reveal the local atomic structure of Kx Na1-x Nb O3 (PSN) solid solutions. The study is performed over the temperature range 10-1023 K for six different x values. We show that only the combined analysis of extended x-ray absorption fine structure and preedge fine structure provides complete and reliable information about the local structure of Nb O6 octahedra. Such extensive treatment of the experimental data shows that the local structure of PSN could be described within the spherical model proposed earlier as a hypothesis for perovskite-type ferroelectric zirconates. We reveal that the Nb atoms are localized near their average positions on the sphere surfaces for all temperatures and x values. With regard to previous results we point out the features of microscopic structure common for PSN and perovskite-type zirconates. AU - Mikhail Lemeshko AU - Nazarenko, Elena S AU - Gonchar, Anastasia A AU - Reznichenko, Larisa A AU - Nedoseykina, Tatiana I AU - Novakovich, Alexander A AU - Mathon, Olivier AU - Joly, Yves AU - Vedrinskiǐ, Rostislav V ID - 2145 IS - 13 JF - Physical Review B - Condensed Matter and Materials Physics TI - EXAFS studies of the local atomic structure of the lead free piezoelectric ceramics Kx Na1-x Nb O3 over the temperature range 10-1023 K VL - 76 ER - TY - JOUR AB - This paper contains a proof of the Manin conjecture for the singular cubic surface S ⊂ P3 that is defined by the equation x1 x22 + x2 x02 + x33 = 0. In fact if U ⊂ S is the Zariski open subset obtained by deleting the unique line from S, and H is the usual exponential height on P3 (Q), then the height zeta function ∑x ∈ U (Q) H (x)- s is analytically continued to the half-plane R e (s) > 9 / 10. AU - De La Bretèche, Régis AU - Browning, Timothy D AU - Derenthal, Ulrich ID - 219 IS - 1 JF - Annales Scientifiques de l'Ecole Normale Superieure TI - On Manin's conjecture for a certain singular cubic surface VL - 40 ER - TY - JOUR AB - Let X ⊂ ℙN be a geometrically integral cubic hypersurface defined over ℚ, with singular locus of dimension at most dim X - 4. The main result in this paper is a proof of the fact that X(ℚ) contains OεX,(BdimX+ε) points of height at most B. AU - Timothy Browning ID - 220 IS - 1-2 JF - Mathematika TI - Counting rational points on cubic hypersurfaces VL - 54 ER -