TY - JOUR
AB - High throughput microarray transcription analyses provide us with the expression profiles for large amounts of plant genes. However, their tissue and cellular resolution is limited. Thus, for detailed functional analysis, it is still necessary to examine the expression pattern of selected candidate genes at a cellular level. Here, we present an in situ mRNA hybridization method that is routinely used for the analysis of plant gene expression patterns. The protocol is optimized for whole mount mRNA localizations in Arabidopsis seedling tissues including embryos, roots, hypocotyls and young primary leaves. It can also be used for comparable tissues in other species. Part of the protocol can also be automated and performed by a liquid handling robot. Here we present a detailed protocol, recommended controls and troubleshooting, along with examples of several applications. The total time to carry out the entire procedure is ∼7 d, depending on the tissue used.
AU - Hejátko, Jan
AU - Blilou, Ikram
AU - Brewer, Philip B
AU - Jirí Friml
AU - Scheres, Ben
AU - Eva Benková
ID - 3020
IS - 4
JF - Nature Protocols
TI - In situ hybridization technique for mRNA detection in whole mount Arabidopsis samples
VL - 1
ER -
TY - JOUR
AB - The basic concepts of the molecular machinery that mediates cell migration have been gleaned from cell culture systems. However, the three-dimensional environment within an organism presents migrating cells with a much greater challenge. They must move between and among other cells while interpreting multiple attractive and repulsive cues to choose their proper path. They must coordinate their cell adhesion with their surroundings and know when to start and stop moving. New insights into the control of these remaining mysteries have emerged from genetic dissection and live imaging of germ cell migration in Drosophila, zebrafish, and mouse embryos. In this review, we first describe germ cell migration in cellular and mechanistic detail in these different model systems. We then compare these systems to highlight the emerging principles. Finally, we contrast the migration of germ cells with that of immune and cancer cells to outline the conserved and different mechanisms.
AU - Kunwar, Prabhat S
AU - Daria Siekhaus
AU - Lehmann, Ruth
ID - 3152
JF - Annual Review of Cell and Developmental Biology
TI - In vivo migration A germ cell perspective
VL - 22
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 - CONF
AB - We introduce the term cosegmentation which denotes the task of segmenting simultaneously the common parts of an image pair. A generative model for cosegmentation is presented. Inference in the model leads to minimizing an energy with an MRF term encoding spatial coherency and a global constraint which attempts to match the appearance histograms of the common parts. This energy has not been proposed previously and its optimization is challenging and NP-hard. For this problem a novel optimization scheme which we call trust region graph cuts is presented. We demonstrate that this framework has the potential to improve a wide range of research: Object driven image retrieval, video tracking and segmentation, and interactive image editing. The power of the framework lies in its generality, the common part can be a rigid/non-rigid object (or scene), observed from different viewpoints or even similar objects of the same class.
AU - Rother, Carsten
AU - Vladimir Kolmogorov
AU - Minka, Thomas P
AU - Blake, Andrew
ID - 3188
TI - Cosegmentation of image pairs by histogram matching - Incorporating a global constraint into MRFs
ER -
TY - CONF
AB - This paper presents an algorithm capable of real-time separation of foreground from background in monocular video sequences. Automatic segmentation of layers from colour/contrast or from motion alone is known to be error-prone. Here motion, colour and contrast cues are probabilistically fused together with spatial and temporal priors to infer layers accurately and efficiently. Central to our algorithm is the fact that pixel velocities are not needed, thus removing the need for optical flow estimation, with its tendency to error and computational expense. Instead, an efficient motion vs non-motion classifier is trained to operate directly and jointly on intensity-change and contrast. Its output is then fused with colour information. The prior on segmentation is represented by a second order, temporal, Hidden Markov Model, together with a spatial MRF favouring coherence except where contrast is high. Finally, accurate layer segmentation and explicit occlusion detection are efficiently achieved by binary graph cut. The segmentation accuracy of the proposed algorithm is quantitatively evaluated with respect to existing ground-truth data and found to be comparable to the accuracy of a state of the art stereo segmentation algorithm. Fore-ground/background segmentation is demonstrated in the application of live background substitution and shown to generate convincingly good quality composite video.
AU - Criminisi, Antonio
AU - Cross, Geoffrey
AU - Blake, Andrew
AU - Vladimir Kolmogorov
ID - 3189
TI - Bilayer segmentation of live video
VL - 1
ER -
TY - JOUR
AB - Algorithms for discrete energy minimization are of fundamental importance in computer vision. In this paper, we focus on the recent technique proposed by Wainwright et al. (Nov. 2005)- tree-reweighted max-product message passing (TRW). It was inspired by the problem of maximizing a lower bound on the energy. However, the algorithm is not guaranteed to increase this bound - it may actually go down. In addition, TRW does not always converge. We develop a modification of this algorithm which we call sequential tree-reweighted message passing. Its main property is that the bound is guaranteed not to decrease. We also give a weak tree agreement condition which characterizes local maxima of the bound with respect to TRW algorithms. We prove that our algorithm has a limit point that achieves weak tree agreement. Finally, we show that, our algorithm requires half as much memory as traditional message passing approaches. Experimental results demonstrate that on certain synthetic and real problems, our algorithm outperforms both the ordinary belief propagation and tree-reweighted algorithm in (M. J. Wainwright, et al., Nov. 2005). In addition, on stereo problems with Potts interactions, we obtain a lower energy than graph cuts.
AU - Vladimir Kolmogorov
ID - 3190
IS - 10
JF - IEEE Transactions on Pattern Analysis and Machine Intelligence
TI - Convergent tree reweighted message passing for energy minimization
VL - 28
ER -
TY - CONF
AB - The Feistel-network is a popular structure underlying many block-ciphers where the cipher is constructed from many simpler rounds, each defined by some function which is derived from the secret key.
Luby and Rackoff showed that the three-round Feistel-network – each round instantiated with a pseudorandom function secure against adaptive chosen plaintext attacks (CPA) – is a CPA secure pseudorandom permutation, thus giving some confidence in the soundness of using a Feistel-network to design block-ciphers.
But the round functions used in actual block-ciphers are – for efficiency reasons – far from being pseudorandom. We investigate the security of the Feistel-network against CPA distinguishers when the only security guarantee we have for the round functions is that they are secure against non-adaptive chosen plaintext attacks (nCPA). We show that in the information-theoretic setting, four rounds with nCPA secure round functions are sufficient (and necessary) to get a CPA secure permutation. Unfortunately, this result does not translate into the more interesting pseudorandom setting. In fact, under the so-called Inverse Decisional Diffie-Hellman assumption the Feistel-network with four rounds, each instantiated with a nCPA secure pseudorandom function, is in general not a CPA secure pseudorandom permutation.
AU - Maurer, Ueli M
AU - Oswald, Yvonne A
AU - Krzysztof Pietrzak
AU - Sjödin, Johan
ID - 3214
TI - Luby Rackoff ciphers from weak round functions
VL - 4004
ER -
TY - CONF
AB - 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.
AU - Dodis, Yevgeniy
AU - Krzysztof Pietrzak
AU - Przydatek, Bartosz
ID - 3215
TI - Separating sources for encryption and secret sharing
VL - 3876
ER -
TY - CONF
AB - 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.
AU - Krzysztof Pietrzak
ID - 3216
TI - A tight bound for EMAC
VL - 4052
ER -
TY - CONF
AB - 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.
AU - Krzysztof Pietrzak
ID - 3217
TI - Composition implies adaptive security in minicrypt
VL - 4004
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 -
TY - JOUR
AB - 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.
AU - Kedrov, Alexej
AU - Harald Janovjak
AU - Ziegler, Christine
AU - Kühlbrandt, Werner
AU - Mueller, Daniel J
ID - 3414
IS - 1
JF - Journal of Molecular Biology
TI - Observing folding pathways and kinetics of a single sodium-proton antiporter from Escherichia coli
VL - 355
ER -
TY - GEN
AU - Harald Janovjak
AU - Kedrov, Alexej
AU - Cisneros, David
AU - Sapra, Tanuj K
AU - Struckmeier, Jens
AU - Mueller, Daniel J
ID - 3415
T2 - Neurobiology of Aging
TI - Imaging and detecting molecular interactions of single membrane proteins
VL - 27
ER -
TY - GEN
AB - 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.
AU - Gasper Tkacik
AU - Schneidman, E.
AU - Berry, M. J.
AU - Bialek, William S
ID - 3431
T2 - ArXiv
TI - Ising models for networks of real neurons
ER -
TY - JOUR
AB - 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.
AU - Betancourt, Andrea J
AU - Jonathan Bollback
ID - 3437
IS - 6
JF - Current Opinion in Genetics & Development
TI - Fitness effects of beneficial mutations: the mutational landscape model in experimental evolution
VL - 16
ER -
TY - CONF
AB - 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.
AU - Krishnendu Chatterjee
AU - Jagadeesan, Rhada
AU - Pitcher, Corin
ID - 3449
TI - Games for controls
ER -