@article{3933, abstract = {Resident dendritic cells (DC) within the T cell area of the lymph node take up soluble antigens that enter via the afferent lymphatics before antigen carrying DC arrive from the periphery. The reticular network within the lymph node is a conduit system forming the infrastructure for the fast delivery of soluble substances from the afferent lymph to the lumen of high endothelial venules (HEVs). Using high-resolution light microscopy and 3D reconstruction, we show here that these conduits are unique basement membrane-like structures ensheathed by fibroblastic reticular cells with occasional resident DC embedded within this cell layer. Conduit-associated DC are capable of taking up and processing soluble antigens transported within the conduits, whereas immigrated mature DC occur remote from the reticular fibers. The conduit system is, therefore, not a closed compartment that shuttles substances through the lymph node but represents the morphological equivalent to the filtering function of the lymph node.}, author = {Sixt, Michael K and Kanazawa, Nobuo and Selg, Manuel and Samson, Thomas and Roos, Gunnel and Reinhardt, Dieter and Pabst, Reinhard and Lutz, Manfred and Sorokin, Lydia}, journal = {Immunity}, number = {1}, pages = {19 -- 29}, publisher = {Cell Press}, title = {{The conduit system transports soluble antigens from the afferent lymph to resident dendritic cells in the T cell area of the lymph node}}, doi = {10.1016/j.immuni.2004.11.013}, volume = {22}, year = {2005}, } @article{3983, abstract = {Cdc25 phosphatases are key activators of the eukaryotic cell cycle and compelling anticancer targets because their overexpression has been associated with numerous cancers. However, drug discovery targeting these phosphatases has been hampered by the lack of structural information about how Cdc25s interact with their native protein substrates, the cyclin-dependent kinases. Herein, we predict a docked orientation for Cdc25B with its Cdk2-pTpY-CycA protein substrate by a rigid-body docking method and refine the docked models with full-scale molecular dynamics simulations and minimization. We validate the stable ensemble structure experimentally by a variety of in vitro and in vivo techniques. Specifically, we compare our model with a crystal structure of the substrate-trapping mutant of Cdc25B. We identify and validate in vivo a novel hot-spot residue on Cdc25B (Arg492) that plays a central role in protein substrate recognition. We identify a hot-spot residue on the Substrate Cdk2 (Asp206) and confirm its interaction with hot-spot residues on Cdc25 using hot-spot swapping and double mutant cycles to derive interaction energies. Our experimentally validated model is consistent with previous studies of Cdk2 and its interaction partners and initiates the opportunity for drug discovery of inhibitors that target the remote binding sites of this protein-protein interaction.}, author = {Sohn, Jungsan and Parks, Jerry M and Buhrman, Gregory and Brown, Paul and Kristjánsdóttir, Kolbrun and Safi, Alexias and Herbert Edelsbrunner and Yang, Weitao T and Rudolph, Johannes}, journal = {Biochemistry}, number = {50}, pages = {16563 -- 16573}, publisher = {ACS}, title = {{Experimental validation of the docking orientation of Cdc25 with its Cdk2-CycA protein substrate}}, doi = {10.1021/bi0516879}, volume = {44}, year = {2005}, } @inproceedings{3982, abstract = {We present an efficient algorithm for generating a small set of coarse alignments between interacting proteins using meaningful features on their surfaces. The proteins are treated as rigid bodies, but the results are more generally useful as the produced configurations can serve as input to local improvement algorithms that allow for protein flexibility. We apply our algorithm to a diverse set of protein complexes from the Protein Data Bank, demonstrating the effectivity of our algorithm, both for bound and for unbound protein docking problems.}, author = {Wang, Yusu and Agarwal, Pankaj K and Brown, Paul and Herbert Edelsbrunner and Rudolph, Johannes}, pages = {64 -- 75}, publisher = {World Scientific Publishing}, title = {{Coarse and reliable geometric alignment for protein docking}}, doi = {10.1142/9789812702456_0007}, year = {2005}, } @article{4144, abstract = {Wnt11 plays a central role in tissue morphogenesis during vertebrate gastrulation, but the molecular and cellular mechanisms by which Wnt11 exerts its effects remain poorly understood. Here, we show that Wnt11 functions during zebrafish gastrulation by regulating the cohesion of mesodermal and endodermal (mesendodermal) progenitor cells. Importantly, we demonstrate that Wnt11 activity in this process is mediated by the GTPase Rab5, a key regulator of early endocytosis, as blocking Rab5c activity in wild-type embryos phenocopies slb/wnt11 mutants, and enhancing Rab5c activity in slb/wnt11 mutant embryos rescues the mutant phenotype. In addition, we find that Wnt11 and Rab5c control the endocytosis of E-cadherin and are required in mesendodermal cells for E-cadherin-mediated cell cohesion. Together, our results suggest that Wnt11 controls tissue morphogenesis by modulating E-cadherin-mediated cell cohesion through Rab5c, a novel mechanism of Wnt signaling in gastrulation.}, author = {Ulrich, Florian and Krieg, Michael and Schötz, Eva and Link, Vinzenz and Castanon, Irinka and Schnabel, Viktor and Taubenberger, Anna and Müller, Daniel and Puech, Pierre and Heisenberg, Carl-Philipp J}, journal = {Developmental Cell}, number = {4}, pages = {555 -- 564}, publisher = {Cell Press}, title = {{Wnt11 functions in gastrulation by controlling cell cohesion through Rab5c and E-cadherin}}, doi = {10.1016/j.devcel.2005.08.011}, volume = {9}, year = {2005}, } @article{4138, abstract = {Adaptive dynamics describes the evolution of an asexual population through the successive substitution of mutations of small effect. Waxman & Gavrilets (2005) give an excellent overview of the method and its applications. In this note, we focus on the plausibility of the key assumption that mutations have small effects, and the consequences of relaxing that assumption. We argue that: (i) successful mutations often have large effects; (ii) such mutations generate a qualitatively different evolutionary pattern, which is inherently stochastic; and (iii) in models of competition for a continuous resource, selection becomes very weak once several phenotypes are established. This makes the effects of introducing new mutations unpredictable using the methods of adaptive dynamics. We should make clear at the outset that our criticism is of methods that rely on local analysis of fitness gradients (eqn 2 of Waxman & Gavrilets, 2005), and not of the broader idea that evolution can be understood by examining the invasion of successive mutations. We use the term ‘adaptive dynamics’ to refer to the former technique, and contrast it with a more general population genetic analysis of probabilities of invasion.}, author = {Nicholas Barton and Jitka Polechova}, journal = {Journal of Evolutionary Biology}, number = {5}, pages = {1186 -- 1190}, publisher = {Wiley-Blackwell}, title = {{The limitations of adaptive dynamics as a model of evolution}}, doi = {10.1111/j.1420-9101.2005.00943.x}, volume = {18}, year = {2005}, } @article{4155, abstract = {During vertebrate gastrulation, progenitor cells of different germ layers acquire specific adhesive properties that contribute to germ layer formation and separation. Wnt signals have been suggested to function in this process by modulating the different levels of adhesion between the germ layers, however, direct evidence for this is still lacking. Here we show that Wnt11, a key signal regulating gastrulation movements, is needed for the adhesion of zebrafish mesendodermal progenitor cells to fibronectin, an abundant extracellular matrix component during gastrulation. To measure this effect, we developed an assay to quantify the adhesion of single zebrafish primary mesendodermal progenitors using atomic-force microscopy (AFM). We observed significant differences in detachment force and work between cultured mesendodermal progenitors from wild-type embryos and from slb/wit11 mutant embryos, which carry a loss-of-function mutation in the wnt11 gene, when tested on fibronectin-coated substrates. These differences were probably due to reduced adhesion to the fibronectin substrate as neither the overall cell morphology nor the cell elasticity grossly differed between wild-type and mutant cells. Furthermore, in the presence of inhibitors of fibronectin-integrin binding, such as RGD peptides, the adhesion force and work were strongly decreased, indicating that integrins are involved in the binding of mesendodermal progenitors in our assay. These findings demonstrate that AFM can be used to quantitatively determine the substrate-adhesion of cultured primary gastrulating cells and provide insight into the role of Wnt11 signalling in modulating cell adhesion at the single cell scale.}, author = {Puech, Pierre and Taubenberger, Anna and Ulrich, Florian and Krieg, Michael and Mueller, Daniel and Heisenberg, Carl-Philipp J}, journal = {Journal of Cell Science}, number = {18}, pages = {4199 -- 4206}, publisher = {Company of Biologists}, title = {{Measuring cell adhesion forces of primary gastrulating cells from zebrafish using atomic force microscopy}}, doi = {10.1242/​jcs.02547}, volume = {118}, year = {2005}, } @article{4171, abstract = {During vertebrate gastrulation, the three germ layers, ectoderm, mesoderm and endoderm are formed, and the resulting progenitor cells are brought into the positions from which they will later contribute more complex tissues and organs. A core element in this process is the internalization of mesodermal and endodermal progenitors at the onset of gastrulation. Although many of the molecules that induce mesendoderm have been identified, much less is known about the cellular mechanisms underlying mesendodermal cell internalization and germ layer formation. Here we show that at the onset of zebrafish gastrulation, mesendodermal progenitors in dorsal/axial regions of the germ ring internalize by single cell delamination. Once internalized, mesendodermal progenitors upregulate ECadherin (Cadherin 1) expression, become increasingly motile and eventually migrate along the overlying epiblast (ectodermal) cell layer towards the animal pole of the gastrula. When E-Cadherin function is compromised, mesendodermal progenitors still internalize, but, with gastrulation proceeding, fail to elongate and efficiently migrate along the epiblast, whereas epiblast cells themselves exhibit reduced radial cell intercalation movements. This indicates that cadherin-mediated cell-cell adhesion is needed within the forming shield for both epiblast cell intercalation, and mesendodermal progenitor cell elongation and migration during zebrafish gastrulation. Our data provide insight into the cellular mechanisms underlying mesendodermal progenitor cell internalization and subsequent migration during zebrafish gastrulation, and the role of cadherin-mediated cell-cell adhesion in these processes.}, author = {Montero, Juan and Carvalho, Lara and Wilsch Bräuninger, Michaela and Kilian, Beate and Mustafa, Chigdem and Heisenberg, Carl-Philipp J}, journal = {Development}, number = {6}, pages = {1187 -- 1198}, publisher = {Company of Biologists}, title = {{Shield formation at the onset of zebrafish gastrulation}}, doi = {10.1242/dev.01667}, volume = {132}, year = {2005}, } @article{4249, abstract = {We examined causes of speciation in asexual populations in both sympatry and parapatry, providing an alternative explanation for the speciation patterns reported by Dieckmann and Doebeli (1999) and Doebeli and Dieckmann (2003). Both in sympatry and parapatry, they find that speciation occurs relatively easily. We reveal that in the sympatric clonal model, the equilibrium distribution is continuous and the disruptive selection driving evolution of discrete clusters is only transient. Hence, if discrete phenotypes are to remain stable in the sympatric sexual model, there should be some source of nontransient disruptive selection that will drive evolution of assortment. We analyze sexually reproducing populations using the Bulmer’s infinitesimal model and show that cost-free assortment alone leads to speciation and disruptive selection only arises when the optimal distribution cannot be matched—in this example, because the phenotypic range is limited. In addition, Doebeli and Dieckmann’s analyses assumed a high genetic variance and a high mutation rate. Thus, these theoretical models do not support the conclusion that sympatric speciation is a likely outcome of competition for resources. In their parapatric model (Doebeli and Dieckmann 2003), clustering into distinct phenotypes is driven by edge effects, rather than by frequency-dependent competition.}, author = {Jitka Polechova and Nicholas Barton}, journal = {Evolution; International Journal of Organic Evolution}, number = {6}, pages = {1194 -- 1210}, publisher = {Wiley-Blackwell}, title = {{Speciation through competition: A critical review}}, doi = {10.1111/j.0014-3820.2005.tb01771.x}, volume = {59}, year = {2005}, } @article{4251, abstract = {In finite populations subject to selection, genetic drift generates negative linkage disequilibrium, on average, even if selection acts independently (i.e. multiplicatively) upon all loci. Negative disequilibrium reduces the variance in fitness and hence, by FISHER's Fundamental Theorem (1930), slows the rate of increase in mean fitness. Modifiers that increase recombination eliminate the negative disequilibria that impede selection and consequently increase in frequency by 'hitch-hiking'. In addition, recombinant progeny are more fit on average than non-recombinant progeny when there is negative linkage disequilibrium and loci interact multiplicatively. For both these reasons, stochastic fluctuations in linkage disequilibrium in finite populations favor the evolution of increased rates of recombination, even in the absence of epistatic interactions among loci and even when disequilibrium is initially absent. The method developed within this paper quantifies the strength of selection on a modifier allele that increases recombination due to stochastically generated linkage disequilibria. The analysis indicates that, in a population subject to multiplicative selection, genetic associations generated by drift do select for increased recombination, a result that is confirmed by Monte Carlo simulations. Selection for a modifier that increases recombination is highest when linkage among all loci is tight, when beneficial alleles rise from low to high frequency, and when the population size is small.}, author = {Nicholas Barton and Otto, Sarah P}, journal = {Genetics}, number = {4}, pages = {2353 -- 2370}, publisher = {Genetics Society of America}, title = {{Evolution of recombination due to random drift}}, doi = {10.1534/genetics.104.032821}, volume = {169}, year = {2005}, } @article{4252, abstract = {Empirical studies of quantitative genetic variation have revealed robust patterns that are observed both across traits and across species. However, these patterns have no compelling explanation, and some of the observations even appear to be mutually incompatible. We review and extend a major class of theoretical models, ‘mutation–selection models’, that have been proposed to explain quantitative genetic variation. We also briefly review an alternative class of ‘balancing selection models’. We consider to what extent the models are compatible with the general observations, and argue that a key issue is understanding and modelling pleiotropy. We discuss some}, author = {Johnson, Toby and Nicholas Barton}, journal = {Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences}, number = {1459}, pages = {1411 -- 1425}, publisher = {Royal Society, The}, title = {{Theoretical models of selection and mutationon quantitative traits}}, doi = {10.1098/rstb.2005.1667}, volume = {360}, year = {2005}, } @inproceedings{4404, author = {Alur, Rajeev and Pavol Cerny and Madhusudan,P. and Nam,Wonhong}, pages = {98 -- 109}, publisher = {ACM}, title = {{Synthesis of interface specifications for Java classes}}, doi = {1542}, year = {2005}, } @inproceedings{4412, abstract = {The periodic resource model for hierarchical, compositional scheduling abstracts task groups by resource requirements. We study this model in the presence of dataflow constraints between the tasks within a group (intragroup dependencies), and between tasks in different groups (inter-group dependencies). We consider two natural semantics for dataflow constraints, namely, RTW (real-time workshop) semantics and LET (logical execution time) semantics. We show that while RTW semantics offers better end-to-end latency on the task group level, LET semantics allows tighter resource bounds in the abstraction hierarchy and therefore provides better composability properties. This result holds both for intragroup and intergroup dependencies, as well as for shared and for distributed resources.}, author = {Matic, Slobodan and Thomas Henzinger}, pages = {99 -- 110}, publisher = {IEEE}, title = {{Trading end-to-end latency for composability}}, doi = {10.1109/RTSS.2005.43}, year = {2005}, } @inproceedings{4418, abstract = {We present a new software system architecture for the implementation of hard real-time applications. The core of the system is a microkernel whose reactivity (interrupt handling as in synchronous reactive programs) and proactivity (task scheduling as in traditional RTOSs) are fully programmable. The microkernel, which we implemented on a StrongARM processor, consists of two interacting domain-specific virtual machines, a reactive E (Embedded) machine and a proactive S (Scheduling) machine. The microkernel code (or microcode) that runs on the microkernel is partitioned into E and S code. E code manages the interaction of the system with the physical environment: the execution of E code is triggered by environment interrupts, which signal external events such as the arrival of a message or sensor value, and it releases application tasks to the S machine. S code manages the interaction of the system with the processor: the execution of S code is triggered by hardware interrupts, which signal internal events such as the completion of a task or time slice, and it dispatches application tasks to the CPU, possibly preempting a running task. This partition of the system orthogonalizes the two main concerns of real-time implementations: E code refers to environment time and thus defines the reactivity of the system in a hardware- and scheduler-independent fashion; S code refers to CPU time and defines a system scheduler. If both time lines can be reconciled, then the code is called time safe; violations of time safety are handled again in a programmable way, by run-time exceptions. The separation of E from S code permits the independent programming, verification, optimization, composition, dynamic adaptation, and reuse of both reaction and scheduling mechanisms. Our measurements show that the system overhead is very acceptable even for large sets of task, generally in the 0.2--0.3% range.}, author = {Kirsch, Christoph M and Sanvido, Marco A and Thomas Henzinger}, pages = {35 -- 45}, publisher = {ACM}, title = {{A programmable microkernel for real-time systems}}, doi = {10.1145/1064979.1064986}, year = {2005}, } @article{4454, abstract = {We define five increasingly comprehensive classes of infinite-state systems, called STS1--STS5, whose state spaces have finitary structure. For four of these classes, we provide examples from hybrid systems.STS1 These are the systems with finite bisimilarity quotients. They can be analyzed symbolically by iteratively applying predecessor and Boolean operations on state sets, starting from a finite number of observable state sets. Any such iteration is guaranteed to terminate in that only a finite number of state sets can be generated. This enables model checking of the μ-calculus.STS2 These are the systems with finite similarity quotients. They can be analyzed symbolically by iterating the predecessor and positive Boolean operations. This enables model checking of the existential and universal fragments of the μ-calculus.STS3 These are the systems with finite trace-equivalence quotients. They can be analyzed symbolically by iterating the predecessor operation and a restricted form of positive Boolean operations (intersection is restricted to intersection with observables). This enables model checking of all ω-regular properties, including linear temporal logic.STS4 These are the systems with finite distance-equivalence quotients (two states are equivalent if for every distance d, the same observables can be reached in d transitions). The systems in this class can be analyzed symbolically by iterating the predecessor operation and terminating when no new state sets are generated. This enables model checking of the existential conjunction-free and universal disjunction-free fragments of the μ-calculus.STS5 These are the systems with finite bounded-reachability quotients (two states are equivalent if for every distance d, the same observables can be reached in d or fewer transitions). The systems in this class can be analyzed symbolically by iterating the predecessor operation and terminating when no new states are encountered (this is a weaker termination condition than above). This enables model checking of reachability properties.}, author = {Thomas Henzinger and Majumdar, Ritankar S and Raskin, Jean-François}, journal = {ACM Transactions on Computational Logic (TOCL)}, number = {1}, pages = {1 -- 32}, publisher = {ACM}, title = {{A classification of symbolic transition systems}}, doi = {10.1145/1042038.1042039}, volume = {6}, year = {2005}, } @inproceedings{4455, abstract = {We define quantitative similarity functions between timed transition systems that measure the degree of closeness of two systems as a real, in contrast to the traditional boolean yes/no approach to timed simulation and language inclusion. Two systems are close if for each timed trace of one system, there exists a corresponding timed trace in the other system with the same sequence of events and closely corresponding event timings. We show that timed CTL is robust with respect to our quantitative version of bisimilarity, in particular, if a system satisfies a formula, then every close system satisfies a close formula. We also define a discounted version of CTL over timed systems, which assigns to every CTL formula a real value that is obtained by discounting real time. We prove the robustness of discounted CTL by establishing that close states in the bisimilarity metric have close values for all discounted CTL formulas.}, author = {Thomas Henzinger and Majumdar, Ritankar S and Prabhu, Vinayak S}, pages = {226 -- 241}, publisher = {Springer}, title = {{Quantifying similarities between timed systems}}, doi = {10.1007/11603009_18}, volume = {3829}, year = {2005}, } @inproceedings{4456, abstract = {A modular program analysis considers components independently and provides a succinct summary for each component, which is used when checking the rest of the system. Consider a system consisting of a library and a client. A temporal summary, or interface, of the library specifies legal sequences of library calls. The interface is safe if no call sequence violates the library's internal invariants; the interface is permissive if it contains every such sequence. Modular program analysis requires full interfaces, which are both safe and permissive: the client does not cause errors in the library if and only if it makes only sequences of library calls that are allowed by the full interface of the library.Previous interface-based methods have focused on safe interfaces, which may be too restrictive and thus reject good clients. We present an algorithm for automatically synthesizing software interfaces that are both safe and permissive. The algorithm generates interfaces as graphs whose vertices are labeled with predicates over the library's internal state, and whose edges are labeled with library calls. The interface state is refined incrementally until the full interface is constructed. In other words, the algorithm automatically synthesizes a typestate system for the library, against which any client can be checked for compatibility. We present an implementation of the algorithm which is based on the BLAST model checker, and we evaluate some case studies.}, author = {Thomas Henzinger and Jhala, Ranjit and Majumdar, Ritankar S}, pages = {31 -- 40}, publisher = {ACM}, title = {{Permissive interfaces}}, doi = {10.1145/1081706.1081713}, year = {2005}, } @inproceedings{4457, abstract = {We present a compositional approach to the implementation of hard real-time software running on a distributed platform. We explain how several code suppliers, coordinated by a system integrator, can independently generate different parts of the distributed software. The task structure, interaction, and timing is specified as a Giotto program. Each supplier is given a part of the Giotto program and a timing interface, from which the supplier generates task and scheduling code. The integrator then checks, individually for each supplier, in pseudo-polynomial time, if the supplied code meets its timing specification. If all checks succeed, then the supplied software parts are guaranteed to work together and implement the original Giotto program. The feasibility of the approach is demonstrated by a prototype implementation.}, author = {Thomas Henzinger and Kirsch, Christoph M and Matic, Slobodan}, pages = {21 -- 30}, publisher = {ACM}, title = {{Composable code generation for distributed Giotto}}, doi = {10.1145/1065910.1065914}, year = {2005}, } @inproceedings{4536, abstract = {We show how to automatically construct and refine rectangular abstractions of systems of linear differential equations. From a hybrid automaton whose dynamics are given by a system of linear differential equations, our method computes automatically a sequence of rectangular hybrid automata that are increasingly precise overapproximations of the original hybrid automaton. We prove an optimality criterion for successive refinements. We also show that this method can take into account a safety property to be verified, refining only relevant parts of the state space. The practicability of the method is illustrated on a benchmark case study. }, author = {Doyen, Laurent and Thomas Henzinger and Raskin, Jean-François}, pages = {144 -- 161}, publisher = {Springer}, title = {{Automatic rectangular refinement of affine hybrid systems}}, doi = {DOI: 10.1007/11603009_13}, volume = {3829}, year = {2005}, } @inproceedings{4541, abstract = {Much recent research has focused on the applications of games with ω-regular objectives in the control and verification of reactive systems. However, many of the game-based models are ill-suited for these applications, because they assume that each player has complete information about the state of the system (they are “perfect-information” games). This is because in many situations, a controller does not see the private state of the plant. Such scenarios are naturally modeled by “partial-information” games. On the other hand, these games are intractable; for example, partial-information games with simple reachability objectives are 2EXPTIME-complete. We study the intermediate case of “semiperfect-information” games, where one player has complete knowledge of the state, while the other player has only partial knowledge. This model is appropriate in control situations where a controller must cope with plant behavior that is as adversarial as possible, i.e., the controller has partial information while the plant has perfect information. As is customary, we assume that the controller and plant take turns to make moves. We show that these semiperfect-information turn-based games are equivalent to perfect-information concurrent games, where the two players choose their moves simultaneously and independently. Since the perfect-information concurrent games are well-understood, we obtain several results of how semiperfect-information turn-based games differ from perfect-information turn-based games on one hand, and from partial-information turn-based games on the other hand. In particular, semiperfect-information turn-based games can benefit from randomized strategies while the perfect-information variety cannot, and semiperfect-information turn-based games are in NP ∩ coNP for all parity objectives. }, author = {Krishnendu Chatterjee and Thomas Henzinger}, pages = {1 -- 18}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Semiperfect-information games}}, doi = {10.1007/11590156_1}, volume = {3821}, year = {2005}, } @inproceedings{4553, abstract = {The theory of graph games with ω-regular winning conditions is the foundation for modeling and synthesizing reactive processes. In the case of stochastic reactive processes, the corresponding stochastic graph games have three players, two of them (System and Environment) behaving adversarially, and the third (Uncertainty) behaving probabilistically. We consider two problems for stochastic graph games: the qualitative problem asks for the set of states from which a player can win with probability 1 (almost-sure winning); the quantitative problem asks for the maximal probability of winning (optimal winning) from each state. We show that for Rabin winning conditions, both problems are in NP. As these problems were known to be NP-hard, it follows that they are NP-complete for Rabin conditions, and dually, coNP-complete for Streett conditions. The proof proceeds by showing that pure memoryless strategies suffice for qualitatively and quantitatively winning stochastic graph games with Rabin conditions. This insight is of interest in its own right, as it implies that controllers for Rabin objectives have simple implementations. We also prove that for every ω-regular condition, optimal winning strategies are no more complex than almost-sure winning strategies.}, author = {Krishnendu Chatterjee and de Alfaro, Luca and Thomas Henzinger}, pages = {878 -- 890}, publisher = {Springer}, title = {{The complexity of stochastic Rabin and Streett games}}, doi = {10.1007/11523468_71}, volume = {3580}, year = {2005}, } @inproceedings{4554, abstract = {Games played on graphs may have qualitative objectives, such as the satisfaction of an ω-regular property, or quantitative objectives, such as the optimization of a real-valued reward. When games are used to model reactive systems with both fairness assumptions and quantitative (e.g., resource) constraints, then the corresponding objective combines both a qualitative and a quantitative component. In a general case of interest, the qualitative component is a parity condition and the quantitative component is a mean-payoff reward. We study and solve such mean-payoff parity games. We also prove some interesting facts about mean-payoff parity games which distinguish them both from mean-payoff and from parity games. In particular, we show that optimal strategies exist in mean-payoff parity games, but they may require infinite memory.}, author = {Krishnendu Chatterjee and Thomas Henzinger and Jurdziński, Marcin}, pages = {178 -- 187}, publisher = {IEEE}, title = {{Mean-payoff parity games}}, doi = {10.1109/LICS.2005.26}, year = {2005}, } @inproceedings{4560, abstract = {We define and study a quantitative generalization of the traditional boolean framework of model-based specification and verification. In our setting, propositions have integer values at states, and properties have integer values on traces. For example, the value of a quantitative proposition at a state may represent power consumed at the state, and the value of a quantitative property on a trace may represent energy used along the trace. The value of a quantitative property at a state, then, is the maximum (or minimum) value achievable over all possible traces from the state. In this framework, model checking can be used to compute, for example, the minimum battery capacity necessary for achieving a given objective, or the maximal achievable lifetime of a system with a given initial battery capacity. In the case of open systems, these problems require the solution of games with integer values. Quantitative model checking and game solving is undecidable, except if bounds on the computation can be found. Indeed, many interesting quantitative properties, like minimal necessary battery capacity and maximal achievable lifetime, can be naturally specified by quantitative-bound automata, which are finite automata with integer registers whose analysis is constrained by a bound function f that maps each system K to an integer f(K). Along with the linear-time, automaton-based view of quantitative verification, we present a corresponding branching-time view based on a quantitative-bound μ-calculus, and we study the relationship, expressive power, and complexity of both views. }, author = {Chakrabarti, Arindam and Krishnendu Chatterjee and Thomas Henzinger and Kupferman, Orna and Majumdar, Ritankar S}, pages = {50 -- 64}, publisher = {Springer}, title = {{Verifying quantitative properties using bound functions}}, doi = {10.1007/11560548_7}, volume = {3725}, year = {2005}, } @inproceedings{4557, abstract = {Planning in adversarial and uncertain environments can be modeled as the problem of devising strategies in stochastic perfect information games. These games are generalizations of Markov decision processes (MDPs): there are two (adversarial) players, and a source of randomness. The main practical obstacle to computing winning strategies in such games is the size of the state space. In practice therefore, one typically works with abstractions of the model. The diffculty is to come up with an abstraction that is neither too coarse to remove all winning strategies (plans), nor too fine to be intractable. In verification, the paradigm of counterexample-guided abstraction refinement has been successful to construct useful but parsimonious abstractions automatically. We extend this paradigm to probabilistic models (namely, perfect information games and, as a special case, MDPs). This allows us to apply the counterexample-guided abstraction paradigm to the AI planning problem. As special cases, we get planning algorithms for MDPs and deterministic systems that automatically construct system abstractions.}, author = {Krishnendu Chatterjee and Thomas Henzinger and Jhala, Ranjit and Majumdar, Ritankar S}, pages = {104 -- 111}, publisher = {AUAI Press}, title = {{Counterexample-guided planning}}, year = {2005}, } @inproceedings{4579, abstract = {BLAST is an automatic verification tool for checking temporal safety properties of C programs. Given a C program and a temporal safety property, BLAST statically proves that either the program satisfies the safety property or the program has an execution trace that exhibits a violation of the property. BLAST constructs, explores, and refines abstractions of the program state space based on lazy predicate abstraction and interpolation-based predicate discovery. We show how BLAST can be used to statically prove memory safety for C programs. We take a two-step approach. First, we use Ccured, a type-based memory safety analyzer, to annotate with run-time checks all program points that cannot be proved memory safe by the type system. Second, we use BLAST to remove as many of the run-time checks as possible (by proving that these checks never fail), and to generate for the remaining run-time checks execution traces that witness them fail. Our experience shows that BLAST can remove many of the run-time checks added by Ccured and provide useful information to the programmer about many of the remaining checks.}, author = {Beyer, Dirk and Thomas Henzinger and Jhala, Ranjit and Majumdar, Ritankar S}, pages = {2 -- 18}, publisher = {Springer}, title = {{Checking memory safety with BLAST}}, doi = {10.1007/978-3-540-31984-9_2}, volume = {3442}, year = {2005}, } @inproceedings{4576, abstract = {We present a language for specifying web service interfaces. A web service interface puts three kinds of constraints on the users of the service. First, the interface specifies the methods that can be called by a client, together with types of input and output parameters; these are called signature constraints. Second, the interface may specify propositional constraints on method calls and output values that may oc- cur in a web service conversation; these are called consis- tency constraints. Third, the interface may specify temporal constraints on the ordering of method calls; these are called protocol constraints. The interfaces can be used to check, first, if two or more web services are compatible, and second, if a web service A can be safely substituted for a web ser- vice B. The algorithm for compatibility checking verifies that two or more interfaces fulfill each others’ constraints. The algorithm for substitutivity checking verifies that service A demands fewer and fulfills more constraints than service B.}, author = {Beyer, Dirk and Chakrabarti, Arindam and Thomas Henzinger}, pages = {148 -- 159}, publisher = {ACM}, title = {{Web service interfaces}}, doi = {10.1145/1060745.1060770}, year = {2005}, } @article{4625, abstract = {Temporal logic is two-valued: formulas are interpreted as either true or false. When applied to the analysis of stochastic systems, or systems with imprecise formal models, temporal logic is therefore fragile: even small changes in the model can lead to opposite truth values for a specification. We present a generalization of the branching-time logic CTL which achieves robustness with respect to model perturbations by giving a quantitative interpretation to predicates and logical operators, and by discounting the importance of events according to how late they occur. In every state, the value of a formula is a real number in the interval [0,1], where 1 corresponds to truth and 0 to falsehood. The boolean operators and and or are replaced by min and max, the path quantifiers ∃ and ∀ determine sup and inf over all paths from a given state, and the temporal operators ⋄ and □ specify sup and inf over a given path; a new operator averages all values along a path. Furthermore, all path operators are discounted by a parameter that can be chosen to give more weight to states that are closer to the beginning of the path. We interpret the resulting logic DCTL over transition systems, Markov chains, and Markov decision processes. We present two semantics for DCTL: a path semantics, inspired by the standard interpretation of state and path formulas in CTL, and a fixpoint semantics, inspired by the μ-calculus evaluation of CTL formulas. We show that, while these semantics coincide for CTL, they differ for DCTL, and we provide model-checking algorithms for both semantics.}, author = {de Alfaro, Luca and Faella, Marco and Thomas Henzinger and Majumdar, Ritankar S and Stoelinga, Mariëlle}, journal = {Theoretical Computer Science}, number = {1}, pages = {139 -- 170}, publisher = {Elsevier}, title = {{Model checking discounted temporal properties}}, doi = {10.1016/j.tcs.2005.07.033}, volume = {345}, year = {2005}, } @inproceedings{4624, abstract = {Surveying results from [5] and [6], we motivate and introduce the theory behind formalizing rich interfaces for software and hardware components. Rich interfaces specify the protocol aspects of component interaction. Their formalization, called interface automata, permits a compiler to check the compatibility of component interaction protocols. Interface automata 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, while still maintaining compatibility.}, author = {de Alfaro, Luca and Thomas Henzinger}, pages = {83 -- 104}, publisher = {Springer}, title = {{Interface-based design}}, doi = {10.1007/1-4020-3532-2_3}, volume = {195}, year = {2005}, } @inproceedings{575, abstract = {We present the first demonstration of Jozsa's "counterfactual computation", using an optical Grover's search algorithm. We put the algorithm in a superposition of 'running' and 'not-running', obtaining information even though the algorithm does not run.}, author = {Onur Hosten and Rakher, Matthew T and Barreiro, Julio T and Peters, Nicholas A and Kwiat, Paul G}, pages = {365 -- 367}, publisher = {IEEE}, title = {{Counterfactual quantum computation}}, doi = { 10.1109/QELS.2005.1548783}, volume = {1}, year = {2005}, } @article{6153, abstract = {A current challenge in neuroscience is to bridge the gaps between genes, proteins, neurons, neural circuits, and behavior in a single animal model. The nematode Caenorhabditis elegans has unique features that facilitate this synthesis. Its nervous system includes exactly 302 neurons, and their pattern of synaptic connectivity is known. With only five olfactory neurons, C. elegans can dynamically respond to dozens of attractive and repellant odors. Thermosensory neurons enable the nematode to remember its cultivation temperature and to track narrow isotherms. Polymodal sensory neurons detect a wide range of nociceptive cues and signal robust escape responses. Pairing of sensory stimuli leads to long-lived changes in behavior consistent with associative learning. Worms exhibit social behaviors and complex ultradian rhythms driven by Ca2+ oscillators with clock-like properties. Genetic analysis has identified gene products required for nervous system function and elucidated the molecular and neural bases of behaviors.}, author = {de Bono, Mario and Villu Maricq, Andres}, issn = {0147-006X}, journal = {Annual Review of Neuroscience}, pages = {451--501}, publisher = {Annual Reviews}, title = {{Neuronal substrates of complex behaviors in C. elegans}}, doi = {10.1146/annurev.neuro.27.070203.144259}, volume = {28}, year = {2005}, } @article{6154, author = {Cheung, Benny H.H. and Cohen, Merav and Rogers, Candida and Albayram, Onder and de Bono, Mario}, issn = {0960-9822}, journal = {Current Biology}, number = {10}, pages = {905--917}, publisher = {Elsevier}, title = {{Experience-dependent modulation of C. elegans behavior by ambient oxygen}}, doi = {10.1016/j.cub.2005.04.017}, volume = {15}, year = {2005}, } @article{8028, abstract = {Transmission of signals within the brain is essential for cognitive function, but it is not clear how neural circuits support reliable and accurate signal propagation over a sufficiently large dynamic range. Two modes of propagation have been studied: synfire chains, in which synchronous activity travels through feedforward layers of a neuronal network, and the propagation of fluctuations in firing rate across these layers. In both cases, a sufficient amount of noise, which was added to previous models from an external source, had to be included to support stable propagation. Sparse, randomly connected networks of spiking model neurons can generate chaotic patterns of activity. We investigate whether this activity, which is a more realistic noise source, is sufficient to allow for signal transmission. We find that, for rate-coded signals but not for synfire chains, such networks support robust and accurate signal reproduction through up to six layers if appropriate adjustments are made in synaptic strengths. We investigate the factors affecting transmission and show that multiple signals can propagate simultaneously along different pathways. Using this feature, we show how different types of logic gates can arise within the architecture of the random network through the strengthening of specific synapses.}, author = {Vogels, Tim P and Abbott, L. F.}, issn = {0270-6474}, journal = {Journal of Neuroscience}, number = {46}, pages = {10786--10795}, publisher = {Society for Neuroscience}, title = {{Signal propagation and logic gating in networks of integrate-and-fire neurons}}, doi = {10.1523/jneurosci.3508-05.2005}, volume = {25}, year = {2005}, } @article{8029, abstract = {Neural network modeling is often concerned with stimulus-driven responses, but most of the activity in the brain is internally generated. Here, we review network models of internally generated activity, focusing on three types of network dynamics: (a) sustained responses to transient stimuli, which provide a model of working memory; (b) oscillatory network activity; and (c) chaotic activity, which models complex patterns of background spiking in cortical and other circuits. We also review propagation of stimulus-driven activity through spontaneously active networks. Exploring these aspects of neural network dynamics is critical for understanding how neural circuits produce cognitive function.}, author = {Vogels, Tim P and Rajan, Kanaka and Abbott, L.F.}, issn = {0147-006X}, journal = {Annual Review of Neuroscience}, number = {1}, pages = {357--376}, publisher = {Annual Reviews}, title = {{Neural network dynamics}}, doi = {10.1146/annurev.neuro.28.061604.135637}, volume = {28}, year = {2005}, } @article{9491, abstract = {Cytosine DNA methylation in vertebrates is widespread, but methylation in plants is found almost exclusively at transposable elements and repetitive DNA [1]. Within regions of methylation, methylcytosines are typically found in CG, CNG, and asymmetric contexts. CG sites are maintained by a plant homolog of mammalian Dnmt1 acting on hemi-methylated DNA after replication. Methylation of CNG and asymmetric sites appears to be maintained at each cell cycle by other mechanisms. We report a new type of DNA methylation in Arabidopsis, dense CG methylation clusters found at scattered sites throughout the genome. These clusters lack non-CG methylation and are preferentially found in genes, although they are relatively deficient toward the 5′ end. CG methylation clusters are present in lines derived from different accessions and in mutants that eliminate de novo methylation, indicating that CG methylation clusters are stably maintained at specific sites. Because 5-methylcytosine is mutagenic, the appearance of CG methylation clusters over evolutionary time predicts a genome-wide deficiency of CG dinucleotides and an excess of C(A/T)G trinucleotides within transcribed regions. This is exactly what we find, implying that CG methylation clusters have contributed profoundly to plant gene evolution. We suggest that CG methylation clusters silence cryptic promoters that arise sporadically within transcription units.}, author = {Tran, Robert K. and Henikoff, Jorja G. and Zilberman, Daniel and Ditt, Renata F. and Jacobsen, Steven E. and Henikoff, Steven}, issn = {1879-0445}, journal = {Current Biology}, number = {2}, pages = {154--159}, publisher = {Elsevier}, title = {{DNA methylation profiling identifies CG methylation clusters in Arabidopsis genes}}, doi = {10.1016/j.cub.2005.01.008}, volume = {15}, year = {2005}, } @article{9514, abstract = {Background: DNA methylation occurs at preferred sites in eukaryotes. In Arabidopsis, DNA cytosine methylation is maintained by three subfamilies of methyltransferases with distinct substrate specificities and different modes of action. Targeting of cytosine methylation at selected loci has been found to sometimes involve histone H3 methylation and small interfering (si)RNAs. However, the relationship between different cytosine methylation pathways and their preferred targets is not known. Results: We used a microarray-based profiling method to explore the involvement of Arabidopsis CMT3 and DRM DNA methyltransferases, a histone H3 lysine-9 methyltransferase (KYP) and an Argonaute-related siRNA silencing component (AGO4) in methylating target loci. We found that KYP targets are also CMT3 targets, suggesting that histone methylation maintains CNG methylation genome-wide. CMT3 and KYP targets show similar proximal distributions that correspond to the overall distribution of transposable elements of all types, whereas DRM targets are distributed more distally along the chromosome. We find an inverse relationship between element size and loss of methylation in ago4 and drm mutants. Conclusion: We conclude that the targets of both DNA methylation and histone H3K9 methylation pathways are transposable elements genome-wide, irrespective of element type and position. Our findings also suggest that RNA-directed DNA methylation is required to silence isolated elements that may be too small to be maintained in a silent state by a chromatin-based mechanism alone. Thus, parallel pathways would be needed to maintain silencing of transposable elements.}, author = {Tran, Robert K. and Zilberman, Daniel and de Bustos, Cecilia and Ditt, Renata F. and Henikoff, Jorja G. and Lindroth, Anders M. and Delrow, Jeffrey and Boyle, Tom and Kwong, Samson and Bryson, Terri D. and Jacobsen, Steven E. and Henikoff, Steven}, issn = {1465-6906}, journal = {Genome Biology}, number = {11}, publisher = {Springer Nature}, title = {{Chromatin and siRNA pathways cooperate to maintain DNA methylation of small transposable elements in Arabidopsis}}, doi = {10.1186/gb-2005-6-11-r90}, volume = {6}, year = {2005}, } @article{843, abstract = {The impact of an amino acid replacement on the organism's fitness can vary from lethal to selectively neutral and even, in rare cases, beneficial. Substantial data are available on either pathogenic or acceptable replacements. However, the whole distribution of coefficients of selection against individual replacements is not known for any organism. To ascertain this distribution for human proteins, we combined data on pathogenic missense mutations, on human non-synonymous SNPs and on human-chimpanzee divergence of orthologous proteins. Fractions of amino acid replacements which reduce fitness by >10-2, 10-2-10-4, 10-4-10-5 and <10-5 are 25, 49, 14 and 12%, respectively. On average, the strength of selection against a replacement is substantially higher when chemically dissimilar amino acids are involved, and the Grantham's index of a replacement explains 35% of variance in the average logarithm of selection coefficients associated with different replacements. Still, the impact of a replacement depends on its context within the protein more than on its own nature. Reciprocal replacements are often associated with rather different selection coefficients, in particular, replacements of non-polar amino acids with polar ones are typically much more deleterious than replacements in the opposite direction. However, differences between evolutionary fluxes of reciprocal replacements are only weakly correlated with the differences between the corresponding selection coefficients.}, author = {Yampolsky, Lev Y and Fyodor Kondrashov and Kondrashov, Alexey S}, journal = {Human Molecular Genetics}, number = {21}, pages = {3191 -- 3201}, publisher = {Oxford University Press}, title = {{Distribution of the strength of selection against amino acid replacements in human proteins}}, doi = {10.1093/hmg/ddi350}, volume = {14}, year = {2005}, } @article{8491, abstract = {Fast multidimensional NMR with a time resolution of a few seconds provides a new tool for high throughput screening and site-resolved real-time studies of kinetic molecular processes by NMR. Recently we have demonstrated the feasibility to record protein 1H–15N correlation spectra in a few seconds of acquisition time using a new SOFAST-HMQC experiment (Schanda and Brutscher (2005) J. Am. Chem. Soc. 127, 8014). Here, we investigate in detail the performance of SOFAST-HMQC to record 1H–15N and 1H−13C correlation spectra of proteins of different size and at different magnetic field strengths. Compared to standard 1H–15N correlation experiments SOFAST-HMQC provides a significant gain in sensitivity, especially for fast repetition rates. Guidelines are provided on how to set up SOFAST-HMQC experiments for a given protein sample. In addition, an alternative pulse scheme, IPAP-SOFAST-HMQC is presented that allows application on NMR spectrometers equipped with cryogenic probes, and fast measurement of one-bond 1H–13C and 1H–15N scalar and residual dipolar coupling constants.}, author = {Schanda, Paul and Kupče, Ēriks and Brutscher, Bernhard}, issn = {0925-2738}, journal = {Journal of Biomolecular NMR}, keywords = {Spectroscopy, Biochemistry}, number = {4}, pages = {199--211}, publisher = {Springer Nature}, title = {{SOFAST-HMQC experiments for recording two-dimensional deteronuclear correlation spectra of proteins within a few seconds}}, doi = {10.1007/s10858-005-4425-x}, volume = {33}, year = {2005}, } @article{8492, abstract = {We demonstrate for different protein samples that 2D 1H−15N correlation NMR spectra can be recorded in a few seconds of acquisition time using a new band-selective optimized flip-angle short-transient heteronuclear multiple quantum coherence experiment. This has enabled us to measure fast hydrogen−deuterium exchange rate constants along the backbone of a small globular protein fragment by real-time 2D NMR.}, author = {Schanda, Paul and Brutscher, Bernhard}, issn = {0002-7863}, journal = {Journal of the American Chemical Society}, keywords = {Colloid and Surface Chemistry, Biochemistry, General Chemistry, Catalysis}, number = {22}, pages = {8014--8015}, publisher = {American Chemical Society}, title = {{Very fast two-dimensional NMR spectroscopy for real-time investigation of dynamic events in proteins on the time scale of seconds}}, doi = {10.1021/ja051306e}, volume = {127}, year = {2005}, } @article{8516, abstract = {The purpose of this paper is to construct examples of diffusion for E-Hamiltonian perturbations of completely integrable Hamiltonian systems in 2d-dimensional phase space, with d large. In the first part of the paper, simple and explicit examples are constructed illustrating absence of ‘long-time’ stability for size E Hamiltonian perturbations of quasi-convex integrable systems already when the dimension 2d of phase space becomes as large as log 1/E . We first produce the example in Gevrey class and then a real analytic one, with some additional work. In the second part, we consider again E-Hamiltonian perturbations of completely integrable Hamiltonian system in 2d-dimensional space with E-small but not too small, |E| > exp(−d), with d the number of degrees of freedom assumed large. It is shown that for a class of analytic time-periodic perturbations, there exist linearly diffusing trajectories. The underlying idea for both examples is similar and consists in coupling a fixed degree of freedom with a large number of them. The procedure and analytical details are however significantly different. As mentioned, the construction in Part I is totally elementary while Part II is more involved, relying in particular on the theory of normally hyperbolic invariant manifolds, methods of generating functions, Aubry–Mather theory, and Mather’s variational methods.}, author = {Bourgain, Jean and Kaloshin, Vadim}, issn = {0022-1236}, journal = {Journal of Functional Analysis}, keywords = {Analysis}, number = {1}, pages = {1--61}, publisher = {Elsevier}, title = {{On diffusion in high-dimensional Hamiltonian systems}}, doi = {10.1016/j.jfa.2004.09.006}, volume = {229}, year = {2005}, } @article{877, abstract = {Sequence analysis of protein and mitochondrially encoded tRNA genes shows that substitutions producing pathogenic effects in humans are often found in normal, healthy individuals from other species. Analysis of stability of protein and tRNA structures shows that the disease-causing effects of pathogenic mutations can be neutralized by other, compensatory substitutions that restore the structural stability of the molecule. Further study of such substitutions will, hopefully, lead to new methods for curing genetic dis- eases that may be based on the correction of molecule stability as a whole instead of reversing an individual pathogenic mutation.}, author = {Kondrashov, Fyodor}, journal = {Biofizika}, number = {3}, pages = {389 -- 395}, publisher = {Pleiades Publishing}, title = {{The analysis of monomer sequences in protein and tRNA and the manifestation of the compensation of pathogenic deviations in their evolution}}, volume = {50}, year = {2005}, } @article{878, abstract = {Negative trade-offs are thought to be a pervasive phenomenon and to inhibit evolution at all levels. New evidence shows that at the molecular level, there may be no trade-offs preventing the emergence of an enzyme with multiple functions. }, author = {Fyodor Kondrashov}, journal = {Nature Genetics}, number = {1}, pages = {9 -- 10}, publisher = {Nature Publishing Group}, title = {{In search of the limits of evolution}}, doi = {10.1038/ng0105-9}, volume = {37}, year = {2005}, } @article{882, abstract = {Some mutations in human mitochondrial tRNAs are severely pathogenic. The available computational methods have a poor record of predicting the impact of a tRNA mutation on the phenotype and fitness. Here patterns of evolution at tRNA sites that harbor pathogenic mutations and at sites that harbor phenotypically cryptic polymorphisms were compared. Mutations that are pathogenic to humans occupy more conservative sites, are only rarely fixed in closely related species, and, when located in stem structures, often disrupt Watson-Crick pairing and display signs of compensatory evolution. These observations make it possible to classify ∼90% of all known pathogenic mutations as deleterious together with only ∼30% of polymorphisms. These polymorphisms segregate at frequencies that are more than two times lower than frequencies of polymorphisms classified as benign, indicating that at least ∼30% of known polymorphisms in mitochondrial tRNAs affect fitness negatively.}, author = {Fyodor Kondrashov}, journal = {Human Molecular Genetics}, number = {16}, pages = {2415 -- 2419}, publisher = {Oxford University Press}, title = {{Prediction of pathogenic mutations in mitochondrially encoded human tRNAs}}, doi = {10.1093/hmg/ddi243}, volume = {14}, year = {2005}, } @article{880, abstract = {Here, I describe a case of loss of the D-arm by mitochondrial cysteine tRNA in the nine-banded armadillo (Dasypus novemcinctus) convergent with mt tRNASer(AGY). Such evolution sheds light on the relationship between structure and function of tRNA molecules and its impact on the patterns of molecular evolution.}, author = {Kondrashov, Fyodor}, journal = {Biofizika}, number = {3}, pages = {396 -- 403}, publisher = {Pleiades Publishing}, title = {{The convergent evolution of the secondary structure of mitochondrial cysteine tRNA in the nine-banded armadillo Dasypus novemcinctus}}, volume = {50}, year = {2005}, } @article{893, abstract = {Amino acid composition of proteins varies substantially between taxa and, thus, can evolve. For example, proteins from organisms with (G+C)-rich (or (A+T)-rich) genomes contain more (or fewer) amino acids encoded by (G+C)-rich codons. However, no universal trends in ongoing changes of amino acid frequencies have been reported. We compared sets of orthologous proteins encoded by triplets of closely related genomes from 15 taxa representing all three domains of life (Bacteria, Archaea and Eukaryota), and used phylogenies to polarize amino acid substitutions. Cys, Met, His, Ser and Phe accrue in at least 14 taxa, whereas Pro, Ala, Glu and Gly are consistently lost. The same nine amino acids are currently accrued or lost in human proteins, as shown by analysis of non-synonymous single-nucleotide polymorphisms. All amino acids with declining frequencies are thought to be among the first incorporated into the genetic code; conversely, all amino acids with increasing frequencies, except Ser, were probably recruited late. Thus, expansion of initially under-represented amino acids, which began over 3,400 million years ago, apparently continues to this day.}, author = {Jordan, Ingo K and Fyodor Kondrashov and Adzhubeǐ, Ivan A and Wolf, Yuri I and Koonin, Eugene V and Kondrashov, Alexey S and Sunyaev, Shamil R}, journal = {Nature}, number = {7026}, pages = {633 -- 638}, publisher = {Nature Publishing Group}, title = {{A universal trend of amino acid gain and loss in protein evolution}}, doi = {10.1038/nature03306}, volume = {433}, year = {2005}, } @article{9529, abstract = {Eukaryotic organisms have the remarkable ability to inherit states of gene activity without altering the underlying DNA sequence. This epigenetic inheritance can persist over thousands of years, providing an alternative to genetic mutations as a substrate for natural selection. Epigenetic inheritance might be propagated by differences in DNA methylation, post-translational histone modifications, and deposition of histone variants. Mounting evidence also indicates that small interfering RNA (siRNA)-mediated mechanisms play central roles in setting up and maintaining states of gene activity. Much of the epigenetic machinery of many organisms, including Arabidopsis, appears to be directed at silencing viruses and transposable elements, with epigenetic regulation of endogenous genes being mostly derived from such processes.}, author = {Zilberman, Daniel and Henikoff, Steven}, issn = {0959-437X}, journal = {Current Opinion in Genetics and Development}, number = {5}, pages = {557--562}, publisher = {Elsevier}, title = {{Epigenetic inheritance in Arabidopsis: Selective silence}}, doi = {10.1016/j.gde.2005.07.002}, volume = {15}, year = {2005}, } @article{13431, abstract = {Hydrogel stamps can microstructure solid surfaces, i.e., modify the surface topology of metals, glasses, and crystals. It is demonstrated that stamps soaked in an appropriate etchant can remove material with micrometer-scale precision. The Figure shows an array of concentric circles etched in glass using the immersion wet stamping process described (scale bar: 500 μm).}, author = {Smoukov, S. K. and Bishop, K. J. M. and Klajn, Rafal and Campbell, C. J. and Grzybowski, B. A.}, issn = {1521-4095}, journal = {Advanced Materials}, keywords = {Mechanical Engineering, Mechanics of Materials, General Materials Science}, number = {11}, pages = {1361--1365}, publisher = {Wiley}, title = {{Cutting into solids with micropatterned gels}}, doi = {10.1002/adma.200402086}, volume = {17}, year = {2005}, } @article{13433, abstract = {Self-assembled monolayers (SAMs) of alkane thiols on gold and other metals are versatile constructs with which to study interfacial phenomena and reactions at surfaces. Surface properties of SAMs - e.g., wettability, stability in diverse environments, propensity to interact with or to resist adsorption of macromolecules -- depend on and can be controlled flexibly by the properties of the functional (head) groups in the w position of the alkyl chain. SAMs provide a basis for many important scientific and technological applications, ranging from micropatterning methods, through sensing, to biological recognition. Despite their importance, the literature on SAMs and the synthesis of molecules that constitute them remains scattered and often conflicting. The purpose of this Review is (i) to summarize the applications and physical properties of SAMs and (ii) to systematize the strategies of synthesis of ω-functionalized alkane thiols. Generic retrosynthetic scheme is developed that allows efficient synthetic planning. Issues related to the selection of appropriate protecting groups and the ways of introduction of the thiol functionality are discussed in detail, and illustrated with examples of syntheses of several complex alkane thiols.}, author = {Witt, Dariusz and Klajn, Rafal and Barski, Piotr and Grzybowski, Bartosz}, issn = {1875-5348}, journal = {Current Organic Chemistry}, keywords = {Organic Chemistry}, number = {18}, pages = {1763--1797}, publisher = {Bentham Science}, title = {{Applications, properties and synthesis of w-functionalized n-alkanethiols and disulfides - the building blocks of self-assembled monolayers}}, doi = {10.2174/1385272043369421}, volume = {8}, year = {2005}, } @article{13432, abstract = {A new experimental technique is described that uses reaction−diffusion phenomena as a means of one-step microfabrication of complex, multilevel surface reliefs. Thin films of dry gelatin doped with potassium hexacyanoferrate are chemically micropatterned with a solution of silver nitrate delivered from an agarose stamp. Precipitation reaction between the two salts causes the surface to deform. The mechanism of surface deformation is shown to involve a sequence of reactions, diffusion, and gel swelling/contraction. This mechanism is established experimentally and provides a basis of a theoretical lattice-gas model that allows prediction surface topographies emerging from arbitrary geometries of the stamped features. The usefulness of the technique is demonstrated by using it to rapidly prepare two types of mold for passive microfluidic mixers.}, author = {Campbell, Christopher J. and Klajn, Rafal and Fialkowski, Marcin and Grzybowski, Bartosz A.}, issn = {1520-5827}, journal = {Langmuir}, keywords = {Electrochemistry, Spectroscopy, Surfaces and Interfaces, Condensed Matter Physics, General Materials Science}, number = {1}, pages = {418--423}, publisher = {American Chemical Society}, title = {{One-step multilevel microfabrication by reaction−diffusion}}, doi = {10.1021/la0487747}, volume = {21}, year = {2005}, }