MOTIVATION: De novo peptide sequencing based on tandem mass spectrometry data is the key technology of shotgun proteomics for identifying peptides without any database and assembling unknown proteins. However, owing to the low ion coverage in tandem mass spectra, the order of certain consecutive amino acids cannot be determined if all of their supporting fragment ions are missing, which results in the low precision of de novo sequencing. RESULTS: In order to solve this problem, we developed pNovo 3, which used a learning-to-rank framework to distinguish similar peptide candidates for each spectrum. Three metrics for measuring the similarity between each experimental spectrum and its corresponding theoretical spectrum were used as important features, in which the theoretical spectra can be precisely predicted by the pDeep algorithm using deep learning. On seven benchmark datasets from six diverse species, pNovo 3 recalled 29-102% more correct spectra, and the precision was 11-89% higher than three other state-of-the-art de novo sequencing algorithms. Furthermore, compared with the newly developed DeepNovo, which also used the deep learning approach, pNovo 3 still identified 21-50% more spectra on the nine datasets used in the study of DeepNovo. In summary, the deep learning and learning-to-rank techniques implemented in pNovo 3 significantly improve the precision of de novo sequencing, and such machine learning framework is worth extending to other related research fields to distinguish the similar sequences. AVAILABILITY AND IMPLEMENTATION: pNovo 3 can be freely downloaded from http://pfind.ict.ac.cn/software/pNovo/index.html. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Proteogenomics has been well accepted as a tool to discover novel genes. In most conventional proteogenomic studies, a global false discovery rate is used to filter out false positives for identifying credible novel peptides. However, it has been found that the actual level of false positives in novel peptides is often out of control and behaves differently for different genomes. RESULTS: To quantitatively model this problem, we theoretically analyze the subgroup false discovery rates of annotated and novel peptides. Our analysis shows that the annotation completeness ratio of a genome is the dominant factor influencing the subgroup FDR of novel peptides. Experimental results on two real datasets of Escherichia coli and Mycobacterium tuberculosis support our conjecture. CONTACT: [email protected] or [email protected] or [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Protein identification is the most important and basic problem for proteomics. Using tandem mass spectrometry and database search is one of the most widely used identification techniques. However, the improved sensitivity of mass spectrometers, rapid expansion of databases and more complex analysis, like post-translational modification and non-specific enzymatic digestion, have challenged current restricted protein identification search engines in scale and speed severely. In this paper, we proposed an open protein identification method relaxing enzyme, and presented our distributed design to support big protein database with non-specific digestion analysis based on pFind, a practical tandem mass spectra search engine developed in China. With classical bigger protein databases ipi. HUMAN and uniprot-sprot we got nearly linear speedup in a 20-blade cluster. By further analysis, we can expect real time identification to some extent.

MOTIVATION: Identification of post-translationally modified proteins has become one of the central issues of current proteomics. Spectral library search is a new and promising computational approach to mass spectrometry-based protein identification. However, its potential in identification of unanticipated post-translational modifications has rarely been explored. The existing spectral library search tools are designed to match the query spectrum to the reference library spectra with the same peptide mass. Thus, spectra of peptides with unanticipated modifications cannot be identified. RESULTS: In this article, we present an open spectral library search tool, named pMatch. It extends the existing library search algorithms in at least three aspects to support the identification of unanticipated modifications. First, the spectra in library are optimized with the full peptide sequence information to better tolerate the peptide fragmentation pattern variations caused by some modification(s). Second, a new scoring system is devised, which uses charge-dependent mass shifts for peak matching and combines a probability-based model with the general spectral dot-product for scoring. Third, a target-decoy strategy is used for false discovery rate control. To demonstrate the effectiveness of pMatch, a library search experiment was conducted on a public dataset with over 40,000 spectra in comparison with SpectraST, the most popular library search engine. Additional validations were done on four published datasets including over 150,000 spectra. The results showed that pMatch can effectively identify unanticipated modifications and significantly increase spectral identification rate. AVAILABILITY: http://pfind.ict.ac.cn/pmatch/. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Tandem mass spectrometry-based database searching has become an important technology for peptide and protein identification. One of the key challenges in database searching is the remarkable increase in computational demand, brought about by the expansion of protein databases, semi- or non-specific enzymatic digestion, post-translational modifications and other factors. Some software tools choose peptide indexing to accelerate processing. However, peptide indexing requires a large amount of time and space for construction, especially for the non-specific digestion. Additionally, it is not flexible to use. RESULTS: We developed an algorithm based on the longest common prefix (ABLCP) to efficiently organize a protein sequence database. The longest common prefix is a data structure that is always coupled to the suffix array. It eliminates redundant candidate peptides in databases and reduces the corresponding peptide-spectrum matching times, thereby decreasing the identification time. This algorithm is based on the property of the longest common prefix. Even enzymatic digestion poses a challenge to this property, but some adjustments can be made to this algorithm to ensure that no candidate peptides are omitted. Compared with peptide indexing, ABLCP requires much less time and space for construction and is subject to fewer restrictions. CONCLUSIONS: The ABLCP algorithm can help to improve data analysis efficiency. A software tool implementing this algorithm is available at http://pfind.ict.ac.cn/pfind2dot5/index.htm.

BACKGROUND: Peptide identification via tandem mass spectrometry is the basic task of current proteomics research. Due to the complexity of mass spectra, the majority of mass spectra cannot be interpreted at present. The existence of unexpected or unknown protein post-translational modifications is a major reason. RESULTS: This paper describes an efficient and sequence database-independent approach to detecting abundant post-translational modifications in high-accuracy peptide mass spectra. The approach is based on the observation that the spectra of a modified peptide and its unmodified counterpart are correlated with each other in their peptide masses and retention time. Frequently occurring peptide mass differences in a data set imply possible modifications, while small and consistent retention time differences provide orthogonal supporting evidence. We propose to use a bivariate Gaussian mixture model to discriminate modification-related spectral pairs from random ones. Due to the use of two-dimensional information, accurate modification masses and confident spectral pairs can be determined as well as the quantitative influences of modifications on peptide retention time. CONCLUSION: Experiments on two glycoprotein data sets demonstrate that our method can effectively detect abundant modifications and spectral pairs. By including the discovered modifications into database search or by propagating peptide assignments between paired spectra, an average of 10% more spectra are interpreted.

MOTIVATION: RNA secondary structures with pseudoknots are often predicted by minimizing free energy, which is proved to be NP-hard. Due to kinetic reasons the real RNA secondary structure often has local instead of global minimum free energy. This implies that we may improve the performance of RNA secondary structure prediction by taking kinetics into account and minimize free energy in a local area. RESULT: we propose a novel algorithm named FlexStem to predict RNA secondary structures with pseudoknots. Still based on MFE criterion, FlexStem adopts comprehensive energy models that allow complex pseudoknots. Unlike classical thermodynamic methods, our approach aims to simulate the RNA folding process by successive addition of maximal stems, reducing the search space while maintaining or even improving the prediction accuracy. This reduced space is constructed by our maximal stem strategy and stem-adding rule induced from elaborate statistical experiments on real RNA secondary structures. The strategy and the rule also reflect the folding characteristic of RNA from a new angle and help compensate for the deficiency of merely relying on MFE in RNA structure prediction. We validate FlexStem by applying it to tRNAs, 5SrRNAs and a large number of pseudoknotted structures and compare it with the well-known algorithms such as RNAfold, PKNOTS, PknotsRG, HotKnots and ILM according to their overall sensitivities and specificities, as well as positive and negative controls on pseudoknots. The results show that FlexStem significantly increases the prediction accuracy through its local search strategy. AVAILABILITY: Software is available at http://pfind.ict.ac.cn/FlexStem/. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

We demonstrate a new algorithm named FlexStem to predict RNA secondary structures with pseudoknots. Our approach is based on the free energy minimization criterion, and utilizes a sophisticated energy model that is more accurate and supports more types of pseudoknots. By using a "maximal stem" and "stem merging" strategy, the search space for RNA structure prediction is significantly reduced. We have also developed a greedy search algorithm with perturbation on stems. The FlexStem algorithm is applied to a large number of sequences taken from Sprinzl, Pseudobase and other reliable resource. We find that FlexStem outperforms the well-known optimal and heuristic algorithms such as Mfold, PKNOTS, HotKnots and ILM in overall sensitivity and has comparable results to those algorithms in overall specificity. Performance evaluation demonstrate that FlexStem requires significantly less time than the optimal algorithm PKNOTS. In addition, our algorithm has better prediction results on pseudoknot-free sequences compared to competing algorithms.

A rate-based switch fabric called smoothed buffer crossbar has been proposed in our recent work. It can provide 100% rate-guaranteed service with only a two-cell buffer at each crosspoint, and can also support best-effort service with an additional bandwidth regulator. However, the widely used max- flow model for bandwidth regulation is neither scalable nor of 100% throughput. In order to evaluate the performance of bandwidth regulator, we first introduce the 100% ideal throughput measurement in this paper. Then we prove that the total arrival average (TAA) algorithm has got this property, which does not happen in the max-flow allocation. Then an O(N) algorithm called proportion scaling allocation (PSA) is presented. Simulations reveal that PSA can deliver nearly 100% throughput even in a frequently changing traffic pattern. As a comparison, both theoretical and experimental evidences are given to show the inefficiency of the max-flow model.

Simulation is crucial to performance evaluation of switches. Currently stochastic simulation is the predominant approach, which has two drawbacks: few workload patterns and long simulation times. In this paper, we propose a novel switch simulation method that is based on two techniques: exhaustive workload pattern generation and smoothed periodic input generation. The exhaustive workload pattern generation can produce a huge number of nonuniform workload patterns, which far exceeds the traditional few ones; conclusions based on such truly extensive simulations are much more convincing. The periodic input or cell arrival pattern outperforms the stochastic counterpart in terms of easy repetition and fast convergence of simulation; in particular, among periodic inputs, the smoothed periodic input is most favorable to switch scheduling, and hence switches performing poor with it probably performs worse under others. Combining these two techniques together can systematically identify lots of stuck states at which some switches show poor performances such as low throughput. Specifically, this method discovers that the throughput of iSLIP, FIRM and DRRM, each with one iteration, may be lower than 60% under certain nonuniform and smoothed periodic traffic pattern.

UNLABELLED: A software package, IndexToolkit, aimed at overcoming the disadvantage of FASTA-format databases for frequent searching, is developed to utilize an indexing strategy to substantially accelerate sequence queries. IndexToolkit includes user-friendly tools and an Application Programming Interface (API) to facilitate indexing, storage and retrieval of protein sequence databases. As open source, it provides a sequence-retrieval developing framework, which is easily extensible for high-speed-request proteomic applications, such as database searching or modification discovering. We applied IndexToolkit to database searching engine pFind to demonstrate its effect. Experimental studies show that IndexToolkit is able to support significantly faster searches of protein database. AVAILABILITY: The IndexToolkit is free to use under the open source GNU GPL license. The source code and the compiled binary can be freely accessed through the website http://pfind.jdl.ac.cn/IndexToolkit. In this website, the more detailed information including screenshots and documentations for users and developers is also available.

Input queued switches have been well studied in the recent past. A scheduling algorithm is required to schedule the transfer of packets through the switch fabric (e.g. crossbar) at every time slot. The maximum weight matching (MWM) algorithm is known to deliver 100% throughput under any admissible traffic. However, MWM is not practical for its high computational complexity O(N/sup 3/). In this paper, we study a class of approximation algorithms to MWM from the point of view of local search. Notably we observe that: (a) Local search is well suitable for parallel computation. (b) Each line card of high performance router has at least one processor. Based on the two important observations, a parallelized greedy scheduling algorithm is proposed. The proposed algorithm is proved to be rate stable under any admissible traffic. Simulation results show that our algorithm outperforms other randomized approximations to MWM.

Scalability considerations drive the switch fabric design to evolve from output queueing to input queueing and further to combined input and crosspoint queueing (CICQ). However, few CICQ switches are known with guaranteed quality of service, and credit-based flow control induces a scalability bottleneck. In this paper, we propose a novel CICQ switch called the smoothed buffered crossbar or sBUX, based on a new design objective of smoothness and on a new rate-based flow control scheme called the smoothed multiplexer or sMUX. It is proved that with a buffer of just four cells at each crosspoint, sBUX can utilize 100% of the switch capacity to provide deterministic guarantees of bandwidth and fairness, delay and jitter bounds for each flow. In particular, neither credit-based flow control nor speedup is used, and arbitrary fabric-internal latency is allowed between line cards and the switch core.

Summary: Research in proteomics requires powerful database-searching software to automatically identify protein sequences in a complex protein mixture via tandem mass spectrometry. In this paper, we describe a novel database-searching software system called pFind (peptide/protein Finder), which employs an effective peptide-scoring algorithm that we reported earlier. The pFind server is implemented with the C++ STL, .Net and XML technologies. As a result, high speed and good usability of the software are achieved. Availability: The pFind web server can be freely accessed through the website http://pfind.jdl.ac.cn. In this website, the compiled binary of the local version is also available. Contact: [email protected]

A number of different approaches have been proposed to predict elemental component formulas (or molecular formulas) of molecular ions in low and medium resolution mass spectra. Most of them rely on isotope patterns, enumerate all possible formulas for an ion, and exclude certain formulas violating chemical constraints. However, these methods cannot be well generalized to the component prediction of fragment ions in tandem mass spectra. In this paper, a new method, FFP (Fragment ion Formula Prediction), is presented to predict elemental component formulas of fragment ions. In the FFP method, the prediction of the best formulas is converted into the minimization of the distance between theoretical and observed isotope patterns. And, then, a novel local search model is proposed to generate a set of candidate formulas efficiently. After the search, FFP applies a new multiconstraint filtering to exclude as many invalid and improbable formulas as possible. FFP is experimentally compared with the previous enumeration methods, and shown to outperform them significantly. The results of this paper can help to improve the reliability of de novo in the identification of peptide sequences.

Input queued switching architectures have become predominant in high speed switches and routers. In this paper, we change the point of view from weight-based matching to weight-based service, and propose a distributed load adaptive scheduling (DLAS) algorithm. In DLAS, the round robin arbiters are used to find a matching between the input ports and output ports. Once the matching between an input-output pair is established, the scheduler will keep it for a certain period, which is a function of the number of cells queued in the corresponding VOQ. Simulation results show that our scheme achieves high throughput and low delay under admissible traffic. For uniform Bernoulli i.i.d. traffic, it achieves 100% throughput, and for nonuniform traffic, its throughput is almost 100%.

It is important to smooth the quality variability and improve the utilization of the available network bandwidth in a streaming session from a scalable streaming server to the client over the network with bandwidth variation. In this paper, we propose an on-line smoothing scheduling algorithm for real-time scalable media stream with the variable network bandwidth and packet loss. This algorithm adopts a rate-distortion optimized framework and real-time scheduling scheme to select and schedule the packets according to the network status. It attempts to minimize the quality variability in client while at the same time maximizing the utilization of the variable network bandwidth. Experiments show that, compared with frame-based scheduling algorithm, our proposed on-line smoothing algorithm not only improves the quality in decoded video frames but also make the quality variation smoother.

Digital video cassette recording (VCR) functionality enables quick and user friendly browsing of multimedia content, thus is highly desirable in streaming video application. In this paper, we propose a layer-based implementation scheme and a layer-based soft real-time scheduling algorithm for efficient implementation of scalable streaming video system to provide full VCR functionality over a dynamic wireless network. Scalable streams provide a layer-based representation for transmitting media contents. Besides the real-time constraint, unequal priorities of scalable streams at different layers and frames are taken into account to support VCR functionality in the proposed algorithms. Thus, the better usage of available bandwidth and smoother playback can be achieved in the streaming system. Simulated results show that, with the proposed algorithms, the playback quality can be efficiently improved.

Some wireless communication systems, such as mobile ad hoc network, operate on a limited battery supply, and energy efficiency is therefore crucial to the network survival time. This paper proposes a multiscale load adaptive scheduling (MLAS) scheme to determine the transmission time of the packets. In MLAS, traffic is predicted over the scale of time window, and then a transmission time stretching algorithm is proposed to adjust the packet transmission time packet by packet. Compared with the fixed transmission time scheme, MLAS can reduce the energy consumption of data transmission by up to 90% corresponding to the load factor and the burst characteristic. MLAS also outperforms the look ahead based scheme in the performance of energy efficiency with the same average delay.