@article{3787,
abstract = {DNA samples were extracted from ethanol and formalin-fixed decapod crustacean tissue using a new method based on Tetramethylsilane (TMS)-Chelex. It is shown that neither an indigestible matrix of cross-linked protein nor soluble PCR inhibitors impede PCR success when dealing with formalin-fixed material. Instead, amplification success from formalin-fixed tissue appears to depend on the presence of unmodified DNA in the extracted sample. A staining method that facilitates the targeting of samples with a high content of unmodified DNA is provided.},
author = {Palero, Ferran and Hall, Sally and Clark, Paul and Johnston, David and Mackenzie Dodds, Jackie and Thatje, Sven},
journal = {Scientia Marina},
number = {3},
pages = {465 -- 470},
publisher = {Consejo Superior de Investigaciones Científicas},
title = {{DNA extraction from formalin-fixed tissue: new light from the deep sea}},
doi = {10.3989/scimar.2010.74n3465},
volume = {74},
year = {2010},
}
@inproceedings{3838,
abstract = {We present a numerical approximation technique for the analysis of continuous-time Markov chains that describe net- works of biochemical reactions and play an important role in the stochastic modeling of biological systems. Our approach is based on the construction of a stochastic hybrid model in which certain discrete random variables of the original Markov chain are approximated by continuous deterministic variables. We compute the solution of the stochastic hybrid model using a numerical algorithm that discretizes time and in each step performs a mutual update of the transient prob- ability distribution of the discrete stochastic variables and the values of the continuous deterministic variables. We im- plemented the algorithm and we demonstrate its usefulness and efficiency on several case studies from systems biology.},
author = {Henzinger, Thomas A and Mateescu, Maria and Mikeev, Linar and Wolf, Verena},
location = {Trento, Italy},
pages = {55 -- 65},
publisher = {Springer},
title = {{Hybrid numerical solution of the chemical master equation}},
doi = {10.1145/1839764.1839772},
year = {2010},
}
@inproceedings{3852,
abstract = {We introduce two-level discounted games played by two players on a perfect-information stochastic game graph. The upper level game is a discounted game and the lower level game is an undiscounted reachability game. Two-level games model hierarchical and sequential decision making under uncertainty across different time scales. We show the existence of pure memoryless optimal strategies for both players and an ordered field property for such games. We show that if there is only one player (Markov decision processes), then the values can be computed in polynomial time. It follows that whether the value of a player is equal to a given rational constant in two-level discounted games can be decided in NP intersected coNP. We also give an alternate strategy improvement algorithm to compute the value. },
author = {Chatterjee, Krishnendu and Majumdar, Ritankar},
location = {Minori, Italy},
pages = {22 -- 29},
publisher = {EPTCS},
title = {{Discounting in games across time scales}},
doi = {10.4204/EPTCS.25.6},
volume = {25},
year = {2010},
}
@inproceedings{3845,
abstract = {This paper presents Aligators, a tool for the generation of universally quantified array invariants. Aligators leverages recurrence solving and algebraic techniques to carry out inductive reasoning over array content. The Aligators’ loop extraction module allows treatment of multi-path loops by exploiting their commutativity and serializability properties. Our experience in applying Aligators on a collection of loops from open source software projects indicates the applicability of recurrence and algebraic solving techniques for reasoning about arrays.},
author = {Henzinger, Thomas A and Hottelier, Thibaud and Kovács, Laura and Rybalchenko, Andrey},
location = {Yogyakarta, Indonesia},
pages = {348 -- 356},
publisher = {Springer},
title = {{Aligators for arrays}},
doi = {10.1007/978-3-642-16242-8_25},
volume = {6397},
year = {2010},
}
@inproceedings{4381,
abstract = {Cloud computing aims to give users virtually unlimited pay-per-use computing resources without the burden of managing the underlying infrastructure. We claim that, in order to realize the full potential of cloud computing, the user must be presented with a pricing model that offers flexibility at the requirements level, such as a choice between different degrees of execution speed and the cloud provider must be presented with a programming model that offers flexibility at the execution level, such as a choice between different scheduling policies. In such a flexible framework, with each job, the user purchases a virtual computer with the desired speed and cost characteristics, and the cloud provider can optimize the utilization of resources across a stream of jobs from different users. We designed a flexible framework to test our hypothesis, which is called FlexPRICE (Flexible Provisioning of Resources in a Cloud Environment) and works as follows. A user presents a job to the cloud. The cloud finds different schedules to execute the job and presents a set of quotes to the user in terms of price and duration for the execution. The user then chooses a particular quote and the cloud is obliged to execute the job according to the chosen quote. FlexPRICE thus hides the complexity of the actual scheduling decisions from the user, but still provides enough flexibility to meet the users actual demands. We implemented FlexPRICE in a simulator called PRICES that allows us to experiment with our framework. We observe that FlexPRICE provides a wide range of execution options-from fast and expensive to slow and cheap-- for the whole spectrum of data-intensive and computation-intensive jobs. We also observe that the set of quotes computed by FlexPRICE do not vary as the number of simultaneous jobs increases.},
author = {Henzinger, Thomas A and Tomar, Anmol and Singh, Vasu and Wies, Thomas and Zufferey, Damien},
location = {Miami, USA},
pages = {83 -- 90},
publisher = {IEEE},
title = {{FlexPRICE: Flexible provisioning of resources in a cloud environment}},
doi = {10.1109/CLOUD.2010.71 },
year = {2010},
}
@inproceedings{489,
abstract = {Graph games of infinite length are a natural model for open reactive processes: one player represents the controller, trying to ensure a given specification, and the other represents a hostile environment. The evolution of the system depends on the decisions of both players, supplemented by chance. In this work, we focus on the notion of randomised strategy. More specifically, we show that three natural definitions may lead to very different results: in the most general cases, an almost-surely winning situation may become almost-surely losing if the player is only allowed to use a weaker notion of strategy. In more reasonable settings, translations exist, but they require infinite memory, even in simple cases. Finally, some traditional problems becomes undecidable for the strongest type of strategies.},
author = {Cristau, Julien and David, Claire and Horn, Florian},
booktitle = {Proceedings of GandALF 2010},
location = {Minori, Amalfi Coast, Italy},
pages = {30 -- 39},
publisher = {Open Publishing Association},
title = {{How do we remember the past in randomised strategies? }},
doi = {10.4204/EPTCS.25.7},
volume = {25},
year = {2010},
}
@misc{5391,
abstract = {Concurrent data structures with fine-grained synchronization are notoriously difficult to implement correctly. The difficulty of reasoning about these implementations does not stem from the number of variables or the program size, but rather from the large number of possible interleavings. These implementations are therefore prime candidates for model checking. We introduce an algorithm for verifying linearizability of singly-linked heap-based concurrent data structures. We consider a model consisting of an unbounded heap where each node consists an element from an unbounded data domain, with a restricted set of operations for testing and updating pointers and data elements. Our main result is that linearizability is decidable for programs that invoke a fixed number of methods, possibly in parallel. This decidable fragment covers many of the common implementation techniques — fine-grained locking, lazy synchronization, and lock-free synchronization. We also show how the technique can be used to verify optimistic implementations with the help of programmer annotations. We developed a verification tool CoLT and evaluated it on a representative sample of Java implementations of the concurrent set data structure. The tool verified linearizability of a number of implementations, found a known error in a lock-free imple- mentation and proved that the corrected version is linearizable.},
author = {Cerny, Pavol and Radhakrishna, Arjun and Zufferey, Damien and Chaudhuri, Swarat and Alur, Rajeev},
issn = {2664-1690},
pages = {27},
publisher = {IST Austria},
title = {{Model checking of linearizability of concurrent list implementations}},
doi = {10.15479/AT:IST-2010-0001},
year = {2010},
}
@article{3303,
abstract = {Biological traits result in part from interactions between different genetic loci. This can lead to sign epistasis, in which a beneficial adaptation involves a combination of individually deleterious or neutral mutations; in this case, a population must cross a “fitness valley” to adapt. Recombination can assist this process by combining mutations from different individuals or retard it by breaking up the adaptive combination. Here, we analyze the simplest fitness valley, in which an adaptation requires one mutation at each of two loci to provide a fitness benefit. We present a theoretical analysis of the effect of recombination on the valley-crossing process across the full spectrum of possible parameter regimes. We find that low recombination rates can speed up valley crossing relative to the asexual case, while higher recombination rates slow down valley crossing, with the transition between the two regimes occurring when the recombination rate between the loci is approximately equal to the selective advantage provided by the adaptation. In large populations, if the recombination rate is high and selection against single mutants is substantial, the time to cross the valley grows exponentially with population size, effectively meaning that the population cannot acquire the adaptation. Recombination at the optimal (low) rate can reduce the valley-crossing time by up to several orders of magnitude relative to that in an asexual population. },
author = {Weissman, Daniel and Feldman, Marcus and Fisher, Daniel},
journal = {Genetics},
number = {4},
pages = {1389 -- 1410},
publisher = {Genetics Society of America},
title = {{The rate of fitness-valley crossing in sexual populations}},
doi = {10.1534/genetics.110.123240},
volume = {186},
year = {2010},
}
@inproceedings{3719,
abstract = {The induction of a signaling pathway is characterized by transient complex formation and mutual posttranslational modification of proteins. To faithfully capture this combinatorial process in a math- ematical model is an important challenge in systems biology. Exploiting the limited context on which most binding and modification events are conditioned, attempts have been made to reduce the com- binatorial complexity by quotienting the reachable set of molecular species, into species aggregates while preserving the deterministic semantics of the thermodynamic limit. Recently we proposed a quotienting that also preserves the stochastic semantics and that is complete in the sense that the semantics of individual species can be recovered from the aggregate semantics. In this paper we prove that this quotienting yields a sufficient condition for weak lumpability and that it gives rise to a backward Markov bisimulation between the original and aggregated transition system. We illustrate the framework on a case study of the EGF/insulin receptor crosstalk.},
author = {Feret, Jérôme and Henzinger, Thomas A and Koeppl, Heinz and Petrov, Tatjana},
location = {Jena, Germany},
pages = {142--161},
publisher = {Open Publishing Association},
title = {{Lumpability abstractions of rule-based systems}},
volume = {40},
year = {2010},
}
@article{3776,
abstract = {The prevalence of recombination in eukaryotes poses one of the most puzzling questions in biology. The most compelling general explanation is that recombination facilitates selection by breaking down the negative associations generated by random drift (i.e. Hill-Robertson interference, HRI). I classify the effects of HRI owing to: deleterious mutation, balancing selection and selective sweeps on: neutral diversity, rates of adaptation and the mutation load. These effects are mediated primarily by the density of deleterious mutations and of selective sweeps. Sequence polymorphism and divergence suggest that these rates may be high enough to cause significant interference even in genomic regions of high recombination. However, neither seems able to generate enough variance in fitness to select strongly for high rates of recombination. It is plausible that spatial and temporal fluctuations in selection generate much more fitness variance, and hence selection for recombination, than can be explained by uniformly deleterious mutations or species-wide selective sweeps.},
author = {Barton, Nicholas H},
journal = {Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences},
number = {1552},
pages = {2559 -- 2569},
publisher = {Royal Society},
title = {{Genetic linkage and natural selection}},
doi = {10.1098/rstb.2010.0106},
volume = {365},
year = {2010},
}
@article{3790,
abstract = {Cell shape and motility are primarily controlled by cellular mechanics. The attachment of the plasma membrane to the underlying actomyosin cortex has been proposed to be important for cellular processes involving membrane deformation. However, little is known about the actual function of membrane-to-cortex attachment (MCA) in cell protrusion formation and migration, in particular in the context of the developing embryo. Here, we use a multidisciplinary approach to study MCA in zebrafish mesoderm and endoderm (mesendoderm) germ layer progenitor cells, which migrate using a combination of different protrusion types, namely, lamellipodia, filopodia, and blebs, during zebrafish gastrulation. By interfering with the activity of molecules linking the cortex to the membrane and measuring resulting changes in MCA by atomic force microscopy, we show that reducing MCA in mesendoderm progenitors increases the proportion of cellular blebs and reduces the directionality of cell migration. We propose that MCA is a key parameter controlling the relative proportions of different cell protrusion types in mesendoderm progenitors, and thus is key in controlling directed migration during gastrulation.},
author = {Diz Muñoz, Alba and Krieg, Michael and Bergert, Martin and Ibarlucea Benitez, Itziar and Müller, Daniel and Paluch, Ewa and Heisenberg, Carl-Philipp J},
journal = {PLoS Biology},
number = {11},
publisher = {Public Library of Science},
title = {{Control of directed cell migration in vivo by membrane-to-cortex attachment}},
doi = {10.1371/journal.pbio.1000544},
volume = {8},
year = {2010},
}
@inbook{3795,
abstract = {The (apparent) contour of a smooth mapping from a 2-manifold to the plane, f: M → R2 , is the set of critical values, that is, the image of the points at which the gradients of the two component functions are linearly dependent. Assuming M is compact and orientable and measuring difference with the erosion distance, we prove that the contour is stable.},
author = {Edelsbrunner, Herbert and Morozov, Dmitriy and Patel, Amit},
booktitle = {Topological Data Analysis and Visualization: Theory, Algorithms and Applications},
pages = {27 -- 42},
publisher = {Springer},
title = {{The stability of the apparent contour of an orientable 2-manifold}},
doi = {10.1007/978-3-642-15014-2_3},
year = {2010},
}
@article{3834,
abstract = {Background
The chemical master equation (CME) is a system of ordinary differential equations that describes the evolution of a network of chemical reactions as a stochastic process. Its solution yields the probability density vector of the system at each point in time. Solving the CME numerically is in many cases computationally expensive or even infeasible as the number of reachable states can be very large or infinite. We introduce the sliding window method, which computes an approximate solution of the CME by performing a sequence of local analysis steps. In each step, only a manageable subset of states is considered, representing a "window" into the state space. In subsequent steps, the window follows the direction in which the probability mass moves, until the time period of interest has elapsed. We construct the window based on a deterministic approximation of the future behavior of the system by estimating upper and lower bounds on the populations of the chemical species.
Results
In order to show the effectiveness of our approach, we apply it to several examples previously described in the literature. The experimental results show that the proposed method speeds up the analysis considerably, compared to a global analysis, while still providing high accuracy.
Conclusions
The sliding window method is a novel approach to address the performance problems of numerical algorithms for the solution of the chemical master equation. The method efficiently approximates the probability distributions at the time points of interest for a variety of chemically reacting systems, including systems for which no upper bound on the population sizes of the chemical species is known a priori.},
author = {Wolf, Verena and Goel, Rushil and Mateescu, Maria and Henzinger, Thomas A},
journal = {BMC Systems Biology},
number = {42},
pages = {1 -- 19},
publisher = {BioMed Central},
title = {{Solving the chemical master equation using sliding windows}},
doi = {10.1186/1752-0509-4-42},
volume = {4},
year = {2010},
}
@inproceedings{3839,
abstract = {We present a loop property generation method for loops iterating over multi-dimensional arrays. When used on matrices, our method is able to infer their shapes (also called types), such as upper-triangular, diagonal, etc. To gen- erate loop properties, we first transform a nested loop iterating over a multi- dimensional array into an equivalent collection of unnested loops. Then, we in- fer quantified loop invariants for each unnested loop using a generalization of a recurrence-based invariant generation technique. These loop invariants give us conditions on matrices from which we can derive matrix types automatically us- ing theorem provers. Invariant generation is implemented in the software package Aligator and types are derived by theorem provers and SMT solvers, including Vampire and Z3. When run on the Java matrix package JAMA, our tool was able to infer automatically all matrix types describing the matrix shapes guaranteed by JAMA’s API.},
author = {Henzinger, Thomas A and Hottelier, Thibaud and Kovács, Laura and Voronkov, Andrei},
location = {Madrid, Spain},
pages = {163 -- 179},
publisher = {Springer},
title = {{Invariant and type inference for matrices}},
doi = {10.1007/978-3-642-11319-2_14},
volume = {5944},
year = {2010},
}
@inproceedings{3853,
abstract = {Quantitative languages are an extension of boolean languages that assign to each word a real number. Mean-payoff automata are finite automata with numerical weights on transitions that assign to each infinite path the long-run average of the transition weights. When the mode of branching of the automaton is deterministic, nondeterministic, or alternating, the corresponding class of quantitative languages is not robust as it is not closed under the pointwise operations of max, min, sum, and numerical complement. Nondeterministic and alternating mean-payoff automata are not decidable either, as the quantitative generalization of the problems of universality and language inclusion is undecidable. We introduce a new class of quantitative languages, defined by mean-payoff automaton expressions, which is robust and decidable: it is closed under the four pointwise operations, and we show that all decision problems are decidable for this class. Mean-payoff automaton expressions subsume deterministic meanpayoff automata, and we show that they have expressive power incomparable to nondeterministic and alternating mean-payoff automata. We also present for the first time an algorithm to compute distance between two quantitative languages, and in our case the quantitative languages are given as mean-payoff automaton expressions.},
author = {Chatterjee, Krishnendu and Doyen, Laurent and Edelsbrunner, Herbert and Henzinger, Thomas A and Rannou, Philippe},
location = {Paris, France},
pages = {269 -- 283},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Mean-payoff automaton expressions}},
doi = {10.1007/978-3-642-15375-4_19},
volume = {6269},
year = {2010},
}
@inproceedings{3860,
abstract = {In mean-payoff games, the objective of the protagonist is to ensure that the limit average of an infinite sequence of numeric weights is nonnegative. In energy games, the objective is to ensure that the running sum of weights is always nonnegative. Generalized mean-payoff and energy games replace individual weights by tuples, and the limit average (resp. running sum) of each coordinate must be (resp. remain) nonnegative. These games have applications in the synthesis of resource-bounded processes with multiple resources. We prove the finite-memory determinacy of generalized energy games and show the inter- reducibility of generalized mean-payoff and energy games for finite-memory strategies. We also improve the computational complexity for solving both classes of games with finite-memory strategies: while the previously best known upper bound was EXPSPACE, and no lower bound was known, we give an optimal coNP-complete bound. For memoryless strategies, we show that the problem of deciding the existence of a winning strategy for the protagonist is NP-complete.},
author = {Chatterjee, Krishnendu and Doyen, Laurent and Henzinger, Thomas A and Raskin, Jean},
location = {Chennai, India},
pages = {505 -- 516},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Generalized mean-payoff and energy games}},
doi = {10.4230/LIPIcs.FSTTCS.2010.505},
volume = {8},
year = {2010},
}
@article{4243,
abstract = {We investigate a new model for populations evolving in a spatial continuum. This model can be thought of as a spatial version of the Lambda-Fleming-Viot process. It explicitly incorporates both small scale reproduction events and large scale extinction-recolonisation events. The lineages ancestral to a sample from a population evolving according to this model can be described in terms of a spatial version of the Lambda-coalescent. Using a technique of Evans (1997), we prove existence and uniqueness in law for the model. We then investigate the asymptotic behaviour of the genealogy of a finite number of individuals sampled uniformly at random (or more generally `far enough apart') from a two-dimensional torus of sidelength L as L tends to infinity. Under appropriate conditions (and on a suitable timescale) we can obtain as limiting genealogical processes a Kingman coalescent, a more general Lambda-coalescent or a system of coalescing Brownian motions (with a non-local coalescence mechanism).},
author = {Barton, Nicholas H and Etheridge, Alison and Véber, Amandine},
journal = {Electronic Journal of Probability},
number = {7},
pages = {162 -- 216},
publisher = {Institute of Mathematical Statistics},
title = {{A new model for evolution in a spatial continuum}},
doi = {10.1214/EJP.v15-741},
volume = {15},
year = {2010},
}
@inproceedings{4382,
abstract = {Transactional memory (TM) has shown potential to simplify the task of writing concurrent programs. Inspired by classical work on databases, formal definitions of the semantics of TM executions have been proposed. Many of these definitions assumed that accesses to shared data are solely performed through transactions. In practice, due to legacy code and concurrency libraries, transactions in a TM have to share data with non-transactional operations. The semantics of such interaction, while widely discussed by practitioners, lacks a clear formal specification. Those interactions can vary, sometimes in subtle ways, between TM implementations and underlying memory models. We propose a correctness condition for TMs, parametrized opacity, to formally capture the now folklore notion of strong atomicity by stipulating the two following intuitive requirements: first, every transaction appears as if it is executed instantaneously with respect to other transactions and non-transactional operations, and second, non-transactional operations conform to the given underlying memory model. We investigate the inherent cost of implementing parametrized opacity. We first prove that parametrized opacity requires either instrumenting non-transactional operations (for most memory models) or writing to memory by transactions using potentially expensive read-modify-write instructions (such as compare-and-swap). Then, we show that for a class of practical relaxed memory models, parametrized opacity can indeed be implemented with constant-time instrumentation of non-transactional writes and no instrumentation of non-transactional reads. We show that, in practice, parametrizing the notion of correctness allows developing more efficient TM implementations.},
author = {Guerraoui, Rachid and Henzinger, Thomas A and Kapalka, Michal and Singh, Vasu},
location = {Santorini, Greece},
pages = {263 -- 272},
publisher = {ACM},
title = {{Transactions in the jungle}},
doi = {10.1145/1810479.1810529},
year = {2010},
}
@article{3772,
author = {Barton, Nicholas H},
journal = {PLoS Genetics},
number = {6},
publisher = {Public Library of Science},
title = {{Understanding adaptation in large populations}},
doi = {10.1371/journal.pgen.1000987},
volume = {6},
year = {2010},
}
@article{3777,
abstract = {Under the classical view, selection depends more or less directly on mutation: standing genetic variance is maintained by a balance between selection and mutation, and adaptation is fuelled by new favourable mutations. Recombination is favoured if it breaks negative associations among selected alleles, which interfere with adaptation. Such associations may be generated by negative epistasis, or by random drift (leading to the Hill-Robertson effect). Both deterministic and stochastic explanations depend primarily on the genomic mutation rate, U. This may be large enough to explain high recombination rates in some organisms, but seems unlikely to be so in general. Random drift is a more general source of negative linkage disequilibria, and can cause selection for recombination even in large populations, through the chance loss of new favourable mutations. The rate of species-wide substitutions is much too low to drive this mechanism, but local fluctuations in selection, combined with gene flow, may suffice. These arguments are illustrated by comparing the interaction between good and bad mutations at unlinked loci under the infinitesimal model.},
author = {Barton, Nicholas H},
journal = {Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences},
number = {1544},
pages = {1281 -- 1294},
publisher = {Royal Society},
title = {{Mutation and the evolution of recombination}},
doi = {10.1098/rstb.2009.0320},
volume = {365},
year = {2010},
}