@inproceedings{3215, abstract = {Most cryptographic primitives such as encryption, authentication or secret sharing require randomness. Usually one assumes that perfect randomness is available, but those primitives might also be realized under weaker assumptions. In this work we continue the study of building secure cryptographic primitives from imperfect random sources initiated by Dodis and Spencer (FOCS’02). Their main result shows that there exists a (high-entropy) source of randomness allowing for perfect encryption of a bit, and yet from which one cannot extract even a single weakly random bit, separating encryption from extraction. Our main result separates encryption from 2-out-2 secret sharing (both in the information-theoretic and in the computational settings): any source which can be used to achieve one-bit encryption also can be used for 2-out-2 secret sharing of one bit, but the converse is false, even for high-entropy sources. Therefore, possibility of extraction strictly implies encryption, which in turn strictly implies 2-out-2 secret sharing.}, author = {Dodis, Yevgeniy and Krzysztof Pietrzak and Przydatek, Bartosz}, pages = {601 -- 616}, publisher = {Springer}, title = {{Separating sources for encryption and secret sharing}}, doi = {10.1007/11681878_31}, volume = {3876}, year = {2006}, } @inproceedings{3217, abstract = {To prove that a secure key-agreement protocol exists one must at least show P ≠NP. Moreover any proof that the sequential composition of two non-adaptively secure pseudorandom functions is secure against at least two adaptive queries must falsify the decisional Diffie-Hellman assumption, a standard assumption from public-key cryptography. Hence proving any of this two seemingly unrelated statements would require a significant breakthrough. We show that at least one of the two statements is true. To our knowledge this gives the first positive cryptographic result (namely that composition implies some weak adaptive security) which holds in Minicrypt, but not in Cryptomania, i.e. under the assumption that one-way functions exist, but public-key cryptography does not.}, author = {Krzysztof Pietrzak}, pages = {328 -- 338}, publisher = {Springer}, title = {{Composition implies adaptive security in minicrypt}}, doi = {10.1007/11761679_20}, volume = {4004}, year = {2006}, } @inproceedings{3216, abstract = {We prove a new upper bound on the advantage of any adversary for distinguishing the encrypted CBC-MAC (EMAC) based on random permutations from a random function. Our proof uses techniques recently introduced in [BPR05], which again were inspired by [DGH + 04]. The bound we prove is tight — in the sense that it matches the advantage of known attacks up to a constant factor — for a wide range of the parameters: let n denote the block-size, q the number of queries the adversary is allowed to make and ℓ an upper bound on the length (i.e. number of blocks) of the messages, then for ℓ ≤ 2 n/8 and q≥ł2 the advantage is in the order of q 2/2 n (and in particular independent of ℓ). This improves on the previous bound of q 2ℓΘ(1/ln ln ℓ)/2 n from [BPR05] and matches the trivial attack (which thus is basically optimal) where one simply asks random queries until a collision is found.}, author = {Krzysztof Pietrzak}, pages = {168 -- 179}, publisher = {Springer}, title = {{A tight bound for EMAC}}, doi = {10.1007/11787006_15}, volume = {4052}, year = {2006}, } @article{3522, abstract = {We observed sharp wave/ripples (SWR) during exploration within brief (< 2.4 s) interruptions of or during theta oscillations. CA1 network responses of SWRs occurring during exploration (eSWR) and SWRs detected in waking immobility or sleep were similar. However, neuronal activity during eSWR was location dependent, and eSWR-related firing was stronger inside the place field than outside. The eSPW-related firing increase was stronger than the baseline increase inside compared to outside, suggesting a “supralinear” summation of eSWR and place-selective inputs. Pairs of cells with similar place fields and/or correlated firing during exploration showed stronger coactivation during eSWRs and subsequent sleep-SWRs. Sequential activation of place cells was not required for the reactivation of waking co-firing patterns; cell pairs with symmetrical cross-correlations still showed reactivated waking co-firing patterns during sleep-SWRs. We suggest that place-selective firing during eSWRs facilitates initial associations between cells with similar place fields that enable place-related ensemble patterns to recur during subsequent sleep-SWRs.}, author = {Joseph O'Neill and Senior,Timothy and Jozsef Csicsvari}, journal = {Neuron}, number = {1}, pages = {143 -- 155}, publisher = {Elsevier}, title = {{Place-selective firing of CA1 pyramidal cells during sharp wave/ripple network patterns in exploratory behavior}}, doi = {10.1016/j.neuron.2005.10.037}, volume = {49}, year = {2006}, } @article{3607, abstract = {We apply new analytical methods to understand the consequences of population bottlenecks for expected additive genetic variance. We analyze essentially all models for multilocus epistasis that have been numerically simulated to demonstrate increased additive variance. We conclude that for biologically plausible models, large increases in expected additive variance–attributable to epistasis rather than dominance–are unlikely. Naciri-Graven and Goudet (2003) found that as the number of epistatically interacting loci increases, additive variance tends to be inflated more after a bottleneck. We argue that this result reflects biologically unrealistic aspects of their models. Specifically, as the number of loci increases, higher-order epistatic interactions become increasingly important in these models, with an increasing fraction of the genetic variance becoming nonadditive, contrary to empirical observations. As shown by Barton and Turelli (2004), without dominance, conversion of nonadditive to additive variance depends only on the variance components and not on the number of loci per se. Numerical results indicating that more inbreeding is needed to produce maximal release of additive variance with more loci follow directly from our analytical results, which show that high levels of inbreeding (F > 0.5) are needed for significant conversion of higher-order components. We discuss alternative approaches to modeling multilocus epistasis and understanding its consequences.}, author = {Turelli, Michael and Nicholas Barton}, journal = {Evolution; International Journal of Organic Evolution}, number = {9}, pages = {1763 -- 1776}, publisher = {Wiley-Blackwell}, title = {{Will population bottlenecks and multilocus epistasis increase additive genetic variance?}}, doi = {10.1111/j.0014-3820.2006.tb00521.x}, volume = {60}, year = {2006}, } @inproceedings{3683, abstract = {Many algorithms to remove distortion from document images have be proposed in recent years, but so far there is no reliable method for comparing their performance. In this paper we propose a collection of methods to measure the quality of such restoration algorithms for document image which show a non-linear distortion due to perspective or page curl. For the result from these measurement to be meaningful, a common data set of ground truth is required. We therefore started with the buildup of a document image database that is meant to serve as a common data basis for all kinds of restoration from images of 3D-shaped document. The long term goal would be to establish this database and following extensions in the area of document image dewarping as an as fruitful and indispensable tool as e.g. the NIST database is for OCR, or the Caltech database is for object and face recognition.}, author = {Christoph Lampert and Breuel,Thomas M}, publisher = {Springer}, title = {{Objective quality measurement for geometric document image restoration}}, year = {2006}, } @inproceedings{3685, abstract = {Video compression currently is dominated by engineering and fine-tuned heuristic methods. In this paper, we propose to instead apply the well-developed machinery of machine learning in order to support the optimization of existing video encoders and the creation of new ones. Exemplarily, we show how by machine learning we can improve one encoding step that is crucial for the performance of all current video standards: macroblock mode decision. By formulating the problem in a Bayesian setup, we show that macroblock mode decision can be reduced to a classification problem with a cost function for misclassification that is sample dependent. We demonstrate how to apply different machine learning techniques to obtain suitable classifiers and we show in detailed experiments that all of these perform better than the state-of-the-art heuristic method}, author = {Christoph Lampert}, pages = {936 -- 940}, publisher = {IEEE}, title = {{Machine learning for video compression: Macroblock mode decision}}, doi = {10.1109/ICPR.2006.778}, year = {2006}, } @article{3750, abstract = {We applied a single-cell assay to characterize how transcription dynamics affects protein expression levels of a tetracycline-inducible gene expression system. Transcriptional activity of the tetracycline promoter in response to a steady level of inducer is steady in ΔacrAB efflux mutant but pulsating in wildtype Escherichia coli cells. We found that the expression level of the green fluorescent protein is several folds higher in ΔacrAB efflux mutant than in wildtype cells.}, author = {Le,Thuc T. and Calin Guet and Cluzel,Philippe}, journal = {Protein Expression and Purification}, number = {1}, pages = {28 -- 31}, publisher = {Elsevier}, title = {{Protein expression enhancement in efflux-deleted mutant bacteria}}, volume = {48}, year = {2006}, } @article{3767, abstract = {Models of RNA secondary structure folding are widely used to study evolution in theory and simulation. However, systematic studies of the parameters involved are rare. In this paper, we study by simulation how RNA evolution is influenced by three different factors, namely the mutation rate, scaling of the fitness function, and distance measure. We found that for low mutation rates the qualitative evolutionary behavior is robust with respect to the scaling of the fitness function. For efficient mutation rates, which are close to the error threshold, scaling and distance measure have a strong influence on the evolutionary behavior. A global distance measure that takes sequence information additively into account lowers the error threshold. When using a local sequence-structure alignment for the distance, we observed a smoother evolution of the fitness over time. Finally, in addition to the well known error threshold, we identify another threshold of the mutation rate, called divergence threshold, where the qualitative transient behavior changes from a localized to an exploratory search.}, author = {Anne Kupczok and Dittrich,Peter}, journal = {Journal of Theoretical Biology}, number = {3}, pages = {726 -- 35}, publisher = {Elsevier}, title = {{Determinants of simulated RNA evolution.}}, doi = {10.1016/j.jtbi.2005.06.019}, volume = {238}, year = {2006}, } @article{3813, abstract = {Hyperpolarization-activated channels (Ih or HCN channels) are widely expressed in principal neurons in the central nervous system. However, Ih in inhibitory GABAergic interneurons is less well characterized. We examined the functional properties of Ih in fast-spiking basket cells (BCs) of the dentate gyrus, using hippocampal slices from 17- to 21-day-old rats. Bath application of the Ih channel blocker ZD 7288 at a concentration of 30 microm induced a hyperpolarization of 5.7 +/- 1.5 mV, an increase in input resistance and a correlated increase in apparent membrane time constant. ZD 7288 blocked a hyperpolarization-activated current in a concentration-dependent manner (IC50, 1.4 microm). The effects of ZD 7288 were mimicked by external Cs+. The reversal potential of Ih was -27.4 mV, corresponding to a Na+ to K+ permeability ratio (PNa/PK) of 0.36. The midpoint potential of the activation curve of Ih was -83.9 mV, and the activation time constant at -120 mV was 190 ms. Single-cell expression analysis using reverse transcription followed by quantitative polymerase chain reaction revealed that BCs coexpress HCN1 and HCN2 subunit mRNA, suggesting the formation of heteromeric HCN1/2 channels. ZD 7288 increased the current threshold for evoking antidromic action potentials by extracellular stimulation, consistent with the expression of Ih in BC axons. Finally, ZD 7288 decreased the frequency of miniature inhibitory postsynaptic currents (mIPSCs) in hippocampal granule cells, the main target cells of BCs, to 70 +/- 4% of the control value. In contrast, the amplitude of mIPSCs was unchanged, consistent with the presence of Ih in inhibitory terminals. In conclusion, our results suggest that Ih channels are expressed in the somatodendritic region, axon and presynaptic elements of fast-spiking BCs in the hippocampus.}, author = {Aponte, Yexica and Lien, Cheng-Chang and Reisinger, Ellen and Peter Jonas}, journal = {Journal of Physiology}, number = {Pt 1}, pages = {229 -- 43}, publisher = {Wiley-Blackwell}, title = {{Hyperpolarization-activated cation channels in fast-spiking interneurons of rat hippocampus}}, doi = {10.1113/jphysiol.2005.104042}, volume = {574}, year = {2006}, } @misc{3814, abstract = {The axon terminals (mossy fibers) of hippocampal dentate granule cells form characteristic synaptic connections with large spines or excrescences of both hilar mossy cells and CA3 pyramidal neurons. Interneurons of the hilar region and area CA3 are also prominent targets of mossy fibers. The tracing of biocytin-filled mossy fibers and immunolabeling of target cells with interneuron markers has revealed that the majority of mossy fiber synapses project to gamma aminobutyric acid (GABA)-ergic inhibitory interneurons rather than to excitatory principal cells, although the functional implications of these quantitative differences are unclear. Following a brief description of the "classical" mossy fiber synapse on excrescences of CA3 pyramidal cells, the present review focuses on the contacts formed between granule cells and GABAergic interneurons, both normally and after synaptic reorganization. In response to deafferentation of mossy cell target cells, which include both granule cells and interneurons, mossy fibers "sprout" new axon collaterals that form a band of supragranular mossy fibers in the inner molecular layer of the dentate gyrus. Although most newly formed recurrent mossy fibers establish synapses with granule cells, there is an apparently convergent input of new mossy fibers onto GABA-immunoreactive interneuron dendrites that traverse the inner molecular layer. These mossy fiber-interneuron synapses in the dentate gyrus are observed in chronically epileptic rats and may be the structural correlate of the granule cell hyperinhibition observed in these animals in vivo. Together, the findings reviewed here establish mossy fiber synapses as an important component of inhibitory circuits in the hippocampus.}, author = {Frotscher, Michael and Peter Jonas and Sloviter, Robert S}, booktitle = {Cell and Tissue Research}, number = {2}, pages = {361 -- 7}, publisher = {Springer}, title = {{Synapses formed by normal and abnormal hippocampal mossy fibers (Review)}}, doi = {10.1007/s00441-006-0269-2}, volume = {326}, year = {2006}, } @article{3815, abstract = {It is widely accepted that the hippocampus plays a major role in learning and memory. The mossy fiber synapse between granule cells in the dentate gyrus and pyramidal neurons in the CA3 region is a key component of the hippocampal trisynaptic circuit. Recent work, partially based on direct presynaptic patch-clamp recordings from hippocampal mossy fiber boutons, sheds light on the mechanisms of synaptic transmission and plasticity at mossy fiber synapses. A high Na(+) channel density in mossy fiber boutons leads to a large amplitude of the presynaptic action potential. Together with the fast gating of presynaptic Ca(2+) channels, this generates a large and brief presynaptic Ca(2+) influx, which can trigger transmitter release with high efficiency and temporal precision. The large number of release sites, the large size of the releasable pool of vesicles, and the huge extent of presynaptic plasticity confer unique strength to this synapse, suggesting a large impact onto the CA3 pyramidal cell network under specific behavioral conditions. The characteristic properties of the hippocampal mossy fiber synapse may be important for pattern separation and information storage in the dentate gyrus-CA3 cell network.}, author = {Bischofberger, Josef and Engel, Dominique and Frotscher, Michael and Peter Jonas}, journal = {Pflugers Archiv : European Journal of Physiology}, number = {3}, pages = {361 -- 72}, publisher = {Springer}, title = {{Timing and efficacy of transmitter release at mossy fiber synapses in the hippocampal network}}, doi = {10.1007/s00424-006-0093-2}, volume = {453}, year = {2006}, } @article{3811, abstract = {Networks of GABAergic neurons are key elements in the generation of gamma oscillations in the brain. Computational studies suggested that the emergence of coherent oscillations requires hyperpolarizing inhibition. Here, we show that GABA(A) receptor-mediated inhibition in mature interneurons of the hippocampal dentate gyrus is shunting rather than hyperpolarizing. Unexpectedly, when shunting inhibition is incorporated into a structured interneuron network model with fast and strong synapses, coherent oscillations emerge. In comparison to hyperpolarizing inhibition, networks with shunting inhibition show several advantages. First, oscillations are generated with smaller tonic excitatory drive. Second, network frequencies are tuned to the gamma band. Finally, robustness against heterogeneity in the excitatory drive is markedly improved. In single interneurons, shunting inhibition shortens the interspike interval for low levels of drive but prolongs it for high levels, leading to homogenization of neuronal firing rates. Thus, shunting inhibition may confer increased robustness to gamma oscillations in the brain.}, author = {Vida, Imre and Bartos, Marlene and Peter Jonas}, journal = {Neuron}, number = {1}, pages = {107 -- 17}, publisher = {Elsevier}, title = {{Shunting inhibition improves robustness of gamma oscillations in hippocampal interneuron networks by homogenizing firing rates}}, doi = {10.1016/j.neuron.2005.11.036}, volume = {49}, year = {2006}, } @article{3817, author = {Frotscher, Michael and Gundelfinger, Eckart and Peter Jonas and Neher, Erwin and Seeburg, Peter}, journal = {Cell and Tissue Research}, number = {2}, pages = {203 -- 4}, publisher = {Springer}, title = {{The most important recent advances in synapse research from my point of view--and what remains to be done}}, doi = {10.1007/s00441-006-0325-y}, volume = {326}, year = {2006}, } @article{3912, abstract = {Invasive species often dramatically change native species communities by directly and indirectly out-competing native species. We studied the direct interference abilities of the invasive garden ant, Lasius neglectus VAN LOON, BOOMSMA & ANDRÁSFALVY, 1990, by performing one-to-one aggression tests of L. neglectus workers towards three native Lasius ant species that occur at the edge of a L. neglectus supercolony in Seva, Spain. Our results show that L. neglectus is highly aggressive against all three native Lasius species tested (L. grandis FOREL, 1909, L. emarginatus (OLIVIER, 1792), and L. cinereus SEIFERT, 1992), expressed as a higher attack rate of L. neglectus and behavioural dominance throughout the aggressive encounters. Attacks of L. neglectus were performed fastest and most frequent against L. grandis, and also the highest antennation frequencies were observed in encounters between these two species. This could be due to the largest difference in body size, or due to a greater overlap in ecological niche between L. neglectus and L. grandis compared to the other two native species. There was only weak support for L. neglectus workers from the periphery of the supercolony to be more aggressive relative to workers from the centre, even though the former encounter native ant species on a daily basis at the edge of the supercolony.}, author = {Cremer, Sylvia and Ugelvig, Line V and Lommen, Suzanne and Petersen, Klaus and Pedersen, Jes}, journal = {Myrmecological News}, pages = {13 -- 19}, publisher = {Österreichische Gesellschaft für Entomofaunistik}, title = {{Attack of the invasive garden ant: aggression behaviour of Lasius neglectus (Hymenoptera: Formicidae) against native Lasius species in Spain}}, volume = {9}, year = {2006}, } @article{3914, abstract = {We compare the performances of established means of character selection for discriminant analysis in species distinction with a combination procedure for finding the optimal character combination (minimum classification error, minimum number of required characters), using morphometric data sets from the ant genera Cardiocondyla, Lasius and Tetramorium. The established methods are empirical character selection as well as forward selection, backward elimination and stepwise selection of discriminant analysis. The combination procedure is clearly superior to the established methods of character selection, and is widely applicable.}, author = {Moder, Karl and Schlick Steiner, Birgit and Steiner, Florian and Cremer, Sylvia and Christian, Erhard and Seifert, Bernhard}, journal = {Journal of Zoological Systematics and Evolutionary Research}, number = {1}, pages = {82 -- 87}, publisher = {Wiley-Blackwell}, title = {{Optimal species distinction by discriminant analysis: comparing established methods of character selection with a combination procedure using ant morphometrics as a case study}}, doi = {10.1111/j.1439-0469.2006.00372.x}, volume = {45}, year = {2006}, } @article{3913, abstract = {Many invasive ant species, such as the Argentine ant or the red imported fire ant, have huge colonies with thousands of mass-foraging workers, which quickly monopolise resources and therefore represent a considerable threat to the native ant fauna. Cardiocondyla obscurior and several other species of this myrmicine genus have similarly been transferred throughout the tropics by human activities. However, because their colonies are tiny and workers forage solitarily, Cardiocondyla are often not recognized as successful invaders. Here, we document that the life history of Cardiocondyla closely resembles that of the more conspicuous tramp species, with polygyny, intranidal mating, budding, worker sterility, low genetic variability, and possibly also unicoloniality. Given that introduced Cardiocondyla may locally reach a very high population density, the effects of these stealthy invaders on the native arthropod fauna should receive more attention.}, author = {Heinze, Jürgen and Cremer, Sylvia and Eckl, Norbert and Schrempf, Alexandra}, journal = {Insectes Sociaux}, number = {1}, pages = {1 -- 7}, publisher = {Springer}, title = {{Stealthy invaders: the biology of Cardiocondyla tramp ants}}, doi = {10.1007/s00040-005-0847-4}, volume = {53}, year = {2006}, } @article{3932, abstract = {OBJECTIVES: The EGFR is expressed in malignant ovarian tumor tissue, and tissue content of EGFR has been directly associated with poor prognosis in patients with ovarian cancer. The uPA system plays a role in pericellular proteolysis, cell migration, invasion, and is over-expressed in ovarian cancer. This study explored the effects of EGF on uPAR expression in the ovarian cancer cell line OVCAR-3. METHODS: We used OVCAR-3 cells and the following methods: cell migration assay, time-lapse video microscopy, real-time PCR, assays for cellular binding of 125I-uPA and cellular degradation of 125I-uPA:PAI-1 complex, biosynthetic labeling using 35S-methionin, Western blot, Northern blot, and ELISAs for uPA, PAI-1, and uPAR. RESULTS: EGF up-regulates both protein and mRNA not only for uPAR, but also for the ligand uPA and its inhibitor PAI-1. Cell surface uPAR, in control as well as EGF-stimulated cells, is present only in the intact, not the cleaved, form. Ligand binding experiments showed an increase of endogenously occupied uPAR, whereas non-occupied receptor sites were not increased. In addition, EGF treatment resulted in decreased degradation of radiolabeled uPA:PAI-1 complex. This suggests decreased internalization of uPAR, since the complex is internalized together with uPAR. Like EGF, colchicine, which inhibits endocytosis, increased cell surface expression of uPAR. In addition, we found an immediate increase of uPAR after exposing the cells to EGF and this was accompanied by a transient increase of cell migration. The increase of cell surface uPAR in response to EGF is accompanied by increased release of the soluble form of uPAR (suPAR) to the medium as well as by increased cell migration. Both uPAR and suPAR increased in cells treated with the endocytosis inhibitor colchicine even though cell migration was inhibited, suggesting that the mechanism of uPAR shedding is not related to cell migration. CONCLUSION: Increased cell surface uPAR in response to EGF stimulation results from mobilization of uPAR from detergent-resistant domains, increased expression of uPAR mRNA, and decreased internalization and degradation of uPAR. Both the anti-uPAR antibody R3, which inhibits binding of uPA, and the EGFR phosphorylation inhibitor Iressa inhibited cell migration in response to uPA as well as to EGF, suggesting that EGFR and uPAR are engaged in the same multiprotein assembly on the cell surface.}, author = {Henic, Emir and Michael Sixt and Hansson, Stefan and Høyer-Hansen, Gunilla and Casslén, Bertil}, journal = {Gynecologic Oncology}, number = {1}, pages = {28 -- 39}, publisher = {Elsevier}, title = {{EGF-stimulated migration in ovarian cancer cells is associated with decreased internalization, increased surface expression, and increased shedding of the urokinase plasminogen activator receptor}}, doi = {10.1016/j.ygyno.2005.09.038}, volume = {101}, year = {2006}, } @article{3978, abstract = {Evaluating the quality of experimentally determined protein structural models is an essential step toward identifying potential errors and guiding further structural refinement. Herein, we report the use of proton local density as a sensitive measure to assess the quality of nuclear magnetic resonance (NMR) structures. Using 256 high-resolution crystal structures with protons added and optimized, we show that the local density of different proton types display distinct distributions. These distributions can be characterized by statistical moments and are used to establish local density Z-scores for evaluating both global and local packing for individual protons. Analysis of 546 crystal structures at various resolutions shows that the local density Z-scores increase as the structural resolution decreases and correlate well with the ClashScore (Word et al. J Mol Biol 1999;285(4):1711-1733) generated by all atom contact analysis. Local density Z-scores for NMR structures exhibit a significantly wider range of values than for X-ray structures and demonstrate a combination of potentially problematic inflation and compression. Water-refined NMR structures show improved packing quality. Our analysis of a high-quality structural ensemble of ubiquitin refined against order parameters shows proton density distributions that correlate nearly perfectly with our standards derived from crystal structures, further validating our approach. We present an automated analysis and visualization tool for proton packing to evaluate the quality of NMR structures.}, author = {Ban, Yih-En Andrew and Rudolph, Johannes and Zhou, Pei and Herbert Edelsbrunner}, journal = {Proteins: Structure, Function and Bioinformatics}, number = {4}, pages = {852 -- 864}, publisher = {Wiley-Blackwell}, title = {{Evaluating the quality of NMR structures by local density of protons}}, doi = {10.1002/prot.20811}, volume = {62}, year = {2006}, } @article{3979, abstract = {Protein-protein interactions, which form the basis for most cellular processes, result in the formation of protein interfaces. Believing that the local shape of proteins is crucial, we take a geometric approach and present a definition of an interface surface formed by two or more proteins as a subset of their Voronoi diagram. The definition deals with the difficult and important problem of specifying interface boundaries by invoking methods used in the alpha shape representation of molecules, the discrete flow on Delaunay simplices to define pockets and reconstruct surfaces, and the assessment of the importance of topological features. We present an algorithm to construct the surface and define a hierarchy that distinguishes core and peripheral regions. This hierarchy is shown to have correlation with hot-spots in protein-protein interactions. Finally, we study the geometric and topological properties of interface surfaces and show their high degree of contortion.}, author = {Ban, Yih-En Andrew and Herbert Edelsbrunner and Rudolph, Johannes}, journal = {Journal of the ACM}, number = {3}, pages = {361 -- 378}, publisher = {ACM}, title = {{Interface surfaces for protein-protein complexes}}, doi = {10.1145/1147954.1147957}, volume = {53}, year = {2006}, } @article{3980, abstract = {Given a smoothly embedded 2-manifold in R-3, we define the elevation of a point as the height difference to a canonically defined second point on the same manifold. Our definition is invariant under rigid motions and can be used to define features such as lines of discontinuous or continuous but non-smooth elevation. We give an algorithm for finding points of locally maximum elevation, which we suggest mark cavities and protrusions and are useful in matching shapes as for example in protein docking.}, author = {Agarwal, Pankaj K and Herbert Edelsbrunner and Harer, John and Wang, Yusu}, journal = {Discrete & Computational Geometry}, number = {4}, pages = {553 -- 572}, publisher = {Springer}, title = {{Extreme elevation on a 2-manifold}}, doi = {10.1007/s00454-006-1265-8}, volume = {36}, year = {2006}, } @article{4345, abstract = {Der Artikel beschäftigt sich mit dem Konzept der Bibliothek 2.0 (bzw. Library 2.0). Er skizziert anhand einiger Beispiele die Entwicklung zum Web 2.0 und beschreibt, wie Web 2.0-Technologien und -Anwendungen in Bibliotheken eingesetzt werden. Im Mittelpunkt stehen Social-Tagging-Systeme, benutzerorientierte Erweiterungen von Bibliothekskatalogen und Dokumentenservern sowie der Einsatz von Weblogs an Bibliotheken. Ferner werden neue Anforderungen an Bibliothekare diskutiert.}, author = {Patrick Danowski and Heller,Lambert}, journal = {Bibliotheksdienst}, number = {11}, pages = {1250 -- 1271}, publisher = {Zentral- und Landesbibliothek Berlin}, title = {{Bibliothek 2.0 - Die Bibliothek der Zukunft?}}, doi = {424}, volume = {40}, year = {2006}, } @article{4352, abstract = {Anopheles darlingi is the primary malaria vector in Latin America, and is especially important in Amazonian Brazil. Historically, control efforts have been focused on indoor house spraying using a variety of insecticides, but since the mid-1990s there has been a shift to patient treatment and focal insecticide fogging. Anopheles darlingi was believed to have been significantly reduced in a gold-mining community, Peixoto de Azevedo (in Mato Grosso State), in the early 1990s by insecticide use during a severe malaria epidemic. In contrast, although An. darlingi was eradicated from some districts of the city of Belem (the capital of Para State) in 1968 to reduce malaria, populations around the water protection area in the eastern district were treated only briefly. To investigate the population structure of An. darlingi including evidence for a population bottleneck in Peixoto, we analyzed eight microsatellite loci of 256 individuals from seven locations in Brazil: three in Amapa State, three in Para State, and one in Mato Grosso State. Allelic diversity and mean expected heterozygosity were high for all populations (mean number alleles/locus and H(E) were 13.5 and 0.834, respectively) and did not differ significantly between locations. Significant heterozygote deficits were associated with linkage disequilibrium, most likely due to either the Wahlund effect or selection. We found no evidence for a population bottleneck in Peixoto, possibly because the reduction was not extreme enough to be detected. Overall estimates of long-term N(e) varied from 92.4 individuals under the linkage disequilibrium model to infinity under the heterozygote excess model. Fixation indices and analysis of molecular variance demonstrated significant differentiation between locations north and south of the Amazon River, suggesting a degree of genetic isolation between them, attributed to isolation by distance.}, author = {Conn, Jan E and Vineis, Joseph H and Jonathan Bollback and Onyabe, David Y and Wilkerson, Richard C and Povoa, Marinete M}, journal = {The American Journal of Tropical Medicine and Hygiene}, number = {5}, pages = {798 -- 806}, publisher = {American Society of Tropical Medicine and Hygiene}, title = {{Population structure of the malaria vector Anopheles darlingi in a malaria-endemic region of eastern Amazonian Brazil}}, volume = {74}, year = {2006}, } @article{4351, abstract = {BACKGROUND: Character mapping on phylogenies has played an important, if not critical role, in our understanding of molecular, morphological, and behavioral evolution. Until very recently we have relied on parsimony to infer character changes. Parsimony has a number of serious limitations that are drawbacks to our understanding. Recent statistical methods have been developed that free us from these limitations enabling us to overcome the problems of parsimony by accommodating uncertainty in evolutionary time, ancestral states, and the phylogeny. RESULTS: SIMMAP has been developed to implement stochastic character mapping that is useful to both molecular evolutionists, systematists, and bioinformaticians. Researchers can address questions about positive selection, patterns of amino acid substitution, character association, and patterns of morphological evolution. CONCLUSION: Stochastic character mapping, as implemented in the SIMMAP software, enables users to address questions that require mapping characters onto phylogenies using a probabilistic approach that does not rely on parsimony. Analyses can be performed using a fully Bayesian approach that is not reliant on considering a single topology, set of substitution model parameters, or reconstruction of ancestral states. Uncertainty in these quantities is accommodated by using MCMC samples from their respective posterior distributions.}, author = {Jonathan Bollback}, journal = {BMC Bioinformatics}, publisher = {BioMed Central}, title = {{SIMMAP: stochastic character mapping of discrete traits on phylogenies}}, doi = {10.1186/1471-2105-7-88}, volume = {7}, year = {2006}, } @inproceedings{3180, abstract = {One of the most exciting advances in early vision has been the development of efficient energy minimization algorithms. Many early vision tasks require labeling each pixel with some quantity such as depth or texture. While many such problems can be elegantly expressed in the language of Markov Random Fields (MRF's), the resulting energy minimization problems were widely viewed as intractable. Recently, algorithms such as graph cuts and loopy belief propagation (LBP) have proven to be very powerful: for example, such methods form the basis for almost all the top-performing stereo methods. Unfortunately, most papers define their own energy function, which is minimized with a specific algorithm of their choice. As a result, the tradeoffs among different energy minimization algorithms are not well understood. In this paper we describe a set of energy minimization benchmarks, which we use to compare the solution quality and running time of several common energy minimization algorithms. We investigate three promising recent methods - graph cuts, LBP, and tree-reweighted message passing - as well as the well-known older iterated conditional modes (ICM) algorithm. Our benchmark problems are drawn from published energy functions used for stereo, image stitching and interactive segmentation. We also provide a general-purpose software interface that allows vision researchers to easily switch between optimization methods with minimal overhead. We expect that the availability of our benchmarks and interface will make it significantly easier for vision researchers to adopt the best method for their specific problems. Benchmarks, code, results and images are available at http://vision.middlebury.edu/MRF.}, author = {Szeliski, Richard S and Zabih, Ramin and Scharstein, Daniel and Veksler, Olga and Vladimir Kolmogorov and Agarwala, Aseem and Tappen, Marshall F and Rother, Carsten}, pages = {16 -- 29}, publisher = {Springer}, title = {{A comparative study of energy minimization methods for Markov random fields}}, doi = {10.1007/11744047_2}, volume = {3952}, year = {2006}, } @inproceedings{3184, abstract = {Algorithms for discrete energy minimization play a fundamental role for low-level vision. Known techniques include graph cuts, belief propagation (BP) and recently introduced tree-reweighted message passing (TRW). So far, the standard benchmark for their comparison has been a 4-connected grid-graph arising in pixel-labelling stereo. This minimization problem, however, has been largely solved: recent work shows that for many scenes TRW finds the global optimum. Furthermore, it is known that a 4-connecled grid-graph is a poor stereo model since it does not take occlusions into account. We propose the problem of stereo with occlusions as a new test bed for minimization algorithms. This is a more challenging graph since it has much larger connectivity, and it also serves as a better stereo model. An attractive feature of this problem is that increased connectivity does not result in increased complexity of message passing algorithms. Indeed, one contribution of this paper is to show that sophisticated implementations of BP and TRW have the same time and memory complexity as that of 4-connecled grid-graph stereo. The main conclusion of our experimental study is that for our problem graph cut outperforms both TRW and BP considerably. TRW achieves consistently a lower energy than BP. However, as connectivity increases the speed of convergence of TRW becomes slower. Unlike 4-connected grids, the difference between the energy of the best optimization method and the lower bound of TRW appears significant. This shows the hardness of the problem and motivates future research.}, author = {Vladimir Kolmogorov and Rother, Carsten}, pages = {1 -- 15}, publisher = {Springer}, title = {{Comparison of energy minimization algorithms for highly connected graphs}}, doi = {10.1007/11744047_1}, volume = {3952 LNCS}, year = {2006}, } @article{3185, abstract = {This paper describes models and algorithms for the real-time segmentation of foreground from background layers in stereo video sequences. Automatic separation of layers from color/contrast or from stereo alone is known to be error-prone. Here, color, contrast, and stereo matching information are fused to infer layers accurately and efficiently. The first algorithm, Layered Dynamic Programming (LDP), solves stereo in an extended six-state space that represents both foreground/background layers and occluded regions. The stereo-match likelihood is then fused with a contrast-sensitive color model that is learned on-the-fly and stereo disparities are obtained by dynamic programming. The second algorithm, Layered Graph Cut (LGC), does not directly solve stereo. Instead, the stereo match likelihood is marginalized over disparities to evaluate foreground and background hypotheses and then fused with a contrast-sensitive color model like the one used in LDP. Segmentation is solved efficiently by ternary graph cut. Both algorithms are evaluated with respect to ground truth data and found to have similar performance, substantially better than either stereo or color/contrast alone. However, their characteristics with respect to computational efficiency are rather different. The algorithms are demonstrated in the application of background substitution and shown to give good quality composite video output.}, author = {Vladimir Kolmogorov and Criminisi, Antonio and Blake, Andrew and Cross, Geoffrey and Rother, Carsten}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, number = {9}, pages = {1480 -- 1492}, publisher = {IEEE}, title = {{Probabilistic fusion of stereo with color and contrast for bilayer segmentation}}, doi = {10.1109/TPAMI.2006.193}, volume = {28}, year = {2006}, } @inproceedings{3186, abstract = {We introduce a new approach to modelling gradient flows of contours and surfaces. While standard variational methods (e.g. level sets) compute local interface motion in a differential fashion by estimating local contour velocity via energy derivatives, we propose to solve surface evolution PDEs by explicitly estimating integral motion of the whole surface. We formulate an optimization problem directly based on an integral characterization of gradient flow as an infinitesimal move of the (whole) surface giving the largest energy decrease among all moves of equal size. We show that this problem can be efficiently solved using recent advances in algorithms for global hypersurface optimization [4, 2, 11]. In particular, we employ the geo-cuts method [4] that uses ideas from integral geometry to represent continuous surfaces as cuts on discrete graphs. The resulting interface evolution algorithm is validated on some 2D and 3D examples similar to typical demonstrations of level-set methods. Our method can compute gradient flows of hypersurfaces with respect to a fairly general class of continuous functional and it is flexible with respect to distance metrics on the space of contours/surfaces. Preliminary tests for standard L2 distance metric demonstrate numerical stability, topological changes and an absence of any oscillatory motion.}, author = {Boykov, Yuri and Vladimir Kolmogorov and Cremers, Daniel and Delong, Andrew}, pages = {409 -- 422}, publisher = {Springer}, title = {{An integral solution to surface evolution PDEs via geo cuts}}, doi = {10.1007/11744078_32}, volume = {3953}, year = {2006}, } @inbook{3404, author = {Harald Janovjak and Sawhney, Ravi K and Stark, Martin and Mueller, Daniel J}, booktitle = {Techniques in Microscopy for Biomedical Applications}, pages = {213 -- 284}, publisher = {World Scientific Publishing}, title = {{Atomic force microscopy}}, volume = {2}, year = {2006}, } @article{3413, abstract = {Despite their crucial importance for cellular function, little is known about the folding mechanisms of membrane proteins. Recently details of the folding energy landscape were elucidated by atomic force microscope (AFM)-based single molecule force spectroscopy. Upon unfolding and extraction of individual membrane proteins energy barriers in structural elements such as loops and helices were mapped and quantified with the precision of a few amino acids. Here we report on the next logical step: controlled refolding of single proteins into the membrane. First individual bacteriorhodopsin monomers were partially unfolded and extracted from the purple membrane by pulling at the C-terminal end with an AFM tip. Then by gradually lowering the tip, the protein was allowed to refold into the membrane while the folding force was recorded. We discovered that upon refolding certain helices are pulled into the membraneagainst a sizable externalforce of several tens of picoNewton. From the mechanical work, which the helix performs on the AFM cantilever, we derive an upper limit for the Gibbs free folding energy. Subsequent unfolding allowed us to analyze the pattern of unfolding barriers and corroborate that the protein had refolded into the native state.}, author = {Kessler, Max and Gottschalk, Kay E and Harald Janovjak and Mueller, Daniel J and Gaub, Hermann}, journal = {Journal of Molecular Biology}, number = {2}, pages = {644 -- 654}, publisher = {Elsevier}, title = {{Bacteriorhodopsin folds into the membrane against an external force}}, doi = {10.1016/j.jmb.2005.12.065}, volume = {357}, year = {2006}, } @article{3414, abstract = {Mechanisms of folding and misfolding of membrane proteins are of interest in cell biology. Recently, we have established single-molecule force spectroscopy to observe directly the stepwise folding of the Na+/H+antiporter NhaA from Escherichia coli in vitro. Here, we improved this approach significantly to track the folding intermediates of asingle NhaA polypeptide forming structural segments such as the Na+-binding site, transmembrane α-helices, and helical pairs. The folding rates of structural segments ranged from 0.31 s−1 to 47 s−1, providing detailed insight into a distinct folding hierarchy of an unfolded polypeptide into the native membrane protein structure. In some cases, however, the folding chain formed stable and kinetically trapped non-native structures, which could be assigned to misfolding events of the antiporter.}, author = {Kedrov, Alexej and Harald Janovjak and Ziegler, Christine and Kühlbrandt, Werner and Mueller, Daniel J}, journal = {Journal of Molecular Biology}, number = {1}, pages = {2 -- 8}, publisher = {Elsevier}, title = {{Observing folding pathways and kinetics of a single sodium-proton antiporter from Escherichia coli}}, doi = {10.1016/j.jmb.2005.10.028}, volume = {355}, year = {2006}, } @misc{3415, author = {Harald Janovjak and Kedrov, Alexej and Cisneros, David and Sapra, Tanuj K and Struckmeier, Jens and Mueller, Daniel J}, booktitle = {Neurobiology of Aging}, pages = {546 -- 561}, publisher = {Elsevier}, title = {{Imaging and detecting molecular interactions of single membrane proteins}}, doi = {10.1016/j.neurobiolaging.2005.03.031}, volume = {27}, year = {2006}, } @article{3437, abstract = {The mutational landscape model is a theoretical model describing sequence evolution in natural populations. However, recent experimental work has begun to test its predictions in laboratory populations of microbes. Several of these studies have focused on testing the prediction that the effects of beneficial mutations should be roughly exponentially distributed. The prediction appears to be borne out by most of these studies, at least qualitatively. Another study showed that a modified version of the model was able to predict, with reasonable accuracy, which of a ranked set of beneficial alleles will be fixed next. Although it remains to be seen whether the mutational landscape model adequately describes adaptation in organisms other than microbes, together these studies suggest that adaptive evolution has surprisingly general properties that can be successfully captured by theoretical models.}, author = {Betancourt, Andrea J and Jonathan Bollback}, journal = {Current Opinion in Genetics & Development}, number = {6}, pages = {618 -- 623}, publisher = {Elsevier}, title = {{Fitness effects of beneficial mutations: the mutational landscape model in experimental evolution}}, doi = {10.1016/j.gde.2006.10.006}, volume = {16}, year = {2006}, } @unpublished{3431, abstract = {Ising models with pairwise interactions are the least structured, or maximum-entropy, probability distributions that exactly reproduce measured pairwise correlations between spins. Here we use this equivalence to construct Ising models that describe the correlated spiking activity of populations of 40 neurons in the retina, and show that pairwise interactions account for observed higher-order correlations. By first finding a representative ensemble for observed networks we can create synthetic networks of 120 neurons, and find that with increasing size the networks operate closer to a critical point and start exhibiting collective behaviors reminiscent of spin glasses.}, author = {Gasper Tkacik and Schneidman, E. and Berry, M. J. and Bialek, William S}, booktitle = {ArXiv}, pages = {1 -- 4}, publisher = {ArXiv}, title = {{Ising models for networks of real neurons}}, year = {2006}, } @inproceedings{3449, abstract = {We argue that games are expressive enough to encompass (history-based) access control, (resource) usage control (e.g., dynamic adaptive access control of reputation systems), accountability based controls (e.g., insurance), controls derived from rationality assumptions on participants (e.g., network mechanisms), and their composition. Building on the extensive research into games, we demonstrate that this expressive power coexists with a formal analysis framework comparable to that available for access control.}, author = {Krishnendu Chatterjee and Jagadeesan, Rhada and Pitcher, Corin}, pages = {70 -- 82}, publisher = {IEEE}, title = {{Games for controls}}, doi = {10.1109/CSFW.2006.14}, year = {2006}, } @misc{3463, abstract = {It is widely accepted that the hippocampus plays a major role in learning and memory. The mossy fiber synapse between granule cells in the dentate gyrus and pyramidal neurons in the CA3 region is a key component of the hippocampal trisynaptic circuit. Recent work, partially based on direct presynaptic patch-clamp recordings from hippocampal mossy fiber boutons, sheds light on the mechanisms of synaptic transmission and plasticity at mossy fiber synapses. A high Na(+) channel density in mossy fiber boutons leads to a large amplitude of the presynaptic action potential. Together with the fast gating of presynaptic Ca(2+) channels, this generates a large and brief presynaptic Ca(2+) influx, which can trigger transmitter release with high efficiency and temporal precision. The large number of release sites, the large size of the releasable pool of vesicles, and the huge extent of presynaptic plasticity confer unique strength to this synapse, suggesting a large impact onto the CA3 pyramidal cell network under specific behavioral conditions. The characteristic properties of the hippocampal mossy fiber synapse may be important for pattern separation and information storage in the dentate gyrus-CA3 cell network.}, author = {Bischofberger, Joseph and Engel, Dominique and Frotscher, Michael and Peter Jonas}, booktitle = {Pflugers Archiv : European Journal of Physiology}, number = {3}, pages = {361 -- 372}, publisher = {Springer}, title = {{Timing and efficacy of transmitter release at mossy fiber synapses in the hippocampal network. (Review)}}, doi = {10.1007/s00424-006-0093-2}, volume = {453}, year = {2006}, } @inproceedings{3499, abstract = {We study infinite stochastic games played by n-players on a finite graph with goals specified by sets of infinite traces. The games are concurrent (each player simultaneously and independently chooses an action at each round), stochastic (the next state is determined by a probability distribution depending on the current state and the chosen actions), infinite (the game continues for an infinite number of rounds), nonzero-sum (the players’ goals are not necessarily conflicting), and undiscounted. We show that if each player has an upward-closed objective, then there exists an ε-Nash equilibrium in memoryless strategies, for every ε>0; and exact Nash equilibria need not exist. Upward-closure of an objective means that if a set Z of infinitely repeating states is winning, then all supersets of Z of infinitely repeating states are also winning. Memoryless strategies are strategies that are independent of history of plays and depend only on the current state. We also study the complexity of finding values (payoff profile) of an ε-Nash equilibrium. We show that the values of an ε-Nash equilibrium in nonzero-sum concurrent games with upward-closed objectives for all players can be computed by computing ε-Nash equilibrium values of nonzero-sum concurrent games with reachability objectives for all players and a polynomial procedure. As a consequence we establish that values of an ε-Nash equilibrium can be computed in TFNP (total functional NP), and hence in EXPTIME. }, author = {Krishnendu Chatterjee}, pages = {271 -- 286}, publisher = {Springer}, title = {{Nash equilibrium for upward-closed objectives}}, doi = {10.1007/11874683_18}, volume = {4207}, year = {2006}, } @inproceedings{3500, abstract = {The classical algorithm for solving Bu ̈chi games requires time O(n · m) for game graphs with n states and m edges. For game graphs with constant outdegree, the best known algorithm has running time O(n2/logn). We present two new algorithms for Bu ̈chi games. First, we give an algorithm that performs at most O(m) more work than the classical algorithm, but runs in time O(n) on infinitely many graphs of constant outdegree on which the classical algorithm requires time O(n2). Second, we give an algorithm with running time O(n · m · log δ(n)/ log n), where 1 ≤ δ(n) ≤ n is the outdegree of the game graph. Note that this algorithm performs asymptotically better than the classical algorithm if δ(n) = O(log n).}, author = {Krishnendu Chatterjee and Thomas Henzinger and Piterman, Nir}, publisher = {ACM}, title = {{Algorithms for Büchi Games}}, year = {2006}, } @misc{3510, abstract = {Embodiments automatically generate an accurate network of watertight NURBS patches from polygonal models of objects while automatically detecting and preserving character lines thereon. These embodiments generate from an initial triangulation of the surface, a hierarchy of progressively coarser triangulations of the surface by performing a sequence of edge contractions using a greedy algorithm that selects edge contractions by their numerical properties. Operations are also performed to connect the triangulations in the hierarchy using homeomorphisms that preserve the topology of the initial triangulation in the coarsest triangulation. A desired quadrangulation of the surface can then be generated by homeomorphically mapping edges of a coarsest triangulation in the hierarchy back to the initial triangulation. This quadrangulation is topologically consistent with the initial triangulation and is defined by a plurality of quadrangular patches. These quadrangular patches are linked together by a (U, V) mesh that is guaranteed to be continuous at patch boundaries. A grid is then preferably fit to each of the quadrangles in the resulting quadrangulation by decomposing each of the quadrangles into k.sup.2 smaller quadrangles. A watertight NURBS model may be generated from the resulting quadrangulation.}, author = {Edelsbrunner, Herbert and Fu, Ping and Nekhayev, Dmitry and Facello, Michael and Williams, Steven}, title = {{Method, apparatus and computer program products for automatically generating NURBS models of triangulated surfaces using homeomorphism}}, year = {2006}, } @misc{3511, abstract = {Methods, apparatus and computer program products provide efficient techniques for designing and printing shells of hearing-aid devices with a high degree of quality assurance and reliability and with a reduced number of manual and time consuming production steps and operations. These techniques also preferably provide hearing-aid shells having internal volumes that can approach a maximum allowable ratio of internal volume relative to external volume. These high internal volumes facilitate the inclusion of hearing-aid electrical components having higher degrees of functionality and/or the use of smaller and less conspicuous hearing-aid shells. A preferred method includes operations to generate a watertight digital model of a hearing-aid shell by thickening a three-dimensional digital model of a shell surface in a manner that eliminates self-intersections and results in a thickened model having an internal volume that is a high percentage of an external volume of the model. }, author = {Fu, Ping and Nekhayev, Dmitry and Edelsbrunner, Herbert}, title = {{Manufacturing methods and systems for rapid production of hearing-aid shells}}, year = {2006}, } @misc{3512, abstract = {Methods, apparatus and computer program products provide efficient techniques for reconstructing surfaces from data point sets. These techniques include reconstructing surfaces from sets of scanned data points that have preferably undergone preprocessing operations to improve their quality by, for example, reducing noise and removing outliers. These techniques include reconstructing a dense and locally two-dimensionally distributed 3D point set (e.g., point cloud) by merging stars in two-dimensional weighted Delaunay triangulations within estimated tangent planes. The techniques include determining a plurality of stars from a plurality of points p.sub.i in a 3D point set S that at least partially describes the 3D surface, by projecting the plurality of points p.sub.i onto planes T.sub.i that are each estimated to be tangent about a respective one of the plurality of points p.sub.i. The plurality of stars are then merged into a digital model of the 3D surface.}, author = {Fletcher, Yates and Gloth, Tobias and Edelsbrunner, Herbert and Fu, Ping}, title = {{Method, apparatus and computer products that reconstruct surfaces from data points}}, year = {2006}, } @article{3545, abstract = {The functional organization of the basal ganglia ( BG) is often defined according to one of two opposing schemes. The first proposes multiple, essentially independent channels of information processing. The second posits convergence and lateral integration of striatal channels at the level of the globus pallidus ( GP). We tested the hypothesis that these proposed aspects of functional connectivity within the striatopallidal axis are dynamic and related to brain state. Local field potentials ( LFPs) were simultaneously recorded from multiple sites in striatum and GP in anesthetized rats during slow-wave activity( SWA) and during global activation evoked by sensory stimulation. Functional connectivity was inferred from comparative analyses of the internuclear and intranuclear coherence between bipolar derivations of LFPs. During prominent SWA, as shown in the electrocorticogram and local field potentials in the basal ganglia, intranuclear coherence, and, thus, lateral functional connectivity within striatum or globus pallidus was relatively weak. Furthermore, the temporal coupling of LFPs recorded across these two nuclei involved functional convergence at the level of GP. Global activation, indicated by a loss of SWA, was accompanied by a rapid functional reorganization of the striatopallidal axis. Prominent lateral functional connectivity developed within GP and, to a significantly more constrained spatial extent, striatum. Additionally, functional convergence on GP was no longer apparent, despite increased internuclear coherence. These data demonstrate that functional connectivity within the BG is highly dynamic and suggest that the relative expression of organizational principles, such as parallel, independent processing channels, striatopallidal convergence, and lateral integration within BG nuclei, is dependent on brain state.}, author = {Magill,Peter J and Pogosyan,Alek and Sharott,Andrew and Jozsef Csicsvari and Bolam, John Paul and Brown,Peter}, journal = {Journal of Neuroscience}, number = {23}, pages = {6318 -- 6329}, publisher = {Society for Neuroscience}, title = {{Changes in functional connectivity within the rat striatopallidal axis during global brain activation in vivo}}, doi = {10.1523/​JNEUROSCI.0620-06.2006}, volume = {26}, year = {2006}, } @inproceedings{3559, abstract = {Persistent homology is the mathematical core of recent work on shape, including reconstruction, recognition, and matching. Its per- tinent information is encapsulated by a pairing of the critical values of a function, visualized by points forming a diagram in the plane. The original algorithm in [10] computes the pairs from an ordering of the simplices in a triangulation and takes worst-case time cubic in the number of simplices. The main result of this paper is an algorithm that maintains the pairing in worst-case linear time per transposition in the ordering. A side-effect of the algorithm’s anal- ysis is an elementary proof of the stability of persistence diagrams [7] in the special case of piecewise-linear functions. We use the algorithm to compute 1-parameter families of diagrams which we apply to the study of protein folding trajectories.}, author = {Cohen-Steiner, David and Herbert Edelsbrunner and Morozov, Dmitriy}, pages = {119 -- 126}, publisher = {ACM}, title = {{Vines and vineyards by updating persistence in linear time}}, doi = {10.1145/1137856.1137877}, year = {2006}, } @inproceedings{3560, abstract = {We continue the study of topological persistence [5] by investigat- ing the problem of simplifying a function f in a way that removes topological noise as determined by its persistence diagram [2]. To state our results, we call a function g an ε-simplification of another function f if ∥f − g∥∞ ≤ ε, and the persistence diagrams of g are the same as those of f except all points within L1-distance at most ε from the diagonal have been removed. We prove that for func- tions f on a 2-manifold such ε-simplification exists, and we give an algorithm to construct them in the piecewise linear case.}, author = {Herbert Edelsbrunner and Morozov, Dmitriy and Pascucci, Valerio}, pages = {127 -- 134}, publisher = {ACM}, title = {{Persistence-sensitive simplification of functions on 2-manifolds}}, doi = {10.1145/1137856.1137878}, year = {2006}, } @misc{3594, author = {Pemberton, Josephine M and Swanson, Graeme M and Nicholas Barton and Livingstone, Suzanne R and Senn, Helen V}, booktitle = {Deer}, number = {9}, pages = {22 -- 26}, publisher = {BDS }, title = {{Hybridisation between red and sika deer in Scotland}}, volume = {13}, year = {2006}, } @article{3609, abstract = {Bombina bombina and B. variegata are two anciently diverged toad taxa that have adapted to different breeding habitats yet hybridize freely in zones of overlap where their parapatric distributions meet. Here, we report on a joint genetic and ecological analysis of a hybrid zone in the vicinity of Stryi in western Ukraine. We used five unlinked allozyme loci, two nuclear single nucleotide polymorphisms and a mitochondrial DNA haplotype as genetic markers. Parallel allele frequency clines with a sharp central step occur across a sharp ecotone, where transitions in aquatic habitat, elevation, and terrestrial vegetation coincide. The width of the hybrid zone, estimated as the inverse of the maximum gradient in allele frequency, is 2.3 km. This is the smallest of four estimates derived from different clinal transects across Europe. We argue that the narrow cline near Stryi is mainly due to a combination of habitat distribution and habitat preference. Adult toads show a preference for either ponds (B. bombina) or puddles (B. variegata), which is known to affect the distribution of genotypes within the hybrid zones. At Stryi, it should cause a reduction of the dispersal rate across the ecotone and thus narrow the cline. A detailed comparison of all five intensively studied Bombina transects lends support to the hypothesis that habitat distribution plus habitat preference can jointly affect the structure of hybrid zones and, ultimately, the resulting barriers to gene flow between differentiated gene pools. This study also represents a resampling of an area that was last studied more than 70 years ago. Our allele-frequency clines largely coincide with those that were described then on the basis of morphological variation. However, we found asymmetrical introgression of B. variegata genes into B. bombina territory along the bank of a river.}, author = {Yanchukov, Alexey and Hofman, Sebastian and Szymura, Jacek M and Mezhzherin, Sergey V and Morozov-Leonov, Sviatoslav and Nicholas Barton and Nürnberger, Beate}, journal = {Evolution; International Journal of Organic Evolution}, number = {3}, pages = {583 -- 600}, publisher = {Wiley-Blackwell}, title = {{Hybridization of Bombina bombina and B. variegata (Anura, Discoglossidae) at a sharp ecotone in western Ukraine: comparisons across transects and over time}}, doi = {10.1111/j.0014-3820.2006.tb01139.x}, volume = {60}, year = {2006}, } @article{3608, abstract = {We study the evolution of inversions that capture locally adapted alleles when two populations are exchanging migrants or hybridizing. By suppressing recombination between the loci, a new inversion can spread. Neither drift nor coadaptation between the alleles (epistasis) is needed, so this local adaptation mechanism may apply to a broader range of genetic and demographic situations than alternative hypotheses that have been widely discussed. The mechanism can explain many features observed in inversion systems. It will drive an inversion to high frequency if there is no countervailing force, which could explain fixed differences observed between populations and species. An inversion can be stabilized at an intermediate frequency if it also happens to capture one or more deleterious recessive mutations, which could explain polymorphisms that are common in some species. This polymorphism can cycle in frequency with the changing selective advantage of the locally favored alleles. The mechanism can establish underdominant inversions that decrease heterokaryotype fitness by several percent if the cause of fitness loss is structural, while if the cause is genic there is no limit to the strength of underdominance that can result. The mechanism is expected to cause loci responsible for adaptive species-specific differences to map to inversions, as seen in recent QTL studies. We discuss data that support the hypothesis, review other mechanisms for inversion evolution, and suggest possible tests. }, author = {Kirkpatrick, Mark and Nicholas Barton}, journal = {Genetics}, number = {1}, pages = {419 -- 434}, publisher = {Genetics Society of America}, title = {{Chromosome inversions, local adaptation, and speciation}}, doi = {10.1534/genetics.105.047985}, volume = {173}, year = {2006}, } @article{3610, abstract = {For a model of diallelic loci with arbitrary epistasis, Barton and Turelli [2004. Effects of genetic drift on variance components under a general model of epistasis. Evolution 58, 2111–2132] gave results for variances among and within replicate lines obtained by inbreeding without selection. Here, we discuss the relation between their population genetic methods and classical quantitative genetic arguments. In particular, we consider the case of no dominance using classical identity by descent arguments, which generalizes their results from two alleles to multiple alleles. To clarify the connections between the alternative methods, we obtain the same results using an intermediate method, which explicitly identifies the statistical effects of sets of loci. We also discuss the effects of population bottlenecks on covariances among relatives.}, author = {Hill, William G and Nicholas Barton and Turelli, Michael}, journal = {Theoretical Population Biology}, number = {1}, pages = {56 -- 62}, publisher = {Academic Press}, title = {{Prediction of effects of genetic drift on variance components under a general model of epistasis}}, doi = {10.1016/j.tpb.2005.10.001}, volume = {70}, year = {2006}, } @inproceedings{3679, abstract = {This paper describes a new system for "Finding Satellite Tracks” in astronomical images based on the modern geometric approach. There is an increasing need of using methods with solid mathematical and statistical foundation in astronomical image processing. Where the computational methods are serving in all disciplines of science, they are becoming popular in the field of astronomy as well. Currently different computational systems are required to be numerically optimized before to get applied on astronomical images. So at present there is no single system which solves the problems of astronomers using computational methods based on modern approaches. The system "Finding Satellite Tracks” is based on geometric matching method "Recognition by Adaptive Subdivision of Transformation Space (RAST)".}, author = {Ali,Haider and Christoph Lampert and Breuel,Thomas M}, pages = {892 -- 901}, publisher = {Springer}, title = {{Satellite tracks removal in astronomical images}}, doi = {10.1007/11892755_92}, volume = {4225}, year = {2006}, } @inproceedings{3677, abstract = {We propose a video retrieval framework based on a novel combination of spatiograms and the Jensen-Shannon divergence, and validate its performance in two quantitative experiments on TRECVID BBC Rushes data. In the first experiment, color-based methods are tested by grouping redundant shots in an unsupervised clustering. Results of the second experiment show that motion-based spatiograms make a promising fast, compressed-domain descriptor for the detection of interview scenes.}, author = {Ulges, Adrian and Christoph Lampert and Keysers,Daniel}, pages = {1 -- 10}, publisher = {NIST (National Institute of Standards and Technology, US Department of Commerce)}, title = {{Spatiogram-based shot distances for video retrieval}}, year = {2006}, } @inproceedings{3680, abstract = {The detection of counterfeit in printed documents is currently based mainly on built-in security features or on human expertise. We propose a classification system that supports non-expert users to distinguish original documents from PC-made forgeries by analyzing the printing technique used. Each letter in a document is classified using a support vector machine that has been trained to distinguish laser from inkjet printouts. A color-coded visualization helps the user to interpret the per-letter classification results}, author = {Christoph Lampert and Mei,Lin and Breuel,Thomas M}, pages = {639 -- 634}, publisher = {IEEE}, title = {{Printing technique classification for document counterfeit detection}}, doi = {10.1109/ICCIAS.2006.294214}, volume = {1}, year = {2006}, } @article{3695, abstract = {We give an analytical and geometrical treatment of what it means to separate a Gaussian kernel along arbitrary axes in Ropfn, and we present a separation scheme that allows us to efficiently implement anisotropic Gaussian convolution filters for data of arbitrary dimensionality. Based on our previous analysis we show that this scheme is optimal with regard to the number of memory accesses and interpolation operations needed. The proposed method relies on nonorthogonal convolution axes and works completely in image space. Thus, it avoids the need for a fast Fourier transform (FFT)-subroutine. Depending on the accuracy and speed requirements, different interpolation schemes and methods to implement the one-dimensional Gaussian (finite impulse response and infinite impulse response) can be integrated. Special emphasis is put on analyzing the performance and accuracy of the new method. In particular, we show that without any special optimization of the source code, it can perform anisotropic Gaussian filtering faster than methods relying on the FFT.}, author = {Christoph Lampert and Wirjadi,Oliver}, journal = {IEEE Transactions on Image Processing (TIP)}, number = {11}, pages = {3501 -- 3513}, publisher = {IEEE}, title = {{An optimal non-orthogonal separation of the anisotropic Gaussian convolution filter}}, doi = { 10.1109/TIP.2006.877501 }, volume = {15}, year = {2006}, } @inproceedings{3693, abstract = {Gaussian filtering in one, two or three dimensions is among the most commonly needed tasks in signal and image processing. Finite impulse response filters in the time domain with Gaussian masks are easy to implement in either floating or fixed point arithmetic, because Gaussian kernels are strictly positive and bounded. But these implementations are slow for large images or kernels. With the recursive IIR-filters and FFT-based methods, there are at least two alternative methods to perform Gaussian filtering in a faster way, but so far they are only applicable when floating-point hardware is available. In this paper, a fixed-point implementation of recursive Gaussian filtering is discussed and applied to isotropic and anisotropic image filtering by making use of a non-orthogonal separation scheme of the Gaussian filter.}, author = {Christoph Lampert and Wirjadi,Oliver}, pages = {1565 -- 1568}, publisher = {IEEE}, title = {{Anisotropic Gaussian filtering using fixed point arithmetic}}, doi = {10.1109/ICIP.2006.312606}, year = {2006}, } @inproceedings{3692, author = {Keysers,Daniel and Christoph Lampert and Breuel,Thomas M}, publisher = {SPIE}, title = {{Color image dequantization by constrained diffusion}}, doi = {10.1117/12.648713}, volume = {6058}, year = {2006}, } @article{3729, abstract = {Measuring the visco-elastic properties of biological macromolecules constitutes an important step towards the understanding of dynamic biological processes, such as cell adhesion, muscle function, or plant cell wall stability. Force spectroscopy techniques based on the atomic force microscope (AFM) are increasingly used to study the complex visco-elastic response of (bio-)molecules on a single-molecule level. These experiments either require that the AFM cantilever is actively oscillated or that the molecule is clamped at constant force to monitor thermal cantilever motion. Here we demonstrate that the visco-elasticity of single bio-molecules can readily be extracted from the Brownian cantilever motion during conventional force-extension measurements. It is shown that the characteristics of the cantilever determine the signal-to-noise (S/N) ratio and time resolution. Using a small cantilever, the visco-elastic properties of single dextran molecules were resolved with a time resolution of 8.3 ms. The presented approach can be directly applied to probe the dynamic response of complex bio-molecular systems or proteins in force-extension experiments.}, author = {Bippes, Christian A and Humphris, Andrew D and Stark, Martin and Mueller, Daniel J and Harald Janovjak}, journal = {European Biophysics Journal}, number = {3}, pages = {287 -- 292}, publisher = {Springer}, title = {{Direct measurement of single-molecule visco-elasticity in atomic force microscope force-extension experiments}}, doi = {10.1007/s00249-005-0023-9}, volume = {35}, year = {2006}, } @article{3728, abstract = {Mechanical unfolding of single bacteriorhodopsins from a membrane bilayer is studied using molecular dynamics simulations. The initial conformation of the lipid membrane is determined through all-atom simulations and then its coarse-grained representation is used in the studies of stretching. A Go-like model with a realistic contact map and with Lennard–Jones contact interactions is applied to model the protein–membrane system. The model qualitatively reproduces the experimentally observed differences between force-extension patterns obtained on bacteriorhodopsin at different temperatures and predicts a lack of symmetry in the choice of the terminus to pull by. It also illustrates the decisive role of the interactions of the protein with the membrane in determining the force pattern and thus the stability of transmembrane proteins.}, author = {Cieplak, Marek and Filipek, Sławomir and Harald Janovjak and Krzysko, Krystiana A}, journal = {Biochimica et Biophysica Acta (BBA) - Biomembranes}, number = {4}, pages = {537 -- 544}, publisher = {Elsevier}, title = {{Pulling single bacteriorhodopsin out of a membrane: Comparison of simulation and experiment}}, doi = {10.1016/j.bbamem.2006.03.028}, volume = {1758}, year = {2006}, } @inbook{3722, author = {Harald Janovjak and Mueller, Daniel J}, booktitle = {Bioanalytik}, publisher = {Spektrum Akademischer Verlag}, title = {{Rastersondenmikroskopie}}, year = {2006}, } @article{3755, abstract = {A primitive example of adaptation in gene expression is the balance between the rate of synthesis and degradation of cellular RNA, which allows rapid responses to environmental signals. Here, we investigate how multidrug efflux pump systems mediate the dynamics of a simple drug-inducible system in response to a steady level of inducer. Using fluorescence correlation spectroscopy, we measured in real time within a single bacterium the transcription activity at the RNA level of the acrAB-TolC multidrug efflux pump system. When cells are exposed to constant level of anhydrotetracycline inducer and are adsorbed onto a poly-L-lysine-coated surface, we found that the acrAB-TolC promoter is steadily active. We also monitored the activity of the tet promoter to characterize the effect of this efflux system on the dynamics of drug-inducible transcription. We found that the transcriptional response of the tet promoter to a steady level of aTc rises and then falls back to its preinduction level. The rate of RNA degradation was constant throughout the transcriptional pulse, indicating that the modulation of intracellular inducer concentration alone can produce this pulsating response. Single-cell experiments together with numerical simulations suggest that such pulsating response in drug-inducible genetic systems is a property emerging from the dependence of drug-inducible transcription on multidrug efflux systems.}, author = {Le,Thuc T. and Emonet,Thierry and Harlepp, Sébastien and Calin Guet and Cluzel,Philippe}, journal = {Biophysical Journal}, number = {9}, pages = {3315 -- 3321}, publisher = {Biophysical Society}, title = {{Dynamical determinants of drug-inducible gene expression in a single bacterium}}, doi = {10.1529/biophysj.105.073353}, volume = {90}, year = {2006}, } @inproceedings{3758, abstract = {Control of physical simulation has become a popular topic in the field of computer graphics. Keyframe control has been applied to simulations of rigid bodies, smoke, liquid, flocks, and finite element-based elastic bodies. In this paper, we create a framework for controlling systems of interacting particles -- paying special attention to simulations of cloth and flocking behavior. We introduce a novel integrator-swapping approximation in order to apply the adjoint method to linearized implicit schemes appropriate for cloth simulation. This allows the control of cloth while avoiding computationally infeasible derivative calculations. Meanwhile, flocking control using the adjoint method is significantly more efficient than currently-used methods for constraining group behaviors, allowing the controlled simulation of greater numbers of agents in fewer optimization iterations.}, author = {Wojtan, Christopher J and Mucha, Peter and Turk, Greg}, pages = {15 -- 23}, publisher = {ACM}, title = {{Keyframe control of complex particle systems using the adjoint method}}, year = {2006}, } @article{3818, abstract = {Rigorous analysis of synaptic transmission in the central nervous system requires access to presynaptic terminals. However, cortical terminals have been largely inaccessible to presynaptic patch-clamp recording, due to their small size. Using improved patch-clamp techniques in brain slices, we recorded from mossy fiber terminals in the CA3 region of the hippocampus, which have a diameter of 2-5 microm. The major steps of improvement were the enhanced visibility provided by high-numerical aperture objectives and infrared illumination, the development of vibratomes with minimal vertical blade vibrations and the use of sucrose-based solutions for storage and cutting. Based on these improvements, we describe a protocol that allows us to routinely record from hippocampal mossy fiber boutons. Presynaptic recordings can be obtained in slices from both rats and mice. Presynaptic recordings can be also obtained in slices from transgenic mice in which terminals are labeled with enhanced green fluorescent protein.}, author = {Bischofberger, Josef and Engel, Dominique and Li, Liyi and Geiger, Jörg R and Peter Jonas}, journal = {Nature Protocols}, number = {4}, pages = {2075 -- 81}, publisher = {Nature Publishing Group}, title = {{Patch-clamp recording from mossy fiber terminals in hippocampal slices}}, doi = {10.1038/nprot.2006.312 }, volume = {1}, year = {2006}, } @inproceedings{3890, abstract = {We consider two-player infinite games played on graphs. The games are concurrent, in that at each state the players choose their moves simultaneously and independently, and stochastic, in that the moves determine a probability distribution for the successor state. The value of a game is the maximal probability with which a player can guarantee the satisfaction of her objective. We show that the values of concurrent games with w-regular objectives expressed as parity conditions can be decided in NP boolean AND coNP. This result substantially improves the best known previous bound of 3EXPTIME. It also shows that the full class of concurrent parity games is no harder than the special case of turn-based stochastic reachability games, for which NP boolean AND coNP is the best known bound. While the previous, more restricted NP boolean AND coNP results for graph games relied on the existence of particularly simple (pure memoryless) optimal strategies, in concurrent games with parity objectives optimal strategies may not exist, and epsilon-optimal strategies (which achieve the value of the game within a parameter epsilon > 0) require in general both randomization and infinite memory. Hence our proof must rely on a more detailed analysis of strategies and, in addition to the main result, yields two results that are interesting on their own. First, we show that there exist epsilon-optimal strategies that in the limit coincide with memoryless strategies; this parallels the celebrated result of Mertens-Neyman for concurrent games with limit-average objectives. Second, we complete the characterization of the memory requirements for epsilon-optimal strategies for concurrent games with parity conditions, by showing that memoryless strategies suffice for epsilon-optimality for coBachi conditions.}, author = {Krishnendu Chatterjee and de Alfaro, Luca and Thomas Henzinger}, pages = {678 -- 687}, publisher = {SIAM}, title = {{The complexity of quantitative concurrent parity games}}, doi = {10.1145/1109557.1109631}, year = {2006}, } @inproceedings{3889, 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 Buchi 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}, pages = {287 -- 302}, publisher = {Springer}, title = {{Algorithms for omega-regular games with imperfect information}}, doi = {10.1007/11874683_19}, volume = {4207}, year = {2006}, } @inproceedings{3891, 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 (proceeds for infinite number of rounds). The analysis of concurrent stochastic games can be classified into: quantitative analysis, analyzing the optimum value of the game; and qualitative analysis, analyzing the set of 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 are strictly richer than 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, that states 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 Phi, for the player. We also show that the optimum values of zero-sum (strictly conflicting objectives) games with tail objectives can be related to equilibrium values of nonzero-sum (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 sub-class of one-player stochastic games (Markov decision processes).}, author = {Krishnendu Chatterjee}, pages = {256 -- 270}, publisher = {Springer}, title = {{Concurrent games with tail objectives}}, doi = {10.1007/11874683_17}, volume = {4207}, year = {2006}, } @inproceedings{3888, abstract = {A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with omega-regular winning conditions specified as Rabin or Streett objectives. These games are NP-complete and coNP-complete, respectively. The value of the game for a player at a state s given an objective Phi is the maximal probability with which the player can guarantee the satisfaction of Phi from s. We present a strategy-improvement algorithm to compute values in stochastic Rabin games, where an improvement step involves solving Markov decision processes (MDPs) and nonstochastic Rabin games. The algorithm also computes values for stochastic Streett games but does not directly yield an optimal strategy for Streett objectives. We then show how to obtain an optimal strategy for Streett objectives by solving certain nonstochastic Streett games.}, author = {Krishnendu Chatterjee and Thomas Henzinger}, pages = {375 -- 389}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Strategy improvement for stochastic Rabin and Streett games}}, doi = {10.1007/11817949_25}, volume = {4137}, year = {2006}, } @article{3908, abstract = {It is commonly believed that both the average length and the frequency of microsatellites correlate with genome size. We have estimated the frequency and the average length for 69 perfect dinucleotide microsatellites in an insect with an exceptionally large genome: Chorthippus biguttulus (Orthoptera, Acrididae). Dinucleotide microsatellites are not more frequent in C. biguttulus, but repeat arrays are 1.4 to 2 times longer than in other insect species. The average repeat number in C. biguttulus lies in the range of higher vertebrates. Natural populations are highly variable. At least 30 alleles per locus were found and the expected heterozygosity is above 0.95 at all three loci studied. In contrast, the observed heterozygosity is much lower (≤0.51), which could be caused by long null alleles.}, author = {Ustinova, Jana and Achmann, Roland and Cremer, Sylvia and Mayer, Frieder}, journal = {Journal of Molecular Evolution}, number = {2}, pages = {158 -- 167}, publisher = {Springer}, title = {{Long repeats in a huge gemome: microsatellite loci in the grasshopper Chorthippus biguttulus}}, doi = {10.1007/s00239-005-0022-6}, volume = {62}, year = {2006}, } @article{3934, abstract = {T cells develop in the thymus in a highly specialized cellular and extracellular microenvironment. The basement membrane molecule, laminin-5 (LN-5), is predominantly found in the medulla of the human thymic lobules. Using high-resolution light microscopy, we show here that LN-5 is localized in a bi-membranous conduit-like structure, together with other typical basement membrane components including collagen type IV, nidogen and perlecan. Other interstitial matrix components, such as fibrillin-1 or -2, tenascin-C or fibrillar collagen types, were also associated with these structures. Three-dimensional (3D) confocal microscopy suggested a tubular structure, whereas immunoelectron and transmission electron microscopy showed that the core of these tubes contained fibrillar collagens enwrapped by the LN-5-containing membrane. These medullary conduits are surrounded by thymic epithelial cells, which in vitro were found to bind LN-5, but also fibrillin and tenascin-C. Dendritic cells were also detected in close vicinity to the conduits. Both of these stromal cell types express major histocompatibility complex (MHC) class II molecules capable of antigen presentation. The conduits are connected to blood vessels but, with an average diameter of 2 mum, they are too small to transport cells. However, evidence is provided that smaller molecules such as a 10 kDa dextran, but not large molecules (>500 kDa), can be transported in the conduits. These results clearly demonstrate that a conduit system, which is also known from secondary lymphatic organs such as lymph nodes and spleen, is present in the medulla of the human thymus, and that it might serve to transport small blood-borne molecules or chemokines to defined locations within the medulla.}, author = {Drumea-Mirancea, Mihaela and Wessels, Johannes T and Müller, Claudia A and Essl, Mike and Eble, Johannes A and Tolosa, Eva and Koch, Manuel and Reinhardt, Dieter P and Michael Sixt and Sorokin, Lydia and Stierhof, York-Dieter and Schwarz, Heinz and Klein, Gerd}, journal = {Journal of Cell Science}, number = {Pt 7}, pages = {1396 -- 1405}, publisher = {Company of Biologists}, title = {{Characterization of a conduit system containing laminin-5 in the human thymus: a potential transport system for small molecules}}, doi = {10.1242/​jcs.02840}, volume = {119}, year = {2006}, } @article{3935, abstract = {Integrins regulate cell behavior through the assembly of multiprotein complexes at the site of cell adhesion. Parvins are components of such a multiprotein complex. They consist of three members (alpha-, beta-, and gamma-parvin), form a functional complex with integrin-linked kinase (ILK) and PINCH, and link integrins to the actin cytoskeleton. Whereas alpha- and beta-parvins are widely expressed, gamma-parvin has been reported to be expressed in hematopoietic organs. In the present study, we report the expression pattern of the parvins in hematopoietic cells and the phenotypic analysis of gamma-parvin-deficient mice. Whereas alpha-parvin is not expressed in hematopoietic cells, beta-parvin is only found in myeloid cells and gamma-parvin is present in both cells of the myeloid and lymphoid lineages, where it binds ILK. Surprisingly, loss of gamma-parvin expression had no effect on blood cell differentiation, proliferation, and survival and no consequence for the T-cell-dependent antibody response and lymphocyte and dendritic cell migration. These data indicate that despite the high expression of gamma-parvin in hematopoietic cells it must play a more subtle role for blood cell homeostasis.}, author = {Chu, Haiyan and Thievessen, Ingo and Michael Sixt and Lämmermann, Tim and Waisman, Ari and Braun, Attila and Noegel, Angelika A and Fässler, Reinhard}, journal = {Molecular and Cellular Biology}, number = {5}, pages = {1817 -- 1825}, publisher = {American Society for Microbiology}, title = {{γ-Parvin is dispensable for hematopoiesis, leukocyte trafficking, and T-cell-dependent antibody response}}, doi = {10.1128/MCB.26.5.1817-1825.2006}, volume = {26}, year = {2006}, } @article{3936, abstract = {At least eight of the twelve known members of the beta1 integrin family are expressed on hematopoietic cells. Among these, the VCAM-1 receptor alpha4beta1 has received most attention as a main factor mediating firm adhesion to the endothelium during blood cell extravasation. Therapeutic trials are ongoing into the use of antibodies and small molecule inhibitors to target this interaction and hence obtain anti-inflammatory effects. However, extravasation is only one possible process that is mediated by beta1 integrins and there is evidence that they also mediate leukocyte retention and positioning in the tissue, lymphocyte activation and possibly migration within the interstitium. Genetic mouse models where integrins are selectively deleted on blood cells have been used to investigate these functions and further studies will be invaluable to critically evaluate therapeutic trials.}, author = {Michael Sixt and Bauer, Martina and Lämmermann, Tim and Fässler, Reinhard}, journal = {Current Opinion in Cell Biology}, number = {5}, pages = {482 -- 490}, publisher = {Elsevier}, title = {{β1 integrins: zip codes and signaling relay for blood cells}}, doi = {10.1016/j.ceb.2006.08.007}, volume = {18}, year = {2006}, } @article{4140, abstract = {Wnt11 is a key signal, determining cell polarization and migration during vertebrate gastrulation. It is known that Wnt11 functionally interacts with several signaling components, the homologues of which control planar cell polarity in Drosophila melanogaster. Although in D. melanogaster these components are thought to polarize cells by asymmetrically localizing at the plasma membrane, it is not yet clear whether their subcellular localization plays a similarly important role in vertebrates. We show that in zebrafish embryonic cells, Wnt11 locally functions at the plasma membrane by accumulating its receptor, Frizzled 7, on adjacent sites of cell contacts. Wnt11-induced Frizzled 7 accumulations recruit the intracellular Wnt signaling mediator Dishevelled, as well as Wnt11 itself, and locally increase cell contact persistence. This increase in cell contact persistence is mediated by the local interaction of Wnt11, Frizzled 7, and the atypical cadherin Flamingo at the plasma membrane, and it does not require the activity of further downstream effectors of Wnt11 signaling, such as RhoA and Rok2. We propose that Wnt11, by interacting with Frizzled 7 and Flamingo, modulates local cell contact persistence to coordinate cell movements during gastrulation.}, author = {Witzel, Sabine and Zimyanin, Vitaly and Carreira Barbosa, Filipa and Tada, Masazumi and Heisenberg, Carl-Philipp J}, journal = {Journal of Cell Biology}, number = {5}, pages = {791 -- 802}, publisher = {Rockefeller University Press}, title = {{Wnt11 controls cell contact persistence by local accumulation of Frizzled 7 at the plasma membrane}}, doi = {10.1083/jcb.200606017}, volume = {175}, year = {2006}, } @article{4145, abstract = {The detection of microRNAs (miRNAs) at single-cell resolution is important for studying the role of these posttranscriptional regulators. Here, we use a dual-fluorescent green fluorescent protein (GFP)-reporter/monomeric red fluorescent protein (mRFP)-sensor (DFRS) plasmid, injected into zebrafish blastomeres or electroporated into defined tissues of mouse embryos in utero or ex utero, to monitor the dynamics of specific miRNAs in individual live cells. This approach reveals, for example, that in the developing mouse central nervous system,, miR-124a is expressed not only in postmitotic neurons but also in neuronal progenitor cells. Collectively, our results demonstrate that acute administration of DFRS plasmids.offers an alternative to previous in situ hybridization and transgenic approaches and allows the monitoring of miRNA appearance and disappearance in defined cell lineages during vertebrate development.}, author = {Tonelli, Davide and Calegari, Frederico and Fei, Ji and Nomura, Tadashi and Osumi, Noriko and Heisenberg, Carl-Philipp J and Huttner, Wieland}, journal = {Biotechniques}, number = {6}, pages = {727 -- 732}, publisher = {Informa Healthcare}, title = {{Single-cell detection of microRNAs in developing vertebrate embryos after acute administration of a dual-fluorescence reporter/sensor plasmid}}, doi = {10.2144/000112296}, volume = {41}, year = {2006}, } @article{4176, abstract = {During vertebrate gastrulation, a well-orchestrated series of morphogenetic changes leads to the formation of the three germ layers: the ectoderm, mesoderm and endoderm. The analysis of gene expression patterns during gastrulation has been central to the identification of genes involved in germ layer formation. However, many proteins are regulated on a translational or post-translational level and are thus undetectable by gene expression analysis. Therefore, we developed a 2D-gel-based comparative proteomic approach to target proteins involved in germ layer morphogenesis during zebrafish gastrulation. Proteomes of ectodermal and mesendodermal progenitor cells were compared and 35 significantly regulated proteins were identified by mass spectrometry, including several proteins with predicted functions in cytoskeletal organization. A comparison of our proteomic results with data obtained in an accompanying microarray-based gene expression analysis revealed no significant overlap, confirming the complementary nature of proteomics and transcriptomics. The regulation of ezrin2, which was identified based on a reduction in spot intensity in mesendodermal cells, was independently validated. Furthermore, we show that ezrin2 is activated by phosphorylation in mesendodermal cells and is required for proper germ layer morphogenesis. We demonstrate the feasibility of proteomics in zebrafish, concluding that proteomics is a valuable tool for analysis of early development.}, author = {Link, Vinzenz and Carvalho, Lara and Castanon, Irinka and Stockinger, Petra and Shevchenko, Andrej and Heisenberg, Carl-Philipp J}, journal = {Journal of Cell Science}, number = {10}, pages = {2073 -- 2083}, publisher = {Company of Biologists}, title = {{Identification of regulators of germ layer morphogenesis using proteomics in zebrafish}}, doi = {10.1242/jcs.02928}, volume = {119}, year = {2006}, } @article{4173, abstract = {Background: Zebrafish (D. rerio) has become a powerful and widely used model system for the analysis of vertebrate embryogenesis and organ development. While genetic methods are readily available in zebrafish, protocols for two dimensional (2D) gel electrophoresis and proteomics have yet to be developed. Results: As a prerequisite to carry out proteomic experiments with early zebrafish embryos, we developed a method to efficiently remove the yolk from large batches of embryos. This method enabled high resolution 2D gel electrophoresis and improved Western blotting considerably. Here, we provide detailed protocols for proteomics in zebrafish from sample preparation to mass spectrometry (MS), including a comparison of databases for MS identification of zebrafish proteins. Conclusion: The provided protocols for proteomic analysis of early embryos enable research to be taken in novel directions in embryogenesis.}, author = {Link, Vinzenz and Shevchenko, Andrej and Heisenberg, Carl-Philipp J}, journal = {BMC Developmental Biology}, pages = {1 -- 9}, publisher = {BioMed Central}, title = {{Proteomics of early zebrafish embryos}}, doi = {10.1186/1471-213X-6-1}, volume = {6}, year = {2006}, } @article{4178, abstract = {Detailed reconstruction of the spatiotemporal history of embryonic cells is key to understanding tissue formation processes but is often complicated by the large number of cells involved, particularly so in vertebrates. Through a combination of high-resolution time-lapse lineage tracing and antibody staining, we have analyzed the movement of mesencephalic and metencephalic cell populations in the early zebrafish embryo. To facilitate the analysis of our cell tracking data, we have created TracePilot, a software tool that allows interactive manipulation and visualization of tracking data. We demonstrate its utility by showing novel visualizations of cell movement in the developing zebrafish brain. TracePilot (http://www.mpi-cbg.de/tracepilot) is Java-based, available free of charge, and has a program structure that allows the incorporation of additional analysis tools.}, author = {Langenberg, Tobias and Dracz, Tadeusz and Oates, Andrew and Heisenberg, Carl-Philipp J and Brand, Michael}, journal = {Developmental Dynamics}, number = {4}, pages = {928 -- 933}, publisher = {Wiley-Blackwell}, title = {{Analysis and visualization of cell movement in the developing zebrafish brain}}, doi = {10.1002/dvdy.20692}, volume = {235}, year = {2006}, } @article{4184, abstract = {Epithelial morphogenesis depends on coordinated changes in cell shape, a process that is still poorly understood. During zebrafish epiboly and Drosophila dorsal closure, cell-shape changes at the epithelial margin are of critical importance. Here evidence is provided for a conserved mechanism of local actin and myosin 2 recruitment during theses events. It was found that during epiboly of the zebrafish embryo, the movement of the outer epithelium (enveloping layer) over the yolk cell surface involves the constriction of marginal cells. This process depends on the recruitment of actin and myosin 2 within the yolk cytoplasm along the margin of the enveloping layer. Actin and myosin 2 recruitment within the yolk cytoplasm requires the Ste20-like kinase Msn1, an orthologue of Drosophila Misshapen. Similarly, in Drosophila, actin and myosin 2 localization and cell constriction at the margin of the epidermis mediate dorsal closure and are controlled by Misshapen. Thus, this study has characterized a conserved mechanism underlying coordinated cell-shape changes during epithelial morphogenesis.}, author = {Köppen, Mathias and Fernández, Beatriz and Carvalho, Lara and Jacinto, António and Heisenberg, Carl-Philipp J}, journal = {Development}, number = {14}, pages = {2671 -- 2681}, publisher = {Company of Biologists}, title = {{Coordinated cell-shape changes control epithelial movement in zebrafish and Drosophila}}, doi = {doi: 10.1242/dev.02439}, volume = {133}, year = {2006}, } @article{4218, abstract = {The molecular and cellular mechanisms governing cell motility and directed migration in response to the chemokine SDF-1 are largely unknown. Here, we demonstrate that zebrafish primordial germ cells whose migration is guided by SDF-1 generate bleb-like protrusions that are powered by cytoplasmic flow. Protrusions are formed at sites of higher levels of free calcium where activation of myosin contraction occurs. Separation of the acto-myosin cortex from the plasma membrane at these sites is followed by a flow of cytoplasm into the forming bleb. We propose that polarized activation of the receptor CXCR4 leads to a rise in free calcium that in turn activates myosin contraction in the part of the cell responding to higher levels of the ligand SDF-1. The biased formation of new protrusions in a particular region of the cell in response to SDF-1 defines the leading edge and the direction of cell migration.}, author = {Blaser, Heiko and Reichman Fried, Michal and Castanon, Irinka and Dumstrei, Karin and Marlow, Florence and Kawakami, Koichi and Solnica Krezel, Lilianna and Heisenberg, Carl-Philipp J and Raz, Erez}, journal = {Developmental Cell}, number = {5}, pages = {613 -- 627}, publisher = {Cell Press}, title = {{Migration of zebrafish primordial germ cells: A role for myosin contraction and cytoplasmic flow}}, doi = {10.1016/j.devcel.2006.09.023}, volume = {11}, year = {2006}, } @article{4237, abstract = {The growth function of populations is central in biomathematics. The main dogma is the existence of density-dependence mechanisms, which can be modelled with distinct functional forms that depend on the size of the Population. One important class of regulatory functions is the theta-logistic, which generalizes the logistic equation. Using this model as a motivation, this paper introduces a simple dynamical reformulation that generalizes many growth functions. The reformulation consists of two equations, one for population size, and one for the growth rate. Furthermore, the model shows that although population is density-dependent, the dynamics of the growth rate does not depend either on population size, nor on the carrying capacity. Actually, the growth equation is uncoupled from the population size equation, and the model has only two parameters, a Malthusian parameter rho and a competition coefficient theta. Distinct sign combinations of these parameters reproduce not only the family of theta-logistics, but also the van Bertalanffy, Gompertz and Potential Growth equations, among other possibilities. It is also shown that, except for two critical points, there is a general size-scaling relation that includes those appearing in the most important allometric theories, including the recently proposed Metabolic Theory of Ecology. With this model, several issues of general interest are discussed such as the growth of animal population, extinctions, cell growth and allometry, and the effect of environment over a population. (c) 2005 Elsevier Ltd. All rights reserved.}, author = {de Vladar, Harold}, journal = {Journal of Theoretical Biology}, number = {2}, pages = {245 -- 256}, publisher = {Elsevier}, title = {{Density-dependence as a size-independent regulatory mechanism}}, doi = {3802}, volume = {238}, year = {2006}, } @article{4235, author = {Harold Vladar and González,J. A}, journal = {Journal of Theoretical Biology}, pages = {91 -- 109}, publisher = {Elsevier}, title = {{Dynamic response of cancer under the influence of immunological activity and therapy}}, year = {2006}, } @article{4248, abstract = {In finite populations, genetic drift generates interference between selected loci, causing advantageous alleles to be found more often on different chromosomes than on the same chromosome, which reduces the rate of adaptation. This “Hill–Robertson effect” generates indirect selection to increase recombination rates. We present a new method to quantify the strength of this selection. Our model represents a new beneficial allele (A) entering a population as a single copy, while another beneficial allele (B) is sweeping at another locus. A third locus affects the recombination rate between selected loci. Using a branching process model, we calculate the probability distribution of the number of copies of A on the different genetic backgrounds, after it is established but while it is still rare. Then, we use a deterministic model to express the change in frequency of the recombination modifier, due to hitchhiking, as A goes to fixation. We show that this method can give good estimates of selection for recombination. Moreover, it shows that recombination is selected through two different effects: it increases the fixation probability of new alleles, and it accelerates selective sweeps. The relative importance of these two effects depends on the relative times of occurrence of the beneficial alleles.}, author = {Roze, Denis and Nicholas Barton}, journal = {Genetics}, number = {3}, pages = {1793 -- 1811}, publisher = {Genetics Society of America}, title = {{The Hill-Robertson effect and the evolution of recombination}}, doi = {10.1534/genetics.106.058586 }, volume = {173}, year = {2006}, } @misc{4250, abstract = {A recent analysis has shown that divergence between human and chimpanzee varies greatly across the genome. Although this is consistent with ‘hybridisation’ between the diverging human and chimp lineages, such observations can be explained more simply by the null model of allopatric speciation.}, author = {Nicholas Barton}, booktitle = {Current Biology}, number = {16}, pages = {647 -- 650}, publisher = {Cell Press}, title = {{Evolutionary Biology: How did the human species form?}}, doi = {10.1016/j.cub.2006.07.032}, volume = {16}, year = {2006}, } @inproceedings{4359, author = {Thomas Wies and Kuncak, Viktor and Lam,Patrick and Podelski,Andreas and Rinard,Martin}, pages = {157 -- 173}, publisher = {Springer}, title = {{Field Constraint Analysis}}, doi = {1551}, year = {2006}, } @inproceedings{4373, author = {Maler, Oded and Dejan Nickovic and Pnueli,Amir}, pages = {2 -- 16}, publisher = {Springer}, title = {{Real Time Temporal Logic: Past, Present, Future}}, doi = {1571}, year = {2006}, } @inproceedings{4374, author = {Maler, Oded and Dejan Nickovic and Pnueli,Amir}, pages = {274 -- 289}, publisher = {Springer}, title = {{From MITL to Timed Automata}}, doi = {1570}, year = {2006}, } @inproceedings{4406, abstract = {We propose and evaluate a new algorithm for checking the universality of nondeterministic finite automata. In contrast to the standard algorithm, which uses the subset construction to explicitly determinize the automaton, we keep the determinization step implicit. Our algorithm computes the least fixed point of a monotone function on the lattice of antichains of state sets. We evaluate the performance of our algorithm experimentally using the random automaton model recently proposed by Tabakov and Vardi. We show that on the difficult instances of this probabilistic model, the antichain algorithm outperforms the standard one by several orders of magnitude. We also show how variations of the antichain method can be used for solving the language-inclusion problem for nondeterministic finite automata, and the emptiness problem for alternating finite automata.}, author = {De Wulf, Martin and Doyen, Laurent and Thomas Henzinger and Raskin, Jean-François}, pages = {17 -- 30}, publisher = {Springer}, title = {{Antichains: A new algorithm for checking universality of finite automata}}, doi = {10.1007/11817963_5}, volume = {4144}, year = {2006}, } @inproceedings{4401, author = {Alur, Rajeev and Pavol Cerny and Zdancewic,Steve}, pages = {107 -- 118}, publisher = {Springer}, title = {{Preserving Secrecy Under Refinement}}, doi = {1543}, year = {2006}, } @inproceedings{4437, abstract = {The synthesis of reactive systems requires the solution of two-player games on graphs with ω-regular objectives. When the objective is specified by a linear temporal logic formula or nondeterministic Büchi automaton, then previous algorithms for solving the game require the construction of an equivalent deterministic automaton. However, determinization for automata on infinite words is extremely complicated, and current implementations fail to produce deterministic automata even for relatively small inputs. We show how to construct, from a given nondeterministic Büchi automaton, an equivalent nondeterministic parity automaton that is good for solving games with objective . The main insight is that a nondeterministic automaton is good for solving games if it fairly simulates the equivalent deterministic automaton. In this way, we omit the determinization step in game solving and reactive synthesis. The fact that our automata are nondeterministic makes them surprisingly simple, amenable to symbolic implementation, and allows an incremental search for winning strategies.}, author = {Thomas Henzinger and Piterman, Nir}, pages = {395 -- 410}, publisher = {Springer}, title = {{Solving games without determinization}}, doi = {10.1007/11874683_26}, volume = {4207}, year = {2006}, } @inproceedings{4436, abstract = {We present an assume-guarantee interface algebra for real-time components. In our formalism a component implements a set of task sequences that share a resource. A component interface consists of an arrival rate function and a latency for each task sequence, and a capacity function for the shared resource. The interface specifies that the component guarantees certain task latencies depending on assumptions about task arrival rates and allocated resource capacities. Our algebra defines compatibility and refinement relations on interfaces. Interface compatibility can be checked on partial designs, even when some component interfaces are yet unknown. In this case interface composition computes as new assumptions the weakest constraints on the unknown components that are necessary to satisfy the specified guarantees. Interface refinement is defined in a way that ensures that compatible interfaces can be refined and implemented independently. Our algebra thus formalizes an interface-based design methodology that supports both the incremental addition of new components and the independent stepwise refinement of existing components. We demonstrate the flexibility and efficiency of the framework through simulation experiments.}, author = {Thomas Henzinger and Matic, Slobodan}, pages = {253 -- 266}, publisher = {IEEE}, title = {{An interface algebra for real-time components}}, doi = {10.1109/RTAS.2006.11}, year = {2006}, } @inproceedings{4432, abstract = {We add freeze quantifiers to the game logic ATL in order to specify real-time objectives for games played on timed structures. We define the semantics of the resulting logic TATL by restricting the players to physically meaningful strategies, which do not prevent time from diverging. We show that TATL can be model checked over timed automaton games. We also specify timed optimization problems for physically meaningful strategies, and we show that for timed automaton games, the optimal answers can be approximated to within any degree of precision.}, author = {Thomas Henzinger and Prabhu, Vinayak S}, pages = {1 -- 17}, publisher = {Springer}, title = {{Timed alternating-time temporal logic}}, doi = {10.1007/11867340_1}, volume = {4202}, year = {2006}, } @inproceedings{4431, abstract = {We summarize some current trends in embedded systems design and point out some of their characteristics, such as the chasm between analytical and computational models, and the gap between safety-critical and best-effort engineering practices. We call for a coherent scientific foundation for embedded systems design, and we discuss a few key demands on such a foundation: the need for encompassing several manifestations of heterogeneity, and the need for constructivity in design. We believe that the development of a satisfactory Embedded Systems Design Science provides a timely challenge and opportunity for reinvigorating computer science.}, author = {Thomas Henzinger and Sifakis, Joseph}, pages = {1 -- 15}, publisher = {Springer}, title = {{The embedded systems design challenge}}, doi = {10.1007/11813040_1}, volume = {4085}, year = {2006}, } @article{4451, abstract = {One source of complexity in the μ-calculus is its ability to specify an unbounded number of switches between universal (AX) and existential (EX) branching modes. We therefore study the problems of satisfiability, validity, model checking, and implication for the universal and existential fragments of the μ-calculus, in which only one branching mode is allowed. The universal fragment is rich enough to express most specifications of interest, and therefore improved algorithms are of practical importance. We show that while the satisfiability and validity problems become indeed simpler for the existential and universal fragments, this is, unfortunately, not the case for model checking and implication. We also show the corresponding results for the alternation-free fragment of the μ-calculus, where no alternations between least and greatest fixed points are allowed. Our results imply that efforts to find a polynomial-time model-checking algorithm for the μ-calculus can be replaced by efforts to find such an algorithm for the universal or existential fragment.}, author = {Thomas Henzinger and Kupferman, Orna and Majumdar, Ritankar S}, journal = {Theoretical Computer Science}, number = {2}, pages = {173 -- 186}, publisher = {Elsevier}, title = {{On the universal and existential fragments of the mu-calculus}}, doi = {10.1016/j.tcs.2005.11.015}, volume = {354}, year = {2006}, } @inproceedings{4523, abstract = {We consider the problem if a given program satisfies a specified safety property. Interesting programs have infinite state spaces, with inputs ranging over infinite domains, and for these programs the property checking problem is undecidable. Two broad approaches to property checking are testing and verification. Testing tries to find inputs and executions which demonstrate violations of the property. Verification tries to construct a formal proof which shows that all executions of the program satisfy the property. Testing works best when errors are easy to find, but it is often difficult to achieve sufficient coverage for correct programs. On the other hand, verification methods are most successful when proofs are easy to find, but they are often inefficient at discovering errors. We propose a new algorithm, Synergy, which combines testing and verification. Synergy unifies several ideas from the literature, including counterexample-guided model checking, directed testing, and partition refinement.This paper presents a description of the Synergy algorithm, its theoretical properties, a comparison with related algorithms, and a prototype implementation called Yogi.}, author = {Gulavani, Bhargav S and Thomas Henzinger and Kannan, Yamini and Nori, Aditya V and Rajamani, Sriram K}, pages = {117 -- 127}, publisher = {ACM}, title = {{Synergy: A new algorithm for property checking}}, doi = {10.1145/1181775.1181790}, year = {2006}, } @inproceedings{4526, abstract = {We designed and implemented a new programming language called Hierarchical Timing Language (HTL) for hard realtime systems. Critical timing constraints are specified within the language,and ensured by the compiler. Programs in HTL are extensible in two dimensions without changing their timing behavior: new program modules can be added, and individual program tasks can be refined. The mechanism supporting time invariance under parallel composition is that different program modules communicate at specified instances of time. Time invariance under refinement is achieved by conservative scheduling of the top level. HTL is a coordination language, in that individual tasks can be implemented in "foreign" languages. As a case study, we present a distributed HTL implementation of an automotive steer-by-wire controller.}, author = {Ghosal, Arkadeb and Thomas Henzinger and Iercan, Daniel and Kirsch, Christoph M and Sangiovanni-Vincentelli, Alberto}, pages = {132 -- 141}, publisher = {ACM}, title = {{A hierarchical coordination language for interacting real-time tasks}}, doi = {10.1145/1176887.1176907}, year = {2006}, } @inproceedings{4528, abstract = {Computational modeling of biological systems is becoming increasingly common as scientists attempt to understand biological phenomena in their full complexity. Here we distinguish between two types of biological models mathematical and computational - according to their different representations of biological phenomena and their diverse potential. 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 give an overview of the main modeling efforts in this direction, and discuss some of the new challenges that executable biology poses for computer science and biology. We argue that for executable biology to reach its full potential as a mainstream biological technique, formal and algorithmic approaches must be integrated into biological research, driving biology towards a more precise engineering discipline.}, author = {Fisher, Jasmin and Thomas Henzinger}, pages = {1675 -- 1682}, publisher = {IEEE}, title = {{Executable biology}}, doi = {10.1109/WSC.2006.322942}, year = {2006}, } @inproceedings{4539, abstract = {Games on graphs with ω-regular objectives provide a model for the control and synthesis of reactive systems. Every ω-regular objective can be decomposed into a safety part and a liveness part. The liveness part ensures that something good happens “eventually.” Two main strengths of the classical, infinite-limit formulation of liveness are robustness (independence from the granularity of transitions) and simplicity (abstraction of complicated time bounds). However, the classical liveness formulation suffers from the drawback that the time until something good happens may be unbounded. A stronger formulation of liveness, so-called finitary liveness, overcomes this drawback, while still retaining robustness and simplicity. Finitary liveness requires that there exists an unknown, fixed bound b such that something good happens within b transitions. While for one-shot liveness (reachability) objectives, classical and finitary liveness coincide, for repeated liveness (Büchi) objectives, the finitary formulation is strictly stronger. In this work we study games with finitary parity and Streett (fairness) objectives. We prove the determinacy of these games, present algorithms for solving these games, and characterize the memory requirements of winning strategies. Our algorithms can be used, for example, for synthesizing controllers that do not let the response time of a system increase without bound.}, author = {Krishnendu Chatterjee and Thomas Henzinger}, pages = {257 -- 271}, publisher = {Springer}, title = {{Finitary winning in omega-regular games}}, doi = {10.1007/11691372_17}, volume = {3920}, year = {2006}, } @inproceedings{4538, abstract = {A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with ω-regular winning conditions specified as parity objectives. These games lie in NP ∩ coNP. We present a strategy improvement algorithm for stochastic parity games; this is the first non-brute-force algorithm for solving these games. From the strategy improvement algorithm we obtain a randomized subexponential-time algorithm to solve such games.}, author = {Krishnendu Chatterjee and Thomas Henzinger}, pages = {512 -- 523}, publisher = {Springer}, title = {{Strategy improvement and randomized subexponential algorithms for stochastic parity games}}, doi = {10.1007/11672142_42}, volume = {3884}, year = {2006}, } @inproceedings{4551, abstract = {We consider Markov decision processes (MDPs) with multiple discounted reward 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 achieved by a memoryless strategy; however, unlike in the single-objective case, the memoryless strategy may require randomization. Moreover, we show that the Pareto curve can be approximated in polynomial time in the size of the MDP. 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; but the question whether it is realizable by a deterministic memoryless strategy is NP-complete. These results provide efficient algorithms for design exploration in MDP models with multiple objectives. This research was supported in part by the AFOSR MURI grant F49620-00-1-0327, and the NSF grants CCR-0225610, CCR-0234690, and CCR-0427202. }, author = {Krishnendu Chatterjee and Majumdar, Ritankar S and Thomas Henzinger}, pages = {325 -- 336}, publisher = {Springer}, title = {{Markov decision processes with multiple objectives}}, doi = {10.1007/11672142_26}, volume = {3884}, year = {2006}, } @article{4550, abstract = {In 2-player non-zero-sum games, Nash equilibria capture the options for rational behavior if each player attempts to maximize her payoff. In contrast to classical game theory, we consider lexicographic objectives: first, each player tries to maximize her own payoff, and then, the player tries to minimize the opponent's payoff. Such objectives arise naturally in the verification of systems with multiple components. There, instead of proving that each component satisfies its specification no matter how the other components behave, it sometimes suffices to prove that each component satisfies its specification provided that the other components satisfy their specifications. We say that a Nash equilibrium is secure if it is an equilibrium with respect to the lexicographic objectives of both players. We prove that in graph games with Borel winning conditions, which include the games that arise in verification, there may be several Nash equilibria, but there is always a unique maximal payoff profile of a secure equilibrium. We show how this equilibrium can be computed in the case of ω-regular winning conditions, and we characterize the memory requirements of strategies that achieve the equilibrium.}, author = {Krishnendu Chatterjee and Thomas Henzinger and Jurdziński, Marcin}, journal = {Theoretical Computer Science}, number = {1-2}, pages = {67 -- 82}, publisher = {Elsevier}, title = {{Games with secure equilibria}}, doi = {10.1016/j.tcs.2006.07.032}, volume = {365}, year = {2006}, } @inproceedings{4549, abstract = {We present a compositional theory of system verification, where specifications assign real-numbered costs to systems. These costs can express a wide variety of quantitative system properties, such as resource consumption, price, or a measure of how well a system satisfies its specification. The theory supports the composition of systems and specifications, and the hiding of variables. Boolean refinement relations are replaced by real-numbered distances between descriptions of a system at different levels of detail. We show that the classical Boolean rules for compositional reasoning have quantitative counterparts in our setting. While our general theory allows costs to be specified by arbitrary cost functions, we also consider a class of linear cost functions, which give rise to an instance of our framework where all operations are computable in polynomial time.}, author = {Krishnendu Chatterjee and de Alfaro, Luca and Faella, Marco and Thomas Henzinger and Majumdar, Ritankar S and Stoelinga, Mariëlle}, pages = {179 -- 188}, publisher = {IEEE}, title = {{Compositional quantitative reasoning}}, doi = {10.1109/QEST.2006.11}, year = {2006}, } @inproceedings{4552, abstract = {A concurrent reachability game is a two-player game played on a graph: at each state, the players simultaneously and independently select moves; the two moves determine jointly a probability distribution over the successor states. The objective for player 1 consists in reaching a set of target states; the objective for player 2 is to prevent this, so that the game is zero-sum. Our contributions are two-fold. First, we present a simple proof of the fact that in concurrent reachability games, for all epsilon > 0, memoryless epsilon-optimal strategies exist. A memoryless strategy is independent of the history of plays, and an epsilon-optimal strategy achieves the objective with probability within epsilon of the value of the game. In contrast to previous proofs of this fact, which rely on the limit behavior of discounted games using advanced Puisieux series analysis, our proof is elementary and combinatorial. Second, we present a strategy-improvement (a.k.a. policy-iteration) algorithm for concurrent games with reachability objectives.}, author = {Krishnendu Chatterjee and de Alfaro, Luca and Thomas Henzinger}, pages = {291 -- 300}, publisher = {IEEE}, title = {{Strategy improvement for concurrent reachability games}}, doi = {10.1109/QEST.2006.48}, year = {2006}, } @inproceedings{4574, abstract = {Many software model checkers are based on predicate abstraction. If the verification goal depends on pointer structures, the approach does not work well, because it is difficult to find adequate predicate abstractions for the heap. In contrast, shape analysis, which uses graph-based heap abstractions, can provide a compact representation of recursive data structures. We integrate shape analysis into the software model checker Blast. Because shape analysis is expensive, we do not apply it globally. Instead, we ensure that, like predicates, shape graphs are computed and stored locally, only where necessary for proving the verification goal. To achieve this, we extend lazy abstraction refinement, which so far has been used only for predicate abstractions, to three-valued logical structures. This approach does not only increase the precision of model checking, but it also increases the efficiency of shape analysis. We implemented the technique by extending Blast with calls to Tvla.}, author = {Beyer, Dirk and Thomas Henzinger and Théoduloz, Grégory}, pages = {532 -- 546}, publisher = {Springer}, title = {{Lazy shape analysis}}, doi = {10.1007/11817963_48}, volume = {4144}, year = {2006}, } @unpublished{573, abstract = {Mitchison and Jozsa recently suggested that the "chained-Zeno" counterfactual computation protocol recently proposed by Hosten et al. is counterfactual for only one output of the computer. This claim was based on the existing abstract algebraic definition of counterfactual computation, and indeed according to this definition, their argument is correct. However, a more general definition (physically adequate) for counterfactual computation is implicitly assumed by Hosten et. al. Here we explain in detail why the protocol is counterfactual and how the "history tracking" method of the existing description inadequately represents the physics underlying the protocol. Consequently, we propose a modified definition of counterfactual computation. Finally, we comment on one of the most interesting aspects of the error-correcting protocol. }, author = {Hosten, Onur and Rakher, Matthew and Barreiro, Julio and Peters, Nicholas and Kwiat, Paul}, pages = {12}, publisher = {ArXiv}, title = {{Counterfactual computation revisited}}, year = {2006}, }