Search

Motivation: Tandem mass spectrometry has become a standard tool for identifying post-translational modifications (PTMs) of proteins. Algorithmic searches for PTMs from tandem mass spectrum data (MS/MS) tend to be hampered by noisy data as well as by a combinatorial explosion of search space. This leads to high uncertainty and long search-execution times., Results: To address this issue, we present PTMTreeSearch, a new algorithm that uses a large database of known PTMs to identify PTMs from MS/MS data. For a given peptide sequence, PTMTreeSearch builds a computational tree wherein each path from the root to the leaves is labeled with the amino acids of a peptide sequence. Branches then represent PTMs. Various empirical tree pruning rules have been designed to decrease the search-execution time by eliminating biologically unlikely solutions. PTMTreeSearch first identifies a relatively small set of high confidence PTM types, and in a second stage, performs a more exhaustive search on this restricted set using relaxed search parameter settings. An analysis of experimental data shows that using the same criteria for false discovery, PTMTreeSearch annotates more peptides than the current state-of-the-art methods and PTM identification algorithms, and achieves this at roughly the same execution time. PTMTreeSearch is implemented as a plugable scoring function in the X!Tandem search engine., Availability: The source code of PTMTreeSearch and a demo server application can be found at http://net.icgeb.org/ptmtreesearch

Motivation: Identification of proteins by mass spectrometry-based proteomics requires automated interpretation of peptide tandem mass spectrometry spectra. The effectiveness of peptide identification can be greatly improved by filtering out extraneous noise peaks before the subsequent database searching steps., Results: Here we present a novel chemical rule-based filtering algorithm, termed CRF, which makes use of the predictable patterns (rules) of collision-induced peptide fragmentation. The algorithm selects peak pairs that obey the common fragmentation rules within plausible limits of mass tolerance as well as peak intensity and produces spectra that can be subsequently submitted to any search engine. CRF increases the positive predictive value and decreases the number of random matches and thus improves performance by 15-20% in terms of peptide annotation using search engines, such as X!Tandem. Importantly, the algorithm also achieves data compression rates of ∼75%., Availability: The MATLAB source code and a web server are available at http://hydrax.icgeb.trieste.it/CRFilter/., Supplementary Information: Supplementary data are available at Bioinformatics online.

Plants undergo an extensive change in gene regulation during abiotic stress. It is of great agricultural importance to know which genes are affected during stress response. The genome sequence of a number of plant species has been determined, among them Arabidopsis and Oryza sativa, whose genome has been annotated most completely as of yet, and are well-known organisms widely used as experimental systems. This paper applies a statistical algorithm for predicting new stress-induced motifs and genes by analyzing promoter sets co-regulated by abiotic stress in the previously mentioned two species. After identifying characteristic putative regulatory motif sequence pairs (dyads) in the promoters of 125 stress-regulated Arabidopsis genes and 87 O. sativa genes, these dyads were used to screen the entire Arabidopsis and O. sativa promoteromes to find related stress-induced genes whose promoters contained a large number of these dyads found by our algorithm. We were able to predict a number of putative dyads, characteristic of a large number of stress-regulated genes, some of them newly discovered by our algorithm and serve as putative transcription factor binding sites. Our new motif prediction algorithm comes complete with a stand-alone program. This algorithm may be used in motif discovery in the future in other species. The more than 1,200 Arabidopsis and 1,700 Orzya sativa genes found by our algorithm are good candidates for further experimental studies in abiotic stress.

ROC ('receiver operator characteristics') analysis is a visual as well as numerical method used for assessing the performance of classification algorithms, such as those used for predicting structures and functions from sequence data. This review summarizes the fundamental concepts of ROC analysis and the interpretation of results using examples of sequence and structure comparison. We overview the available programs and provide evaluation guidelines for genomic/proteomic data, with particular regard to applications to large and heterogeneous databases used in bioinformatics.

Development and testing of protein classification algorithms are hampered by the fact that the protein universe is characterized by groups vastly different in the number of members, in average protein size, similarity within group, etc. Datasets based on traditional cross-validation (k-fold, leave-one-out, etc.) may not give reliable estimates on how an algorithm will generalize to novel, distantly related subtypes of the known protein classes. Supervised cross-validation, i.e., selection of test and train sets according to the known subtypes within a database has been successfully used earlier in conjunction with the SCOP database. Our goal was to extend this principle to other databases and to design standardized benchmark datasets for protein classification. Hierarchical classification trees of protein categories provide a simple and general framework for designing supervised cross-validation strategies for protein classification. Benchmark datasets can be designed at various levels of the concept hierarchy using a simple graph-theoretic distance. A combination of supervised and random sampling was selected to construct reduced size model datasets, suitable for algorithm comparison. Over 3000 new classification tasks were added to our recently established protein classification benchmark collection that currently includes protein sequence (including protein domains and entire proteins), protein structure and reading frame DNA sequence data. We carried out an extensive evaluation based on various machine-learning algorithms such as nearest neighbor, support vector machines, artificial neural networks, random forests and logistic regression, used in conjunction with comparison algorithms, BLAST, Smith-Waterman, Needleman-Wunsch, as well as 3D comparison methods DALI and PRIDE. The resulting datasets provide lower, and in our opinion more realistic estimates of the classifier performance than do random cross-validation schemes. A combination of supervised and random sampling was used to construct model datasets, suitable for algorithm comparison.

We present two efficient network propagation algorithms that operate on a binary tree, i.e., a sparse-edged substitute of an entire similarity network. TreeProp-N is based on passing increments between nodes while TreeProp-E employs propagation to the edges of the tree. Both algorithms improve protein classification efficiency.

Motivation: Likelihood ratio approximants (LRA) have been widely used for model comparison in statistics. The present study was undertaken in order to explore their utility as a scoring (ranking) function in the classification of protein sequences., Results: We used a simple LRA-based on the maximal similarity (or minimal distance) scores of the two top ranking sequence classes. The scoring methods (Smith-Waterman, BLAST, local alignment kernel and compression based distances) were compared on datasets designed to test sequence similarities between proteins distantly related in terms of structure or evolution. It was found that LRA-based scoring can significantly outperform simple scoring methods.

Mutation/selection algorithms were applied to increase the efficiency and the robustness of sparse random networks. Selection for better efficiency leads to the well-known star topology, while selection for robustness only results in a relatively dense core and a small periphery. Concomitant selection for both efficiency and robustness leads to networks with intermittent center/periphery values. Networks evolving under multiple attack regimes develop distinct topologies with larger cores, and are characterized by parameter distributions different from those developing under single-attack regimes.

Motivation: Distance measures built on the notion of text compression have been used for the comparison and classification of entire genomes and mitochondrial genomes. The present study was undertaken in order to explore their utility in the classification of protein sequences., Results: We constructed compression-based distance measures (CBMs) using the Lempel-Zlv and the PPMZ compression algorithms and compared their performance with that of the Smith-Waterman algorithm and BLAST, using nearest neighbour or support vector machine classification schemes. The datasets included a subset of the SCOP protein structure database to test distant protein similarities, a 3-phosphoglycerate-kinase sequences selected from archaean, bacterial and eukaryotic species as well as low and high-complexity sequence segments of the human proteome, CBMs values show a dependence on the length and the complexity of the sequences compared. In classification tasks CBMs performed especially well on distantly related proteins where the performance of a combined measure, constructed from a CBM and a BLAST score, approached or even slightly exceeded that of the Smith-Waterman algorithm and two hidden Markov model-based algorithms.

Unlabelled: An improved version of the PRIDE (PRobaility of IDEntity) fold prediction algorithm has been developed, based on more solid statistical basis, fast search capabilities and efficient input structure processing. The new algorithm is effective in identifying protein structures at the 'H' level of the CATH hierarchy., Availability: The new algorithm is integrated into the PRIDE2 web servers at http://pride.szbk.u-szeged.hu and http://www.icgeb.org/pride., Supplementary Information: Detailed documentation and performance evaluation is available in the description section of the PRIDE2 web server.

Atom depth, originally defined as the distance between a protein atom and the nearest water molecule surrounding a protein, is a simple but valuable geometrical descriptor of the protein interior. It can be easily computed from the 3D structure of a protein, thus complementing the information provided by the calculation of the solvent accessible surface area and buried surface area. Depth has been found to be correlated with several molecular, residue and atomic properties, such as average protein domain size, protein stability, free energy of formation of protein complexes, amino acid type hydrophobicity, residue conservation and hydrogen/deuterium amide proton exchange rates.

Atom depth, defined as the distance (dpx, A) of a nonhydrogen atom from its closest solvent-accessible protein neighbor, provides a simple but precise description of the protein interior. Mean residue depths can be easily computed and are very sensitive to structural features. From the analysis of the average and maximum atom depths of a set of 136 protein structures, we derive a limit of approximately 200 residues for protein and protein domain size. The average and maximum atom depths in a protein are related to its size but not to the fold type. From the same set of structures, we calculated the mean residue depths for the 20 amino acid types, and show that they correlate well with hydrophobicity scales. We show that dpx values can be used to partition atoms in discrete layers according to their depth and to identify atoms that, although buried, are potential targets for posttranslational modifications like phosphorylation. Finally, we find a correlation between highly conserved residues in structural neighbors of the same fold type, and their mean residue depth in the reference structure.

Summary: In order to obtain an accurate description of the protein interior, we describe a simple and fast algorithm that measures the depth of each atom in a protein (dpx), defined as its distance (A) from the closest solvent accessible atom. The program reads a PDB file containing the atomic solvent accessibility in the B-factor field, and writes a file in the same format, where the B-factor field now contains the dpx value. Output structure files can be thus directly displayed with molecular graphics programs like RASMOL, MOLMOL, Swiss-PDB View and colored according to dpx values., Availability: The algorithm is implemented in a standalone program written in C and its source is freely available at ftp.icgeb.trieste.it/pub/DPX or on request from the authors.

Motivation: A simple and fast algorithm is described that calculates a measure of protrusion (cx) for atoms in protein structures, directly useable with the common molecular graphics programs., Results: A sphere of predetermined radius is centered around each non-hydrogen atom, and the volume occupied by the protein and the free volume within the sphere (internal and external volumes, respectively) are calculated. Atoms in protruding regions have a high ratio (cx) between the external and the internal volume. The program reads a PDB file, and writes the output in the same format, with cx values in the B factor field. Output structure files can be directly displayed with standard molecular graphics programs like RASMOL, MOLMOL, Swiss-PDB Viewer and colored according to cx values. We show the potential use of this program in the analysis of two protein-protein complexes and in the prediction of limited proteolysis sites in native proteins., Availability: The algorithm is implemented in a standalone program written in C and its source is freely available at ftp.icgeb.trieste.it/pub/CX or on request from the authors.

Results: A WWW server for protein domain homology prediction, based on BLAST search and a simple data-mining algorithm (Hegyi,H. and Pongor,S. (1993) Comput. Appl. Biosci., 9, 371-372), was constructed providing a tabulated list and a graphic plot of similarities., Availability: http://www.icgeb.trieste.it/domain. Mirror site is available at http://sbase.abc.hu/domain. A standalone programme will be available on request., Supplementary Information: A series of help files is available at the above addresses.