@inproceedings{3021, abstract = {Polarized transport of the plant hormone auxin influences multiple growth processes in plants and is regulated by plasma-membrane-localized efflux and uptake carriers. The PGP (P-glycoprotein) ABC transporters (ATP-binding-cassette transporters), PIN (pin-formed) subfamily of major facilitator proteins and members of AUX/LAX families have been shown to independently transport auxin both in planta and in heterologous systems. However, PIN- and PGP-mediated transport in heterologous systems exhibits decreased substrate specificity and inhibitor-sensitivity compared with what is seen in plants and plant cells. To determine whether PIN-PGP interactions enhance transport specificity, we analysed interactions of the representative auxin-transporting PGPs with PIN1 and AUX1 in planta and in heterologous systems. Here, we provide evidence that PINs and PGPs interact and function both independently and co-ordinately to control polar auxin transport and impart transport specificity and directionality. These interactions take place in protein complexes stabilized by PGPs in detergent-resistant microdomains.}, author = {Bandyopadhyay, Anindita and Blakeslee, Joshua and Lee, Ok Ran and Mravec, Jozef and Sauer, Michael and Titapiwatanakun, Boosaree and Makam, Srinivas N and Bouchard, Rodolphe and Geisler, Markus and Martinoia, Enrico and Jirí Friml and Peer, Wendy A and Murphy, Angus S}, number = {1}, pages = {137 -- 141}, publisher = {Portland Press}, title = {{Interactions of PIN and PGP auxin transport mechanisms}}, doi = {10.1042/BST0350137}, volume = {35}, year = {2007}, } @article{3029, abstract = {In Arabidopsis thaliana, lateral roots are formed from root pericycle cells adjacent to the xylem poles. Lateral root development is regulated antagonistically by the plant hormones auxin and cytokinin. While a great deal is known about how auxin promotes lateral root development, the mechanism of cytokinin repression is still unclear. Elevating cytokinin levels was observed to disrupt lateral root initiation and the regular pattern of divisions that characterizes lateral root development in Arabidopsis. To identify the stage of lateral root development that is sensitive to cytokinins, we targeted the expression of the Agrobacterium tumefaciens cytokinin biosynthesis enzyme isopentenyltransferase to either xylem-pole pericycle cells or young lateral root primordia using GAL4-GFP enhancer trap lines. Transactivation experiments revealed that xylem-pole pericycle cells are sensitive to cytokinins, whereas young lateral root primordia are not. This effect is physiologically significant because transactivation of the Arabidopsis cytokinin degrading enzyme cytokinin oxidase 1 in lateral root founder cells results in increased lateral root formation. We observed that cytokinins perturb the expression of PIN genes in lateral root founder cells and prevent the formation of an auxin gradient that is required to pattern lateral root primordia.}, author = {Laplaze, Laurent and Eva Benková and Casimiro, Ilda and Maes, Lies and Vanneste, Steffen and Swarup, Ranjan and Weijers, Dolf and Calvo, Vanessa and Parizot, Boris and Herrera-Rodriguez, Maria Begoña and Offringa, Remko and Graham, Neil and Doumas, Patrick and Jirí Friml and Bogusz, Didier and Beeckman, Tom and Bennett, Malcolm}, journal = {Plant Cell}, number = {12}, pages = {3889 -- 3900}, publisher = {American Society of Plant Biologists}, title = {{Cytokinins act directly on lateral root founder cells to inhibit root initiation}}, doi = {10.1105/tpc.107.055863}, volume = {19}, year = {2007}, } @article{3026, abstract = {In plants, each developmental process integrates a network of signaling events that are regulated by different phytohormones, and interactions among hormonal pathways are essential to modulate their effect. Continuous growth of roots results from the postembryonic activity of cells within the root meristem that is controlled by the coordinated action of several phytohormones, including auxin and ethylene. Although their interaction has been studied intensively, the molecular and cellular mechanisms underlying this interplay are unknown. We show that the effect of ethylene on root growth is largely mediated by the regulation of the auxin biosynthesis and transport-dependent local auxin distribution. Ethylene stimulates auxin biosynthesis and basipetal auxin transport toward the elongation zone, where it activates a local auxin response leading to inhibition of cell elongation. Consistently, in mutants affected in auxin perception or basipetal auxin transport, ethylene cannot activate the auxin response nor regulate the root growth. In addition, ethylene modulates the transcription of several components of the auxin transport machinery. Thus, ethylene achieves a local activation of the auxin signaling pathway and regulates root growth by both stimulating the auxin biosynthesis and by modulating the auxin transport machinery.}, author = {Růžička, Kamil and Ljung, Karin and Vanneste, Steffen and Podhorská, Radka and Beeckman, Tom and Jirí Friml and Eva Benková}, journal = {Plant Cell}, number = {7}, pages = {2197 -- 2212}, publisher = {American Society of Plant Biologists}, title = {{Ethylene regulates root growth through effects on auxin biosynthesis and transport dependent auxin distribution}}, doi = {10.1105/tpc.107.052126}, volume = {19}, year = {2007}, } @article{3028, abstract = {In plants, cell polarity and tissue patterning are connected by intercellular flow of the phytohormone auxin, whose directional signaling depends on polar subcellular localization of PIN auxin transport proteins. The mechanism of polar targeting of PINs or other cargos in plants is largely unidentified, with the PINOID kinase being the only known molecular component. Here, we identify PP2A phosphatase as an important regulator of PIN apical-basal targeting and auxin distribution. Genetic analysis, localization, and phosphorylation studies demonstrate that PP2A and PINOID both partially colocalize with PINs and act antagonistically on the phosphorylation state of their central hydrophilic loop, hence mediating PIN apical-basal polar targeting. Thus, in plants, polar sorting by the reversible phosphorylation of cargos allows for their conditional delivery to specific intracellular destinations. In the case of PIN proteins, this mechanism enables switches in the direction of intercellular auxin fluxes, which mediate differential growth, tissue patterning, and organogenesis.}, author = {Michniewicz, Marta and Zago, Marcelo K and Abas, Lindy and Weijers, Dolf and Schweighofer, Alois and Meskiene, Irute and Heisler, Marcus G and Ohno, Carolyn and Zhang, Jing and Huang, Fang and Schwab, Rebecca and Weigel, Detlef and Meyerowitz, Elliot M and Luschnig, Christian and Offringa, Remko and Jirí Friml}, journal = {Cell}, number = {6}, pages = {1044 -- 1056}, publisher = {Cell Press}, title = {{Antagonistic regulation of PIN phosphorylation by PP2A and PINOID directs auxin flux}}, doi = {10.1016/j.cell.2007.07.033}, volume = {130}, year = {2007}, } @article{3024, abstract = {The plant hormone auxin is frequently observed to be asymmetrically distributed across adjacent cells during crucial stages of growth and development. These auxin gradients depend on polar transport and regulate a wide variety of processes, including embryogenesis, organogenesis, vascular tissue differentiation, root meristem maintenance and tropic growth. Auxin can mediate such a perplexing array of developmental processes by acting as a general trigger for the change in developmental program in cells where it accumulates and by providing vectorial information to the tissues by its polar intercellular flow. In recent years, a wealth of molecular data on the mechanism of auxin transport and its regulation has been generated, providing significant insights into the action of this versatile coordinative signal.}, author = {Vieten, Anne and Sauer, Michael and Brewer, Philip and Friml, Jirí}, journal = {Trends in Plant Science}, number = {4}, pages = {160 -- 168}, publisher = {Cell Press}, title = {{Molecular and cellular aspects of auxin-transport-mediated development}}, doi = {10.1016/j.tplants.2007.03.006}, volume = {12}, year = {2007}, } @inproceedings{3192, abstract = {Many computer vision applications rely on the efficient optimization of challenging, so-called non-submodular, binary pairwise MRFs. A promising graph cut based approach for optimizing such MRFs known as "roof duality" was recently introduced into computer vision. We study two methods which extend this approach. First, we discuss an efficient implementation of the "probing" technique introduced recently by Boros et al. [5]. It simplifies the MRF while preserving the global optimum. Our code is 400-700 faster on some graphs than the implementation of [5]. Second, we present a new technique which takes an arbitrary input labeling and tries to improve its energy. We give theoretical characterizations of local minima of this procedure. We applied both techniques to many applications, including image segmentation, new view synthesis, superresolution, diagram recognition, parameter learning, texture restoration, and image deconvolution. For several applications we see that we are able to find the global minimum very efficiently, and considerably outperform the original roof duality approach. In comparison to existing techniques, such as graph cut, TRW, BP, ICM, and simulated annealing, we nearly always find a lower energy.}, author = {Rother, Carsten and Vladimir Kolmogorov and Lempitsky, Victor and Szummer, Martin}, publisher = {IEEE}, title = {{Optimizing binary MRFs via extended roof duality}}, doi = {10.1109/CVPR.2007.383203}, year = {2007}, } @inproceedings{3191, abstract = {The maximum flow algorithm for minimizing energy functions of binary variables has become a standard tool in computer vision. In many cases, unary costs of the energy depend linearly on parameter lambda. In this paper we study vision applications for which it is important to solve the maxflow problem for different lambda's. An example is a weighting between data and regularization terms in image segmentation or stereo: it is desirable to vary it both during training (to learn lambda from ground truth data) and testing (to select best lambda using high-knowledge constraints, e.g. user input). We review algorithmic aspects of this parametric maximum flow problem previously unknown in vision, such as the ability to compute all breakpoints of lambda and corresponding optimal configurations infinite time. These results allow, in particular, to minimize the ratio of some geometric functional, such as flux of a vector field over length (or area). Previously, such functional were tackled with shortest path techniques applicable only in 2D. We give theoretical improvements for "PDE cuts" [5]. We present experimental results for image segmentation, 3D reconstruction, and the cosegmentation problem.}, author = {Vladimir Kolmogorov and Boykov, Yuri and Rother, Carsten}, publisher = {IEEE}, title = {{Applications of parametric maxflow in computer vision}}, doi = {10.1109/ICCV.2007.4408910}, year = {2007}, } @article{3193, abstract = {Optimization techniques based on graph cuts have become a standard tool for many vision applications. These techniques allow to minimize efficiently certain energy functions corresponding to pairwise Markov Random Fields (MRFs). Currently, there is an accepted view within the computer vision community that graph cuts can only be used for optimizing a limited class of MRF energies (e.g., submodular functions). In this survey, we review some results that show that graph cuts can be applied to a much larger class of energy functions (in particular, nonsubmodular functions). While these results are well-known in the optimization community, to our knowledge they were not used in the context of computer vision and MRF optimization. We demonstrate the relevance of these results to vision on the problem of binary texture restoration. }, author = {Vladimir Kolmogorov and Rother, Carsten}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, number = {7}, pages = {1274 -- 1279}, publisher = {IEEE}, title = {{Minimizing nonsubmodular functions with graph cuts - A review}}, doi = {10.1109/TPAMI.2007.1031}, volume = {29}, year = {2007}, } @article{3187, abstract = {Stereo vision has numerous applications in robotics, graphics, inspection and other areas. A prime application, one which has driven work on stereo in our laboratory, is teleconferencing in which the use of a stereo webcam already makes possible various transformations of the video stream. These include digital camera control, insertion of virtual objects, background substitution, and eye-gaze correction [9, 8].}, author = {Blake, Andrew and Criminisi, Antonio and Cross, Geoffrey and Vladimir Kolmogorov and Rother, Carsten}, journal = {Springer Tracts in Advanced Robotics}, pages = {295 -- 304}, publisher = {Springer}, title = {{Fusion of stereo colour and contrast}}, doi = {10.1007/978-3-540-48113-3_27}, volume = {28}, year = {2007}, } @inproceedings{3218, abstract = {A (k, ℓ)-robust combiner for collision-resistant hash-functions is a construction which from ℓ hash-functions constructs a hash-function which is collision-resistant if at least k of the components are collision-resistant. One trivially gets a (k, ℓ)-robust combiner by concatenating the output of any ℓ - k + 1 of the components, unfortunately this is not very practical as the length of the output of the combiner is quite large. We show that this is unavoidable as no black-box (k, ℓ)-robust combiner whose output is significantly shorter than what can be achieved by concatenation exists. This answers a question of Boneh and Boyen (Crypto'06). }, author = {Krzysztof Pietrzak}, pages = {23 -- 33}, publisher = {Springer}, title = {{Non-trivial black-box combiners for collision-resistant hash-functions don't exist}}, doi = {10.1007/978-3-540-72540-4_2}, volume = {4515}, year = {2007}, } @article{3305, abstract = {The accumulation of deleterious mutations plays a major role in evolution, and key to this are the interactions between their fitness effects, known as epistasis. Whether mutations tend to interact synergistically (with multiple mutations being more deleterious than would be expected from their individual fitness effects) or antagonistically is important for a variety of evolutionary questions, particularly the evolution of sex. Unfortunately, the experimental evidence on the prevalence and strength of epistasis is mixed and inconclusive. Here we study theoretically whether synergistic or antagonistic epistasis is likely to be favored by evolution and by how much. We find that in the presence of recombination, evolution favors less synergistic or more antagonistic epistasis whenever mutations that change the epistasis in this direction are possible. This is because evolution favors increased buffering against the effects of deleterious mutations. This suggests that we should not expect synergistic epistasis to be widespread in nature and hence that the mutational deterministic hypothesis for the advantage of sex may not apply widely.}, author = {Desai, Michael M and Daniel Weissman and Feldman, Marcus W}, journal = {Genetics}, number = {2}, pages = {1001 -- 10}, publisher = {Genetics Society of America}, title = {{Evolution can favor antagonistic epistasis}}, doi = {10.1534/genetics.107.075812}, volume = {177}, year = {2007}, } @article{3411, abstract = {Mechanical single-molecule techniques offer exciting possibilities to investigate protein folding and stability in native environments at submolecular resolution. By applying a free-energy reconstruction procedure developed by Hummer and Szabo, which is based on a statistical theorem introduced by Jarzynski, we determined the unfolding free energy of the membrane proteins bacteriorhodopsin (BR), halorhodopsin, and the sodium-proton antiporter NhaA. The calculated energies ranged from 290.5kcal/mol for BR to 485.5kcal/mol for NhaA. For the remarkably stable BR, the equilibrium unfolding free energy was independent of pulling rate and temperature ranging between 18 and 42°C. Our experiments also revealed heterogeneous energetic properties in individual transmembrane helices. In halorhodopsin, the stabilization of a short helical segment yielded a characteristic signature in the energy profile. In NhaA, a pronounced peak was observed at a functionally important site in the protein. Since a large variety of single- and multispan membrane proteins can be tackled in mechanical unfolding experiments, our approach provides a basis for systematically elucidating energetic properties of membrane proteins with the resolution of individual secondary-structure elements.}, author = {Preiner, Johannes and Harald Janovjak and Rankl, Christian and Knaus, Helene and Cisneros, David A and Kedrov, Alexej and Kienberger, Ferry and Mueller, Daniel J and Hinterdorfer, Peter}, journal = {Biophysical Journal}, number = {3}, pages = {930 -- 937}, publisher = {Biophysical Society}, title = {{Free energy of membrane protein unfolding derived from single-molecule force measurements}}, doi = {10.1529/biophysj.106.096982}, volume = {93}, year = {2007}, } @misc{3412, abstract = {Molecular interactions are the basic language of biological processes. They establish the forces interacting between the building blocks of proteins and other macromolecules, thus determining their functional roles. Because molecular interactions trigger virtually every biological process, approaches to decipher their language are needed. Single-molecule force spectroscopy (SMFS) has been used to detect and characterize different types of molecular interactions that occur between and within native membrane proteins. The first experiments detected and localized molecular interactions that stabilized membrane proteins, including how these interactions were established during folding of α-helical secondary structure elements into the native protein and how they changed with oligomerization, temperature, and mutations. SMFS also enables investigators to detect and locate molecular interactions established during ligand and inhibitor binding. These exciting applications provide opportunities for studying the molecular forces of life. Further developments will elucidate the origins of molecular interactions encoded in their lifetimes, interaction ranges, interplay, and dynamics characteristic of biological systems.}, author = {Kedrov, Alexej and Harald Janovjak and Sapra, Tanuj K and Mueller, Daniel J}, booktitle = {Annual Review of Biophysics}, pages = {233 -- 260}, publisher = {Annual Reviews}, title = {{Deciphering molecular interactions of native membrane proteins by single-molecule force spectroscopy}}, doi = {10.1146/annurev.biophys.36.040306.132640}, volume = {36}, year = {2007}, } @article{3427, abstract = {We present a general theoretical framework to discuss mechanisms of morphogen transport and gradient formation in a cell layer. Trafficking events on the cellular scale lead to transport on larger scales. We discuss in particular the case of transcytosis where morphogens undergo repeated rounds of internalization into cells and recycling. Based on a description on the cellular scale, we derive effective nonlinear transport equations in one and two dimensions which are valid on larger scales. We derive analytic expressions for the concentration dependence of the effective diffusion coefficient and the effective degradation rate. We discuss the effects of a directional bias on morphogen transport and those of the coupling of the morphogen and receptor kinetics. Furthermore, we discuss general properties of cellular transport processes such as the robustness of gradients and relate our results to recent experiments on the morphogen Decapentaplegic (Dpp) that acts in the wing disk of the fruit fly Drosophila. © 2007 The American Physical Society}, author = {Bollenbach, Mark Tobias and Kruse, Karsten and Pantazis, Periklis and Gonzalez Gaitan, Marcos and Julicher, Frank}, journal = {Physical Review E Statistical Nonlinear and Soft Matter Physics}, number = {1}, publisher = {American Institute of Physics}, title = {{Morphogen transport in epithelia}}, doi = {10.1103/PhysRevE.75.011901}, volume = {75}, year = {2007}, } @article{3523, abstract = {On the linear track, the recent firing sequences of CA1 place cells recur during sharp wave/ripple patterns (SWRs) in a reverse temporal order [Foster & Wilson (2006) Nature, 440, 680-683]. We have found similar reverse-order reactivation during SWRs in open-field exploration where the firing sequence of cells varied before each SWR. Both the onset times and the firing patterns of cells showed a tendency for reversed sequences during SWRs. These effects were observed for SWRs that occurred during exploration, but not for those during longer immobility periods. Additionally, reverse reactivation was stronger when it was preceded by higher speed (> 5 cm/s) run periods. The trend for reverse-order SWR reactivation was not significantly different in familiar and novel environments, even though SWR-associated firing rates of both pyramidal cells and interneurons were reduced in novel environments as compared with familiar. During exploration-associated SWRs (eSWR) place cells retain place-selective firing [O'Neill et al. (2006) Neuron, 49, 143-155]. Here, we have shown that each cell's firing onset was more delayed and firing probability more reduced during eSWRs the further the rat was from the middle of the cell's place field; that is, cells receiving less momentary place-related excitatory drive fired later during SWR events. However, even controlling for place field distance, the recent firing of cells was still significantly correlated with SWR reactivation sequences. We therefore propose that both place-related drive and the firing history of cells contribute to reverse reactivation during eSWRs.}, author = {Jozsef Csicsvari and Joseph O'Neill and Allen, Kevin and Senior,Timothy}, journal = {European Journal of Neuroscience}, number = {3}, pages = {704 -- 716}, publisher = {Wiley-Blackwell}, title = {{Place-selective firing contributes to the reverse-order reactivation of CA1 pyramidal cells during sharp waves in open-field exploration}}, doi = {10.1111/j.1460-9568.2007.05684.x}, volume = {26}, year = {2007}, } @inproceedings{3601, abstract = {In this paper, the multiobjective optimal design of space-based reconfigurable sensor networks with novel adaptive MEMS antennas is investigated by using multiobjective evolutionary algorithms. The non-dominated sorting genetic algorithm II (NSGA-II) is employed to obtain multi-criteria Pareto-optimal solutions, which allows system designers to easily make a reasonable trade-off choice from the set of non-dominated solutions according to their preferences and system requirements. As a case study, a cluster-based satellite sensing network is simulated under multiple objectives. Most importantly, this paper also presents the application of our newly designed adaptive MEMS antennas together with the NSGA-II to the multiobjective optimal design of space-based reconfigurable sensor networks.}, author = {Yang, Erfu and Haridas, Nakul and El-Rayis, Ahmed O and Erdogan, Ahmet T and Arslan, Tughrul and Nicholas Barton}, pages = {27 -- 34}, publisher = {IEEE}, title = {{Multiobjective optimal design of MEMS-based reconfigurable and evolvable sensor networks for space applications}}, doi = {10.1109/AHS.2007.76}, year = {2007}, } @techreport{3687, abstract = {Recent years have seen huge advances in object recognition from images. Recognition rates beyond 95% are the rule rather than the exception on many datasets. However, most state-of-the-art methods can only decide if an object is present or not. They are not able to provide information on the object location or extent within in the image. We report on a simple yet powerful scheme that extends many existing recognition methods to also perform localization of object bounding boxes. This is achieved by maximizing the classification score over all possible subrectangles in the image. Despite the impression that this would be computationally intractable, we show that in many situations efficient algorithms exist which solve a generalized maximum subrectangle problem. We show how our method is applicable to a variety object detection frameworks and demonstrate its performance by applying it to the popular bag of visual words model, achieving competitive results on the PASCAL VOC 2006 dataset.}, author = {Blaschko,Matthew B and Hofmann,Thomas and Christoph Lampert}, booktitle = {Unknown}, number = {164}, publisher = {Max-Planck-Institute for Biological Cybernetics}, title = {{Efficient subwindow search for object localization}}, year = {2007}, } @inproceedings{3701, abstract = {The extraction of a parametric global motion from a motion field is a task with several applications in video processing. We present two probabilistic formulations of the problem and carry out optimization using the RAST algorithm, a geometric matching method novel to motion estimation in video. RAST uses an exhaustive and adaptive search of transformation space and thus gives – in contrast to local sampling optimization techniques used in the past – a globally optimal solution. Among other applications, our framework can thus be used as a source of ground truth for benchmarking motion estimation algorithms. Our main contributions are: first, the novel combination of a state-of-the-art MAP criterion for dominant motion estimation with a search procedure that guarantees global optimality. Second, experimental results that illustrate the superior performance of our approach on synthetic flow fields as well as real-world video streams. Third, a significant speedup of the search achieved by extending the model with an additional smoothness prior.}, author = {Ulges, Adrian and Christoph Lampert and Keysers,Daniel and Breuel,Thomas M}, pages = {204 -- 213}, publisher = {Springer}, title = {{Optimal dominant motion estimation using adaptive search of transformation space}}, doi = {10.1007/978-3-540-74936-3_21}, volume = {4713}, year = {2007}, } @article{3731, abstract = {A cell's ability to regulate gene transcription depends in large part on the energy with which transcription factors (TFs) bind their DNA regulatory sites. Obtaining accurate models of this binding energy is therefore an important goal for quantitative biology. In this article, we present a principled likelihood-based approach for inferring physical models of TF-DNA binding energy from the data produced by modern high-throughput binding assays. Central to our analysis is the ability to assess the relative likelihood of different model parameters given experimental observations. We take a unique approach to this problem and show how to compute likelihood without any explicit assumptions about the noise that inevitably corrupts such measurements. Sampling possible choices for model parameters according to this likelihood function, we can then make probabilistic predictions for the identities of binding sites and their physical binding energies. Applying this procedure to previously published data on the Saccharomyces cerevisiae TF Abf1p, we find models of TF binding whose parameters are determined with remarkable precision. Evidence for the accuracy of these models is provided by an astonishing level of phylogenetic conservation in the predicted energies of putative binding sites. Results from in vivo and in vitro experiments also provide highly consistent characterizations of Abf1p, a result that contrasts with a previous analysis of the same data.}, author = {Kinney,Justin B and Gasper Tkacik and Callan,Curtis G}, journal = {PNAS}, number = {2}, pages = {501 -- 506}, publisher = {National Academy of Sciences}, title = {{Precise physical models of protein-DNA interaction from high-throughput data}}, doi = {10.1073/pnas.0609908104}, volume = {104}, year = {2007}, } @article{3765, abstract = {We present an extension to Lagrangian finite element methods to allow for large plastic deformations of solid materials. These behaviors are seen in such everyday materials as shampoo, dough, and clay as well as in fantastic gooey and blobby creatures in special effects scenes. To account for plastic deformation, we explicitly update the linear basis functions defined over the finite elements during each simulation step. When these updates cause the basis functions to become ill-conditioned, we remesh the simulation domain to produce a new high-quality finite-element mesh, taking care to preserve the original boundary. We also introduce an enhanced plasticity model that preserves volume and includes creep and work hardening/softening. We demonstrate our approach with simulations of synthetic objects that squish, dent, and flow. To validate our methods, we compare simulation results to videos of real materials.}, author = {Bargteil, Adam and Wojtan, Christopher J and Hodgins, Jessica and Turk, Greg}, journal = {ACM Transactions on Graphics}, number = {3}, publisher = {ACM}, title = {{A finite element method for animating large viscoplastic flow}}, doi = {10.1145/1276377.1276397}, volume = {26}, year = {2007}, } @inproceedings{3762, abstract = {In this paper, we present a simple method for animating natural phenomena such as erosion, sedimentation, and acidic corrosion. We discretize the appropriate physical or chemical equations using finite differences, and we use the results to modify the shape of a solid body. We remove mass from an object by treating its surface as a level set and advecting it inward, and we deposit the chemical and physical byproducts into simulated fluid. Similarly, our technique deposits sediment onto a surface by advecting the level set outward. Our idea can be used for off-line high quality animations as well as interactive applications such as games, and we demonstrate both in this paper.}, author = {Wojtan, Christopher J and Carlson, Mark and Mucha, Peter and Turk, Greg}, pages = {15 -- 22}, publisher = {Eurographics Association}, title = {{Animating corrosion and erosion}}, doi = {10.2312/NPH/NPH07/015-022}, year = {2007}, } @article{3816, abstract = {Gamma frequency oscillations are thought to provide a temporal structure for information processing in the brain. They contribute to cognitive functions, such as memory formation and sensory processing, and are disturbed in some psychiatric disorders. Fast-spiking, parvalbumin-expressing, soma-inhibiting interneurons have a key role in the generation of these oscillations. Experimental analysis in the hippocampus and the neocortex reveals that synapses among these interneurons are highly specialized. Computational analysis further suggests that synaptic specialization turns interneuron networks into robust gamma frequency oscillators.}, author = {Bartos, Marlene and Vida, Imre and Peter Jonas}, journal = {Nature Reviews Neuroscience}, number = {1}, pages = {45 -- 56}, publisher = {Nature Publishing Group}, title = {{Synaptic mechanisms of synchronized gamma oscillations in inhibitory interneuron networks (Review)}}, doi = {10.1038/nrn2044 }, volume = {8}, year = {2007}, } @article{3911, abstract = {Life in a social group increases the risk of disease transmission. To counteract this threat, social insects have evolved manifold antiparasite defenses, ranging from social exclusion of infected group members to intensive care. It is generally assumed that individuals performing hygienic behaviors risk infecting themselves, suggesting a high direct cost of helping. Our work instead indicates the opposite for garden ants. Social contact with individual workers, which were experimentally exposed to a fungal parasite, provided a clear survival benefit to nontreated, naive group members upon later challenge with the same parasite. This first demonstration of contact immunity in Social Hymenoptera and complementary results from other animal groups and plants suggest its general importance in both antiparasite and antiherbivore defense. In addition to this physiological prophylaxis of adult ants, infection of the brood was prevented in our experiment by behavioral changes of treated and naive workers. Parasite-treated ants stayed away from the brood chamber, whereas their naive nestmates increased brood-care activities. Our findings reveal a direct benefit for individuals to perform hygienic behaviors toward others, and this might explain the widely observed maintenance of social cohesion under parasite attack in insect societies.}, author = {Ugelvig, Line V and Cremer, Sylvia}, journal = {Current Biology}, number = {22}, pages = {1967 -- 1971}, publisher = {Cell Press}, title = {{Social prophylaxis: group interaction promotes collective immunity in ant colonies}}, doi = {10.1016/j.cub.2007.10.029}, volume = {17}, year = {2007}, } @article{3909, abstract = {Social insect colonies have evolved collective immune defences against parasites. These ‘social immune systems’ result from the cooperation of the individual group members to combat the increased risk of disease transmission that arises from sociality and group living. In this review we illustrate the pathways that parasites can take to infect a social insect colony and use these pathways as a framework to predict colony defence mechanisms and present the existing evidence. We find that the collective defences can be both prophylactic and activated on demand and consist of behavioural, physiological and organisational adaptations of the colony that prevent parasite entrance, establishment and spread. We discuss the regulation of collective immunity, which requires complex integration of information about both the parasites and the internal status of the insect colony. Our review concludes with an examination of the evolution of social immunity, which is based on the consequences of selection at both the individual and the colony level.}, author = {Cremer, Sylvia and Armitage, Sophie and Schmid Hempel, Paul}, journal = {Current Biology}, number = {16}, pages = {R693 -- R702}, publisher = {Cell Press}, title = {{Social immunity}}, doi = {10.1016/j.cub.2007.06.008}, volume = {17}, year = {2007}, } @article{3910, author = {Hughes, David and Cremer, Sylvia}, journal = {Animal Behaviour}, number = {5}, pages = {1593 -- 1599}, publisher = {Elsevier}, title = {{Plasticity in anti-parasite behaviours and its suggested role in invasion biology}}, doi = {10.1016/j.anbehav.2006.12.025}, volume = {74}, year = {2007}, } @article{3976, abstract = {Herein, we study the interfaces of a set of 146 transient protein-protein interfaces in order to better understand the principles of their interactions. We define and generate the protein interface using tools from computational geometry and topology and then apply statistical analysis to its residue composition. In addition to counting individual occurrences, we evaluate pairing preferences, both across and as neighbors on one side of an interface. Likelihood correction emphasizes novel and unexpected pairs, such as the His-Cys pair found in most complexes of serine proteases with their diverse inhibitors and the Met-Met neighbor pair found in unrelated protein interfaces. We also present a visualization of the protein interface that allows for facile identification of residue-residue contacts and other biochemical properties.}, author = {Headd, Jeffrey J and Ban, Y E Andrew and Brown, Paul and Herbert Edelsbrunner and Vaidya, Madhuwanti and Rudolph, Johannes}, journal = {Journal of Proteome Research}, number = {7}, pages = {2576 -- 2586}, publisher = {American Chemical Society}, title = {{Protein-protein interfaces: Properties, preferences, and projections}}, doi = {10.1021/pr070018+}, volume = {6}, year = {2007}, } @inproceedings{3981, abstract = {Building on the work of Martinetz, Schulten and de Silva, Carlsson, we introduce a 2-parameter family of witness complexes and algorithms for constructing them. This family can be used to determine the gross topology of point cloud data in R-d or other metric spaces. The 2-parameter family is sensitive to differences in sampling density and thus amenable to detecting patterns within the data set. It also lends itself to theoretical analysis. For example, we can prove that in the limit, when the witnesses cover the entire domain, witness complexes in the family that share the first, scale parameter have the same homotopy type.}, author = {Attali, Dominique and Herbert Edelsbrunner and Harer, John and Mileyko, Yuriy}, pages = {386 -- 397}, publisher = {Springer}, title = {{Alpha-beta witness complexes}}, doi = {10.1007/978-3-540-73951-7_34}, volume = {4619}, year = {2007}, } @inproceedings{3975, abstract = {We study the reconstruction of a stratified space from a possibly noisy point sample. Specifically, we use the vineyard of the distance function restricted to a I-parameter family of neighborhoods of a point to assess the local homology of the stratified space at that point. We prove the correctness of this assessment under the assumption of a sufficiently dense sample. We also give an algorithm that constructs the vineyard and makes the local assessment in time at most cubic in the size of the Delaunay triangulation of the point sample.}, author = {Paul Bendich and Cohen-Steiner, David and Herbert Edelsbrunner and Harer, John and Morozov, Dmitriy}, pages = {536 -- 546}, publisher = {IEEE}, title = {{Inferring local homology from sampled stratified spaces}}, doi = {10.1109/FOCS.2007.33}, year = {2007}, } @article{3977, abstract = {Using inclusion-exclusion, we can write the indicator function of a union of finitely many balls as an alternating sum of indicator functions of common intersections of balls. We exhibit abstract simplicial complexes that correspond to minimal inclusion-exclusion formulas. They include the dual complex, as defined in [3], and are characterized by the independence of their simplices and by geometric realizations with the same underlying space as the dual complex.}, author = {Attali, Dominique and Herbert Edelsbrunner}, journal = {Discrete & Computational Geometry}, number = {1}, pages = {59 -- 77}, publisher = {Springer}, title = {{Inclusion-exclusion formulas from independent complexes}}, doi = {10.1007/s00454-006-1274-7}, volume = {37}, year = {2007}, } @article{4152, abstract = {Gastrulation is a morphogenetic process that results in the formation of the embryonic germ layers. Here we detail the major cell movements that occur during zebrafish gastrulation: epiboly, internalization, and convergent extension. Although gastrulation is known to be regulated by signaling pathways such as the Wnt/planar cell polarity pathway, many questions remain about the underlying molecular and cellular mechanisms. Key factors that may play a role in gastrulation cell movements are cell adhesion and cytoskeletal rearrangement. In addition, some of the driving force for gastrulation may derive from tissue interactions such as those described between the enveloping layer and the yolk syncytial layer. Future exploration of gastrulation mechanisms relies on the development of sensitive and quantitative techniques to characterize embryonic germ-layer properties.}, author = {Rohde, Laurel and Heisenberg, Carl-Philipp J}, journal = {International Review of Cytology - A Survey of Cell Biology}, pages = {159 -- 192}, publisher = {Academic Press}, title = {{Zebrafish gastrulation: Cell movements, signals, and mechanisms}}, doi = {10.1016/S0074-7696(07)61004-3}, volume = {261}, year = {2007}, } @article{4182, abstract = {We are interested in the cellular and molecular mechanisms underlying tissue morphogenesis during zebrafish gastrulation. Both differential cell adhesion and contractility have been proposed to be key mechanisms by which tissues form and rearrange in development. To obtain insight into the potential roles of differential cell adhesion and contraction for germ layer morphogenesis during gastrulation, we are analyzing cell adhesion and contraction of germ layer progenitor cells using atomic force microscopy, primary tissue culture and transplantation assays. I will present and discuss data about the differential adhesiveness and contractility of germ layer progenitor cells in the context of germ layer formation during vertebrate gastrulation.}, author = {Krieg, Michael and Arboleda, Yohanna and Müller, Daniel and Heisenberg, Carl-Philipp J}, journal = {European Journal of Cell Biology}, number = {Supplement 1}, pages = {39 -- 39}, publisher = {Elsevier}, title = {{The role of cell adhesion and contractility for germ layer morphogenesis during zebrafish gastrulation}}, doi = {10.1016/j.ejcb.2007.02.002}, volume = {86}, year = {2007}, } @article{4225, abstract = {The discovery of the genetic code was one of the most important advances of modern biology. But there is more to a DNA code than protein sequence; DNA carries signals for splicing, localization, folding, and regulation that are often embedded within the protein-coding sequence. In this issue, Itzkovitz and Alon show that the specific 64-to-20 mapping found in the genetic code may have been optimized for permitting protein-coding regions to carry this extra information and suggest that this property may have evolved as a side benefit of selection to minimize the negative effects of frameshift errors.}, author = {Bollenbach, Mark Tobias and Vetsigian, Kalin and Kishony, Roy}, journal = {Genome Research}, number = {4}, pages = {401 -- 404}, publisher = {Cold Spring Harbor Laboratory Press}, title = {{Evolution and multilevel optimization of the genetic code}}, doi = {10.1101/gr.6144007}, volume = {17}, year = {2007}, } @article{4226, abstract = {In the developing fly wing, secreted morphogens such as Decapentaplegic (Dpp) and Wingless (Wg) form gradients of concentration providing positional information. Dpp forms a longer-range gradient than Wg. To understand how the range is controlled, we measured the four key kinetic parameters governing morphogen spreading: the production rate, the effective diffusion coefficient, the degradation rate, and the immobile fraction. The four parameters had different values for Dpp versus Wg. In addition, Dynamin-dependent endocytosis was required for spreading of Dpp, but not Wg. Thus, the cellular mechanisms of Dpp and Wingless spreading are different: Dpp spreading requires endocytic, intracellular trafficking.}, author = {Anna Kicheva and Pantazis, Periklis and Bollenbach, Tobias and Kalaidzidis, Yannis and Bittig, Thomas and Julicher, Frank and Gonzalez-Gaitan, Marcos}, journal = {Science}, number = {5811}, pages = {521 -- 525}, publisher = {American Association for the Advancement of Science}, title = {{Kinetics of morphogen gradient formation}}, doi = {10.1126/science.1135774}, volume = {315}, year = {2007}, } @inproceedings{4342, abstract = {Library 2.0 and user-generated content are two terms, which are closely connected. In the presentation, I will briefly define both terms. Two example projects where user- generated content and libraries interact will be presented. The cooperation of Wikipedia and the Personennamendatei, the German cooperative name authority files is the first. The second will be Wikisource where users provide transcribed source material. Another important area of user-generated content is social tagging where users index different resources. And if the users will do so much in the future, is there still a place for librarians? But in the future user and librarians become partners and the library will provide the platform: the library 2.0.}, author = {Danowski, Patrick}, location = {Durban, South Africa}, publisher = {IFLA}, title = {{Library 2.0 and User-Generated Content - What can the users do for us?}}, doi = {601}, year = {2007}, } @article{4343, author = {Patrick Danowski and Pfeifer,Barbara}, journal = {Bibliothek - Forschung Und Praxis}, number = {2}, pages = {149 -- 155}, publisher = {De Gruyter}, title = {{Wikipedia und Normdateien: Wege der Vernetzung am Beispiel der Kooperation mit der Personennamendatei}}, doi = {485}, volume = {31}, year = {2007}, } @article{4344, author = {Patrick Danowski and Heller,Lambert}, journal = {Bibliothek - Forschung Und Praxis}, number = {2007}, pages = {130 -- 136}, publisher = {De Gruyter}, title = {{Bibliothek 2.0 ? Wird alles anders?}}, doi = {45}, volume = {31}, year = {2007}, } @article{4353, abstract = {BACKGROUND: The invention of the Genome Sequence 20 DNA Sequencing System (454 parallel sequencing platform) has enabled the rapid and high-volume production of sequence data. Until now, however, individual emulsion PCR (emPCR) reactions and subsequent sequencing runs have been unable to combine template DNA from multiple individuals, as homologous sequences cannot be subsequently assigned to their original sources. METHODOLOGY: We use conventional PCR with 5'-nucleotide tagged primers to generate homologous DNA amplification products from multiple specimens, followed by sequencing through the high-throughput Genome Sequence 20 DNA Sequencing System (GS20, Roche/454 Life Sciences). Each DNA sequence is subsequently traced back to its individual source through 5'tag-analysis. CONCLUSIONS: We demonstrate that this new approach enables the assignment of virtually all the generated DNA sequences to the correct source once sequencing anomalies are accounted for (miss-assignment rate<0.4%). Therefore, the method enables accurate sequencing and assignment of homologous DNA sequences from multiple sources in single high-throughput GS20 run. We observe a bias in the distribution of the differently tagged primers that is dependent on the 5' nucleotide of the tag. In particular, primers 5' labelled with a cytosine are heavily overrepresented among the final sequences, while those 5' labelled with a thymine are strongly underrepresented. A weaker bias also exists with regards to the distribution of the sequences as sorted by the second nucleotide of the dinucleotide tags. As the results are based on a single GS20 run, the general applicability of the approach requires confirmation. However, our experiments demonstrate that 5'primer tagging is a useful method in which the sequencing power of the GS20 can be applied to PCR-based assays of multiple homologous PCR products. The new approach will be of value to a broad range of research areas, such as those of comparative genomics, complete mitochondrial analyses, population genetics, and phylogenetics.}, author = {Binladen, Jonas and Gilbert, M Thomas and Jonathan Bollback and Panitz, Frank and Bendixen, Christian and Nielsen, Rasmus and Willerslev, Eske}, journal = {PLoS One}, number = {2}, publisher = {Public Library of Science}, title = {{The use of coded PCR primers enables high-throughput sequencing of multiple homolog amplification products by 454 parallel sequencing}}, doi = {10.1371/journal.pone.0000197}, volume = {2}, year = {2007}, } @article{4356, abstract = {We used a comparative genomics approach to identify genes that are under positive selection in six strains of Escherichia coli and Shigella flexneri, including five strains that are human pathogens. We find that positive selection targets a wide range of different functions in the E. coli genome, including cell surface proteins such as beta barrel porins, presumably because of the involvement of these genes in evolutionary arms races with other bacteria, phages, and/or the host immune system. Structural mapping of positively selected sites on trans-membrane beta barrel porins reveals that the residues under positive selection occur almost exclusively in the extracellular region of the proteins that are enriched with sites known to be targets of phages, colicins, or the host immune system. More surprisingly, we also find a number of other categories of genes that show very strong evidence for positive selection, such as the enigmatic rhs elements and transposases. Based on structural evidence, we hypothesize that the selection acting on transposases is related to the genomic conflict between transposable elements and the host genome.}, author = {Petersen, Lise and Jonathan Bollback and Dimmic, Matt and Hubisz, Melissa and Nielsen, Rasmus}, journal = {Genome Research}, number = {9}, pages = {1336 -- 1343}, publisher = {Cold Spring Harbor Laboratory Press}, title = {{Genes under positive selection in Escherichia coli}}, doi = {10.1101/gr.6254707}, volume = {17}, year = {2007}, } @article{4355, abstract = {When a beneficial mutation is fixed in a population that lacks recombination, the genetic background linked to that mutation is fixed. As a result, beneficial mutations on different backgrounds experience competition, or "clonal interference," that can cause asexual populations to evolve more slowly than their sexual counterparts. Factors such as a large population size (N) and high mutation rates (mu) increase the number of competing beneficial mutations, and hence are expected to increase the intensity of clonal interference. However, recent theory suggests that, with very large values of Nmu, the severity of clonal interference may instead decline. The reason is that, with large Nmu, genomes including both beneficial mutations are rapidly created by recurrent mutation, obviating the need for recombination. Here, we analyze data from experimentally evolved asexual populations of a bacteriophage and find that, in these nonrecombining populations with very large Nmu, recurrent mutation does appear to ameliorate this cost of asexuality.}, author = {Jonathan Bollback and Huelsenbeck, John P}, journal = {Molecular Biology and Evolution}, number = {6}, pages = {1397 -- 1406}, publisher = {Oxford University Press}, title = {{Clonal interference is alleviated by high mutation rates in large populations}}, doi = {10.1093/molbev/msm056}, volume = {24}, year = {2007}, } @article{4354, abstract = {Homology search is one of the most ubiquitous bioinformatic tasks, yet it is unknown how effective the currently available tools are for identifying noncoding RNAs (ncRNAs). In this work, we use reliable ncRNA data sets to assess the effectiveness of methods such as BLAST, FASTA, HMMer, and Infernal. Surprisingly, the most popular homology search methods are often the least accurate. As a result, many studies have used inappropriate tools for their analyses. On the basis of our results, we suggest homology search strategies using the currently available tools and some directions for future development.}, author = {Freyhult, Eva K and Jonathan Bollback and Gardner, Paul P}, journal = {Genome Research}, number = {1}, pages = {117 -- 25}, publisher = {Cold Spring Harbor Laboratory Press}, title = {{Exploring genomic dark matter: a critical assessment of the performance of homology search methods on noncoding RNA}}, doi = {10.1101/gr.5890907}, volume = {17}, year = {2007}, } @inproceedings{4370, author = {Maler, Oded and Dejan Nickovic and Pnueli,Amir}, pages = {95 -- 107}, publisher = {Springer}, title = {{On synthesizing controllers from bounded-response properties}}, doi = {1568}, year = {2007}, } @inproceedings{4368, author = {Dejan Nickovic and Maler, Oded}, pages = {304 -- 319}, publisher = {Springer}, title = {{AMT: a property-based monitoring tool for analog systems}}, doi = {1567}, year = {2007}, } @article{3022, abstract = {Endocytosis is an essential process by which eukaryotic cells internalize exogenous material or regulate signaling at the cell surface [1]. Different endocytic pathways are well established in yeast and animals; prominent among them is clathrin-dependent endocytosis [2, 3]. In plants, endocytosis is poorly defined, and no molecular mechanism for cargo internalization has been demonstrated so far [4, 5], although the internalization of receptor-ligand complexes at the plant plasma membrane has recently been shown [6]. Here we demonstrate by means of a green-to-red photoconvertible fluorescent reporter, EosFP [7], the constitutive endocytosis of PIN auxin efflux carriers [8] and their recycling to the plasma membrane. Using a plant clathrin-specific antibody, we show the presence of clathrin at different stages of coated-vesicle formation at the plasma membrane in Arabidopsis. Genetic interference with clathrin function inhibits PIN internalization and endocytosis in general. Furthermore, pharmacological interference with cargo recruitment into the clathrin pathway blocks internalization of PINs and other plasma-membrane proteins. Our data demonstrate that clathrin-dependent endocytosis is operational in plants and constitutes the predominant pathway for the internalization of numerous plasma-membrane-resident proteins including PIN auxin efflux carriers.}, author = {Dhonukshe, Pankaj and Aniento, Fernando and Hwang, Inhwan and Robinson, David G and Mravec, Jozef and Stierhof, York-Dieter and Jirí Friml}, journal = {Current Biology}, number = {6}, pages = {520 -- 527}, publisher = {Cell Press}, title = {{Clathrin-mediated constitutive endocytosis of PIN auxin efflux carriers in Arabidopsis}}, doi = {10.1016/j.cub.2007.01.052}, volume = {17}, year = {2007}, } @article{3027, abstract = {Polar transport of the phytohormone auxin controls numerous growth responses in plants. Molecular characterization of auxin transport in Arabidopsis thaliana has provided important insights into the mechanisms underlying the regulation of auxin distribution. In particular, the control of subcellular localization and expression of PIN-type auxin efflux components appears to be fundamental for orchestrated distribution of the growth regulator throughout the entire plant body. Here we describe the identification of two Arabidopsis loci, MOP2 and MOP3 (for MODULATOR OF PIN), that are involved in control of the steady-state levels of PIN protein. Mutations in both loci result in defects in auxin distribution and polar auxin transport, and cause phenotypes consistent with a reduction of PIN protein levels. Genetic interaction between PIN2 and both MOP loci is suggestive of functional cross-talk, which is further substantiated by findings demonstrating that ectopic PIN up-regulation is compensated in the mop background. Thus, in addition to pathways that control PIN localization and transcription, MOP2 and MOP3 appear to be involved in fine-tuning of auxin distribution via post-transcriptional regulation of PIN expression.}, author = {Malenica, Nenad and Abas, Lindy and Benjamins, René and Kitakura, Saeko and Sigmund, Harald F and Jun, Kim S and Hauser, Marie-Theres and Jirí Friml and Luschnig, Christian}, journal = {Plant Journal}, number = {4}, pages = {537 -- 550}, publisher = {Wiley-Blackwell}, title = {{MODULATOR of PIN genes control steady state levels of Arabidopsis PIN proteins}}, doi = {10.1111/j.1365-313X.2007.03158.x}, volume = {51}, year = {2007}, } @article{3144, abstract = {Accumulation of specific proteins at synaptic structures is essential for synapse assembly and function, but mechanisms regulating local protein enrichment remain poorly understood. At the neuromuscular junction (NMJ), subsynaptic nuclei underlie motor axon terminals within extrafusal muscle fibers and are transcriptionally distinct from neighboring nuclei. In this study, we show that expression of the ETS transcription factor Erm is highly concentrated at subsynaptic nuclei, and its mutation in mice leads to severe downregulation of many genes with normally enriched subsynaptic expression. Erm mutant mice display an expansion of the muscle central domain in which acetylcholine receptor (AChR) clusters accumulate, show gradual fragmentation of AChR clusters, and exhibit symptoms of muscle weakness mimicking congenital myasthenic syndrome (CMS). Together, our findings define Erm as an upstream regulator of a transcriptional program selective to subsynaptic nuclei at the NMJ and underscore the importance of transcriptional control of local synaptic protein accumulation.}, author = {Simon Hippenmeyer and Huber, Roland M and Ladle, David R and Murphy, Kenneth and Arber, Silvia}, journal = {Neuron}, number = {5}, pages = {726 -- 740}, publisher = {Elsevier}, title = {{ETS transcription factor Erm controls subsynaptic gene expression in skeletal muscles}}, doi = {10.1016/j.neuron.2007.07.028}, volume = {55}, year = {2007}, } @inproceedings{3223, abstract = {“Hash then encrypt” is an approach to message authentication, where first the message is hashed down using an ε-universal hash function, and then the resulting k-bit value is encrypted, say with a block-cipher. The security of this scheme is proportional to εq2, where q is the number of MACs the adversary can request. As ε is at least 2−k, the best one can hope for is O(q2/2k) security. Unfortunately, such small ε is not achieved by simple hash functions used in practice, such as the polynomial evaluation or the Merkle-Damg ̊ard construction, where ε grows with the message length L. The main insight of this work comes from the fact that, by using ran- domized message preprocessing via a short random salt p (which must then be sent as part of the authentication tag), we can use the “hash then encrypt” paradigm with suboptimal “practical” ε-universal hash func- tions, and still improve its exact security to optimal O(q2/2k). Specif- ically, by using at most an O(logL)-bit salt p, one can always regain the optimal exact security O(q2/2k), even in situations where ε grows polynomially with L. We also give very simple preprocessing maps for popular “suboptimal” hash functions, namely polynomial evaluation and the Merkle-Damg ̊ard construction. Our results come from a general extension of the classical Carter- Wegman paradigm, which we believe is of independent interest. On a high level, it shows that public randomization allows one to use the potentially much smaller “average-case” collision probability in place of the “worst-case” collision probability ε.}, author = {Dodis, Yevgeniy and Krzysztof Pietrzak}, pages = {414 -- 433}, publisher = {Springer}, title = {{Improving the security of MACs via randomized message preprocessing}}, doi = {10.1007/978-3-540-74619-5_26}, volume = {4593}, year = {2007}, } @inproceedings{3222, abstract = {Parallel repetition is well known to reduce the error probability at an exponential rate for single- and multi-prover interactive proofs. Bellare, Impagliazzo and Naor (1997) show that this is also true for protocols where the soundness only holds against computationally bounded provers (e.g. interactive arguments) if the protocol has at most three rounds. On the other hand, for four rounds they give a protocol where this is no longer the case: the error probability does not decrease below some constant even if the protocol is repeated a polynomial number of times. Unfortunately, this protocol is not very convincing as the communication complexity of each instance of the protocol grows linearly with the number of repetitions, and for such protocols the error does not even decrease for some types of interactive proofs. Noticing this, Bellare et al. construct (a quite artificial) oracle relative to which a four round protocol exists whose communication complexity does not depend on the number of parallel repetitions. This shows that there is no “black-box” error reduction theorem for four round protocols. In this paper we give the first computationally sound protocol where k-fold parallel repetition does not decrease the error probability below some constant for any polynomial k (and where the communication complexity does not depend on k). The protocol has eight rounds and uses the universal arguments of Barak and Goldreich (2001). We also give another four round protocol relative to an oracle, unlike the artificial oracle of Bellare et al., we just need a generic group. This group can then potentially be instantiated with some real group satisfying some well defined hardness assumptions (we do not know of any candidate for such a group at the moment).}, author = {Krzysztof Pietrzak and Wikström, Douglas}, pages = {86 -- 102}, publisher = {Springer}, title = {{Parallel repetition of computationally sound protocols revisited}}, doi = {10.1007/978-3-540-70936-7_5}, volume = {4392}, year = {2007}, } @inproceedings{3220, abstract = {We introduce a new primitive called intrusion-resilient secret sharing (IRSS), whose security proof exploits the fact that there exist functions which can be efficiently computed interactively using low communication complexity in k, but not in k-1 rounds. IRSS is a means of sharing a secret message amongst a set of players which comes with a very strong security guarantee. The shares in an IRSS are made artificially large so that it is hard to retrieve them completely, and the reconstruction procedure is interactive requiring the players to exchange k short messages. The adversaries considered can attack the scheme in rounds, where in each round the adversary chooses some player to corrupt and some function, and retrieves the output of that function applied to the share of the corrupted player. This model captures for example computers connected to a network which can occasionally he infected by malicious software like viruses, which can compute any function on the infected machine, but cannot sent out a huge amount of data. Using methods from the bounded-retrieval model, we construct an IRSS scheme which is secure against any computationally unbounded adversary as long as the total amount of information retrieved by the adversary is somewhat less than the length of the shares, and the adversary makes at most k-1 corruption rounds (as described above, where k rounds are necessary for reconstruction). We extend our basic scheme in several ways in order to allow the shares sent by the dealer to be short (the players then blow them up locally) and to handle even stronger adversaries who can learn some of the shares completely. As mentioned, there is an obvious connection between IRSS schemes and the fact that there exist functions with an exponential gap in their communication complexity for k and k-1 rounds. Our scheme implies such a separation which is in several aspects stronger than the previously known ones.}, author = {Dziembowski, Stefan and Krzysztof Pietrzak}, pages = {227 -- 237}, publisher = {IEEE}, title = {{Intrusion resilient secret sharing}}, doi = {10.1109/FOCS.2007.63}, year = {2007}, } @inproceedings{3219, abstract = {Many aspects of cryptographic security proofs can be seen as the proof that a certain system (e.g. a block cipher) is indistinguishable from an ideal system (e.g. a random permutation), for different types of distinguishers. This paper presents a new generic approach to proving upper bounds on the information-theoretic distinguishing advantage (from an ideal system) for a combined system, assuming upper bounds of certain types for the component systems. For a general type of combination operation of systems, including the XOR of functions or the cascade of permutations, we prove two amplification theorems. The first is a product theorem, in the spirit of XOR-lemmas: The distinguishing advantage of the combination of two systems is at most twice the product of the individual distinguishing advantages. This bound is optimal. The second theorem states that the combination of systems is secure against some strong class of distinguishers, assuming only that the components are secure against some weaker class of distinguishers. A key technical tool of the paper is the proof of a tight two-way correspondence, previously only known to hold in one direction, between the distinguishing advantage of two systems and the probability of winning an appropriately defined game. © International Association for Cryptologic Research 2007.}, author = {Maurer, Ueli M and Krzysztof Pietrzak and Renner, Renato}, pages = {130 -- 149}, publisher = {Springer}, title = {{Indistinguishability amplification}}, doi = {10.1007/978-3-540-74143-5_8}, volume = {4622}, year = {2007}, } @inproceedings{3221, abstract = {We investigate a general class of (black-box) constructions for range extension of weak pseudorandom functions: a construction based on m independent functions F 1,...,F m is given by a set of strings over {1,...,m}*, where for example {〈2〉, 〈1,2〉} corresponds to the function X ↦[F 2(X),F 2(F 1(X))]. All efficient constructions for range expansion of weak pseudorandom functions that we are aware of are of this form. We completely classify such constructions as good, bad or ugly, where the good constructions are those whose security can be proven via a black-box reduction, the bad constructions are those whose insecurity can be proven via a black-box reduction, and the ugly constructions are those which are neither good nor bad. Our classification shows that the range expansion from [10] is optimal, in the sense that it achieves the best possible expansion (2 m  − 1 when using m keys). Along the way we show that for weak quasirandom functions (i.e. in the information theoretic setting), all constructions which are not bad – in particular all the ugly ones – are secure.}, author = {Krzysztof Pietrzak and Sjödin, Johan}, pages = {517 -- 533}, publisher = {Springer}, title = {{Range extension for weak PRFs the good the bad and the ugly}}, doi = {10.1007/978-3-540-72540-4_30}, volume = {4515}, year = {2007}, } @article{3436, abstract = {he potential for di? erences between genetic paternity and paternity inferred from behavioral observation has long been recognized. These di? erences are associated with the challenge for females of seeking both genetic and material bene? ts; this challenge is less severe in species with polygynous, non-resource-based mating systems (such as leks) than in those with resource-based systems. We pres- ent the ? rst study of paternity patt erns in a non-resource-based species that does not form true leks. We compared paternity inferred from observed mating behavior to genetically assigned paternity in the Satin Bowerbird (Ptilonorhynchus violaceus) using eight microsatellite markers. Mating behavior was observed and recorded via automated video-cameras positioned at all bowers (29?34 bowers each year) in the study site throughout each mating season. We obtained blood samples and identi- ? ed mothers for 11 chicks in 9 nests. For all chicks, the most likely genetic father had been observed to mate with the mother in the year the chick was sampled. All most likely genetic fathers were assigned with high con? dence and all were bower- holding males. These results demonstrate that genetic paternity can be inferred from observed mating behavior with reasonable con? dence in Satin Bowerbirds. Observed male mating-success is therefore a reliable predictor of reproductive success, and this suggests that high skew in observed male mating-success translates directly to high skew in reproductive success. }, author = {Reynolds, Sheila M and Dryer, Katie and Jonathan Bollback and Uy, J Albert and Patricelli, Gail L and Robson, Timothy and Borgia, Gerald and Braun, Michael J}, journal = {The Auk}, number = {3}, pages = {857 -- 867}, publisher = {University of California Press}, title = {{Behavioral paternity predicts genetic paternity in satin bowerbirds, a species with a non-resource-based mating system}}, doi = {10.1642/0004-8038(2007)124[857:BPPGPI]2.0.CO;2}, volume = {124}, year = {2007}, } @inbook{3432, abstract = {Evolution has left its signature on the molecules and morphology of living organisms. Ancestral reconstruction offers an excellent tool for understanding the process of evolution using comparative information. Methods for ancestral reconstruction have generally focused on reconstructing the ancestral states at the internal nodes of a phylogeny. Often, we are not interested in particular nodes of the phylogeny but the whole history of a character. This chapter focuses on a Bayesian method for estimating these histories, or mutational paths, on phylogenies. Mutational path methods differ most notably from other approaches in their ability to estimate not only the ancestral states at the internal nodes of a phylogeny, but also the order and timing of mutational changes across the phylogeny. The chapter provides a concise introduction to the statistical tools needed for sampling mutational paths on a phylogeny.}, author = {Jonathan Bollback and Gardner, Paul P and Nielsen, Rasmus}, booktitle = {Ancestral Sequence Reconstruction}, editor = {Liberles, David A}, pages = {69 -- 79}, publisher = {Oxford University Press}, title = {{Estimating the history of mutations on a phylogeny}}, doi = {10.1093/acprof:oso/9780199299188.003.0006}, year = {2007}, } @article{3450, author = {Peter Jonas and Buzsáki, György}, journal = {Scholarpedia}, publisher = {Scholarpedia}, title = {{Neural inhibition}}, doi = {10.4249/scholarpedia.3286}, volume = {2}, year = {2007}, } @inproceedings{3561, abstract = {The main result of this paper is an extension of de Silva's Weak Delaunay Theorem to smoothly embedded curves and surfaces in Euclidean space. Assuming a sufficiently fine sampling, we prove that i + 1 points in the sample span an i-simplex in the restricted Delaunay triangulation iff every subset of the i + 1 points has a weak witness.}, author = {Attali, Dominique and Herbert Edelsbrunner and Mileyko, Yuriy}, pages = {143 -- 150}, publisher = {ACM}, title = {{Weak witnesses for Delaunay triangulations of submanifolds}}, doi = {10.1145/1236246.1236267}, year = {2007}, } @inproceedings{3681, abstract = {The extraction of a parametric global motion from a motion field is a task with several applications in video processing. We present two probabilistic formulations of the problem and carry out optimization using the RAST algorithm, a geometric matching method novel to motion estimation in video. RAST uses an exhaustive and adaptive search of transformation space and thus gives – in contrast to local sampling optimization techniques used in the past – a globally optimal solution. Among other applications, our framework can thus be used as a source of ground truth for benchmarking motion estimation algorithms. Our main contributions are: first, the novel combination of a state-of-the-art MAP criterion for dominant motion estimation with a search procedure that guarantees global optimality. Second, experimental results that illustrate the superior performance of our approach on synthetic flow fields as well as real-world video streams. Third, a significant speedup of the search achieved by extending the model with an additional smoothness prior.}, author = {Ulges, Adrian and Christoph Lampert and Keysers,Daniel and Breuel,Thomas M}, pages = {204 -- 213}, publisher = {Springer}, title = {{Optimal dominant motion estimation using adaptive search of transformation space}}, doi = {10.1007/978-3-540-74936-3_21}, volume = {4713}, year = {2007}, } @book{3674, abstract = {Evolution permeates all of biology. But researchers in molecular and cellular biology, genetics, developmental biology, microbiology, and neuroscience have only recently begun to think seriously in terms of evolution. The chief reasons for this shift are the growing list of organisms with sequenced genomes; the increasingly sophisticated ways of interpreting those sequences; and the ever more powerful experimental techniques (and wider range of model organisms) with which to ask questions about evolution as well as mechanism. Evolution serves as a primary text for undergraduate and graduate courses in evolution. It is also a text working scientists can use to educate themselves on how evolution affects their fields. It differs from currently available alternatives in containing more molecular biology than is traditionally the case. But this is not at the expense of traditional evolutionary theory. Indeed, a glance at the Table of Contents and the authors' interests reveals the range of material covered in this book. The authors are world-renowned in population genetics, bacterial genomics, paleontology, human genetics, and developmental biology. The integration of molecular biology and evolutionary biology reflects the current direction of much research among evolutionary scientists.}, author = {Barton, Nicholas H and Briggs, Derek and Eisen, Jonathan and Goldstein, David and Patel, Nipam}, isbn = {978-087969684-9}, pages = {XIV, 833}, publisher = {Cold Spring Harbor Laboratory Press}, title = {{Evolution}}, year = {2007}, } @article{3727, abstract = {Since its invention in the 1990s single-molecule force spectroscopy has been increasingly applied to study protein (un-)folding, cell adhesion, and ligand–receptor interactions. In most force spectroscopy studies, the cantilever of an atomic force microscope (AFM) is separated from a surface at a constant velocity, thus applying an increasing force to folded bio-molecules or bio-molecular bonds. Recently, Fernandez and co-workers introduced the so-called force-clamp technique. Single proteins were subjected to a defined constant force allowing their life times and life time distributions to be directly measured. Up to now, the force-clamping was performed by analogue PID controllers, which require complex additional hardware and might make it difficult to combine the force-feedback with other modes such as constant velocity. These points may be limiting the applicability and versatility of this technique. Here we present a simple, fast, and all-digital (software-based) PID controller that yields response times of a few milliseconds in combination with a commercial AFM. We demonstrate the performance of our feedback loop by force-clamp unfolding of single Ig27 domains of titin and the membrane proteins bacteriorhodopsin (BR) and the sodium/proton antiporter NhaA.}, author = {Bippes, Christian A and Harald Janovjak and Kedrov, Alexej and Mueller, Daniel J}, journal = {Nanotechnology}, number = {4}, publisher = {IOP Publishing Ltd.}, title = {{Digital force-feedback for protein unfolding experiments using atomic force microscopy}}, doi = {10.1088/0957-4484/18/4/044022}, volume = {18}, year = {2007}, } @article{3723, abstract = {The folding and function of proteins is guided by their multidimensional energy landscapes. Local corrugations on rugged energy surfaces determine the dynamics of functionally related conformational changes and molecular flexibilities. By varying the temperature during the force-induced unfolding of the membrane protein bacteriorhodopsin, we directly determined the energy roughness of individual transmembrane α-helices. All helices have rugged energy surfaces with an overall roughness scale of 4−6 kBT, in line with the vital roles of transmembrane helices as functional and structural building blocks. Interestingly, the mechanical unfolding of misfolded membrane proteins in vivo is likely to occur on similarly energy rugged surfaces, which may also provide an energetic framework for small vertical motions of functionally relevant helices. Finally, our results also indicate that transmembrane protein structures can have rough energy surfaces despite their highly restricted conformational spaces in confining lipid bilayer environments. }, author = {Harald Janovjak and Knaus, Helene and Mueller, Daniel J}, journal = {Journal of the American Chemical Society}, number = {2}, pages = {246 -- 247}, publisher = {ACS}, title = {{Transmembrane helices have rough energy surfaces}}, doi = {10.1021/ja065684a}, volume = {129}, year = {2007}, } @unpublished{3742, abstract = {Recent work has shown that probabilistic models based on pairwise interactions-in the simplest case, the Ising model-provide surprisingly accurate descriptions of experiments on real biological networks ranging from neurons to genes. Finding these models requires us to solve an inverse problem: given experimentally measured expectation values, what are the parameters of the underlying Hamiltonian? This problem sits at the intersection of statistical physics and machine learning, and we suggest that more efficient solutions are possible by merging ideas from the two fields. We use a combination of recent coordinate descent algorithms with an adaptation of the histogram Monte Carlo method, and implement these techniques to take advantage of the sparseness found in data on real neurons. The resulting algorithm learns the parameters of an Ising model describing a network of forty neurons within a few minutes. This opens the possibility of analyzing much larger data sets now emerging, and thus testing hypotheses about the collective behaviors of these networks.}, author = {Broderick,Tamara and Dudik,Miroslav and Gasper Tkacik and Schapire,Robert E and Bialek, William S}, booktitle = {ArXiv}, publisher = {ArXiv}, title = {{Faster solutions of the inverse pairwise Ising problem}}, volume = {q-bio.QM}, year = {2007}, } @article{3821, abstract = {Although dendritic signal processing has been extensively investigated in hippocampal pyramidal cells, only little is known about dendritic integration of synaptic potentials in dentate gyrus granule cells, the first stage in the hippocampal trisynaptic circuit. Here we combined dual whole-cell patch-clamp recordings with high-resolution two-photon microscopy to obtain detailed passive cable models of hippocampal granule cells from adult mice. Passive cable properties were determined by direct fitting of the compartmental model to the experimentally measured voltage responses to short and long current pulses. The data are best fit by a cable model with homogenously distributed parameters, including an average specific membrane resistance (R(m)) of 38.0 kohms cm2, a membrane capacitance (C(m)) of 1.0 microF cm(-2), and an intracellular resistivity (R(i)) of 194 ohms cm. Computational analysis shows that signal propagation from somata into dendrites is more efficient in granule cells compared with CA1 pyramidal cells for both steady-state and sinusoidal voltage waveforms up to the gamma frequency range (f50% of 74 Hz). Similarly, distal synaptic inputs from entorhinal fibers can efficiently depolarize the somatic membrane of granule cells. Furthermore, the time course of distal dendritic synaptic potentials is remarkably fast, and temporal summation is restricted to a narrow time window in the range of approximately 10 ms attributable to the rapid dendritic charge redistribution during transient voltage signals. Therefore, the structure of the granule cell dendritic tree may be critically important for precise dendritic signal processing and coincidence detection during hippocampus-dependent memory formation and retrieval.}, author = {Schmidt-Hieber, Christoph and Peter Jonas and Bischofberger, Josef}, journal = {Journal of Neuroscience}, number = {31}, pages = {8430 -- 8441}, publisher = {Society for Neuroscience}, title = {{Subthreshold dendritic signal processing and coincidence detection in dentate gyrus granule cells}}, doi = {10.1523/JNEUROSCI.1787-07.2007}, volume = {27}, year = {2007}, } @article{3820, abstract = {Synapses are the key elements for signal processing and plasticity in the brain. To determine the structural factors underlying the unique functional properties of the hippocampal mossy fiber synapse, the complete quantitative geometry was investigated, using electron microscopy of serial ultrathin sections followed by computer-assisted three-dimensional reconstruction. In particular, parameters relevant for transmitter release and synaptic plasticity were examined. Two membrane specializations were found: active zones (AZs), transmitter release sites, and puncta adherentia, putative adhesion complexes. Individual boutons had, on average, 25 AZs (range, 7-45) that varied in shape and size (mean, 0.1 microm2; range, 0.07-0.17 microm2). The mean distance between individual AZs was 0.45 microm. Mossy fiber boutons and their target structures were mostly ensheathed by astrocytes, but fine glial processes never reached the active zones. Two structural factors are likely to promote synaptic cross talk: the short distance between AZs and the absence of fine glial processes at AZs. Thus, synaptic cross talk may contribute to the efficacy of hippocampal mossy fiber synapses. On average, a bouton contained 20,400 synaptic vesicles; approximately 900 vesicles were located within 60 nm from the active zone, approximately 4400 between 60 and 200 nm, and the remaining beyond 200 nm, suggesting large readily releasable, recycling, and reserve pools. The organization of the different pools may be a key structural correlate of presynaptic plasticity at this synapse. Thus, the mossy fiber bouton differs fundamentally in structure and function from the calyx of Held and other central synapses.}, author = {Rollenhagen, Astrid and Satzler, Kurt and Rodriguez, E Patricia and Peter Jonas and Frotscher, Michael and Lubke, Joachim H}, journal = {Journal of Neuroscience}, number = {39}, pages = {10434 -- 44}, publisher = {Society for Neuroscience}, title = {{Structural determinants of transmission at large hippocampal mossy fiber synapses}}, doi = {10.1523/JNEUROSCI.1946-07.2007}, volume = {27}, year = {2007}, } @article{3819, abstract = {Voltage-gated Ca2+ channels in presynaptic terminals initiate the Ca2+ inflow necessary for transmitter release. At a variety of synapses, multiple Ca2+ channel subtypes are involved in synaptic transmission and plasticity. However, it is unknown whether presynaptic Ca2+ channels differ in gating properties and whether they are differentially activated by action potentials or subthreshold voltage signals. We examined Ca2+ channels in hippocampal mossy fiber boutons (MFBs) by presynaptic recording, using the selective blockers omega-agatoxin IVa, omega-conotoxin GVIa, and SNX-482 to separate P/Q-, N-, and R-type components. Nonstationary fluctuation analysis combined with blocker application revealed a single MFB contained on average approximately 2000 channels, with 66% P/Q-, 26% N-, and 8% R-type channels. Whereas both P/Q-type and N-type Ca2+ channels showed high activation threshold and rapid activation and deactivation, R-type Ca2+ channels had a lower activation threshold and slower gating kinetics. To determine the efficacy of activation of different Ca2+ channel subtypes by physiologically relevant voltage waveforms, a six-state gating model reproducing the experimental observations was developed. Action potentials activated P/Q-type Ca2+ channels with high efficacy, whereas N- and R-type channels were activated less efficiently. Action potential broadening selectively recruited N- and R-type channels, leading to an equalization of the efficacy of channel activation. In contrast, subthreshold presynaptic events activated R-type channels more efficiently than P/Q- or N-type channels. In conclusion, single MFBs coexpress multiple types of Ca2+ channels, which are activated differentially by subthreshold and suprathreshold presynaptic voltage signals.}, author = {Li, Liyi and Bischofberger, Josef and Peter Jonas}, journal = {Journal of Neuroscience}, number = {49}, pages = {13420 -- 9}, publisher = {Society for Neuroscience}, title = {{Differential gating and recruitment of P/Q-, N-, and R-type Ca(2+) channels in hippocampal mossy fiber boutons}}, doi = {10.1523/JNEUROSCI.1709-07.2007}, volume = {27}, year = {2007}, } @inproceedings{3883, abstract = {We consider games where the winning conditions are disjunctions (or dually, conjunctions) of parity conditions; we call them generalized parity games. These winning conditions, while omega-regular, arise naturally when considering fair simulation between parity automata, secure equilibria for parity conditions, and determinization of Rabin automata. We show that these games retain the computational complexity of Rabin and Streett conditions; i.e., they are NP-complete and co-NP-complete, respectively. The (co-) NP-hardness is proved for the special case of a conjunction/disjunction of two parity conditions, which is the case that arises in fair simulation and secure equilibria. However, considering these games as Rabin or Streett games is not optimal. We give an exposition of Zielonka's algorithm when specialized to this kind of games. The complexity of solving these games for k parity objectives with d priorities, n states, and m edges is O(n(2kd) (.) m) (.) (k(.)d)!/ d!(k), as compared to O(n(2kd .) m) - (k (.) d)! when these games are solved as Rabin/Streett games. We also extend the subexponential algorithm for solving parity games recently introduced by Jurdzinski, Paterson, and Zwick to generalized parity games. The resulting complexity of solving generalized parity games is n(O(root n)) (.) (k(.)d)!/d!(k). As a corollary we obtain an improved ald!k gorithm for Rabin and Streett games with d pairs, with time complexity n(O(root n)) (.) d!.}, author = {Krishnendu Chatterjee and Thomas Henzinger and Piterman, Nir}, pages = {153 -- 167}, publisher = {Springer}, title = {{Generalized parity games}}, doi = {10.1007/978-3-540-71389-0_12}, volume = {4423}, year = {2007}, } @article{3882, abstract = {We study infinite stochastic games played by two players over a finite state space, with objectives specified by sets of infinite traces. The games are concurrent (players make moves simultaneously and independently), stochastic (the next state is determined by a probability distribution that depends on the current state and chosen moves of the players) and infinite (proceed for an infinite number of rounds). The analysis of concurrent stochastic games can be classified into: quantitative analysis, analyzing the optimum value of the game and epsilon-optimal strategies that ensure values within epsilon of the optimum value; and qualitative analysis, analyzing the set of states with optimum value 1 and epsilon-optimal strategies for the states with optimum value 1. We consider concurrent games with tail objectives, i.e., objectives that are independent of the finite-prefix of traces, and show that the class of tail objectives is strictly richer than that of the omega-regular objectives. We develop new proof techniques to extend several properties of concurrent games with omega-regular objectives to concurrent games with tail objectives. We prove the positive limit-one property for tail objectives. The positive limit-one property states that for all concurrent games if the optimum value for a player is positive for a tail objective Phi at some state, then there is a state where the optimum value is 1 for the player for the objective Phi. We also show that the optimum values of zero-sum (strictly conflicting objectives) games with tail objectives can be related to equilibrium values of nonzerosum (not strictly conflicting objectives) games with simpler reachability objectives. A consequence of our analysis presents a polynomial time reduction of the quantitative analysis of tail objectives to the qualitative analysis for the subclass of one-player stochastic games (Markov decision processes). }, author = {Krishnendu Chatterjee}, journal = {Theoretical Computer Science}, number = {1-3}, pages = {181 -- 198}, publisher = {Elsevier}, title = {{Concurrent games with tail objectives}}, doi = {10.1016/j.tcs.2007.07.047}, volume = {388}, year = {2007}, } @inproceedings{3884, abstract = {We introduce strategy logic, a logic that treats strategies in two-player games as explicit first-order objects. The explicit treatment of strategies allows us to specify properties of nonzero-sum games in a simple and natural way. We show that the one-alternation fragment of strategy logic is strong enough to express the existence of Nash equilibria and secure equilibria, and subsumes other logics that were introduced to reason about games, such as ATL, ATL*, and game logic. We show that strategy logic is decidable, by constructing tree automata that recognize sets of strategies. While for the general logic, our decision procedure is nonelementary, for the simple fragment that is used above we show that the complexity is polynomial in the size of the game graph and optimal in the size of the formula (ranging from polynomial to 2EXPTIME depending on the form of the formula).}, author = {Krishnendu Chatterjee and Thomas Henzinger and Piterman, Nir}, pages = {59 -- 73}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Strategy logic}}, doi = {10.1007/978-3-540-74407-8_5}, volume = {4703}, year = {2007}, } @inproceedings{3881, abstract = {We present Qualitative Randomized CTL (QRCTL), a qualitative version of pCTL, for specifying properties of Markov Decision Processes (MDPs). QRCTL formulas can express the fact that certain temporal properties hold with probability 0 or 1, but they do not distinguish other probabilities values. We present a symbolic, polynomial time model-checking algorithm for QRCTL on MDPs. Then, we study the equivalence relation induced by QRCTL, called qualitative equivalence. We show that for finite alternating MDPs, where nondeterministic and probabilistic choice occur in different states, qualitative equivalence coincides with alternating bisimulation, and can thus be computed via efficient partition-refinement algorithms. Surprisingly, the result does not hold for non-alternating MDPs. Indeed, we show that no local partition refinement algorithm can compute qualitative equivalence on non-alternating MDPs. Finally, we consider QRCTL*, that is the “star extension” of QRCTL. We show that QRCTL and QRCTL* induce the same qualitative equivalence on alternating MDPs, while on non-alternating MDPs, the equivalence, arising from QRCTL* can be strictly finer We also provide a full characterization of the relation between qualitative equivalence, bisimulation, and alternating bisimulation, according to whether the MDPs are finite, and to whether their transition relations are finite-branching.}, author = {de Alfaro, Luca and Krishnendu Chatterjee and Faella, Marco and Legay, Axel}, pages = {237 -- 248}, publisher = {IEEE}, title = {{Qualitative logics and equivalences for probabilistic systems}}, doi = {10.1109/QEST.2007.15}, year = {2007}, } @inproceedings{3887, abstract = {We consider Markov decision processes (MDPs) with multiple long-run average objectives. Such MDPs occur in design problems where one wishes to simultaneously optimize several criteria, for example, latency and power. The possible trade-offs between the different objectives are characterized by the Pareto curve. We show that every Pareto optimal point can be epsilon-approximated by a memoryless strategy, for all epsilon > 0. In contrast to the single-objective case, the memoryless strategy may require randomization. We show that the Pareto curve can be approximated (a) in polynomial time in the size of the MDP for irreducible MDPs; and (b) in polynomial space in the size of the MDP for all MDPs. Additionally, we study the problem if a given value vector is realizable by any strategy, and show that it can be decided in polynomial time for irreducible MDPs and in NP for all MDPs. These results provide algorithms for design exploration in MDP models with multiple long-run average objectives.}, author = {Krishnendu Chatterjee}, pages = {473 -- 484}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Markov decision processes with multiple long-run average objectives}}, doi = {10.1007/978-3-540-77050-3_39}, volume = {4855}, year = {2007}, } @inproceedings{3886, 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); and the quantitative problem asks for the maximal probability of winning (optimal winning) from each state. We consider ω-regular winning conditions formalized as Müller winning conditions. We show that both the qualitative and quantitative problem for stochastic Müller games are PSPACE-complete. We also consider two well-known sub-classes of Müller objectives, namely, upward-closed and union-closed objectives, and show that both the qualitative and quantitative problem for these sub-classes are coNP-complete.}, author = {Krishnendu Chatterjee}, pages = {436 -- 448}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Stochastic Müller games are PSPACE-complete}}, doi = {10.1007/978-3-540-77050-3_36}, volume = {4855}, year = {2007}, } @inproceedings{3885, 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); and the quantitative problem asks for the maximal probability of winning (optimal winning) from each state. We consider ω-regular winning conditions formalized as Müller winning conditions. We present optimal memory bounds for pure almost-sure winning and optimal winning strategies in stochastic graph games with Müller winning conditions. We also present improved memory bounds for randomized almost-sure winning and optimal strategies.}, author = {Krishnendu Chatterjee}, pages = {138 -- 152}, publisher = {Springer}, title = {{Optimal strategy synthesis in stochastic Müller games}}, doi = {10.1007/978-3-540-71389-0_11}, volume = {4423}, year = {2007}, } @article{3938, abstract = {RhoH is a small GTPase expressed only in the hematopoietic system. With the use of mice with targeted disruption of the RhoH gene, we demonstrated that RhoH is crucial for thymocyte maturation during DN3 to DN4 transition and during positive selection. Furthermore, the differentiation and expansion of DN3 and DN4 thymocytes in vitro were severely impaired. These defects corresponded to defective TCR signaling. Although RhoH is not required for TCR-induced activation of ZAP70 and ZAP70-mediated activation of p38, it is crucial for the tyrosine phosphorylation of LAT, PLCgamma1, and Vav1 and for the activation of Erk and calcium influx. These data suggest that RhoH is important for pre-TCR and TCR signaling because it allows the efficient interaction of ZAP70 with the LAT signalosome, thus regulating thymocyte development.}, author = {Dorn, Tatjana and Kuhn, Ursula and Bungartz, Gerd and Stiller, Sebastian and Bauer, Martina and Ellwart, Joachim and Peters, Thorsten and Scharffetter-Kochanek, Karin and Semmrich, Monika and Laschinger, Melanie and Holzmann, Bernhard and Klinkert, Wolfgang E and Straten, Per Thor and Køllgaard, Tania and Michael Sixt and Brakebusch, Cord}, journal = {Blood}, number = {6}, pages = {2346 -- 2355}, publisher = {American Society of Hematology}, title = {{RhoH is important for positive thymocyte selection and T-cell receptor signaling}}, doi = {10.1182/blood-2006-04-019034}, volume = {109}, year = {2007}, } @article{3937, abstract = {Lymphocyte motility in lymph nodes is regulated by chemokines, but the contribution of integrins to this motility remains obscure. Here we examined lymphocyte migration over CCR7-binding chemokines that 'decorate' lymph node stroma. In a shear-free environment, surface-bound lymph node chemokines but not their soluble counterparts promoted robust and sustained T lymphocyte motility. The chemokine CCL21 induced compartmentalized clustering of the integrins LFA-1 and VLA-4 in motile lymphocytes, but both integrins remained nonadhesive to ligands on lymphocytes, dendritic cells and stroma. The application of shear stress to lymphocytes interacting with CCL21 and integrin ligands promoted robust integrin-mediated adhesion. Thus, lymph node chemokines that promote motility and strongly activate lymphocyte integrins under shear forces fail to stimulate stable integrin adhesiveness in extravascular shear-free environments.}, author = {Woolf, Eilon and Grigorova, Irina and Sagiv, Adi and Grabovsky, Valentin and Feigelson, Sara W and Shulman, Ziv and Hartmann, Tanja and Michael Sixt and Cyster, Jason G and Alon, Ronen}, journal = {Nature Immunology}, number = {10}, pages = {1076 -- 1085}, publisher = {Nature Publishing Group}, title = {{Lymph node chemokines promote sustained T lymphocyte motility without triggering stable integrin adhesiveness in the absence of shear forces}}, doi = {10.1038/ni1499}, volume = {8}, year = {2007}, } @article{3973, abstract = {In this paper we bound the difference between the total mean curvatures of two closed surfaces in R-3 in terms of their total absolute curvatures and the Frechet distance between the volumes they enclose. The proof relies on a combination of methods from algebraic topology and integral geometry. We also bound the difference between the lengths of two curves using the same methods.}, author = {Cohen-Steiner, David and Herbert Edelsbrunner}, journal = {Foundations of Computational Mathematics}, number = {4}, pages = {391 -- 404}, publisher = {Springer}, title = {{Inequalities for the curvature of curves and surfaces}}, doi = {10.1007/s10208-005-0200-3}, volume = {7}, year = {2007}, } @article{3972, abstract = {The persistence diagram of a real-valued function on a topological space is a multiset of points in the extended plane. We prove that under mild assumptions on the function, the persistence diagram is stable: small changes in the function imply only small changes in the diagram. We apply this result to estimating the homology of sets in a metric space and to comparing and classifying geometric shapes.}, author = {Cohen-Steiner, David and Herbert Edelsbrunner and Harer, John}, journal = {Discrete & Computational Geometry}, number = {1}, pages = {103 -- 120}, publisher = {Springer}, title = {{Stability of persistence diagrams}}, doi = {10.1007/s00454-006-1276-5}, volume = {37}, year = {2007}, } @article{4205, abstract = {Background: Bone morphogenetic proteins (Bmps) are required for the specification of ventrolateral cell fates during embryonic dorsoventral patterning and for proper convergence and extension gastrulation movements, but the mechanisms underlying the latter role remained elusive. Results: Via bead implantations, we show that the Bmp gradient determines the direction of lateral mesodermal cell migration during dorsal convergence in the zebrafish gastrula. This effect is independent of its role during dorsoventral patterning and of noncanonical Wnt signaling. However, it requires Bmp signal transduction through AIk8 and Smad5 to negatively regulate Ca2+/Cadherin-dependent cell-cell adhesiveness. In vivo, converging mesodermal cells form lamellipodia that attach to adjacent cells. Bmp signaling diminishes the Cadherin-dependent stability of such contact points, thereby abrogating subsequent cell displacement during lamellipodial retraction. Conclusions: We propose that the ventral-to-dorsal Bmp gradient has an instructive role to establish a reverse gradient of cell-cell adhesiveness, thereby defining different migratory zones and directing lamellipodia-driven cell migrations during dorsal convergence in lateral regions of the zebrafish gastrula.}, author = {Von Der Hardt, Sophia and Bakkers, Jeroen and Inbal, Adi and Carvalho, Lara and Solnica Krezel, Lilianna and Heisenberg, Carl-Philipp J and Hammerschmidt, Matthias}, journal = {Current Biology}, number = {6}, pages = {475 -- 487}, publisher = {Cell Press}, title = {{The Bmp gradient of the zebrafish gastrula guides migrating lateral cells by regulating cell-cell adhesion}}, doi = {10.1016/j.cub.2007.02.013}, volume = {17}, year = {2007}, } @article{4234, abstract = {We study a generalised model of population growth in which the state variable is population growth rate instead of population size. Stochastic parametric perturbations, modelling phenotypic variability, lead to a Langevin system with two sources of multiplicative noise. The stationary probability distributions have two characteristic power-law scales. Numerical simulations show that noise suppresses the explosion of the growth rate which occurs in the deterministic counterpart. Instead, in different parameter regimes populations will grow with "anomalous" stochastic rates and (i) stabilise at "random carrying capacities", or (ii) go extinct in random times. Using logistic fits to reconstruct the simulated data, we find that even highly significant estimations do not recover or reflect information about the deterministic part of the process. Therefore, the logistic interpretation is not biologically meaningful. These results have implications for distinct model-aided calculations in biological situations because these kinds of estimations could lead to spurious conclusions. (c) 2006 Elsevier B.V. All rights reserved.}, author = {de Vladar, Harold and Pen, I.}, journal = {Physica A}, pages = {477 -- 485}, publisher = {Elsevier}, title = {{Determinism, noise, and spurious estimations in a generalised model of population growth}}, doi = {10.1016/j.physa.2006.06.025}, volume = {373}, year = {2007}, } @inproceedings{4233, author = {Harold Vladar}, editor = {Falcón,N. and Loyo de Sardi,Y.}, pages = {91 -- 109}, publisher = {Consejo de Desarrollo Cientifico y Tecnologico}, title = {{Alternativas prebióticas para la síntesis de amino- ácidos y otras moléculas relacionadas}}, doi = {3808}, year = {2007}, } @article{4247, abstract = {Evolution at multiple gene positions is complicated. Direct selection on one gene disturbs the evolutionary dynamics of associated genes. Recent years have seen the development of a multilocus methodology for modeling evolution at arbitrary numbers of gene positions with arbitrary dominance and epistatic relations, mode of inheritance, genetic linkage, and recombination. We show that the approach is conceptually analogous to social evolutionary methodology, which focuses on selection acting on associated individuals. In doing so, we (1) make explicit the links between the multilocus methodology and the foundations of social evolution theory, namely, Price’s theorem and Hamilton’s rule; (2) relate the multilocus approach to levels‐of‐selection and neighbor‐modulated‐fitness approaches in social evolution; (3) highlight the equivalence between genetical hitchhiking and kin selection; (4) demonstrate that the multilocus methodology allows for social evolutionary analyses involving coevolution of multiple traits and genetical associations between nonrelatives, including individuals of different species; (5) show that this methodology helps solve problems of dynamic sufficiency in social evolution theory; (6) form links between invasion criteria in multilocus systems and Hamilton’s rule of kin selection; (7) illustrate the generality and exactness of Hamilton’s rule, which has previously been described as an approximate, heuristic result.}, author = {Gardner, Andy and West, Stuart A and Nicholas Barton}, journal = {American Naturalist}, number = {2}, pages = {207 -- 226}, publisher = {University of Chicago Press}, title = {{The relation between multilocus population genetics and social evolution theory}}, doi = {10.1086/510602}, volume = {169}, year = {2007}, } @article{4246, abstract = {Gaia theory, which describes the life–environment system of the Earth as stable and self-regulating, has remained at the fringes of mainstream biological science owing to its historically inadequate definition and apparent incompatibility with individual-level natural selection. The key issue is whether and why the biosphere might tend towards stability and self-regulation. We review the various ways in which these issues have been addressed by evolutionary and ecological theory, and relate these to ‘Gaia theory’. We then ask how this theory extends the perspectives offered by these disciplines, and how it might be tested by novel modelling approaches and laboratory experiments using emergent technologies.}, author = {Free, Andrew and Nicholas Barton}, journal = {Trends in Ecology and Evolution}, number = {11}, pages = {611 -- 619}, publisher = {Cell Press}, title = {{Do evolution and ecology need the Gaia hypothesis?}}, doi = {10.1016/j.tree.2007.07.007}, volume = {22}, year = {2007}, } @inproceedings{4399, abstract = {A temporal interface for a software component is a finite automaton that specifies the legal sequences of calls to functions that are provided by the component. We compare and evaluate three different algorithms for automatically extracting temporal interfaces from program code: (1) a game algorithm that computes the interface as a representation of the most general environment strategy to avoid a safety violation; (2) a learning algorithm that repeatedly queries the program to construct the minimal interface automaton; and (3) a CEGAR algorithm that iteratively refines an abstract interface hypothesis by adding relevant program variables. For comparison purposes, we present and implement the three algorithms in a unifying formal setting. While the three algorithms compute the same output and have similar worst-case complexities, their actual running times may differ considerably for a given input program. On the theoretical side, we provide for each of the three algorithms a family of input programs on which that algorithm outperforms the two alternatives. On the practical side, we evaluate the three algorithms experimentally on a variety of Java libraries. }, author = {Beyer, Dirk and Thomas Henzinger and Vasu Singh}, pages = {4 -- 19}, publisher = {Springer}, title = {{Algorithms for interface synthesis}}, doi = {10.1007/978-3-540-73368-3_4}, volume = {4590}, year = {2007}, } @inproceedings{4394, author = {Bouillaguet,Charles and Kuncak, Viktor and Thomas Wies and Zee,Karen and Rinard,Martin C.}, pages = {74 -- 88}, publisher = {Springer}, title = {{Using First-Order Theorem Provers in the Jahob Data Structure Verification System}}, doi = {1552}, year = {2007}, } @inproceedings{4398, author = {Berdine,Josh and Calcagno,Cristiano and Cook,Byron and Distefano,Dino and O'Hearn,Peter W. and Thomas Wies and Yang,Hongseok}, pages = {178 -- 192}, publisher = {Springer}, title = {{Shape Analysis for Composite Data Structures}}, doi = {1553}, year = {2007}, } @article{4405, abstract = {Background A central goal of Systems Biology is to model and analyze biological signaling pathways that interact with one another to form complex networks. Here we introduce Qualitative networks, an extension of Boolean networks. With this framework, we use formal verification methods to check whether a model is consistent with the laboratory experimental observations on which it is based. If the model does not conform to the data, we suggest a revised model and the new hypotheses are tested in-silico. Results We consider networks in which elements range over a small finite domain allowing more flexibility than Boolean values, and add target functions that allow to model a rich set of behaviors. We propose a symbolic algorithm for analyzing the steady state of these networks, allowing us to scale up to a system consisting of 144 elements and state spaces of approximately 1086 states. We illustrate the usefulness of this approach through a model of the interaction between the Notch and the Wnt signaling pathways in mammalian skin, and its extensive analysis. Conclusion We introduce an approach for constructing computational models of biological systems that extends the framework of Boolean networks and uses formal verification methods for the analysis of the model. This approach can scale to multicellular models of complex pathways, and is therefore a useful tool for the analysis of complex biological systems. The hypotheses formulated during in-silico testing suggest new avenues to explore experimentally. Hence, this approach has the potential to efficiently complement experimental studies in biology.}, author = {Schaub, Marc A and Thomas Henzinger and Fisher, Jasmin}, journal = {BMC Systems Biology}, number = {4}, publisher = {BioMed Central}, title = {{Qualitative networks: A symbolic approach to analyze biological signaling networks}}, doi = {10.1186/1752-0509-1-4}, volume = {1}, year = {2007}, } @inproceedings{4402, author = {Alur, Rajeev and Pavol Cerny and Chaudhuri,Swarat}, pages = {664 -- 678}, publisher = {Springer}, title = {{Model Checking on Trees with Path Equivalences}}, doi = {1544}, year = {2007}, } @inbook{4417, abstract = {Counterexample-guided abstraction refinement (CEGAR) is a powerful technique to scale automatic program analysis techniques to large programs. However, so far it has been used primarily for model checking in the context of predicate abstraction. We formalize CEGAR for general powerset domains. If a spurious abstract counterexample needs to be removed through abstraction refinement, there are often several choices, such as which program location(s) to refine, which abstract domain(s) to use at different locations, and which abstract values to compute. We define several plausible preference orderings on abstraction refinements, such as refining as “late” as possible and as “coarse” as possible. We present generic algorithms for finding refinements that are optimal with respect to the different preference orderings. We also compare the different orderings with respect to desirable properties, including the property if locally optimal refinements compose to a global optimum. Finally, we point out some difficulties with CEGAR for non-powerset domains.}, author = {Manevich, Roman and Field, John and Thomas Henzinger and Ramalingam, Ganesan and Sagiv, Mooly}, booktitle = {Program Analysis and Compilation, Theory and Practice: Essays Dedicated to Reinhard Wilhelm on the Occasion of His 60th Birthday}, pages = {273 -- 292}, publisher = {Springer}, title = {{Abstract counterexample-based refinement for powerset domains}}, doi = {10.1007/978-3-540-71322-7_13}, volume = {4444}, year = {2007}, } @article{4446, abstract = {The Embedded Machine is a virtual machine that mediates in real time the interaction between software processes and physical processes. It separates the compilation of embedded programs into two phases. The first phase, the platform-independent compiler phase, generates E code (code executed by the Embedded Machine), which supervises the timing, not the scheduling of, application tasks relative to external events such as clock ticks and sensor interrupts. E code is portable and, given an input behavior, exhibits predictable (i.e., deterministic) timing and output behavior. The second phase, the platform-dependent compiler phase, checks the time safety of the E code, that is, whether platform performance (determined by the hardware) and platform utilization (determined by the scheduler of the operating system) enable its timely execution. We have used the Embedded Machine to compile and execute high-performance control applications written in Giotto, such as the flight control system of an autonomous model helicopter.}, author = {Thomas Henzinger and Kirsch, Christoph M}, journal = {ACM Transactions on Programming Languages and Systems (TOPLAS)}, number = {393}, publisher = {ACM}, title = {{The embedded machine: Predictable, portable real-time code}}, doi = {10.1145/1286821.1286824}, volume = {29}, year = {2007}, } @inproceedings{4514, abstract = {Digital technology is increasingly deployed in safety-critical situations. This calls for systematic design and verification methodologies that can cope with three major sources of system complexity: concurrency, real time, and uncertainty. We advocate a two-step process: formal modeling followed by algorithmic analysis (or, “model building” followed by “model checking”). We model the concurrent components of a reactive system as potential collaborators or adversaries in a multi-player game with temporal objectives, such as system safety. The real-time aspect of embedded systems requires models that combine discrete state transitions and continuous state evolutions. Uncertainty in the environment is naturally modeled by probabilistic state changes. As a result, we obtain three orthogonal extensions of the basic state-transition graph model for reactive systems —game graphs, timed graphs, and stochastic graphs— as well as combinations thereof. In this short text, we provide a uniform exposition of the underlying definitions. For verification algorithms, we refer the reader to the literature.}, author = {Thomas Henzinger}, pages = {103 -- 110}, publisher = {Springer}, title = {{Games, time, and probability: Graph models for system design and analysis}}, doi = {10.1007/978-3-540-69507-3_7}, volume = {4362}, year = {2007}, } @inproceedings{4511, abstract = {In the traditional view, a language is a set of words, i.e., a function from words to boolean values. We call this view “qualitative,” because each word either belongs to or does not belong to a language. Let Σ be an alphabet, and let us consider infinite words over Σ. Formally, a qualitative language over Σ is a function A: B . There are many applications of qualitative languages. For example, qualitative languages are used to specify the legal behaviors of systems, and zero-sum objectives of games played on graphs. In the former case, each behavior of a system is either legal or illegal; in the latter case, each outcome of a game is either winning or losing. For defining languages, it is convenient to use finite acceptors (or generators). In particular, qualitative languages are often defined using finite-state machines (so-called ω-automata) whose transitions are labeled by letters from Σ. For example, the states of an ω-automaton may represent states of a system, and the transition labels may represent atomic observables of a behavior. There is a rich and well-studied theory of finite-state acceptors of qualitative languages, namely, the theory of theω-regular languages.}, author = {Thomas Henzinger}, pages = {20 -- 22}, publisher = {Springer}, title = {{Quantitative generalizations of languages}}, doi = {10.1007/978-3-540-73208-2_2}, volume = {4588}, year = {2007}, } @article{4531, abstract = {Caenorhabditis elegans vulval development provides an important paradigm for studying the process of cell fate determination and pattern formation during animal development. Although many genes controlling vulval cell fate specification have been identified, how they orchestrate themselves to generate a robust and invariant pattern of cell fates is not yet completely understood. Here, we have developed a dynamic computational model incorporating the current mechanistic understanding of gene interactions during this patterning process. A key feature of our model is the inclusion of multiple modes of crosstalk between the epidermal growth factor receptor (EGFR) and LIN-12/Notch signaling pathways, which together determine the fates of the six vulval precursor cells (VPCs). Computational analysis, using the model-checking technique, provides new biological insights into the regulatory network governing VPC fate specification and predicts novel negative feedback loops. In addition, our analysis shows that most mutations affecting vulval development lead to stable fate patterns in spite of variations in synchronicity between VPCs. Computational searches for the basis of this robustness show that a sequential activation of the EGFR-mediated inductive signaling and LIN-12 / Notch-mediated lateral signaling pathways is key to achieve a stable cell fate pattern. We demonstrate experimentally a time-delay between the activation of the inductive and lateral signaling pathways in wild-type animals and the loss of sequential signaling in mutants showing unstable fate patterns; thus, validating two key predictions provided by our modeling work. The insights gained by our modeling study further substantiate the usefulness of executing and analyzing mechanistic models to investigate complex biological behaviors.}, author = {Fisher, Jasmin and Piterman, Nir and Hajnal, Alex and Thomas Henzinger}, journal = {PLoS Computational Biology}, publisher = {Public Library of Science}, title = {{Predictive modeling of signaling crosstalk during C. elegans vulval development}}, doi = {10.1371/journal.pcbi.0030092}, volume = {3(5):e92}, year = {2007}, } @article{4529, abstract = {Computational modeling of biological systems is becoming increasingly important in efforts to better understand complex biological behaviors. In this review, we distinguish between two types of biological models—mathematical and computational—which differ in their representations of biological phenomena. We call the approach of constructing computational models of biological systems 'executable biology', as it focuses on the design of executable computer algorithms that mimic biological phenomena. We survey the main modeling efforts in this direction, emphasize the applicability and benefits of executable models in biological research and highlight some of the challenges that executable biology poses for biology and computer science. We claim that for executable biology to reach its full potential as a mainstream biological technique, formal and algorithmic approaches must be integrated into biological research. This will drive biology toward a more precise engineering discipline.}, author = {Fisher, Jasmin and Thomas Henzinger}, journal = {Nature Biotechnology}, pages = {1239 -- 1249}, publisher = {Nature Publishing Group}, title = {{Executable cell biology}}, doi = {10.1038/nbt1356}, volume = {25}, year = {2007}, } @proceedings{4530, abstract = {This book constitutes the refereed proceedings of the 21st International Workshop on Computer Science Logic, CSL 2007, held as the 16th Annual Conference of the EACSL in Lausanne, Switzerland. The 36 revised full papers presented together with the abstracts of six invited lectures are organized in topical sections on logic and games, expressiveness, games and trees, logic and deduction, lambda calculus, finite model theory, linear logic, proof theory, and game semantics.}, author = {Duparc, Jacques and Thomas Henzinger}, booktitle = {CSL: Computer Science Logic}, publisher = {Springer}, title = {{CSL: Computer Science Logic }}, doi = {10.1007/978-3-540-74915-8}, volume = {4646}, year = {2007}, } @inproceedings{4537, abstract = {The classical synthesis problem for reactive systems asks, given a proponent process A and an opponent process B, to refine A so that the closed-loop system A parallel to B satisfies a given specification Phi. The solution of this problem requires the computation of a winning strategy for proponent A in a game against opponent B. We define and study the co-synthesis problem, where the proponent A consists itself of two independent processes, A = A(1)parallel to A(2), with specifications Phi(1) and Phi(2), and the goal is to refine both A(1) and A(2) so that A(1)parallel to A(2)parallel to B satisfies Phi(1) boolean AND Phi(2). For example, if the opponent B is a fair scheduler for the two processes A(1) and A(2), and Phi(i) specifies the requirements of mutual exclusion for A(i) (e.g., starvation freedom), then the co-synthesis problem asks for the automatic synthesis of a mutual-exclusion protocol. We show that co-synthesis defined classically, with the processes A(1) and A(2) either collaborating or competing, does not capture desirable solutions. Instead, the proper formulation of co-synthesis is the one where process A, competes with A(2) but not at the price of violating Phi(1), and vice versa. We call this assume-guarantee synthesis and show that it can be solved by computing secure-equilibrium strategies. In particular, from mutual-exclusion requirements the assume-guarantee synthesis algorithm automatically computes Peterson's protocol.}, author = {Krishnendu Chatterjee and Thomas Henzinger}, pages = {261 -- 275}, publisher = {Springer}, title = {{Assume-guarantee synthesis}}, doi = {10.1007/978-3-540-71209-1_21}, volume = {4424}, year = {2007}, } @article{4547, abstract = {We study observation-based strategies for two-player turn-based games on graphs with omega-regular objectives. An observation-based strategy relies on imperfect information about the history of a play, namely, on the past sequence of observations. Such games occur in the synthesis of a controller that does not see the private state of the plant. Our main results are twofold. First, we give a fixed-point algorithm for computing the set of states from which a player can win with a deterministic observation-based strategy for any omega-regular objective. The fixed point is computed in the lattice of antichains of state sets. This algorithm has the advantages of being directed by the objective and of avoiding an explicit subset construction on the game graph. Second, we give an algorithm for computing the set of states from which a player can win with probability 1 with a randomized observation-based strategy for a Buechi objective. This set is of interest because in the absence of perfect information, randomized strategies are more powerful than deterministic ones. We show that our algorithms are optimal by proving matching lower bounds.}, author = {Krishnendu Chatterjee and Doyen, Laurent and Thomas Henzinger and Raskin, Jean-François}, journal = {Logical Methods in Computer Science}, number = {184}, pages = {1 -- 23}, publisher = {International Federation of Computational Logic}, title = {{Algorithms for omega-regular games with imperfect information}}, doi = {10.2168/LMCS-3(3:4)2007}, volume = {3}, year = {2007}, } @phdthesis{4559, abstract = {We study games played on graphs with omega-regular conditions specified as parity, Rabin, Streett or Muller conditions. These games have applications in the verification, synthesis, modeling, testing, and compatibility checking of reactive systems. Important distinctions between graph games are as follows: (a) turn-based vs. concurrent games, depending on whether at a state of the game only a single player makes a move, or players make moves simultaneously; (b) deterministic vs. stochastic, depending on whether the transition function is a deterministic or a probabilistic function over successor states; and (c) zero-sum vs. non-zero-sum, depending on whether the objectives of the players are strictly conflicting or not. We establish that the decision problem for turn-based stochastic zero-sum games with Rabin, Streett, and Muller objectives are NP-complete, coNP-complete, and PSPACE-complete, respectively, substantially improving the previously known 3EXPTIME bound. We also present strategy improvement style algorithms for turn-based stochastic Rabin and Streett games. In the case of concurrent stochastic zero-sum games with parity objectives we obtain a PSPACE bound, again improving the previously known 3EXPTIME bound. As a consequence, concurrent stochastic zero-sum games with Rabin, Streett, and Muller objectives can be solved in EXPSPACE, improving the previously known 4EXPTIME bound. We also present an elementary and combinatorial proof of the existence of memoryless \epsilon-optimal strategies in concurrent stochastic games with reachability objectives, for all real \epsilon>0, where an \epsilon-optimal strategy achieves the value of the game with in \epsilon against all strategies of the opponent. We also use the proof techniques to present a strategy improvement style algorithm for concurrent stochastic reachability games. We then go beyond \omega-regular objectives and study the complexity of an important class of quantitative objectives, namely, limit-average objectives. In the case of limit-average games, the states of the graph is labeled with rewards and the goal is to maximize the long-run average of the rewards. We show that concurrent stochastic zero-sum games with limit-average objectives can be solved in EXPTIME. Finally, we introduce a new notion of equilibrium, called secure equilibrium, in non-zero-sum games which captures the notion of conditional competitiveness. We prove the existence of unique maximal secure equilibrium payoff profiles in turn-based deterministic games, and present algorithms to compute such payoff profiles. We also show how the notion of secure equilibrium extends the assume-guarantee style of reasoning in the game theoretic framework.}, author = {Krishnendu Chatterjee}, pages = {1 -- 247}, publisher = {University of California, Berkeley}, title = {{Stochastic ω-Regular Games}}, year = {2007}, } @phdthesis{4566, abstract = {Complex system design today calls for compositional design and implementation. However each component is designed with certain assumptions about the environment it is meant to operate in, and delivering certain guarantees if those assumptions are satisfied; numerous inter-component interaction errors are introduced in the manual and error-prone integration process as there is little support in design environments for machine-readably representing these assumptions and guarantees and automatically checking consistency during integration. Based on Interface Automata we propose a framework for compositional design and analysis of systems: a set of domain-specific automata-theoretic type systems for compositional system specification and analysis by behavioral specification of open systems. We focus on three different domains: component-based hardware systems communicating on bidirectional wires. concurrent distributed recursive message-passing software systems, and embedded software system components operating in resource-constrained environments. For these domains we present approaches to formally represent the assumptions and conditional guarantees between interacting open system components. Composition of such components produces new components with the appropriate assumptions and guarantees. We check satisfaction of temporal logic specifications by such components, and the substitutability of one component with another in an arbitrary context. Using this framework one can analyze large systems incrementally without needing extensive summary information to close the system at each stage. Furthermore, we focus only on the inter-component interaction behavior without dealing with the full implementation details of each component. Many of the merits of automata-theoretic model-checking are combined with the compositionality afforded by type-system based techniques. We also present an integer-based extension of the conventional boolean verification framework motivated by our interface formalism for embedded software components. Our algorithms for checking the behavioral compatibility of component interfaces are available in our tool Chic, which can be used as a plug-in for the Java IDE JBuilder and the heterogenous modeling and design environment Ptolemy II. Finally, we address the complementary problem of partitioning a large system into meaningful coherent components by analyzing the interaction patterns between its basic elements. We demonstrate the usefulness of our partitioning approach by evaluating its efficacy in improving unit-test branch coverage for a large software system implemented in C.}, author = {Chakrabarti, Arindam}, pages = {1 -- 244}, publisher = {University of California, Berkeley}, title = {{A framework for compositional design and analysis of systems}}, year = {2007}, } @article{4567, 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 either statically proves that the program satisfies the safety property, or provides an execution path that exhibits a violation of the property (or, since the problem is undecidable, does not terminate). BLAST constructs, explores, and refines abstractions of the program state space based on lazy predicate abstraction and interpolation-based predicate discovery. This paper gives an introduction to BLAST and demonstrates, through two case studies, how it can be applied to program verification and test-case generation. In the first case study, we use BLAST to statically prove memory safety for C programs. We use CCured, a type-based memory-safety analyzer, to annotate a program with run-time assertions that check for safe memory operations. Then, we use BLAST to remove as many of the run-time checks as possible (by proving that these checks never fail), and to generate execution scenarios that violate the assertions for the remaining run-time checks. In our second case study, we use BLAST to automatically generate test suites that guarantee full coverage with respect to a given predicate. Given a C program and a target predicate p, BLAST determines the program locations q for which there exists a program execution that reaches q with p true, and automatically generates a set of test vectors that cause such executions. Our experiments show that BLAST can provide automated, precise, and scalable analysis for C programs.}, author = {Beyer, Dirk and Thomas Henzinger and Jhala, Ranjit and Majumdar, Ritankar S}, journal = {International Journal on Software Tools for Technology Transfer}, number = {5}, pages = {505 -- 525}, publisher = {Springer}, title = {{The software model checker BLAST: Applications to software engineering}}, doi = {10.1007/s10009-007-0044-z}, volume = {9}, year = {2007}, } @inproceedings{4570, abstract = {We consider the minimum-time reachability problem in concurrent two-player timed automaton game structures. We show how to compute the minimum time needed by a player to reach a target location against all possible choices of the opponent. We do not put any syntactic restriction on the game structure, nor do we require any player to guarantee time divergence. We only require players to use receptive strategies which do not block time. The minimal time is computed in part using a fixpoint expression, which we show can be evaluated on equivalence classes of a non-trivial extension of the clock-region equivalence relation for timed automata.}, author = {Brihaye, Thomas and Thomas Henzinger and Prabhu, Vinayak S and Raskin, Jean-François}, pages = {825 -- 837}, publisher = {Springer}, title = {{Minimum-time reachability in timed games}}, doi = {10.1007/978-3-540-73420-8_71}, volume = {4596}, year = {2007}, } @inproceedings{4573, abstract = {In automatic software verification, we have observed a theoretical convergence of model checking and program analysis. In practice, however, model checkers are still mostly concerned with precision, e.g., the removal of spurious counterexamples; for this purpose they build and refine reachability trees. Lattice-based program analyzers, on the other hand, are primarily concerned with efficiency. We designed an algorithm and built a tool that can be configured to perform not only a purely tree-based or a purely lattice-based analysis, but offers many intermediate settings that have not been evaluated before. The algorithm and tool take one or more abstract interpreters, such as a predicate abstraction and a shape analysis, and configure their execution and interaction using several parameters. Our experiments show that such customization may lead to dramatic improvements in the precision-efficiency spectrum.}, author = {Beyer, Dirk and Thomas Henzinger and Théoduloz, Grégory}, pages = {504 -- 518}, publisher = {Springer}, title = {{Configurable software verification: Concretizing the convergence of model checking and program analysis}}, doi = {10.1007/978-3-540-73368-3_51}, volume = {4590}, year = {2007}, } @inproceedings{4572, abstract = {We present a constraint-based algorithm for the synthesis of invariants expressed in the combined theory of linear arithmetic and uninterpreted function symbols. Given a set of programmer-specified invariant templates, our algorithm reduces the invariant synthesis problem to a sequence of arithmetic constraint satisfaction queries. Since the combination of linear arithmetic and uninterpreted functions is a widely applied predicate domain for program verification, our algorithm provides a powerful tool to statically and automatically reason about program correctness. The algorithm can also be used for the synthesis of invariants over arrays and set data structures, because satisfiability questions for the theories of sets and arrays can be reduced to the theory of linear arithmetic with uninterpreted functions. We have implemented our algorithm and used it to find invariants for a low-level memory allocator written in C.}, author = {Beyer, Dirk and Thomas Henzinger and Majumdar, Ritankar S and Rybalchenko, Andrey}, pages = {378 -- 394}, publisher = {Springer}, title = {{Invariant synthesis for combined theories}}, doi = {10.1007/978-3-540-69738-1_27}, volume = {4349}, year = {2007}, } @inproceedings{4571, abstract = {The success of software verification depends on the ability to find a suitable abstraction of a program automatically. We propose a method for automated abstraction refinement which overcomes some limitations of current predicate discovery schemes. In current schemes, the cause of a false alarm is identified as an infeasible error path, and the abstraction is refined in order to remove that path. By contrast, we view the cause of a false alarm -the spurious counterexample- as a full-fledged program, namely, a fragment of the original program whose control-flow graph may contain loops and represent unbounded computations. There are two advantages to using such path programs as counterexamples for abstraction refinement. First, we can bring the whole machinery of program analysis to bear on path programs, which are typically small compared to the original program. Specifically, we use constraint-based invariant generation to automatically infer invariants of path programs-so-called path invariants. Second, we use path invariants for abstraction refinement in order to remove not one infeasibility at a time, but at once all (possibly infinitely many) infeasible error computations that are represented by a path program. Unlike previous predicate discovery schemes, our method handles loops without unrolling them; it infers abstractions that involve universal quantification and naturally incorporates disjunctive reasoning.}, author = {Beyer, Dirk and Thomas Henzinger and Majumdar, Ritankar S and Rybalchenko, Andrey}, pages = {300 -- 309}, publisher = {ACM}, title = {{Path invariants}}, doi = {10.1145/1250734.1250769}, year = {2007}, } @inproceedings{4575, abstract = {We present a case study to illustrate our formalism for the specification and verification of the method-invocation behavior of web-service applications constructed from asynchronously interacting multi-threaded distributed components. Our model is expressive enough to allow the representation of recursion and dynamic thread creation, and yet permits the algorithmic analysis of the following two questions: (1) Does a given service satisfy a safety specification? (2) Can a given service be substituted by a another service in an arbitrary context? Our case study is based on the Amazon.com E-Commerce Services (ECS) platform.}, author = {Beyer, Dirk and Chakrabarti, Arindam and Thomas Henzinger and Seshia, Sanjit A}, pages = {831 -- 838}, publisher = {IEEE}, title = {{An application of web-service interfaces}}, doi = {10.1109/ICWS.2007.32 }, year = {2007}, }