TY - CONF
AB - In the work of the authors (2003), we showed that graph cuts can find hypersurfaces of globally minimal length (or area) under any Riemannian metric. Here we show that graph cuts on directed regular grids can approximate a significantly more general class of continuous non-symmetric metrics. Using submodularity condition (Boros and Hammer, 2002 and Kolmogorov and Zabih, 2004), we obtain a tight characterization of graph-representable metrics. Such "submodular" metrics have an elegant geometric interpretation via hypersurface functionals combining length/area and flux. Practically speaking, we attend 'geo-cuts' algorithm to a wider class of geometrically motivated hypersurface functionals and show how to globally optimize any combination of length/area and flux of a given vector field. The concept of flux was recently introduced into computer vision by Vasilevskiy and Siddiqi (2002) but it was mainly studied within variational framework so far. We are first to show that flux can be integrated into graph cuts as well. Combining geometric concepts of flux and length/area within the global optimization framework of graph cuts allows principled discrete segmentation models and advances the slate of the art for the graph cuts methods in vision. In particular we address the "shrinking" problem of graph cuts, improve segmentation of long thin objects, and introduce useful shape constraints.
AU - Vladimir Kolmogorov
AU - Boykov, Yuri
ID - 3182
TI - What metrics can be approximated by geo cuts or global optimization of length area and flux
VL - 1
ER -
TY - CONF
AB - This paper describes two algorithms capable of real-time segmentation of foreground from background layers in stereo video sequences. Automatic separation of layers from colour/contrast or from stereo alone is known to be error-prone. Here, colour, 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 6-state space that represents both foreground/background layers and occluded regions. The stereo-match likelihood is then fused with a contrast-sensitive colour 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 marginalised over foreground and background hypotheses, and fused with a contrast-sensitive colour 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 perfomance, substantially better than stereo or colour/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 - 3183
TI - Bi-layer segmentation of binocular stereo video
VL - 2
ER -
TY - CONF
AB - We present an improved bound on the advantage of any q-query adversary at distinguishing between the CBC MAC over a random n-bit permutation and a random function outputting n bits. The result assumes that no message queried is a prefix of any other, as is the case when all messages to be MACed have the same length. We go on to give an improved analysis of the encrypted CBC MAC, where there is no restriction on queried messages. Letting m be the block length of the longest query, our bounds are about mq2/2n for the basic CBC MAC and mo(1)q2/2n for the encrypted CBC MAC, improving prior bounds of m2q2/2n. The new bounds translate into improved guarantees on the probability of forging these MACs.
AU - Bellare, Mihir
AU - Krzysztof Pietrzak
AU - Rogaway, Phillip
ID - 3211
TI - Improved security analyses for CBC MACs
VL - 3621
ER -
TY - CONF
AB - The Full-Domain Hash (FDH) signature scheme [3] forms one the most basic usages of random oracles. It works with a family F of trapdoor permutations (TDP), where the signature of m is computed as f−1(h(m)) (here f ∈R F and h is modelled as a random oracle). It is known to be existentially unforgeable for any TDP family F [3], although a much tighter security reduction is known for a restrictive class of TDP’s [10,14] — namely, those induced by a family of claw-free permutations (CFP) pairs. The latter result was shown [11] to match the best possible “black-box” security reduction in the random oracle model, irrespective of the TDP family F (e.g., RSA) one might use.
In this work we investigate the question if it is possible to instantiate the random oracle h with a “real” family of hash functions H such that the corresponding schemes can be proven secure in the standard model, under some natural assumption on the family F. Our main result rules out the existence of such instantiations for any assumption on F which (1) is satisfied by a family of random permutations; and (2) does not allow the attacker to invert f ∈R F on an a-priori unbounded number of points. Moreover, this holds even if the choice of H can arbitrarily depend on f. As an immediate corollary, we rule out instantiating FDH based on general claw-free permutations, which shows that in order to prove the security of FDH in the standard model one must utilize significantly more structure on F than what is sufficient for the best proof of security in the random oracle model.
AU - Dodis, Yevgeniy
AU - Oliveira, Roberto
AU - Krzysztof Pietrzak
ID - 3212
TI - On the generic insecurity of the full domain hash
VL - 3621
ER -
TY - CONF
AB - We study the question whether the sequential or parallel composition of two functions, each indistinguishable from a random function by non-adaptive distinguishers is secure against adaptive distinguishers. The sequential composition of F and G is the function G(F()), the parallel composition is F G where ⋆ is some group operation. It has been shown that composition indeed gives adaptive security in the information theoretic setting, but unfortunately the proof does not translate into the more interesting computational case.
In this work we show that in the computational setting composition does not imply adaptive security: If there is a prime order cyclic group where the decisional Diffie-Hellman assumption holds, then there are functions F and G which are indistinguishable by non-adaptive polynomially time-bounded adversaries, but whose parallel composition can be completely broken (i.e. we recover the key) with only three adaptive queries. We give a similar result for sequential composition. Interestingly, we need a standard assumption from the asymmetric (aka. public-key) world to prove a negative result for symmetric (aka. private-key) systems.
AU - Krzysztof Pietrzak
ID - 3213
TI - Composition does not imply adaptive security
VL - 3621
ER -
TY - JOUR
AB - In the last decade atomic force microscopy has been used to measure the mechanical stability of single proteins. These force spectroscopy experiments have shown that many water-soluble and membrane proteins unfold via one or more intermediates. Recently, Li and co-workers found a linear correlation between the unfolding force of the native state and the intermediate in fibronectin, which they suggested indicated the presence of a molecular memory or multiple unfolding pathways (1). Here, we apply two independent methods in combination with Monte Carlo simulations to analyze the unfolding of α-helices E and D of bacteriorhodopsin (BR). We show that correlation analysis of unfolding forces is very sensitive to errors in force calibration of the instrument. In contrast, a comparison of relative forces provides a robust measure for the stability of unfolding intermediates. The proposed approach detects three energetically different states of α-helices E and D in trimeric BR. These states are not observed for monomeric BR and indicate that substantial information is hidden in forced unfolding experiments of single proteins.
AU - Harald Janovjak
AU - Sapra, Tanuj K
AU - Mueller, Daniel J
ID - 3416
IS - 5
JF - Biophysical Journal
TI - Complex stability of single proteins explored by forced unfolding experiments
VL - 88
ER -
TY - JOUR
AB - Recently, direct measurements of forces stabilizing single proteins or individual receptor–ligand bonds became possible with ultra-sensitive force probe methods like the atomic force microscope (AFM). In force spectroscopy experiments using AFM, a single molecule or receptor–ligand pair is tethered between the tip of a micromachined cantilever and a supporting surface. While the molecule is stretched, forces are measured by the deflection of the cantilever and plotted against extension, yielding a force spectrum characteristic for each biomolecular system. In order to obtain statistically relevant results, several hundred to thousand single-molecule experiments have to be performed, each resulting in a unique force spectrum. We developed software and algorithms to analyse large numbers of force spectra. Our algorithms include the fitting polymer extension models to force peaks as well as the automatic alignment of spectra. The aligned spectra allowed recognition of patterns of peaks across different spectra. We demonstrate the capabilities of our software by analysing force spectra that were recorded by unfolding single transmembrane proteins such as bacteriorhodopsin and NhaA. Different unfolding pathways were detected by classifying peak patterns. Deviant spectra, e.g. those with no attachment or erratic peaks, can be easily identified. The software is based on the programming language C++, the GNU Scientific Library (GSL), the software WaveMetrics IGOR Pro and available open-source at http://bioinformatics.org/fskit/.
AU - Kuhn, Michael
AU - Harald Janovjak
AU - Hubain, Maurice
AU - Mueller, Daniel J
ID - 3417
IS - 2
JF - Journal of Microscopy
TI - Automated alignment and pattern recognition of single-molecule force spectroscopy data
VL - 218
ER -
TY - JOUR
AB - Atomic force microscopy (AFM) allows the critical forces that unfold single proteins and rupture individual receptor–ligand bonds to be measured. To derive the shape of the energy landscape, the dynamic strength of the system is probed at different force loading rates. This is usually achieved by varying the pulling speed between a few nm/s and a few mgrm/s, although for a more complete investigation of the kinetic properties higher speeds are desirable. Above 10 mgrm/s, the hydrodynamic drag force acting on the AFM cantilever reaches the same order of magnitude as the molecular forces. This has limited the maximum pulling speed in AFM single-molecule force spectroscopy experiments. Here, we present an approach for considering these hydrodynamic effects, thereby allowing a correct evaluation of AFM force measurements recorded over an extended range of pulling speeds (and thus loading rates). To support and illustrate our theoretical considerations, we experimentally evaluated the mechanical unfolding of a multi-domain protein recorded at 30 mgrm/s pulling speed.
AU - Harald Janovjak
AU - Struckmeier, Jens
AU - Mueller, Daniel J
ID - 3418
IS - 1
JF - European Biophysics Journal
TI - Hydrodynamic effects in fast AFM single molecule force measurements
VL - 34
ER -
TY - CHAP
AU - Jonathan Bollback
ED - Nielsen, Rasmus
ID - 3433
T2 - Statistical methods in Molecular Evolution
TI - Posterior mapping and posterior predictive distributions
ER -
TY - JOUR
AB - In the hippocampal CA1 area, a relatively homogenous population of pyramidal cells is accompanied by a diversity of GABAergic interneurons. Previously, we found that parvalbumin-expressing basket, axo-axonic, bistratified, and oriens-lacunosum moleculare cells, innervating different domains of pyramidal cells, have distinct firing patterns during network oscillations in vivo. A second family of interneurons, expressing cholecystokinin but not parvalbumin, is known to target the same domains of pyramidal cells as do the parvalbumin cells. To test the temporal activity of these independent and parallel GABAergic inputs, we recorded the precise spike timing of identified cholecystokinin interneurons during hippocampal network oscillations in anesthetized rats and determined their molecular expression profiles and synaptic targets. The cells were cannabinoid receptor type 1 immunopositive. Contrary to the stereotyped firing of parvalbumin interneurons, cholecystokinin-expressing basket and dendrite-innervating cells discharge, on average, with 1.7 ± 2.0 Hz during high-frequency ripple oscillations in an episode-dependent manner. During theta oscillations, cholecystokinin- expressing interneurons fire with 8.8 ± 3.3 Hz at a characteristic time on the ascending phase of theta waves (155 ± 81°), when place cells start firing in freely moving animals. The firing patterns of some interneurons recorded in drug-free behaving rats were similar to cholecystokinin cells in anesthetized animals. Our results demonstrate that cholecystokinin- and parvalbumin-expressing interneurons make different contributions to network oscillations and play distinct roles in different brain states. We suggest that the specific spike timing of cholecystokinin interneurons and their sensitivity to endocannabinoids might contribute to differentiate subgroups of pyramidal cells forming neuronal assemblies, whereas parvalbumin interneurons contribute to synchronizing the entire network. Copyright © 2005 Society for Neuroscience.
AU - Klausberger,Thomas
AU - Marton,Laszlo F
AU - Joseph O'Neill
AU - Huck, Jojanneke H
AU - Dalezios, Yannis
AU - Fuentealba,Pablo
AU - Suen, Wai Yee
AU - Papp, Edit Cs
AU - Kaneko, Takeshi
AU - Watanabe, Masahiko
AU - Jozsef Csicsvari
AU - Somogyi, Péter
ID - 3443
IS - 42
JF - Journal of Neuroscience
TI - Complementary roles of cholecystokinin- and parvalbumin-expressing GABAergic neurons in hippocampal network oscillations
VL - 25
ER -