TY - JOUR AB - 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. AU - Agarwal, Pankaj K AU - Herbert Edelsbrunner AU - Harer, John AU - Wang, Yusu ID - 3980 IS - 4 JF - Discrete & Computational Geometry TI - Extreme elevation on a 2-manifold VL - 36 ER - TY - JOUR AB - 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. AU - Patrick Danowski AU - Heller,Lambert ID - 4345 IS - 11 JF - Bibliotheksdienst TI - Bibliothek 2.0 - Die Bibliothek der Zukunft? VL - 40 ER - TY - JOUR AB - 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. AU - Conn, Jan E AU - Vineis, Joseph H AU - Jonathan Bollback AU - Onyabe, David Y AU - Wilkerson, Richard C AU - Povoa, Marinete M ID - 4352 IS - 5 JF - The American Journal of Tropical Medicine and Hygiene TI - Population structure of the malaria vector Anopheles darlingi in a malaria-endemic region of eastern Amazonian Brazil VL - 74 ER - TY - JOUR AB - 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. AU - Jonathan Bollback ID - 4351 JF - BMC Bioinformatics TI - SIMMAP: stochastic character mapping of discrete traits on phylogenies VL - 7 ER - TY - CONF AB - 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. AU - Szeliski, Richard S AU - Zabih, Ramin AU - Scharstein, Daniel AU - Veksler, Olga AU - Vladimir Kolmogorov AU - Agarwala, Aseem AU - Tappen, Marshall F AU - Rother, Carsten ID - 3180 TI - A comparative study of energy minimization methods for Markov random fields VL - 3952 ER - TY - CONF AB - 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. AU - Vladimir Kolmogorov AU - Rother, Carsten ID - 3184 TI - Comparison of energy minimization algorithms for highly connected graphs VL - 3952 LNCS ER - TY - JOUR AB - 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. AU - Vladimir Kolmogorov AU - Criminisi, Antonio AU - Blake, Andrew AU - Cross, Geoffrey AU - Rother, Carsten ID - 3185 IS - 9 JF - IEEE Transactions on Pattern Analysis and Machine Intelligence TI - Probabilistic fusion of stereo with color and contrast for bilayer segmentation VL - 28 ER - TY - CONF AB - 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. AU - Boykov, Yuri AU - Vladimir Kolmogorov AU - Cremers, Daniel AU - Delong, Andrew ID - 3186 TI - An integral solution to surface evolution PDEs via geo cuts VL - 3953 ER - TY - CHAP AU - Harald Janovjak AU - Sawhney, Ravi K AU - Stark, Martin AU - Mueller, Daniel J ID - 3404 T2 - Techniques in Microscopy for Biomedical Applications TI - Atomic force microscopy VL - 2 ER - TY - JOUR AB - 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. AU - Kessler, Max AU - Gottschalk, Kay E AU - Harald Janovjak AU - Mueller, Daniel J AU - Gaub, Hermann ID - 3413 IS - 2 JF - Journal of Molecular Biology TI - Bacteriorhodopsin folds into the membrane against an external force VL - 357 ER -