Search Results

Recently, [Li, Nguyen, Woodruff, STOC 2014] showed any 1-pass constant probability streaming algorithm for computing a relation f on a vector x in {-m, -(m-1), ..., m}^n presented in the turnstile data stream model can be implemented by maintaining a linear sketch Ax mod q, where A is an r times n integer matrix and q = (q_1, ..., q_r) is a vector of positive integers. The space complexity of maintaining Ax mod q, not including the random bits used for sampling A and q, matches the space of the optimal algorithm. We give multiple strengthenings of this reduction, together with new applications. In particular, we show how to remove the following shortcomings of their reduction: 1. The Box Constraint. Their reduction applies only to algorithms that must be correct even if x_{infinity} = max_{i in [n]} |x_i| is allowed to be much larger than m at intermediate points in the stream, provided that x is in {-m, -(m-1), ..., m}^n at the end of the stream. We give a condition under which the optimal algorithm is a linear sketch even if it works only when promised that x is in {-m, -(m-1), ..., m}^n at all points in the stream. Using this, we show the first super-constant Omega(log m) bits lower bound for the problem of maintaining a counter up to an additive epsilon*m error in a turnstile stream, where epsilon is any constant in (0, 1/2). Previous lower bounds are based on communication complexity and are only for relative error approximation; interestingly, we do not know how to prove our result using communication complexity. More generally, we show the first super-constant Omega(log(m)) lower bound for additive approximation of l_p-norms; this bound is tight for p in [1, 2]. 2. Negative Coordinates. Their reduction allows x_i to be negative while processing the stream. We show an equivalence between 1-pass algorithms and linear sketches Ax mod q in dynamic graph streams, or more generally, the strict turnstile model, in which for all i in [n], x_i is nonnegative at all points in the stream. Combined with [Assadi, Khanna, Li, Yaroslavtsev, SODA 2016], this resolves the 1-pass space complexity of approximating the maximum matching in a dynamic graph stream, answering a question in that work. 3. 1-Pass Restriction. Their reduction only applies to 1-pass data stream algorithms in the turnstile model, while there exist algorithms for heavy hitters and for low rank approximation which provably do better with multiple passes. We extend the reduction to algorithms which make any number of passes, showing the optimal algorithm is to choose a new linear sketch at the beginning of each pass, based on the output of previous passes.

Upon low energy collision induced dissociation (CID), multiply protonated peptides generate a set of interdependent fragment ions detectable by MS/MS, the '[peptide]n+-fragmentome'. In particular dynamic fragmentation of [peptide]n+ ions in a collision cell generates information-rich MS/MS spectra. Currently, database-supported annotations of peptide MS/MS spectra are mainly based on a combination of peptide molecular weight and y type fragment ions, leaving a considerable number of good-quality peptide MS/MS spectra in proteomics studies unannotated. This situation may be improved by a more complete use of the structural information present in the [peptide]n+-fragmentome. The presentation provides an overview on the fragment ions of multiply protonated peptides and their connectivity, comprising a ions, b ions, y ions, and neutral loss reactions from the N-, and C-terminus, and internal b ions. In the low-mass region, the unique set of 19 y1 ions and of the 190 b2 ions carries a particular message, since these ions define the N-or C-terminal amino acid(s). Further, the b1 ions of the basic residues K, H, W, and R carry a specific N-terminal information, which is redundant to that contained in the corresponding b2 ions and in the N-terminal neutral loss peaks. Redundant information is also found in b and y ion series and in complementary b/y ion pairs. The latter are particularly abundant when generated by proline- or aspartate-induced backbone cleavages. From complementary b/y ion pairs the molecular weight of the precursor ion can be reconstructed to confirm or determine its molecular weight. This procedure is helpful in case a mixture of precursor ions is isolated or in case a precursor ion of very low abundance is isolated. Information about the precursor ion charge state is also delivered by precursor ion reconstruction using MS/MS data. In the analysis of covalently modified peptides, reporter ions are of particular importance. These ions can be used for mining of MS/MS data sets for the occurrence of selected modifications. Examples are presented for selected modifications, such as acetylation and phosphorylation. In phosphorylation analysis neutral loss reactions are highly important, and may also carry redundant information, when observed both from the molecular ion and from fragment ions. Search tools, which fully incorporate the current knowledge about the [peptide]n+-fragmentome will increase the scores of peptide/protein identifications by MS/MS and thus will increase the fraction of automatically assigned MS/MS spectra in proteomics studies.