@inproceedings{3183,
abstract = {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.},
author = {Vladimir Kolmogorov and Criminisi, Antonio and Blake, Andrew and Cross, Geoffrey and Rother, Carsten},
pages = {407 -- 414},
publisher = {IEEE},
title = {{Bi-layer segmentation of binocular stereo video}},
doi = {10.1109/CVPR.2005.91},
volume = {2},
year = {2005},
}
@inproceedings{3211,
abstract = {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.},
author = {Bellare, Mihir and Krzysztof Pietrzak and Rogaway, Phillip},
pages = {527 -- 545},
publisher = {Springer},
title = {{Improved security analyses for CBC MACs}},
doi = {10.1007/11535218_32},
volume = {3621},
year = {2005},
}
@inproceedings{3212,
abstract = {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.},
author = {Dodis, Yevgeniy and Oliveira, Roberto and Krzysztof Pietrzak},
pages = {449 -- 466},
publisher = {Springer},
title = {{On the generic insecurity of the full domain hash}},
doi = {10.1007/11535218_27},
volume = {3621},
year = {2005},
}
@inproceedings{3213,
abstract = {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.},
author = {Krzysztof Pietrzak},
pages = {55 -- 65},
publisher = {Springer},
title = {{Composition does not imply adaptive security}},
doi = {10.1007/11535218_4},
volume = {3621},
year = {2005},
}
@article{3416,
abstract = {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.},
author = {Harald Janovjak and Sapra, Tanuj K and Mueller, Daniel J},
journal = {Biophysical Journal},
number = {5},
pages = {37 -- 39},
publisher = {Biophysical Society},
title = {{Complex stability of single proteins explored by forced unfolding experiments}},
doi = {10.1529/biophysj.105.059774},
volume = {88},
year = {2005},
}
@article{3417,
abstract = {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/.},
author = {Kuhn, Michael and Harald Janovjak and Hubain, Maurice and Mueller, Daniel J},
journal = {Journal of Microscopy},
number = {2},
pages = {125 -- 132},
publisher = {Wiley-Blackwell},
title = {{Automated alignment and pattern recognition of single-molecule force spectroscopy data}},
doi = {10.1111/j.1365-2818.2005.01478.x},
volume = {218},
year = {2005},
}
@article{3418,
abstract = {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.},
author = {Harald Janovjak and Struckmeier, Jens and Mueller, Daniel J},
journal = {European Biophysics Journal},
number = {1},
pages = {91 -- 96},
publisher = {Springer},
title = {{Hydrodynamic effects in fast AFM single molecule force measurements}},
doi = {10.1007/s00249-004-0430-3},
volume = {34},
year = {2005},
}
@inbook{3433,
author = {Jonathan Bollback},
booktitle = {Statistical methods in Molecular Evolution},
editor = {Nielsen, Rasmus},
pages = {439 -- 462},
publisher = {Springer},
title = {{Posterior mapping and posterior predictive distributions}},
doi = {10.1007/0-387-27733-1},
year = {2005},
}
@article{3443,
abstract = {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.},
author = {Klausberger,Thomas and Marton,Laszlo F and Joseph O'Neill and Huck, Jojanneke H and Dalezios, Yannis and Fuentealba,Pablo and Suen, Wai Yee and Papp, Edit Cs and Kaneko, Takeshi and Watanabe, Masahiko and Jozsef Csicsvari and Somogyi, Péter},
journal = {Journal of Neuroscience},
number = {42},
pages = {9782 -- 9793},
publisher = {Society for Neuroscience},
title = {{Complementary roles of cholecystokinin- and parvalbumin-expressing GABAergic neurons in hippocampal network oscillations}},
doi = {10.1523/JNEUROSCI.3269-05.2005},
volume = {25},
year = {2005},
}
@misc{3509,
abstract = {Methods, apparatus and computer program products can generate light weight but highly realistic and accurate colored models of three-dimensional colored objects. The colored model may be generated from a second plurality of points that define a coarse digital representation of the surface and at least one texture map containing information derived from a first plurality of colored points that define a fine digital representation of the surface. This derivation is achieved by mapping points within the texture map to the fine digital representation of the three-dimensional surface. Colored scan data may be used to construct the fine digital representation as a triangulated surface (i.e., triangulation) using a wrapping operation.},
author = {Williams, Steven P and Herbert Edelsbrunner and Fu, Ping},
publisher = {Elsevier},
title = {{Methods, apparatus and computer program products for modeling three-dimensional colored objects}},
doi = {US 6,853,373 B2},
year = {2005},
}
@inproceedings{3557,
abstract = {A challenging problem in computer-aided geometric design is the decomposition of a surface into four-sided regions that are then represented by NURBS patches. There are various approaches published in the literature and implemented as commercially available software, but all fall short in either automation or quality of the result. At Raindrop Geomagic, we have recently taken a fresh approach based on concepts from Morse theory. This by itself is not a new idea, but we have some novel ingredients that make this work, one being a rational notion of hierarchy that guides the construction of a simplified decomposition sensitive to only the major critical points.},
author = {Herbert Edelsbrunner},
pages = {9 -- 11},
publisher = {ACM},
title = {{Surface tiling with differential topology}},
doi = {http://dx.doi.org/10.2312/SGP/SGP05/009-011},
year = {2005},
}
@inproceedings{3558,
abstract = {The tandem algorithm combines the marching cube algorithm for surface extraction and the edge contraction algorithm for surface simplification in lock-step to avoid the costly intermediate step of storing the entire extracted surface triangulation. Beyond this basic strategy, we introduce refinements to prevent artifacts in the resulting triangulation, first, by carefully monitoring the amount of simplification during the process and, second, by driving the simplification toward a compromise between shape approximation and mesh quality. We have implemented the algorithm and used extensive computational experiments to document the effects of various design options and to further fine-tune the algorithm.},
author = {Attali, Dominique and Cohen-Steiner, David and Herbert Edelsbrunner},
pages = {139 -- 148},
publisher = {ACM},
title = {{Extraction and simplification of iso-surfaces in tandem}},
year = {2005},
}
@inbook{3576,
abstract = {ears of research in biology have established that all cellular functions are deeply connected to the shape and dynamics of their molec- ular actors. As a response, structural molecular biology has emerged as a new line of experimental research focused on revealing the structure of biomolecules. The analysis of these structures has led to the development of computational biology, whose aim is to predict from molecular simulation properties inaccessible to experimental probes.
Here we focus on the representation of biomolecules used in these sim- ulations, and in particular on the hard sphere models. We review how the geometry of the union of such spheres is used to model their interactions with their environment, and how it has been included in simulations of molecular dynamics.
In parallel, we review our own developments in mathematics and com- puter science on understanding the geometry of unions of balls, and their applications in molecular simulation.},
author = {Herbert Edelsbrunner and Koehl, Patrice},
booktitle = {Combinatorial and Computational Geometry},
pages = {243 -- 275},
publisher = {Cambridge University Press},
title = {{The geometry of biomolecular solvation}},
volume = {52},
year = {2005},
}
@article{3611,
abstract = {We present two novel methods to infer mating patterns from genetic data. They differ from existing statistical methods of parentage inference in that they apply to populations that deviate from Hardy–Weinberg and linkage equilibrium, and so are suited for the study of assortative mating in hybrid zones. The core data set consists of genotypes at several loci for a number of full-sib clutches of unknown parentage. Our inference is based throughout on estimates of allelic associations within and across loci, such as heterozygote deficit and pairwise linkage disequilibrium. In the first method, the most likely parents of a given clutch are determined from the genotypic distribution of the associated adult population, given an explicit model of nonrandom mating. This leads to estimates of the strength of assortment. The second approach is based solely on the offspring genotypes and relies on the fact that a linear relation exists between associations among the offspring and those in the population of breeding pairs. We apply both methods to a sample from the hybrid zone between the fire-bellied toads Bombina bombina and B. variegata (Anura: Disco glossidae) in Croatia. Consistently, both approaches provide no evidence for a departure from random mating, despite adequate statistical power. Instead, B. variegata-like individuals among the adults contributed disproportionately to the offspring cohort, consistent with their preference for the type of breeding habitat in which this study was conducted.},
author = {Nürnberger, Beate and Nicholas Barton and Kruuk, Loeske E and Vines, Timothy H},
journal = {Heredity},
number = {2},
pages = {247 -- 257},
publisher = {Nature Publishing Group},
title = {{Mating patterns in a Bombina hybrid zone: Inferences from adult and full sib genotypes}},
doi = {10.1038/sj.hdy.6800607},
volume = {94},
year = {2005},
}
@article{3612,
abstract = {Left-right asymmetry in snails is intriguing because individuals of opposite chirality are either unable to mate or can only mate with difficulty, so could be reproductively isolated from each other. We have therefore investigated chiral evolution in the Japanese land snail genus Euhadra to understand whether changes in chirality have promoted speciation. In particular, we aimed to understand the effect of the maternal inheritance of chirality on reproductive isolation and gene flow. We found that the mitochondrial DNA phylogeny of Euhadra is consistent with a single, relatively ancient evolution of sinistral species and suggests either recent “single-gene speciation” or gene flow between chiral morphs that are unable to mate. To clarify the conditions under which new chiral morphs might evolve and whether single-gene speciation can occur, we developed a mathematical model that is relevant to any maternal-effect gene. The model shows that reproductive character displacement can promote the evolution of new chiral morphs, tending to counteract the positive frequency-dependent selection that would otherwise drive the more common chiral morph to fixation. This therefore suggests a general mechanism as to how chiral variation arises in snails. In populations that contain both chiral morphs, two different situations are then possible. In the first, gene flow is substantial between morphs even without interchiral mating, because of the maternal inheritance of chirality. In the second, reproductive isolation is possible but unstable, and will also lead to gene flow if intrachiral matings occasionally produce offspring with the opposite chirality. Together, the results imply that speciation by chiral reversal is only meaningful in the context of a complex biogeographical process, and so must usually involve other factors. In order to understand the roles of reproductive character displacement and gene flow in the chiral evolution of Euhadra, it will be necessary to investigate populations in which both chiral morphs coexist.},
author = {Davison, Angus and Chiba, Satoshi and Nicholas Barton and Clarke, Bernard},
journal = {PLoS Biology},
number = {9},
publisher = {Public Library of Science},
title = {{Speciation and gene flow between snails of opposing chirality}},
doi = {10.1371/journal.pbio.0030282},
volume = {3},
year = {2005},
}
@article{3613,
abstract = {The extent of genetic variation in fitness is a crucial issue in evolutionary biology and yet remains largely unresolved. In Drosophila melanogaster, we have devised a method that allows the net effects on fitness of heterozygous wild-type chromosomes to be measured, by competing them against two different “balancer” chromosomes. We have applied the method to a large sample of 40 wild-type third chromosomes and have measured fitnesses of nonlethal chromosomes as well as chromosomes bearing recessive lethals. The measurements were made in the environment to which the population was adapted and did not involve inbreeding. The results show an extraordinary similarity in the behavior of replicates of the same chromosome, indicating consistent genetic effects on total fitness. Some invading chromosomes increased rapidly and some slowly, and some rose to appreciable frequency after several months, but then declined again: in every case, the same pattern was seen in each replicate. We estimated relative fitnesses, rates of change of fitness, and relative viabilities, for each chromosome. There were significant fluctuations around the fitted model, which were also highly replicable. Wild-type chromosomes varied substantially in their effects on heterozygous fitness, and these effects vary through time, most likely as a result of genotype × environment interactions.},
author = {Gardner, Michael P and Fowler, Kevin and Nicholas Barton and Patridge, Linda},
journal = {Genetics},
number = {3},
pages = {1553 -- 1571},
publisher = {Genetics Society of America},
title = {{Genetic variation for total fitness in Drosophila melanogaster: Complex yet replicable patterns}},
doi = {10.1534/genetics.104.032367},
volume = {169},
year = {2005},
}
@inproceedings{3684,
abstract = {Ever since text processors became popular, users have
dreamt of handling documents printed on paper as comfortably
as electronic ones, with full text search typically
appearing very close to the top of the wish list.
This paper presents the design of a prototype system that
takes a step into this direction. The user’s desktop is continuously
monitored and of each detected document a high
resolution snapshot is taken using a digital camera. The
resulting image is processed using specially designed dewarping
and OCR algorithms, making a digital and fully
searchable version of the document available to the user in
real-time. These steps are performed without any user interaction.
This enables the system to run as a background
task without disturbing the user in her work, while at the
same time offering electronic access to all paper documents
that have been present on the desktop during the uptime of
the system.},
author = {Christoph Lampert and Braun,Tim and Ulges, Adrian and Keysers,Daniel and Breuel,Thomas M},
pages = {79 -- 86},
publisher = {CBDAR},
title = {{Oblivious document capture and real-time retrieval}},
year = {2005},
}
@inproceedings{3689,
abstract = {Digital cameras have become almost ubiquitous and their use for fast and casual capturing of natural images is unchallenged. For making images of documents, however, they have not caught up to flatbed scanners yet, mainly because camera images tend to suffer from distortion due to the perspective and are therefore limited in their further use for archival or OCR. For images of non-planar paper surfaces like books, page curl causes additional distortion, which poses an even greater problem due to its nonlinearity. This paper presents a new algorithm for removing both perspective and page curl distortion. It requires only a single camera image as input and relies on a priori layout information instead of additional hardware. Therefore, it is much more user friendly than most previous approaches, and allows for flexible ad hoc document capture. Results are presented showing that the algorithm produces visually pleasing output and increases OCR accuracy, thus having the potential to become a general purpose preprocessing tool for camera based document capture.},
author = {Ulges, Adrian and Christoph Lampert and Breuel,Thomas M},
pages = {1001 -- 1005},
publisher = {IEEE},
title = {{Document image dewarping using robust estimation of curled text lines}},
doi = { 10.1109/ICDAR.2005.90},
volume = {2},
year = {2005},
}
@article{3691,
abstract = {In strictly pseudoconvex domains with smooth boundary, we prove a commutator relationship between admissible integral operators, as introduced by Lieb and Range, and smooth vector fields which are tangential at boundary points. This makes it possible to gain estimates for admissible operators in function spaces which involve tangential derivatives. Examples are given under with circumstances these can be transformed into genuine Sobolev- and C k-estimates.},
author = {Christoph Lampert},
journal = {Publicacions Matemàtiques},
number = {1},
pages = {179 -- 195},
publisher = {Universitat Autònoma de Barcelona, Departament de Matemàtique},
title = {{Boundary regularity of admissible operators}},
doi = {10.5565/PUBLMAT_49105_08},
volume = {49},
year = {2005},
}
@article{3721,
abstract = {Recent advances in atomic force microscopy allowed globular and membrane proteins to be mechanically unfolded on a single-molecule level. Presented is an extension to the existing force spectroscopy experiments. While unfolding single bacteriorhodopsins from native purple membranes, small oscillation amplitudes (6–9nm) were supplied to the vertical displacement of the cantilever at a frequency of 3kHz. The phase and amplitude response of the cantilever-protein system was converted to reveal the elastic (conservative) and viscous (dissipative) contributions to the unfolding process. The elastic response (stiffness) of the extended parts of the protein were in the range of a few tens pN/nm and could be well described by the derivative of the wormlike chain model. Discrete events in the viscous response coincided with the unfolding of single secondary structure elements and were in the range of 1μNs/m. In addition, these force modulation spectroscopy experiments revealed novel mechanical unfolding intermediates of bacteriorhodopsin. We found that kinks result in a loss of unfolding cooperativity in transmembrane helices. Reconstructing force-distance spectra by the integration of amplitude-distance spectra verified their position, offering a novel approach to detect intermediates during the forced unfolding of single proteins.},
author = {Harald Janovjak and Mueller, Daniel J and Humphris, Andrew D},
journal = {Biophysical Journal},
number = {2},
pages = {1423 -- 1431},
publisher = {Biophysical Society},
title = {{Molecular force modulation spectroscopy revealing the dynamic response of single bacteriorhodopsins}},
doi = {10.1529/biophysj.104.052746},
volume = {88},
year = {2005},
}