Search

The main contribution of this work is a fast algorithm to compute the barycentre of a set of networks based on a Laplacian spectral pseudo-distance. The core engine for the reconstruction of the barycentre is an algorithm that explores the large library of Soules bases, and returns a basis that yields a sparse approximation of the sample mean adjacency matrix. We prove that when the networks are random realizations of stochastic block models, then our algorithm reconstructs the population mean adjacency matrix. In addition to the theoretical analysis of the estimator of the barycentre network, we perform Monte Carlo simulations to validate the theoretical properties of the estimator. This work is significant because it opens the door to the design of new spectral-based network synthesis that have theoretical guarantees., Comment: 20 pages

The notion of Fr\'echet mean (also known as "barycenter") network is the workhorse of most machine learning algorithms that require the estimation of a "location" parameter to analyse network-valued data. In this context, it is critical that the network barycenter inherits the topological structure of the networks in the training dataset. The metric - which measures the proximity between networks - controls the structural properties of the barycenter. This work is significant because it provides for the first time analytical estimates of the sample Fr\'echet mean for the stochastic blockmodel, which is at the cutting edge of rigorous probabilistic analysis of random networks. We show that the mean network computed with the Hamming distance is unable to capture the topology of the networks in the training sample, whereas the mean network computed using the effective resistance distance recovers the correct partitions and associated edge density. From a practical standpoint, our work informs the choice of metrics in the context where the sample Fr\'echet mean network is used to characterise the topology of networks for network-valued machine learning, Comment: 23 pages

Proteomics is the large scale study of protein structure and function from biological systems through protein identification and quantification. "Shotgun proteomics" or "bottom-up proteomics" is the prevailing strategy, in which proteins are hydrolyzed into peptides that are analyzed by mass spectrometry. Proteomics studies can be applied to diverse studies ranging from simple protein identification to studies of proteoforms, protein-protein interactions, protein structural alterations, absolute and relative protein quantification, post-translational modifications, and protein stability. To enable this range of different experiments, there are diverse strategies for proteome analysis. The nuances of how proteomic workflows differ may be challenging to understand for new practitioners. Here, we provide a comprehensive overview of different proteomics methods to aid the novice and experienced researcher. We cover from biochemistry basics and protein extraction to biological interpretation and orthogonal validation. We expect this work to serve as a basic resource for new practitioners in the field of shotgun or bottom-up proteomics.

How predictable is the next move of an animal? Specifically, which factors govern the short- and long-term motion patterns and the overall dynamics of landbound, plant-eating animals and ruminants in particular? To answer this question, we here study the movement dynamics of springbok antelopes Antidorcas marsupialis. We propose complementary statistical analysis techniques combined with machine learning approaches to analyze, across multiple time scales, the springbok motion recorded in long-term GPS-tracking of collared springboks at a private wildlife reserve in Namibia. As a new result, we are able to predict the springbok movement within the next hour with a certainty of about 20\%. The remaining 80\% are stochastic in nature and are induced by unaccounted factors in the modeling algorithm and by individual behavioral features of springboks. We find that directedness of motion contributes approximately 17\% to this predicted fraction. We find that the measure for directedeness is strongly dependent on the daily cycle. The previously known daily affinity of springboks to their water points, as predicted from our machine learning algorithm, overall accounts for only 3\% of this predicted deterministic component of springbok motion. Moreover, the resting points are found to affect the motion of springboks at least as much as the formally studied effects of water points. The generality of these statements for the motion patterns and their underlying behavioral reasons for other ruminants can be examined on the basis of our statistical analysis tools., Comment: 17 pages, 9 figures, RevTeX

This work addresses the rising demand for novel tools in statistical and machine learning for "graph-valued random variables" by proposing a fast algorithm to compute the sample Frechet mean, which replaces the concept of sample mean for graphs (or networks). We use convolutional neural networks to learn the morphology of the graphs in a set of graphs. Our experiments on several ensembles of random graphs demonstrate that our method can reliably recover the sample Frechet mean.

For graph-valued data sampled iid from a distribution $\mu$, the sample moments are computed with respect to a choice of metric. In this work, we equip the set of graphs with the pseudo-metric defined by the $\ell_2$ norm between the eigenvalues of the respective adjacency matrices. We use this pseudo metric and the respective sample moments of a graph valued data set to infer the parameters of a distribution $\hat{\mu}$ and interpret this distribution as an approximation of $\mu$. We verify experimentally that complex distributions $\mu$ can be approximated well taking this approach.

The COVID-19 pandemic has presented many challenges that have spurred biotechnological research to address specific problems. Diagnostics is one area where biotechnology has been critical. Diagnostic tests play a vital role in managing a viral threat by facilitating the detection of infected and/or recovered individuals. From the perspective of what information is provided, these tests fall into two major categories, molecular and serological. Molecular diagnostic techniques assay whether a virus is present in a biological sample, thus making it possible to identify individuals who are currently infected. Additionally, when the immune system is exposed to a virus, it responds by producing antibodies specific to the virus. Serological tests make it possible to identify individuals who have mounted an immune response to a virus of interest and therefore facilitate the identification of individuals who have previously encountered the virus. These two categories of tests provide different perspectives valuable to understanding the spread of SARS-CoV-2. Within these categories, different biotechnological approaches offer specific advantages and disadvantages. Here we review the categories of tests developed for the detection of the SARS-CoV-2 virus or antibodies against SARS-CoV-2 and discuss the role of diagnostics in the COVID-19 pandemic.

Wordle is an online word puzzle game that gained viral popularity in January 2022. The goal is to guess a hidden five letter word. After each guess, the player gains information about whether the letters they guessed are present in the word, and whether they are in the correct position. Numerous blogs have suggested guessing strategies and starting word lists that improve the chance of winning. Optimized algorithms can win 100% of games within five of the six allowed trials. However, it is infeasible for human players to use these algorithms due to an inability to perfectly recall all known 5-letter words and perform complex calculations that optimize information gain. Here, we present two different methods for choosing starting words along with a framework for discovering the optimal human strategy based on reinforcement learning. Human Wordle players can use the rules we discover to optimize their chance of winning.

We address the following foundational question: what is the population, and sample, Frechet mean (or median) graph of an ensemble of inhomogeneous Erdos-Renyi random graphs? We prove that if we use the Hamming distance to compute distances between graphs, then the Frechet mean (or median) graph of an ensemble of inhomogeneous random graphs is obtained by thresholding the expected adjacency matrix of the ensemble. We show that the result also holds for the sample mean (or median) when the population expected adjacency matrix is replaced with the sample mean adjacency matrix. Consequently, the Frechet mean (or median) graph of inhomogeneous Erdos-Renyi random graphs exhibits a sharp threshold: it is either the empty graph, or the complete graph. This novel theoretical result has some significant practical consequences; for instance, the Frechet mean of an ensemble of sparse inhomogeneous random graphs is always the empty graph.

To characterize the location (mean, median) of a set of graphs, one needs a notion of centrality that is adapted to metric spaces, since graph sets are not Euclidean spaces. A standard approach is to consider the Frechet mean. In this work, we equip a set of graphs with the pseudometric defined by the norm between the eigenvalues of their respective adjacency matrix. Unlike the edit distance, this pseudometric reveals structural changes at multiple scales, and is well adapted to studying various statistical problems for graph-valued data. We describe an algorithm to compute an approximation to the sample Frechet mean of a set of undirected unweighted graphs with a fixed size using this pseudometric., Comment: arXiv admin note: text overlap with arXiv:2105.04062

The availability of large datasets composed of graphs creates an unprecedented need to invent novel tools in statistical learning for graph-valued random variables. To characterize the average of a sample of graphs, one can compute the sample Frechet mean and median graphs. In this paper, we address the following foundational question: does a mean or median graph inherit the structural properties of the graphs in the sample? An important graph property is the edge density; we establish that edge density is an hereditary property, which can be transmitted from a graph sample to its sample Frechet mean or median graphs, irrespective of the method used to estimate the mean or the median. Because of the prominence of the Frechet mean in graph-valued machine learning, this novel theoretical result has some significant practical consequences., Comment: 14 pages

Deviations from Brownian motion leading to anomalous diffusion are ubiquitously found in transport dynamics, playing a crucial role in phenomena from quantum physics to life sciences. The detection and characterization of anomalous diffusion from the measurement of an individual trajectory are challenging tasks, which traditionally rely on calculating the mean squared displacement of the trajectory. However, this approach breaks down for cases of important practical interest, e.g., short or noisy trajectories, ensembles of heterogeneous trajectories, or non-ergodic processes. Recently, several new approaches have been proposed, mostly building on the ongoing machine-learning revolution. Aiming to perform an objective comparison of methods, we gathered the community and organized an open competition, the Anomalous Diffusion challenge (AnDi). Participating teams independently applied their own algorithms to a commonly-defined dataset including diverse conditions. Although no single method performed best across all scenarios, the results revealed clear differences between the various approaches, providing practical advice for users and a benchmark for developers., Comment: 63 pages, 5 main figures, 1 table, 28 supplementary figures. Website: http://www.andi-challenge.org

To characterize the location (mean, median) of a set of graphs, one needs a notion of centrality that is adapted to metric spaces, since graph sets are not Euclidean spaces. A standard approach is to consider the Fr\'echet mean. In this work, we equip a set of graph with the pseudometric defined by the $\ell_2$ norm between the eigenvalues of their respective adjacency matrix . Unlike the edit distance, this pseudometric reveals structural changes at multiple scales, and is well adapted to studying various statistical problems on sets of graphs. We describe an algorithm to compute an approximation to the Fr\'echet mean of a set of undirected unweighted graphs with a fixed size., Comment: 28 pages

False-positive results and bias may be common features of the biomedical literature today, including risk factor-chronic disease research. A study was undertaken to assess the reliability of base studies used in a meta-analysis examining whether carbon monoxide, particulate matter 10 and 2.5 micro molar, sulfur dioxide, nitrogen dioxide and ozone are risk factors for asthma exacerbation (hospital admission and emergency room visits for asthma attack). The number of statistical tests and models were counted in 17 randomly selected base papers from 87 used in the meta-analysis. P-value plots for each air component were constructed to evaluate the effect heterogeneity of p-values used from all 87 base papers The number of statistical tests possible in the 17 selected base papers was large, median=15,360 (interquartile range=1,536 to 40,960), in comparison to results presented. Each p-value plot showed a two-component mixture with small p-values less than .001 while other p-values appeared random (p-values greater than .05). Given potentially large numbers of statistical tests conducted in the 17 selected base papers, p-hacking cannot be ruled out as explanations for small p-values. Our interpretation of the meta-analysis is that the random p-values indicating null associations are more plausible and that the meta-analysis will not likely replicate in the absence of bias. We conclude the meta-analysis and base papers used are unreliable and do not offer evidence of value to inform public health practitioners about air quality as a risk factor for asthma exacerbation. The following areas are crucial for enabling improvements in risk factor chronic disease observational studies at the funding agency and journal level: preregistration, changes in funding agency and journal editor (and reviewer) practices, open sharing of data and facilitation of reproducibility research., Comment: Paper with supplemental material

We study a method for detecting the origins of anomalous diffusion, when it is observed in an ensemble of times-series, generated experimentally or numerically, without having knowledge about the exact underlying dynamics. The reasons for anomalous diffusive scaling of the mean-squared displacement are decomposed into three root causes: increment correlations are expressed by the "Joseph effect" [Mandelbrot 1968], fat-tails of the increment probability density lead to a "Noah effect" [Mandelbrot 1968], and non-stationarity, to the "Moses effect" [Chen et al. 2017]. After appropriate rescaling, based on the quantification of these effects, the increment distribution converges at increasing times to a time-invariant asymptotic shape. For different processes, this asymptotic limit can be an equilibrium state, an infinite-invariant, or an infinite-covariant density. We use numerical methods of time-series analysis to quantify the three effects in a model of a non-linearly coupled L\'evy walk, compare our results to theoretical predictions, and discuss the generality of the method., Comment: Main text is 13 pages, 3 pages of appendixes

We analyze European temperature variability from station data with the method of detrended fluctuation analysis. This method is known to give a scaling exponent indicating long range correlations in time for temperature anomalies. However, by a more careful look at the fluctuation function we are able to explain the emergent scaling behaviour by short time relaxation, the yearly cycle and one additional process. It turns out that for many stations this interannual variability is an oscillatory mode with a period length of approximately 7-8 years, which is consistent with results of other methods. We discuss the spatial patterns in all parameters and validate the finding of the 7-8 year period by comparing stations with and without this mode.

Comparison of graph structure is a ubiquitous task in data analysis and machine learning, with diverse applications in fields such as neuroscience, cyber security, social network analysis, and bioinformatics, among others. Discovery and comparison of structures such as modular communities, rich clubs, hubs, and trees in data in these fields yields insight into the generative mechanisms and functional properties of the graph. Often, two graphs are compared via a pairwise distance measure, with a small distance indicating structural similarity and vice versa. Common choices include spectral distances (also known as $\lambda$ distances) and distances based on node affinities. However, there has of yet been no comparative study of the efficacy of these distance measures in discerning between common graph topologies and different structural scales. In this work, we compare commonly used graph metrics and distance measures, and demonstrate their ability to discern between common topological features found in both random graph models and empirical datasets. We put forward a multi-scale picture of graph structure, in which the effect of global and local structure upon the distance measures is considered. We make recommendations on the applicability of different distance measures to empirical graph data problem based on this multi-scale view. Finally, we introduce the Python library NetComp which implements the graph distances used in this work.

Identification of nearly all proteins in a system using data-dependent acquisition (DDA) mass spectrometry has become routine for simple organisms, such as bacteria and yeast. Still, quantification of the identified proteins may be a complex process and require multiple different software packages. This protocol describes identification and label-free quantification of proteins from bottom-up proteomics experiments. This method can be used to quantify all the detectable proteins in any DDA dataset collected with high-resolution precursor scans. This protocol may be used to quantify proteome remodeling in response to a drug treatment or a gene knockout. Notably, the method uses the latest and fastest freely-available software, and the entire protocol can be completed in a few hours with data from organisms with relatively small genomes, such as yeast or bacteria.

We decompose the anomalous diffusive behavior found in a model of aging into its fundamental constitutive causes. The model process is a sum of increments that are iterates of a chaotic dynamical system, the Pomeau-Manneville map. The increments can have long-time correlations, fat-tailed distributions and be non-stationary. Each of these properties can cause anomalous diffusion through what is known as the Joseph, Noah and Moses effects, respectively. The model can have either sub- or super-diffusive behavior, which we find is generally due to a combination of the three effects. Scaling exponents quantifying each of the three constitutive effects are calculated using analytic methods and confirmed with numerical simulations. They are then related to the scaling of the distribution of the process through a scaling relation. Finally, the importance of the Moses effect in the anomalous diffusion of experimental systems is discussed., Comment: This is an author-created, un-copyedited version of an article accepted for publication in the New Journal of Physics. IOP Publishing Ltd is not responsible for any errors or omissions in this version of the manuscript or any version derived from it. The Version of Record is available online at https://doi.org/10.1088/1367-2630/aaeea2

The study of time-varying (dynamic) networks (graphs) is of fundamental importance for computer network analytics. Several methods have been proposed to detect the effect of significant structural changes in a time series of graphs. The main contribution of this work is a detailed analysis of a dynamic community graph model. This model is formed by adding new vertices, and randomly attaching them to the existing nodes. It is a dynamic extension of the well-known stochastic blockmodel. The goal of the work is to detect the time at which the graph dynamics switches from a normal evolution -- where balanced communities grow at the same rate -- to an abnormal behavior -- where communities start merging. In order to circumvent the problem of decomposing each graph into communities, we use a metric to quantify changes in the graph topology as a function of time. The detection of anomalies becomes one of testing the hypothesis that the graph is undergoing a significant structural change. In addition the the theoretical analysis of the test statistic, we perform Monte Carlo simulations of our dynamic graph model to demonstrate that our test can detect changes in graph topology.

We report on the development of a new family of SQUID current sensors based on sub-micron cross-type Josephson tunnel junctions. Their low total junction capacitance permit high usable voltage swings of more than 100 {\mu}V and exceptional low noise of the SQUIDs at 4.2 K. Integrated rf-filter as well as high tolerable background fields during cool-down of up to 9.6 mT enable their highly reliable and easy use. With input coil inductances ranging from 10 nH to 2.8 {\mu}H and current sensitivities and coupled energy resolution down to 65 fA/Hz^{1/2} and below 10 h, respectively, they are a versatile tool for numerous applications., Comment: 6 pages, 4 figures

We report on the development of nearly quantum limited SQUIDs with miniature pickup loop dimensions. The implemented high quality and low capacitance cross-type Nb/AlOx/Nb Josephson junctions offer large $I_CR_N$-products and therefore enable an exceptional low noise level of the SQUIDs. Devices with loop dimensions of 1 {\mu}m exhibit white flux noise levels as low as $45 n{\Phi}_0/Hz^{1/2}$ corresponding to an energy resolution {\epsilon} of about 1 h at 4.2 K, with h being Plancks constant. Moreover, the large usable voltage swings of the devices of about 300 {\mu}V allow highly sensitive and easy single-stage operation while exploring nearly the intrinsic noise of the SQUIDs, beneficial e.g. for sensor arrays in SQUID microscopy.

We report on the development of an ultralow noise thin-film based SQUID magnetometer. A niobium thin-film pickup coil is connected to the input coil of a SQUID current sensor. The low capacitance of the used sub-micrometer cross-type Josephson junctions enable superior noise performance of the device. Application scenarios e.g. in geophysics and ultra-low field magnetic resonance imaging are discussed., Comment: 3 pages, 2 figures

We describe here the recent results of a multidisciplinary effort to design a biomarker that can actively and continuously decode the progressive changes in neuronal organization leading to epilepsy, a process known as epileptogenesis. Using an animal model of acquired epilepsy, wechronically record hippocampal evoked potentials elicited by an auditory stimulus. Using a set of reduced coordinates, our algorithm can identify universal smooth low-dimensional configurations of the auditory evoked potentials that correspond to distinct stages of epileptogenesis. We use a hidden Markov model to learn the dynamics of the evoked potential, as it evolves along these smooth low-dimensional subsets. We provide experimental evidence that the biomarker is able to exploit subtle changes in the evoked potential to reliably decode the stage of epileptogenesis and predict whether an animal will eventually recover from the injury, or develop spontaneous seizures.

Covariance matrices are fundamental to the analysis and forecast of economic, physical and biological systems. Although the eigenvalues $\{\lambda_i\}$ and eigenvectors $\{{\bf u}_i\}$ of a covariance matrix are central to such endeavors, in practice one must inevitably approximate the covariance matrix based on data with finite sample size $n$ to obtain empirical eigenvalues $\{\tilde{\lambda}_i\}$ and eigenvectors $\{\tilde{{\bf u}}_i\}$, and therefore understanding the error so introduced is of central importance. We analyze eigenvector error $\|{\bf u}_i - \tilde{{\bf u}}_i \|^2$ while leveraging the assumption that the true covariance matrix having size $p$ is drawn from a matrix ensemble with known spectral properties---particularly, we assume the distribution of population eigenvalues weakly converges as $p\to\infty$ to a spectral density $\rho(\lambda)$ and that the spacing between population eigenvalues is similar to that for the Gaussian orthogonal ensemble. Our approach complements previous analyses of eigenvector error that require the full set of eigenvalues to be known, which can be computationally infeasible when $p$ is large. To provide a scalable approach for uncertainty quantification of eigenvector error, we consider a fixed eigenvalue $\lambda$ and approximate the distribution of the expected square error $r= \mathbb{E}\left[\| {\bf u}_i - \tilde{{\bf u}}_i \|^2\right]$ across the matrix ensemble for all ${\bf u}_i$ associated with $\lambda_i=\lambda$. We find, for example, that for sufficiently large matrix size $p$ and sample size $n>p$, the probability density of $r$ scales as $1/nr^2$. This power-law scaling implies that eigenvector error is extremely heterogeneous---even if $r$ is very small for most eigenvectors, it can be large for others with non-negligible probability. We support this and further results with numerical experiments., Comment: 24 pages, 8 figures

To quantify the fundamental evolution of time-varying networks, and detect abnormal behavior, one needs a notion of temporal difference that captures significant organizational changes between two successive instants. In this work, we propose a family of distances that can be tuned to quantify structural changes occurring on a graph at different scales: from the local scale formed by the neighbors of each vertex, to the largest scale that quantifies the connections between clusters, or communities. Our approach results in the definition of a true distance, and not merely a notion of similarity. We propose fast (linear in the number of edges) randomized algorithms that can quickly compute an approximation to the graph metric. The third contribution involves a fast algorithm to increase the robustness of a network by optimally decreasing the Kirchhoff index. Finally, we conduct several experiments on synthetic graphs and real networks, and we demonstrate that we can detect configurational changes that are directly related to the hidden variables governing the evolution of dynamic networks.

In this work we address the problem of detecting overlapping communities in social networks. Because the word "community" is an ambiguous term, it is necessary to quantify what it means to be a community within the context of a particular type of problem. Our interpretation is that this quantification must be done at a minimum of three scales. These scales are at the level of: individual nodes, individual communities, and the network as a whole. Each of these scales involves quantitative features of community structure that are not accurately represented at the other scales, but are important for defining a particular notion of community. Our work focuses on providing sensible ways to quantify what is desired at each of these scales for a notion of community applicable to social networks, and using these models to develop a community detection algorithm. Appealing features of our approach is that it naturally allows for nodes to belong to multiple communities, and is computationally efficient for large networks with low overall edge density. The scaling of the algorithm is $O(N~\overline{k^2} + \overline{N_{com}^2})$, where $N$ is the number of nodes in the network, $\overline{N_{com}^2}$ is the average squared community size, and $\overline{k^2}$ is the expected value of a node's degree squared. Although our work focuses on developing a computationally efficient algorithm for overlapping community detection in the context of social networks, our primary contribution is developing a methodology that is highly modular and can easily be adapted to target specific notions of community.

We report on the development of highly sensitive SQUIDs featuring sub-micrometer loop dimensions. The integration of high quality and low capacitance SIS Nb/AlOx/Nb cross-type Josephson tunnel junctions results in white flux noise levels as low as 66 n$\Phi_0$/Hz$^{ 1/2} $, well below state-of-the-art values of their Nb-based counterparts based on constriction type junctions. Estimation of the spin sensitivity of the best SQUIDs yield $S_\mu^{ 1/2} < 7 \mu_B$/Hz$^{ 1/2} $ in the white noise region, suitable for the investigation of small spin systems. We discuss fabrication challenges, show results on the electrical characterization of devices with various pickup loops, and describe options for further improvement, which may push the sensitivity of such devices even to single spin resolution., Comment: 8 pages, 3 figures

Several recent works have shown that protein structure can predict site-specific evolutionary sequence variation. In particular, sites that are buried and/or have many contacts with other sites in a structure have been shown to evolve more slowly, on average, than surface sites with few contacts. Here, we present a comprehensive study of the extent to which numerous structural properties can predict sequence variation. The quantities we considered include buriedness (as measured by relative solvent accessibility), packing density (as measured by contact number), structural flexibility (as measured by B factors, root-mean-square fluctuations, and variation in dihedral angles), and variability in designed structures. We obtained structural flexibility measures both from molecular dynamics simulations performed on 9 non-homologous viral protein structures and from variation in homologous variants of those proteins, where available. We obtained measures of variability in designed structures from flexible-backbone design in the Rosetta software. We found that most of the structural properties correlate with site variation in the majority of structures, though the correlations are generally weak (correlation coefficients of 0.1 to 0.4). Moreover, we found that buriedness and packing density were better predictors of evolutionary variation than was structural flexibility. Finally, variability in designed structures was a weaker predictor of evolutionary variability than was buriedness or packing density, but it was comparable in its predictive power to the best structural flexibility measures. We conclude that simple measures of buriedness and packing density are better predictors of evolutionary variation than are more complicated predictors obtained from dynamic simulations, ensembles of homologous structures, or computational protein design., Comment: to appear in Journal of Molecular Evolution (JME)

In the post-genome era, biologists have sought to measure the complete complement of proteins, termed proteomics. Currently, the most effective method to measure the proteome is with shotgun, or bottom-up, proteomics, in which the proteome is digested into peptides that are identified followed by protein inference. Despite continuous improvements to all steps of the shotgun proteomics workflow, observed proteome coverage is often low; some proteins are identified by a single peptide sequence. Complete proteome sequence coverage would allow comprehensive characterization of RNA splicing variants and all post translational modifications, which would drastically improve the accuracy of biological models. There are many reasons for the sequence coverage deficit, but ultimately peptide length determines sequence observability. Peptides that are too short are lost because they match many protein sequences and their true origin is ambiguous. The maximum observable peptide length is determined by several analytical challenges. This paper explores computationally how peptide lengths produced from several common proteome digestion methods limit observable proteome coverage. Iterative proteome cleavage strategies are also explored. These simulations reveal that maximized proteome coverage can be achieved by use of an iterative digestion protocol involving multiple proteases and chemical cleavages that theoretically allow 91.1% proteome coverage., Comment: 10 pages of text/references followed by figure/table legends, six figures, and one table

We report the parametric amplification of a microwave signal in a Kerr medium formed from superconducting qubits. Two mutually coupled flux qubits, embedded in the current antinode of a superconducting coplanar waveguide resonator, are used as a nonlinear element. Shared Josephson junctions provide the qubit-resonator coupling, resulting in a device with a measured gain of about 20 dB. We argue, that this arrangement represents a unit cell which can be straightforwardly extended to a quasi one-dimensional quantum metamaterial with a large tunable Kerr nonlinearity., Comment: 4 pages, 4 figures

Nonlinear dimensionality reduction embeddings computed from datasets do not provide a mechanism to compute the inverse map. In this paper, we address the problem of computing a stable inverse map to such a general bi-Lipschitz map. Our approach relies on radial basis functions (RBFs) to interpolate the inverse map everywhere on the low-dimensional image of the forward map. We demonstrate that the scale-free cubic RBF kernel performs better than the Gaussian kernel: it does not suffer from ill-conditioning, and does not require the choice of a scale. The proposed construction is shown to be similar to the Nystr\"om extension of the eigenvectors of the symmetric normalized graph Laplacian matrix. Based on this observation, we provide a new interpretation of the Nystr\"om extension with suggestions for improvement., Comment: Accepted for publication in Applied and Computational Harmonic Analysis

In many biological applications, we would like to be able to computationally predict mutational effects on affinity in protein-protein interactions. However, many commonly used methods to predict these effects perform poorly in important test cases. In particular, the effects of multiple mutations, non-alanine substitutions, and flexible loops are difficult to predict with available tools and protocols. We present here an existing method applied in a novel way to a new test case; we interrogate affinity differences resulting from mutations in a host-virus protein-protein interface. We use steered molecular dynamics (SMD) to computationally pull the machupo virus (MACV) spike glycoprotein (GP1) away from the human transferrin receptor (hTfR1). We then approximate affinity using the maximum applied force of separation and the area under the force-versus-distance curve. We find, even without the rigor and planning required for free energy calculations, that these quantities can provide novel biophysical insight into the GP1/hTfR1 interaction. First, with no prior knowledge of the system we can differentiate among wild type and mutant complexes. Moreover, we show that this simple SMD scheme correlates well with relative free energy differences computed via free energy perturbation. Second, although the static co-crystal structure shows two large hydrogen-bonding networks in the GP1/hTfR1 interface, our simulations indicate that one of them may not be important for tight binding. Third, one viral site known to be critical for infection may mark an important evolutionary suppressor site for infection-resistant hTfR1 mutants. Finally, our approach provides a framework to compare the effects of multiple mutations, individually and jointly, on protein-protein interactions., Comment: 33 pages, 8 figures, 5 tables

The relative solvent accessibility (RSA) of a residue in a protein measures the extent of burial or exposure of that residue in the 3D structure. RSA is frequently used to describe a protein's biophysical or evolutionary properties. To calculate RSA, a residue's solvent accessibility (ASA) needs to be normalized by a suitable reference value for the given amino acid; several normalization scales have previously been proposed. However, these scales do not provide tight upper bounds on ASA values frequently observed in empirical crystal structures. Instead, they underestimate the largest allowed ASA values, by up to 20%. As a result, many empirical crystal structures contain residues that seem to have RSA values in excess of one. Here, we derive a new normalization scale that does provide a tight upper bound on observed ASA values. We pursue two complementary strategies, one based on extensive analysis of empirical structures and one based on systematic enumeration of biophysically allowed tripeptides. Both approaches yield congruent results that consistently exceed published values. We conclude that previously published ASA normalization values were too small, primarily because the conformations that maximize ASA had not been correctly identified. As an application of our results, we show that empirically derived hydrophobicity scales are sensitive to accurate RSA calculation, and we derive new hydrophobicity scales that show increased correlation with experimentally measured scales., Comment: 16 pages, 4 figures

We demonstrate amplification of a microwave signal by a strongly driven two-level system in a coplanar waveguide resonator. The effect known from optics as dressed-state lasing is observed with a single quantum system formed by a persistent current (flux) qubit. The transmission through the resonator is enhanced when the Rabi frequency of the driven qubit is tuned into resonance with one of the resonator modes. Amplification as well as linewidth narrowing of a weak probe signal has been observed. The laser emission at the resonator's fundamental mode has been studied by measuring the emission spectrum. We analyzed our system and found an excellent agreement between the experimental results and the theoretical predictions obtained in the dressed-state model., Comment: 5 pages, 4 figures

The original contributions of this paper are twofold: a new understanding of the influence of noise on the eigenvectors of the graph Laplacian of a set of image patches, and an algorithm to estimate a denoised set of patches from a noisy image. The algorithm relies on the following two observations: (1) the low-index eigenvectors of the diffusion, or graph Laplacian, operators are very robust to random perturbations of the weights and random changes in the connections of the patch-graph; and (2) patches extracted from smooth regions of the image are organized along smooth low-dimensional structures in the patch-set, and therefore can be reconstructed with few eigenvectors. Experiments demonstrate that our denoising algorithm outperforms the denoising gold-standards.

Constructing an efficient parameterization of a large, noisy data set of points lying close to a smooth manifold in high dimension remains a fundamental problem. One approach consists in recovering a local parameterization using the local tangent plane. Principal component analysis (PCA) is often the tool of choice, as it returns an optimal basis in the case of noise-free samples from a linear subspace. To process noisy data samples from a nonlinear manifold, PCA must be applied locally, at a scale small enough such that the manifold is approximately linear, but at a scale large enough such that structure may be discerned from noise. Using eigenspace perturbation theory and non-asymptotic random matrix theory, we study the stability of the subspace estimated by PCA as a function of scale, and bound (with high probability) the angle it forms with the true tangent space. By adaptively selecting the scale that minimizes this bound, our analysis reveals an appropriate scale for local tangent plane recovery. We also introduce a geometric uncertainty principle quantifying the limits of noise-curvature perturbation for stable recovery. With the purpose of providing perturbation bounds that can be used in practice, we propose plug-in estimates that make it possible to directly apply the theoretical results to real data sets., Comment: 53 pages. Revised manuscript with new content addressing application of results to real data sets

In this paper we address the problem of understanding the success of algorithms that organize patches according to graph-based metrics. Algorithms that analyze patches extracted from images or time series have led to state-of-the art techniques for classification, denoising, and the study of nonlinear dynamics. The main contribution of this work is to provide a theoretical explanation for the above experimental observations. Our approach relies on a detailed analysis of the commute time metric on prototypical graph models that epitomize the geometry observed in general patch graphs. We prove that a parametrization of the graph based on commute times shrinks the mutual distances between patches that correspond to rapid local changes in the signal, while the distances between patches that correspond to slow local changes expand. In effect, our results explain why the parametrization of the set of patches based on the eigenfunctions of the Laplacian can concentrate patches that correspond to rapid local changes, which would otherwise be shattered in the space of patches. While our results are based on a large sample analysis, numerical experimentations on synthetic and real data indicate that the results hold for datasets that are very small in practice.

Huang's Empirical Mode Decomposition (EMD) is an algorithm for analyzing nonstationary data that provides a localized time-frequency representation by decomposing the data into adaptively defined modes. EMD can be used to estimate a signal's instantaneous frequency (IF) but suffers from poor performance in the presence of noise. To produce a meaningful IF, each mode of the decomposition must be nearly monochromatic, a condition that is not guaranteed by the algorithm and fails to be met when the signal is corrupted by noise. In this work, the extraction of modes containing both signal and noise is identified as the cause of poor IF estimation. The specific mechanism by which such "transition" modes are extracted is detailed and builds on the observation of Flandrin and Goncalves that EMD acts in a filter bank manner when analyzing pure noise. The mechanism is shown to be dependent on spectral leak between modes and the phase of the underlying signal. These ideas are developed through the use of simple signals and are tested on a synthetic seismic waveform., Comment: 28 pages, 19 figures. High quality color figures available on Daniel Kaslovsky's website: http://amath.colorado.edu/student/kaslovsk/

We propose a new method to analyze seismic time series and estimate the arrival-times of seismic waves. Our approach combines two ingredients: the times series are first lifted into a high-dimensional space using time-delay embedding; the resulting phase space is then parametrized using a nonlinear method based on the eigenvectors of the graph Laplacian. We validate our approach using a dataset of seismic events that occurred in Idaho, Montana, Wyoming, and Utah, between 2005 and 2006. Our approach outperforms methods based on singular-spectrum analysis, waveleta nalysis, and STA/LTA., Comment: 21 pages, 13 figures

We study a flux qubit in a coplanar waveguide resonator by measuring transmission through the system. In our system with the flux qubit decoupled galvanically from the resonator, the intermediate coupling regime is achieved. In this regime dispersive readout is possible with weak backaction on the qubit. The detailed theoretical analysis and simulations give a good agreement with the experimental data and allow to make the qubit characterization., Comment: 4 pages, 3 figures, to be published in Phys. Rev. B

We study the loss rate for a set of lambda/2 coplanar waveguide resonators at millikelvin temperatures (20 mK - 900mK) and different applied powers (3E-19 W - 1E-12 W). The loss rate becomes power independent below a critical power. For a fixed power, the loss rate increases significantly with decreasing temperature. We show that this behavior can be caused by two-level systems in the surrounding dielectric materials. Interestingly, the influence of the two-level systems is of the same order of magnitude for the different material combinations. That leads to the assumption that the nature of these two-level systems is material independent., Comment: 3 pages, 5 figures, Submitted to Applied Physics Letters

We study spectroscopy of artificial solid-state four-level quantum system. This system is formed by two coupled superconducting flux qubits. When multiple driving frequency of the applied microwaves matches the energy difference between any two levels, the transition to the upper level is induced. We demonstrate two types of the multi-photon transitions: direct transitions between two levels and ladder-type transitions via an intermediate level. For the latter transitions, in particular, the inverse population of the excited state with respect to the ground one is realized. These processes can be useful for the control of the level population for the multilevel scalable quantum systems., Comment: 4 pages, 2 figures; v.2: minor changes

We report measurements of transfer functions and flux shifts of 20 on-chip high T$_C$ DC SQUIDs half of which were made purposely geometrically asymmetric. All of these SQUIDs were fabricated using standard high T$_C$ thin film technology and they were single layer ones, having 140 nm thickness of YBa$_2$Cu$_3$O$_{7-x}$ film deposited by laser ablation onto MgO bicrystal substrates with 24$^0$ misorientation angle. For every SQUID the parameters of its intrinsic asymmetry, i. e., the density of critical current and resistivity of every junction, were measured directly and independently. We showed that the main reason for the on-chip spreading of SQUIDs' voltage-current and voltage-flux characteristics was the intrinsic asymmetry. We found that for SQUIDs with a relative large inductance ($L>120 $ pH) both the voltage modulation and the transfer function were not very sensitive to the junctions asymmetry, whereas SQUIDs with smaller inductance ($L\simeq 65-75 $ pH) were more sensitive. The results obtained in the paper are important for the implementation in the sensitive instruments based on high T$_C$ SQUID arrays and gratings., Comment: 11 pages, 4 tables, 17 figures This version is substantially modified. The Introduction and Section 2 are completely rewritten, while experimental part is mainly the same as in previous version

We compare the results of ground state and spectroscopic measurements carried out on superconducting flux qubits which are effective two-level quantum systems. For a single qubit and for two coupled qubits we show excellent agreement between the parameters of the pseudospin Hamiltonian found using both methods. We argue, that by making use of the ground state measurements the Hamiltonian of N coupled flux qubits can be reconstructed as well at temperatures smaller than the energy level separation. Such a reconstruction of a many-qubit Hamiltonian can be useful for future quantum information processing devices., Comment: 4 pages, 4 figures

The interaction of flux qubits with a low frequency tank circuit is studied. It is shown that changes in the state of the interacting qubits influence the effective impedance of the circuit, which is the essence of the so-called impedance measurement technique. The multiphoton resonant excitations in both single flux qubits and pairs of coupled flux qubits are investigated. In particular, we compare our theoretical results with recent spectroscopy measurements, Landau-Zener interferometry, and multiphoton fringes., Comment: 11 pages, 11 figures; v.2: minor changes

Functional Magnetic Resonance Imaging (fMRI) provides dynamical access into the complex functioning of the human brain, detailing the hemodynamic activity of thousands of voxels during hundreds of sequential time points. One approach towards illuminating the connection between fMRI and cognitive function is through decoding; how do the time series of voxel activities combine to provide information about internal and external experience? Here we seek models of fMRI decoding which are balanced between the simplicity of their interpretation and the effectiveness of their prediction. We use signals from a subject immersed in virtual reality to compare global and local methods of prediction applying both linear and nonlinear techniques of dimensionality reduction. We find that the prediction of complex stimuli is remarkably low-dimensional, saturating with less than 100 features. In particular, we build effective models based on the decorrelated components of cognitive activity in the classically-defined Brodmann areas. For some of the stimuli, the top predictive areas were surprisingly transparent, including Wernicke's area for verbal instructions, visual cortex for facial and body features, and visual-temporal regions for velocity. Direct sensory experience resulted in the most robust predictions, with the highest correlation ($c \sim 0.8$) between the predicted and experienced time series of verbal instructions. Techniques based on non-linear dimensionality reduction (Laplacian eigenmaps) performed similarly. The interpretability and relative simplicity of our approach provides a conceptual basis upon which to build more sophisticated techniques for fMRI decoding and offers a window into cognitive function during dynamic, natural experience., Comment: To appear in: Advances in Neural Information Processing Systems 20, Scholkopf B., Platt J. and Hofmann T. (Editors), MIT Press, 2008

We propose a novel method to embed a functional magnetic resonance imaging (fMRI) dataset in a low-dimensional space. The embedding optimally preserves the local functional coupling between fMRI time series and provides a low-dimensional coordinate system for detecting activated voxels. To compute the embedding, we build a graph of functionally connected voxels. We use the commute time, instead of the geodesic distance, to measure functional distances on the graph. Because the commute time can be computed directly from the eigenvectors of (a symmetric version) the graph probability transition matrix, we use these eigenvectors to embed the dataset in low dimensions. After clustering the datasets in low dimensions, coherent structures emerge that can be easily interpreted. We performed an extensive evaluation of our method comparing it to linear and nonlinear techniques using synthetic datasets and in vivo datasets. We analyzed datasets from the EBC competition obtained with subjects interacting in an urban virtual reality environment. Our exploratory approach is able to detect independently visual areas (V1/V2, V5/MT), auditory areas, and language areas. Our method can be used to analyze fMRI collected during ``natural stimuli''., Comment: 16 pages, 21 figures, submitted to Neuroimage, revised (Jan. 2008)

Laser cooling of the atomic motion paved the way for remarkable achievements in the fields of quantum optics and atomic physics, including Bose-Einstein condensation and the trapping of atoms in optical lattices. More recently superconducting qubits were shown to act as artificial two-level atoms, displaying Rabi oscillations, Ramsey fringes, and further quantum effects. Coupling such qubits to resonators brought the superconducting circuits into the realm of quantum electrodynamics (circuit QED). It opened the perspective to use superconducting qubits as micro-coolers or to create a population inversion in the qubit to induce lasing behavior of the resonator. Furthering these analogies between quantum optical and superconducting systems we demonstrate here Sisyphus cooling of a low frequency LC oscillator coupled to a near-resonantly driven superconducting qubit. In the quantum optics setup the mechanical degrees of freedom of an atom are cooled by laser driving the atom's electronic degrees of freedom. Here the roles of the two degrees of freedom are played by the LC circuit and the qubit's levels, respectively. We also demonstrate the counterpart of the Sisyphus cooling, namely Sisyphus amplification. Parallel to the experimental demonstration we analyze the system theoretically and find quantitative agreement, which supports the interpretation and allows us to estimate system parameters., Comment: 7 pages, 4 figures

Controllable adiabatic evolution of a multi-qubit system can be used for adiabatic quantum computation (AQC). This evolution ends at a configuration where the Hamiltonian of the system encodes the solution of the problem to be solved. As a first steps towards realization of AQC we have investigated two, three and four flux qubit systems. These systems were characterized by making use of a radio-frequency method. We designed two-qubit systems with coupling energies up to several kelvins. For the three-flux-qubit systems we determined the complete ground-state flux diagram in the three dimensional flux space around the qubits common degeneracy point. We show that the system`s Hamiltonian can be completely reconstructed from our measurements. Our concept for the implementation of AQC, by making use of flux qubits, is discussed., Comment: 6 pages, 7 figures, Applied Superconductivity Conference 2006