@misc{3616, author = {Nicholas Barton}, booktitle = {Current Biology}, number = {15}, pages = {R603 -- R604}, publisher = {Cell Press}, title = {{Speciation: Why, how, where and when?}}, doi = {10.1016/j.cub.2004.07.037}, volume = {14}, year = {2004}, } @inproceedings{3688, abstract = {Capturing images of documents using handheld digital cameras has a variety of applications in academia, research, knowledge management, retail, and office settings. The ultimate goal of such systems is to achieve image quality comparable to that currently achieved with flatbed scanners even for curved, warped, or curled pages. This can be achieved by high-accuracy 3D modeling of the page surface, followed by a "flattening" of the surface. A number of previous systems have either assumed only perspective distortions, or used techniques like structured lighting, shading, or side-imaging for obtaining 3D shape. This paper describes a system for handheld camera-based document capture using general purpose stereo vision methods followed by a new document dewarping technique. Examples of shape modeling and dewarping of book images is shown.}, author = {Ulges, Adrian and Christoph Lampert and Breuel,Thomas M}, pages = {198 -- 200}, publisher = {ACM}, title = {{Document capture using stereo vision}}, doi = {10.1145/1030397.1030434}, year = {2004}, } @article{3810, abstract = {Voltage-gated potassium (Kv) channels control action potential repolarization, interspike membrane potential, and action potential frequency in excitable cells. It is thought that the combinatorial association between distinct alpha and beta subunits determines whether Kv channels function as non-inactivating delayed rectifiers or as rapidly inactivating A-type channels. We show that membrane lipids can convert A-type channels into delayed rectifiers and vice versa. Phosphoinositides remove N-type inactivation from A-type channels by immobilizing the inactivation domains. Conversely, arachidonic acid and its amide anandamide endow delayed rectifiers with rapid voltage-dependent inactivation. The bidirectional control of Kv channel gating by lipids may provide a mechanism for the dynamic regulation of electrical signaling in the nervous system.}, author = {Oliver, Dominik and Lien, Cheng-Chang and Soom, Malle and Baukrowitz, Thomas and Peter Jonas and Fakler, Bernd}, journal = {Science}, number = {5668}, pages = {265 -- 70}, publisher = {American Association for the Advancement of Science}, title = {{Functional conversion between A-type and delayed rectifier K+ channels by membrane lipids}}, doi = {10.1126/science.1094113}, volume = {304}, year = {2004}, } @inproceedings{3894, abstract = {We study infinite stochastic games played by n-players on a finite graph with goals given by sets of infinite traces. The games are stochastic (each player simultaneously and independently chooses an action at each round, and 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 a reachability objective, that is, if the goal for each player i is to visit some subset R-i of the states, then there exists an epsilon-Nash equilibrium in memoryless strategies, for every epsilon > 0. However, exact Nash equilibria need not exist. We study the complexity of finding such Nash equilibria, and show that the payoff of some epsilon-Nash equilibrium in memoryless strategies can be epsilon-approximated in NP. We study the important subclass of n-player turn-based probabilistic games, where at each state at most one player has a nontrivial choice of moves. For turn-based probabilistic games, we show the existence of epsilon-Nash equilibria in pure strategies for games where the objective of player i is a Borel set B-i of infinite traces. However, exact Nash equilibria may not exist. For the special case of omega-regular objectives, we show exact Nash equilibria exist, and can be computed in NP when the omega-regular objectives are expressed as parity objectives.}, author = {Krishnendu Chatterjee and Majumdar, Ritankar S and Jurdziński, Marcin}, pages = {26 -- 40}, publisher = {Springer}, title = {{On Nash equilibria in stochastic games}}, doi = {10.1007/978-3-540-30124-0_6}, volume = {3210}, year = {2004}, } @inproceedings{3895, 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 often 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 objectives, which include the games that arise in verification, there may be several Nash equilibria, but there is always a unique maximal payoff profile of secure equilibria. We show how this equilibrium can be computed in the case of omega-regular objectives, and we characterize the memory requirements of strategies that achieve the equilibrium.}, author = {Krishnendu Chatterjee and Thomas Henzinger and Jurdziński, Marcin}, pages = {160 -- 169}, publisher = {IEEE}, title = {{Games with secure equilibria}}, doi = {10.1109/LICS.2004.1319610}, year = {2004}, } @article{3931, abstract = {Hyaluronan is an unsulfated glycosaminoglycan (GAG) that is ubiquitously expressed in the extracellular matrix (ECM) of all vertebrates, where hyaluronan rich matrices constitute a particular permissive environment for the development of complex biological structures and also for tumor progression. Because of its conserved structure and ubiquitous expression, antibodies for its histochemical detection cannot be produced. We have engineered a fusion protein, neurocan-GFP, and expressed it as a secreted molecule in mammalian cells. Neurocan-GFP fusion protein specifically binds to hyaluronan and directly visualizes hyaluronan on tissue sections, revealing a very detailed picture of hyaluronan distribution. The fluorescent fusion protein can be used in combination with antibodies and nuclear markers for double or triple staining. In addition, it is suitable to visualize hyaluronan on living cells by time-lapse video microscopy. The successful production and application of the neurocan-GFP fusion protein opens up new perspectives for using GFP fusion proteins as detection tools in histological and cytological studies complementing conventional antibody and biotin/avidin techniques.}, author = {Zhang, Hui and Baader, Stephan L and Michael Sixt and Kappler, Joachim and Rauch, Uwe}, journal = {Journal of Histochemistry and Cytochemistry}, number = {7}, pages = {915 -- 922}, publisher = {Histochemical Society}, title = {{Neurocan-GFP fusion protein: a new approach to detect hyaluronan on tissue sections and living cells}}, doi = {10.1369/jhc.3A6221.2004}, volume = {52}, year = {2004}, } @article{3929, abstract = {The Nef protein of human and simian immunodeficiency virus (HIV/SIV) is believed to interfere with T cell activation signals by forming a signaling complex at the plasma membrane. Composition and function of the complex are not fully understood. Here we report that Nef recruits the Polycomb Group (PcG) protein Eed, so far known as a nuclear factor and repressor of transcription, to the membrane of cells. The Nef-induced translocation of Eed led to a potent stimulation of Tat-dependent HIV transcription, implying that Eed removal from the nucleus is required for optimal Tat function. Similar to Nef action, activation of integrin receptors recruited Eed to the plasma membrane, also leading to enhanced Tat/Nef-mediated transcription. Our results suggest a link between membrane-associated activation processes and transcriptional derepression and demonstrate how HIV exploits this mechanism.}, author = {Witte, Vanessa and Laffert, Bernd and Rosorius, Olaf and Lischka, Peter and Blume, Katja and Galler, Gunther and Stilper, Andrea and Willbold, Dieter and D'Aloja, Paola and Michael Sixt and Kolanus, Johanna and Ott, Melanie and Kolanus, Waldemar and Schuler, Gerold and Baur, Andreas S}, journal = {Molecular Cell}, number = {2}, pages = {179 -- 190}, publisher = {Cell Press}, title = {{HIV-1 Nef mimics an integrin receptor signal that recruits the polycomb group protein Eed to the plasma membrane}}, doi = {10.1016/S1097-2765(04)00004-8}, volume = {13}, year = {2004}, } @article{3990, abstract = {The writhing number measures the global geometry of a closed space curve or knot. We show that this measure is related to the average winding number of its Gauss map. Using this relationship, we give an algorithm for computing the writhing number for a polygonal knot with n edges in time roughly proportional to n(1.6). We also implement a different, simple algorithm and provide experimental evidence for its practical efficiency.}, author = {Agarwal, Pankaj K and Herbert Edelsbrunner and Wang, Yusu}, journal = {Discrete & Computational Geometry}, number = {1}, pages = {37 -- 53}, publisher = {Springer}, title = {{Computing the writhing number of a polygonal knot}}, doi = {10.1007/s00454-004-2864-x}, volume = {32}, year = {2004}, } @article{4224, abstract = {Developing cells acquire positional information by reading the graded distribution of morphogens. In Drosophila, the Dpp morphogen forms a long-range concentration gradient by spreading from a restricted source in the developing wing. It has been assumed that Dpp spreads by extracellular diffusion. Under this assumption, the main role of endocytosis in gradient formation is to downregulate receptors at the cell surface. These surface receptors bind to the ligand and thereby interfere with its long-range movement. Recent experiments indicate that Dpp spreading is mediated by Dynamin-dependent endocytosis in the target tissue, suggesting that extracellular diffusion alone cannot account for Dpp dispersal. Here, we perform a theoretical study of a model for morphogen spreading based on extracellular diffusion, which takes into account receptor binding and trafficking. We compare profiles of ligand and surface receptors obtained in this model with experimental data. To this end, we monitored directly the pool of surface receptors and extracellular Dpp with specific antibodies. We conclude that current models considering pure extracellular diffusion cannot explain the observed role of endocytosis during Dpp long-range movement.}, author = {Kruse, Karsten and Pantazis, Periklis and Bollenbach, Mark Tobias and Julicher, Frank and Gonzalez Gaitan, Marcos}, journal = {Development}, number = {19}, pages = {4843 -- 4856}, publisher = {Company of Biologists}, title = {{Dpp gradient formation by dynamin-dependent endocytosis: receptor trafficking and the diffusion model}}, doi = {10.1242/dev.01335}, volume = {131}, year = {2004}, } @inbook{4239, author = {Harold Vladar and Cipriani, Roberto and Scharifker, Benjamin and Bubis, Jose}, booktitle = {Life in the Universe From the Miller Experiment to the Search for Life on Other Worlds}, editor = {Seckbach,J. and Chela-Flores,J. and Owen,T. and Raulin,F.}, pages = {83 -- 87}, publisher = {Springer}, title = {{A Mechanism for the Prebiotic Emergence of Proteins}}, doi = {3807}, volume = {7}, year = {2004}, } @article{4253, abstract = {We consider a single genetic locus which carries two alleles, labelled P and Q. This locus experiences selection and mutation. It is linked to a second neutral locus with recombination rate r. If r = 0, this reduces to the study of a single selected locus. Assuming a Moran model for the population dynamics, we pass to a diffusion approximation and, assuming that the allele frequencies at the selected locus have reached stationarity, establish the joint generating function for the genealogy of a sample from the population and the frequency of the P allele. In essence this is the joint generating function for a coalescent and the random background in which it evolves. We use this to characterize, for the diffusion approximation, the probability of identity in state at the neutral locus of a sample of two individuals (whose type at the selected locus is known) as solutions to a system of ordinary differential equations. The only subtlety is to find the boundary conditions for this system. Finally, numerical examples are presented that illustrate the accuracy and predictions of the diffusion approximation. In particular, a comparison is made between this approach and one in which the frequencies at the selected locus are estimated by their value in the absence of fluctuations and a classical structured coalescent model is used.}, author = {Nicholas Barton and Etheridge, Alison M and Sturm, Anja K}, journal = {Annals of Applied Probability}, number = {2}, pages = {754 -- 785}, publisher = {Institute of Mathematical Statistics}, title = {{Coalescence in a Random Background}}, volume = {14}, year = {2004}, } @misc{3142, abstract = {Assembly of neuronal circuits is controlled by the sequential acquisition of neuronal subpopulation-specific identities at progressive developmental steps. Whereas neuronal features involved in initial phases of differentiation are already established at cell-cycle exit, recent findings, based mainly on work in the peripheral nervous system, suggest that the timely integration of signals encountered en route to targets and from the target region itself is essential to control late steps in connectivity. As neurons project towards their targets they require target-derived signals to establish mature axonal projections and acquire neuronal traits such as the expression of distinct combinations of neurotransmitters. Recent evidence presented in this review shows that this principle, of a signaling interplay between target-derived signals and neuronal cell bodies, is often mediated through transcriptional events and is evolutionarily conserved.}, author = {Simon Hippenmeyer and Kramer, Ina and Arber, Silvia}, booktitle = {Trends in Neurosciences}, number = {8}, pages = {482 -- 488}, publisher = {Elsevier}, title = {{Control of neuronal phenotype: What targets tell the cell bodies}}, doi = {10.1016/j.tins.2004.05.012}, volume = {27}, year = {2004}, } @article{3178, abstract = {Minimum cut/maximum flow algorithms on graphs have emerged as an increasingly useful tool for exactor approximate energy minimization in low-level vision. The combinatorial optimization literature provides many min-cut/max-flow algorithms with different polynomial time complexity. Their practical efficiency, however, has to date been studied mainly outside the scope of computer vision. The goal of this paper is to provide an experimental comparison of the efficiency of min-cut/max flow algorithms for applications in vision. We compare the running times of several standard algorithms, as well as a new algorithm that we have recently developed. The algorithms we study include both Goldberg-Tarjan style "push -relabel" methods and algorithms based on Ford-Fulkerson style "augmenting paths." We benchmark these algorithms on a number of typical graphs in the contexts of image restoration, stereo, and segmentation. In many cases, our new algorithm works several times faster than any of the other methods, making near real-time performance possible. An implementation of our max-flow/min-cut algorithm is available upon request for research purposes.}, author = {Boykov, Yuri and Vladimir Kolmogorov}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, number = {9}, pages = {1124 -- 1137}, publisher = {IEEE}, title = {{An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision}}, doi = {10.1109/TPAMI.2004.60}, volume = {26}, year = {2004}, } @article{3173, abstract = {In the last few years, several new algorithms based on graph cuts have been developed to solve energy minimization problems in computer vision. Each of these techniques constructs a graph such that the minimum cut on the graph also minimizes the energy. Yet, because these graph constructions are complex and highly specific to a particular energy function, graph cuts have seen limited application to date. In this paper, we give a characterization of the energy functions that can be minimized by graph cuts. Our results are restricted to functions of binary variables. However, our work generalizes many previous constructions and is easily applicable to vision problems that involve large numbers of labels, such as stereo, motion, image restoration, and scene reconstruction. We give a precise characterization of what energy functions can be minimized using graph cuts, among the energy functions that can be written as a sum of terms containing three or fewer binary variables. We also provide a general-purpose construction to minimize such an energy function. Finally, we give a necessary condition for any energy function of binary variables to be minimized by graph cuts. Researchers who are considering the use of graph cuts to optimize a particular energy function can use our results to determine if this is possible and then follow our construction to create the appropriate graph. A software implementation is freely available.}, author = {Vladimir Kolmogorov and Zabih, Ramin}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, number = {2}, pages = {147 -- 159}, publisher = {IEEE}, title = {{What energy functions can be minimized via graph cuts? }}, doi = {10.1109/TPAMI.2004.1262177}, volume = {26}, year = {2004}, } @article{3172, abstract = {The simultaneous multiple volume (SMV) approach in navigator-gated MRI allows the use of the whole motion range or the entire scan time for the reconstruction of final images by simultaneously acquiring different image volumes at different motion states. The motion tolerance range for each volume is kept small, thus SMV substantially increases the scan efficiency of navigator methods while maintaining the effectiveness of motion suppression. This article reports a general implementation of the SMV approach using a multiprocessor scheduling algorithm. Each motion state is regarded as a processor and each volume is regarded as a job. An efficient scheduling that completes all jobs in minimal time is maintained even when the motion pattern changes. Initial experiments demonstrated that SMV significantly increased the scan efficiency of navigatorgated MRI.}, author = {Vladimir Kolmogorov and Nguyen, Thành D and Nuval, Anthony and Spincemaille, Pascal and Prince, Martin R and Zabih, Ramin and Wang, Yusu}, journal = {Magnetic Resonance in Medicine}, number = {2}, pages = {362 -- 367}, publisher = {Wiley-Blackwell}, title = {{Multiprocessor scheduling implementation of the simultaneous multiple volume SMV navigator method}}, doi = {10.1002/mrm.20162}, volume = {52}, year = {2004}, } @inproceedings{3177, abstract = {Feature space clustering is a popular approach to image segmentation, in which a feature vector of local properties (such as intensity, texture or motion) is computed at each pixel. The feature space is then clustered, and each pixel is labeled with the cluster that contains its feature vector. A major limitation of this approach is that feature space clusters generally lack spatial coherence (i.e., they do not correspond to a compact grouping of pixels). In this paper, we propose a segmentation algorithm that operates simultaneously in feature space and in image space. We define an energy function over both a set of clusters and a labeling of pixels with clusters. In our framework, a pixel is labeled with a single cluster (rather than, for example, a distribution over clusters). Our energy function penalizes clusters that are a poor fit to the data in feature space, and also penalizes clusters whose pixels lack spatial coherence. The energy function can be efficiently minimized using graph cuts. Our algorithm can incorporate both parametric and non-parametric clustering methods. It can be applied to many optimization-based clustering methods, including k-means and k-medians, and can handle models which are very close in feature space. Preliminary results are presented on segmenting real and synthetic images, using both parametric and non-parametric clustering.}, author = {Zabih, Ramin and Vladimir Kolmogorov}, pages = {437 -- 444}, publisher = {IEEE}, title = {{Spatially coherent clustering using graph cuts}}, doi = {10.1109/CVPR.2004.1315196}, volume = {2}, year = {2004}, } @inproceedings{3179, abstract = {The problem of efficient, interactive foreground/background segmentation in still images is of great practical importance in image editing. Classical image segmentation tools use either texture (colour) information, e.g. Magic Wand, or edge (contrast) information, e.g. Intelligent Scissors. Recently, an approach based on optimization by graph-cut has been developed which successfully combines both types of information. In this paper we extend the graph-cut approach in three respects. First, we have developed a more powerful, iterative version of the optimisation. Secondly, the power of the iterative algorithm is used to simplify substantially the user interaction needed for a given quality of result. Thirdly, a robust algorithm for "border matting" has been developed to estimate simultaneously the alpha-matte around an object boundary and the colours of foreground pixels. We show that for moderately difficult examples the proposed method outperforms competitive tools.}, author = {Rother, Carsten and Vladimir Kolmogorov and Blake, Andrew}, number = {3}, pages = {309 -- 314}, publisher = {ACM}, title = {{"GrabCut" - Interactive foreground extraction using iterated graph cuts }}, doi = {10.1145/1015706.1015720}, volume = {23}, year = {2004}, } @article{3420, abstract = {Single-molecule force-spectroscopy was employed to unfold and refold single sodium-proton antiporters (NhaA) of Escherichia coli from membrane patches. Although transmembrane α-helices and extracellular polypeptide loops exhibited sufficient stability to individually establish potential barriers against unfolding, two helices predominantly unfolded pairwise, thereby acting as one structural unit. Many of the potential barriers were detected unfolding NhaA either from the C-terminal or the N-terminal end. It was found that some molecular interactions stabilizing secondary structural elements were directional, while others were not. Additionally, some interactions appeared to occur between the secondary structural elements. After unfolding ten of the 12 helices, the extracted polypeptide was allowed to refold back into the membrane. After five seconds, the refolded polypeptide established all secondary structure elements of the native protein. One helical pair showed a characteristic spring like “snap in” into its folded conformation, while the refolding process of other helices was not detected in particular. Additionally, individual helices required characteristic periods of time to fold. Correlating these results with the primary structure of NhaA allowed us to obtain the first insights into how potential barriers establish and determine the folding kinetics of the secondary structure elements.}, author = {Kedrov, Alexej and Ziegler, Christine and Harald Janovjak and Kühlbrandt, Werner and Mueller, Daniel J}, journal = {Journal of Molecular Biology}, number = {5}, pages = {1143 -- 1152}, publisher = {Elsevier}, title = {{Controlled unfolding and refolding of a single sodium/proton antiporter using atomic force microscopy}}, doi = {10.1016/j.jmb.2004.05.026}, volume = {340}, year = {2004}, } @article{3419, abstract = {The folding and stability of transmembrane proteins is a fundamental and unsolved biological problem. Here, single bacteriorhodopsin molecules were mechanically unfolded from native purple membranes using atomic force microscopy and force spectroscopy. The energy landscape of individual transmembrane α helices and polypeptide loops was mapped by monitoring the pulling speed dependence of the unfolding forces and applying Monte Carlo simulations. Single helices formed independently stable units stabilized by a single potential barrier. Mechanical unfolding of the helices was triggered by 3.9–7.7 Å extension, while natural unfolding rates were of the order of 10−3 s−1. Besides acting as individually stable units, helices associated pairwise, establishing a collective potential barrier. The unfolding pathways of individual proteins reflect distinct pulling speed-dependent unfolding routes in their energy landscapes. These observations support the two-stage model of membrane protein folding in which α helices insert into the membrane as stable units and then assemble into the functional protein.}, author = {Harald Janovjak and Struckmeier, Jens and Hubain, Maurice and Kessler, Max and Kedrov, Alexej and Mueller, Daniel J}, journal = {Structure}, number = {5}, pages = {871 -- 879}, publisher = {Cell Press}, title = {{Probing the energy landscape of the membrane protein bacteriorhodopsin}}, doi = {10.1016/j.str.2004.03.016}, volume = {12}, year = {2004}, } @inbook{3575, abstract = {The Jacobi set of two Morse functions defined on a common - manifold is the set of critical points of the restrictions of one func- tion to the level sets of the other function. Equivalently, it is the set of points where the gradients of the functions are parallel. For a generic pair of Morse functions, the Jacobi set is a smoothly embed- ded 1-manifold. We give a polynomial-time algorithm that com- putes the piecewise linear analog of the Jacobi set for functions specified at the vertices of a triangulation, and we generalize all results to more than two but at most Morse functions.}, author = {Herbert Edelsbrunner and Harer, John}, booktitle = {Foundations of Computational Mathematics}, pages = {37 -- 57}, publisher = {Springer}, title = {{Jacobi sets of multiple Morse functions}}, doi = {10.1017/CBO9781139106962.003}, volume = {312}, year = {2004}, }