@article{3605, abstract = {Many animals and plants show a correlation between the traits of the individuals in the mating pair, implying assortative mating. Given the ubiquity of assortative mating in nature, why and how it has evolved remain open questions. Here we attempt to answer these questions in those cases where the trait under assortment is the same in males and females. We consider the most favorable scenario for assortment to evolve, where the same trait is under assortment and viability selection. We find conditions for assortment to evolve using a multilocus formalism in a haploid population. Our results show how epistasis in fitness between the loci that control the focal trait is crucial for assortment to evolve. We then assume specific forms of assortment in haploids and diploids and study the limiting cases of selective and nonselective mating. We find that selection for increased assortment is weak and that where increased assortment is costly, it does not invade.}, author = {De Cara, Maria A and Nicholas Barton and Kirkpatrick, Mark}, journal = {American Naturalist}, number = {5}, pages = {580 -- 596}, publisher = {University of Chicago Press}, title = {{A model for the evolution of assortative mating}}, doi = {10.1086/587062}, volume = {171}, year = {2008}, } @article{3606, abstract = {Explicit formulae are given for the effects of a barrier to gene flow on random fluctuations in allele frequency; these formulae can also be seen as generating functions for the distribution of coalescence times. The formulae are derived using a continuous diffusion approximation, which is accurate over all but very small spatial scales. The continuous approximation is confirmed by comparison with the exact solution to the stepping stone model. In both one and two spatial dimensions, the variance of fluctuations in allele frequencies increases near the barrier; when the barrier is very strong, the variance doubles. However, the effect on fluctuations close to the barrier is much greater when the population is spread over two spatial dimensions than when it occupies a linear, one-dimensional habitat: barriers of strength comparable with the dispersal range (B≈σ) can have an appreciable effect in two dimensions, whereas only barriers with strength comparable with the characteristic scale (B\! \approx\! L \equals \sigma \sol \sqrt {2 \mu}\hskip2) are significant in one dimension (μ is the rate of mutation or long-range dispersal). Thus, in a two-dimensional population, barriers to gene flow can be detected through their effect on the spatial pattern of genetic marker alleles.}, author = {Nicholas Barton}, journal = {Genetical Research}, number = {1}, pages = {139 -- 149}, publisher = {Cambridge University Press}, title = {{The effect of a barrier to gene flow on patterns of geographic variation}}, doi = {10.1017/S0016672307009081}, volume = {90}, year = {2008}, } @inproceedings{3694, abstract = {Distributed Denial of Service (DDoS) attacks are today the most destabilizing factor in the global internet and there is a strong need for sophisticated solutions. We introduce a formal statistical framework and derive a Bayes optimal packet classifier from it. Our proposed practical algorithm "Adaptive History-Based IP Filtering" (AHIF) mitigates DDoS attacks near the victim and outperforms existing methods by at least 32% in terms of collateral damage. Furthermore, it adjusts to the strength of an ongoing attack and ensures availability of the attacked server. In contrast to other adaptive solutions, firewall rulesets used to resist an attack can be precalculated before an attack takes place. This ensures an immediate response in a DDoS emergency. For evaluation, simulated DDoS attacks and two real-world user traffic datasets are used.}, author = {Goldstein,Markus and Christoph Lampert and Reif,Matthias and Stahl,Armin and Breuel,Thomas M}, pages = {174 -- 179}, publisher = {IEEE}, title = {{Bayes optimal DDoS mitigation by adaptive history-based IP filtering}}, doi = {10.1109/ICN.2008.64}, year = {2008}, } @inproceedings{3698, abstract = {Kernel canonical correlation analysis (KCCA) is a dimensionality reduction technique for paired data. By finding directions that maximize correlation, KCCA learns representations that are more closely tied to the underlying semantics of the data rather than noise. However, meaningful directions are not only those that have high correlation to another modality, but also those that capture the manifold structure of the data. We propose a method that is simultaneously able to find highly correlated directions that are also located on high variance directions along the data manifold. This is achieved by the use of semi-supervised Laplacian regularization of KCCA. We show experimentally that Laplacian regularized training improves class separation over KCCA with only Tikhonov regularization, while causing no degradation in the correlation between modalities. We propose a model selection criterion based on the Hilbert-Schmidt norm of the semi-supervised Laplacian regularized cross-covariance operator, which we compute in closed form.}, author = {Blaschko,Matthew B and Christoph Lampert and Gretton,Arthur}, number = {Part 1}, pages = {133 -- 145}, publisher = {Springer}, title = {{Semi-supervised Laplacian regularization of kernel canonical correlation analysis}}, doi = {10.1007/978-3-540-87479-9_27}, volume = {5211}, year = {2008}, } @inproceedings{3700, abstract = {We propose a new method to partition an unlabeled dataset, called Discriminative Context Partitioning (DCP). It is motivated by the idea of splitting the dataset based only on how well the resulting parts can be separated from a context class of disjoint data points. This is in contrast to typical clustering techniques like K-means that are based on a generative model by implicitly or explicitly searching for modes in the distribution of samples. The discriminative criterion in DCP avoids the problems that density based methods have when the a priori assumption of multimodality is violated, when the number of samples becomes small in relation to the dimensionality of the feature space, or if the cluster sizes are strongly unbalanced. We formulate DCP‘s separation property as a large-margin criterion, and show how the resulting optimization problem can be solved efficiently. Experiments on the MNIST and USPS datasets of handwritten digits and on a subset of the Caltech256 dataset show that, given a suitable context, DCP can achieve good results even in situation where density-based clustering techniques fail.}, author = {Christoph Lampert}, pages = {1 -- 8}, publisher = {IEEE}, title = {{Partitioning of image datasets using discriminative context information}}, doi = {10.1109/CVPR.2008.4587448}, year = {2008}, } @inproceedings{3705, abstract = {Sliding window classifiers are among the most successful and widely applied techniques for object localization. However, training is typically done in a way that is not specific to the localization task. First a binary classifier is trained using a sample of positive and negative examples, and this classifier is subsequently applied to multiple regions within test images. We propose instead to treat object localization in a principled way by posing it as a problem of predicting structured data: we model the problem not as binary classification, but as the prediction of the bounding box of objects located in images. The use of a joint-kernel framework allows us to formulate the training procedure as a generalization of an SVM, which can be solved efficiently. We further improve computational efficiency by using a branch-and-bound strategy for localization during both training and testing. Experimental evaluation on the PASCAL VOC and TU Darmstadt datasets show that the structured training procedure improves pe rformance over binary training as well as the best previously published scores.}, author = {Blaschko,Matthew B and Christoph Lampert}, pages = {2 -- 15}, publisher = {Springer}, title = {{Learning to localize objects with structured output regression}}, doi = {10.1007/978-3-540-88682-2_2}, volume = {5302}, year = {2008}, } @inproceedings{3706, abstract = {We present a new technique for structured prediction that works in a hybrid generative/discriminative way, using a one-class support vector machine to model the joint probability of (input, output)-pairs in a joint reproducing kernel Hilbert space. Compared to discriminative techniques, like conditional random fields or structured output SVMs?, the proposed method has the advantage that its training time depends only on the number of training examples, not on the size of the label space. Due to its generative aspect, it is also very tolerant against ambiguous, incomplete or incorrect labels. Experiments on realistic data show that our method works efficiently and robustly in situations that discriminative techniques have problems with or that are computationally infeasible for them.}, author = {Christoph Lampert and Blaschko,Matthew B}, pages = {1 -- 4}, publisher = {Curran Associates, Inc.}, title = {{Joint kernel support estimation for structured prediction}}, year = {2008}, } @inproceedings{3712, abstract = {We present a new method for spectral clustering with paired data based on kernel canonical correlation analysis, called correlational spectral clustering. Paired data are common in real world data sources, such as images with text captions. Traditional spectral clustering algorithms either assume that data can be represented by a single similarity measure, or by co-occurrence matrices that are then used in biclustering. In contrast, the proposed method uses separate similarity measures for each data representation, and allows for projection of previously unseen data that are only observed in one representation (e.g. images but not text). We show that this algorithm generalizes traditional spectral clustering algorithms and show consistent empirical improvement over spectral clustering on a variety of datasets of images with associated text.}, author = {Blaschko,Matthew B and Christoph Lampert}, pages = {1 -- 8}, publisher = {IEEE}, title = {{Correlational spectral clustering}}, doi = {10.1109/CVPR.2008.4587353}, year = {2008}, } @inproceedings{3714, abstract = {Most successful object recognition systems rely on binary classification, deciding only if an object is present or not, but not providing information on the actual object location. To perform localization, one can take a sliding window approach, but this strongly increases the computational cost, because the classifier function has to be evaluated over a large set of candidate subwindows. In this paper, we propose a simple yet powerful branchand- bound scheme that allows efficient maximization of a large class of classifier functions over all possible subimages. It converges to a globally optimal solution typically in sublinear time. We show how our method is applicable to different object detection and retrieval scenarios. The achieved speedup allows the use of classifiers for localization that formerly were considered too slow for this task, such as SVMs with a spatial pyramid kernel or nearest neighbor classifiers based on the 2-distance. We demonstrate state-of-the-art performance of the resulting systems on the UIUC Cars dataset, the PASCAL VOC 2006 dataset and in the PASCAL VOC 2007 competition.}, author = {Christoph Lampert and Blaschko,Matthew B and Hofmann,Thomas}, pages = {1 -- 8}, publisher = {IEEE}, title = {{Beyond sliding windows: Object localization by efficient subwindow search}}, doi = {10.1109/CVPR.2008.4587586}, year = {2008}, } @inproceedings{3716, abstract = {Most current methods for multi-class object classification and localization work as independent 1-vs-rest classifiers. They decide whether and where an object is visible in an image purely on a per-class basis. Joint learning of more than one object class would generally be preferable, since this would allow the use of contextual information such as co-occurrence between classes. However, this approach is usually not employed because of its computational cost. In this paper we propose a method to combine the efficiency of single class localization with a subsequent decision process that works jointly for all given object classes. By following a multiple kernel learning (MKL) approach, we automatically obtain a sparse dependency graph of relevant object classes on which to base the decision. Experiments on the PASCAL VOC 2006 and 2007 datasets show that the subsequent joint decision step clearly improves the accuracy compared to single class detection. }, author = {Christoph Lampert and Blaschko,Matthew B}, pages = {31 -- 40}, publisher = {Springer}, title = {{A multiple kernel learning approach to joint multi-class object detection}}, doi = {10.1007/978-3-540-69321-5_4}, volume = {5096}, year = {2008}, } @inbook{3726, abstract = {Single-molecule atomic force microscopy (AFM) provides novel ways to characterize the structure-function relationship of native membrane proteins. High-resolution AFM topographs allow observing the structure of single proteins at sub-nanometer resolution as well as their conformational changes, oligomeric state, molecular dynamics and assembly. We will review these feasibilities illustrating examples of membrane proteins in native and reconstituted membranes. Classification of individual topographs of single proteins allows understanding the principles of motions of their extrinsic domains, to learn about their local structural flexibilities and to find the entropy minima of certain conformations. Combined with the visualization of functionally related conformational changes these insights allow understanding why certain flexibilities are required for the protein to function and how structurally flexible regions allow certain conformational changes. Complementary to AFM imaging, single-molecule force spectroscopy (SMFS) experiments detect molecular interactions established within and between membrane proteins. The sensitivity of this method makes it possible to measure interactions that stabilize secondary structures such as transmembrane α-helices, polypeptide loops and segments within. Changes in temperature or protein-protein assembly do not change the locations of stable structural segments, but influence their stability established by collective molecular interactions. Such changes alter the probability of proteins to choose a certain unfolding pathway. Recent examples have elucidated unfolding and refolding pathways of membrane proteins as well as their energy landscapes.}, author = {Engel, Andreas and Harald Janovjak and Fotiadis, Dimtrios and Kedrov, Alexej and Cisneros, David and Mueller, Daniel J}, booktitle = {Single Molecules and Nanotechnology}, pages = {279 -- 311}, publisher = {Springer}, title = {{Single-molecule microscopy and force spectroscopy of membrane proteins}}, doi = {10.1007/978-3-540-73924-1_11}, volume = {12}, year = {2008}, } @article{3734, abstract = {Gene expression levels fluctuate even under constant external conditions. Much emphasis has usually been placed on the components of this noise that are due to randomness in transcription and translation. Here we focus on the role of noise associated with the inputs to transcriptional regulation; in particular, we analyze the effects of random arrival times and binding of transcription factors to their target sites along the genome. This contribution to the total noise sets a fundamental physical limit to the reliability of genetic control, and has clear signatures, but we show that these are easily obscured by experimental limitations and even by conventional methods for plotting the variance vs. mean expression level. We argue that simple, universal models of noise dominated by transcription and translation are inconsistent with the embedding of gene expression in a network of regulatory interactions. Analysis of recent experiments on transcriptional control in the early Drosophila embryo shows that these results are quantitatively consistent with the predicted signatures of input noise, and we discuss the experiments needed to test the importance of input noise more generally.}, author = {Gasper Tkacik and Gregor, Thomas and Bialek, William S}, journal = {PLoS One}, number = {7}, publisher = {Public Library of Science}, title = {{The role of input noise in transcriptional regulation}}, doi = {10.1371/journal.pone.0002774}, volume = {3}, year = {2008}, } @article{3739, abstract = {Changes in a cell's external or internal conditions are usually reflected in the concentrations of the relevant transcription factors. These proteins in turn modulate the expression levels of the genes under their control and sometimes need to perform nontrivial computations that integrate several inputs and affect multiple genes. At the same time, the activities of the regulated genes would fluctuate even if the inputs were held fixed, as a consequence of the intrinsic noise in the system, and such noise must fundamentally limit the reliability of any genetic computation. Here we use information theory to formalize the notion of information transmission in simple genetic regulatory elements in the presence of physically realistic noise sources. The dependence of this "channel capacity" on noise parameters, cooperativity and cost of making signaling molecules is explored systematically. We find that, in the range of parameters probed by recent in vivo measurements, capacities higher than one bit should be achievable. It is of course generally accepted that gene regulatory elements must, in order to function properly, have a capacity of at least one bit. The central point of our analysis is the demonstration that simple physical models of noisy gene transcription, with realistic parameters, can indeed achieve this capacity: it was not self-evident that this should be so. We also demonstrate that capacities significantly greater than one bit are possible, so that transcriptional regulation need not be limited to simple "on-off" components. The question whether real systems actually exploit this richer possibility is beyond the scope of this investigation.}, author = {Gasper Tkacik and Callan,Curtis G and Bialek, William S}, journal = {Physical Review E Statistical Nonlinear and Soft Matter Physics}, number = {1}, publisher = {American Institute of Physics}, title = {{Information capacity of genetic regulatory elements}}, doi = {10.1103/PhysRevE.78.011910}, volume = {78}, year = {2008}, } @article{3740, abstract = {In the simplest view of transcriptional regulation, the expression of a gene is turned on or off by changes in the concentration of a transcription factor (TF). We use recent data on noise levels in gene expression to show that it should be possible to transmit much more than just one regulatory bit. Realizing this optimal information capacity would require that the dynamic range of TF concentrations used by the cell, the input/output relation of the regulatory module, and the noise in gene expression satisfy certain matching relations, which we derive. These results provide parameter-free, quantitative predictions connecting independently measurable quantities. Although we have considered only the simplified problem of a single gene responding to a single TF, we find that these predictions are in surprisingly good agreement with recent experiments on the Bicoid/Hunchback system in the early Drosophila embryo and that this system achieves approximately 90% of its theoretical maximum information transmission.}, author = {Gasper Tkacik and Callan,Curtis G and Bialek, William S}, journal = {PNAS}, number = {34}, pages = {12265 -- 12270}, publisher = {National Academy of Sciences}, title = {{Information flow and optimization in transcriptional regulation}}, doi = {10.1073/pnas.0806077105}, volume = {105}, year = {2008}, } @article{3744, abstract = {It is widely acknowledged that detailed timing of action potentials is used to encode information, for example, in auditory pathways; however, the computational tools required to analyze encoding through timing are still in their infancy. We present a simple example of encoding, based on a recent model of time-frequency analysis, in which units fire action potentials when a certain condition is met, but the timing of the action potential depends also on other features of the stimulus. We show that, as a result, spike-triggered averages are smoothed so much that they do not represent the true features of the encoding. Inspired by this example, we present a simple method, differential reverse correlations, that can separate an analysis of what causes a neuron to spike, and what controls its timing. We analyze with this method the leaky integrate-and-fire neuron and show the method accurately reconstructs the model's kernel.}, author = {Gasper Tkacik and Magnasco, Marcelo O}, journal = {Biosystems}, number = {1-2}, pages = {90 -- 100}, publisher = {Elsevier}, title = {{Decoding spike timing: The differential reverse-correlation method}}, doi = {10.1016/j.biosystems.2008.04.011}, volume = {93}, year = {2008}, } @article{3751, abstract = {Revealing the spectrum of combinatorial regulation of transcription at individual promoters is essential for understanding the complex structure of biological networks. However, the computations represented by the integration of various molecular signals at complex promoters are difficult to decipher in the absence of simple cis regulatory codes. Here we synthetically shuffle the regulatory architecture-operator sequences binding activators and repressors-of a canonical bacterial promoter. The resulting library of complex promoters allows for rapid exploration of promoter encoded logic regulation. Among all possible logic functions, NOR and ANDN promoter encoded logics predominate. A simple transcriptional cis regulatory code determines both logics, establishing a straightforward map between promoter structure and logic phenotype. The regulatory code is determined solely by the type of transcriptional regulation combinations: two repressors generate a NOR: NOT (a OR b) whereas a repressor and an activator generate an ANDN: a AND NOT b. Three-input versions of both logics, having an additional repressor as an input, are also present in the library. The resulting complex promoters cover a wide dynamic range of transcriptional strengths. Synthetic promoter shuffling represents a fast and efficient method for exploring the spectrum of complex regulatory functions that can be encoded by complex promoters. From an engineering point of view, synthetic promoter shuffling enables the experimental testing of the functional properties of complex promoters that cannot necessarily be inferred ab initio from the known properties of the individual genetic components. Synthetic promoter shuffling may provide a useful experimental tool for studying naturally occurring promoter shuffling.}, author = {Kinkhabwala, Ali and Guet, Calin C}, journal = {PLoS One}, number = {4}, publisher = {Public Library of Science}, title = {{Uncovering cis regulatory codes using synthetic promoter shuffling}}, doi = {10.1371/journal.pone.0002030}, volume = {3}, year = {2008}, } @article{3754, abstract = {Fluorescence correlation spectroscopy (FCS) has permitted the characterization of high concentrations of noncoding RNAs in a single living bacterium. Here, we extend the use of FCS to low concentrations of coding RNAs in single living cells. We genetically fuse a red fluorescent protein (RFP) gene and two binding sites for an RNA-binding protein, whose translated product is the RFP protein alone. Using this construct, we determine in single cells both the absolute [mRNA] concentration and the associated [RFP] expressed from an inducible plasmid. We find that the FCS method allows us to reliably monitor in real-time [mRNA] down to similar to 40 nM (i.e. approximately two transcripts per volume of detection). To validate these measurements, we show that [mRNA] is proportional to the associated expression of the RFP protein. This FCS-based technique establishes a framework for minimally invasive measurements of mRNA concentration in individual living bacteria.}, author = {Calin Guet and Bruneaux,Luke and Min,Taejin L and Siegal-Gaskins,Dan and Figueroa,Israel and Emonet,Thierry and Cluzel,Philippe}, journal = {Nucleic Acids Research}, number = {12}, publisher = {Oxford University Press}, title = {{Minimally invasive determination of mRNA concentration in single living bacteria}}, doi = {10.1093/nar/gkn329}, volume = {36}, year = {2008}, } @article{3760, abstract = {We introduce a method for efficiently animating a wide range of deformable materials. We combine a high resolution surface mesh with a tetrahedral finite element simulator that makes use of frequent re-meshing. This combination allows for fast and detailed simulations of complex elastic and plastic behavior. We significantly expand the range of physical parameters that can be simulated with a single technique, and the results are free from common artifacts such as volume-loss, smoothing, popping, and the absence of thin features like strands and sheets. Our decision to couple a high resolution surface with low-resolution physics leads to efficient simulation and detailed surface features, and our approach to creating the tetrahedral mesh leads to an order-of-magnitude speedup over previous techniques in the time spent re-meshing. We compute masses, collisions, and surface tension forces on the scale of the fine mesh, which helps avoid visual artifacts due to the differing mesh resolutions. The result is a method that can simulate a large array of different material behaviors with high resolution features in a short amount of time.}, author = {Wojtan, Christopher J and Turk, Greg}, journal = {ACM Transactions on Graphics}, number = {3}, publisher = {ACM}, title = {{Fast viscoelastic behavior with thin features}}, doi = {10.1145/1360612.1360646}, volume = {27}, year = {2008}, } @article{3769, abstract = {The geometrical representation of the space of phylogenetic trees implies a metric on the space of weighted trees. This metric, the geodesic distance, is the length of the shortest path through that space. We present an exact algorithm to compute this metric. For biologically reasonable trees, the implementation allows fast computations of the geodesic distance, although the running time of the algorithm is worst-case exponential. The algorithm was applied to pairs of 118 gene trees of the metazoa. The results show that a special path in tree space, the cone path, which can be computed in linear time, is a good approximation of the geodesic distance. The program GeoMeTree is a python implementation of the geodesic distance, and it is approximations and is available from www.cibiv.at/software/geometree.}, author = {Anne Kupczok and von Haeseler,Arndt and Klaere,Steffen}, journal = {Journal of Computational Biology}, number = {6}, pages = {577 -- 591}, publisher = {Mary Ann Liebert}, title = {{An Exact Algorithm for the Geodesic Distance between Phylogenetic Trees.}}, doi = {4200}, volume = {15}, year = {2008}, } @article{3822, abstract = {Dentate gyrus granule cells transmit action potentials (APs) along their unmyelinated mossy fibre axons to the CA3 region. Although the initiation and propagation of APs are fundamental steps during neural computation, little is known about the site of AP initiation and the speed of propagation in mossy fibre axons. To address these questions, we performed simultaneous somatic and axonal whole-cell recordings from granule cells in acute hippocampal slices of adult mice at approximately 23 degrees C. Injection of short current pulses or synaptic stimulation evoked axonal and somatic APs with similar amplitudes. By contrast, the time course was significantly different, as axonal APs had a higher maximal rate of rise (464 +/- 30 V s(-1) in the axon versus 297 +/- 12 V s(-1) in the soma, mean +/- s.e.m.). Furthermore, analysis of latencies between the axonal and somatic signals showed that APs were initiated in the proximal axon at approximately 20-30 mum distance from the soma, and propagated orthodromically with a velocity of 0.24 m s(-1). Qualitatively similar results were obtained at a recording temperature of approximately 34 degrees C. Modelling of AP propagation in detailed cable models of granule cells suggested that a approximately 4 times higher Na(+) channel density ( approximately 1000 pS mum(-2)) in the axon might account for both the higher rate of rise of axonal APs and the robust AP initiation in the proximal mossy fibre axon. This may be of critical importance to separate dendritic integration of thousands of synaptic inputs from the generation and transmission of a common AP output.}, author = {Schmidt-Hieber, Christoph and Peter Jonas and Bischofberger, Josef}, journal = {Journal of Physiology}, number = {7}, pages = {1849 -- 57}, publisher = {Wiley-Blackwell}, title = {{Action potential initiation and propagation in hippocampal mossy fibre axons}}, doi = {10.1113/jphysiol.2007.150151 }, volume = {586}, year = {2008}, }