Journal of Bioinformatics and Computational Biology

Various indicators of observed-theoretical spectrum matches were compared and the resulting statistical significance was characterized using permutation resampling. Novel decoy databases built by resampling the terminal positions of peptide sequences were evaluated to identify the conditions for accurate computation of peptide match significance levels. The methodology was tested on real and manually curated tandem mass spectra from peptides across a wide range of sizes. Spectra match indicators from complementary database search programs were profiled and optimal indicators were identified. The combination of the optimal indicator and permuted decoy databases improved the calculation of the peptide match significance compared to the approaches currently implemented in the database search programs that rely on distributional assumptions. Permutation tests using p-values obtained from software-dependent matching scores and E-values outperformed permutation tests using all other indicators. The higher overlap in matches between the database search programs when using end permutation compared to existing approaches confirmed the superiority of the end permutation method to identify peptides. The combination of effective match indicators and the end permutation method is recommended for accurate detection of peptides.

We describe a novel formalism representing a system of chemical reactions, with imprecise rates of reactions and concentrations of chemicals, and describe a model reduction method, pruning, based on the chemical properties. We present two algorithms, midpoint approximation and interval approximation, for construction of efficient model abstractions with uncertainty in data. We evaluate computational feasibility by posing queries in computation tree logic (CTL) on a prototype of extracellular-signal-regulated kinase (ERK) pathway.

Evolutionary conservation information included in position-specific scoring matrix (PSSM) has been widely adopted by sequence-based methods for identifying protein functional sites, because all functional sites, whether in ordered or disordered proteins, are found to be conserved at some extent. However, different functional sites have different conservation patterns, some of them are linear contextual, some of them are mingled with highly variable residues, and some others seem to be conserved independently. Every value in PSSMs is calculated independently of each other, without carrying the contextual information of residues in the sequence. Therefore, adopting the direct output of PSSM for prediction fails to consider the relationship between conservation patterns of residues and the distribution of conservation scores in PSSMs. In order to demonstrate the importance of combining PSSMs with the specific conservation patterns of functional sites for prediction, three different PSSM-based methods for identifying three kinds of functional sites have been analyzed. Results suggest that, different PSSM-based methods differ in their capability to identify different patterns of functional sites, and better combining PSSMs with the specific conservation patterns of residues would largely facilitate the prediction.

Distance-based statistical potentials have long been used to model condensed matter systems, e.g. as scoring functions in differentiating native-like protein structures from decoys. These scoring functions are based on the assumption that the total free energy of the protein can be calculated as the sum of pairwise free energy contributions derived from a statistical analysis of pair-distribution functions. However, this fundamental assumption has been challenged theoretically. In fact the free energy of a system with N particles is only exactly related to the N-body distribution function. Based on this argument coarse-grained multi-body statistical potentials have been developed to capture higher-order interactions. Having a coarse representation of the protein and using geometric contacts instead of pairwise interaction distances renders these models insufficient in modeling details of multi-body effects. In this study, we investigated if extending distance-dependent pairwise atomistic statistical potentials to corresponding interaction functions that are conditional on a third interacting body, defined as quasi-three-body statistical potentials, could model details of three-body interactions. We also tested if this approach could improve the predictive capabilities of statistical scoring functions for protein structure prediction. We analyzed the statistical dependency between two simultaneous pairwise interactions and showed that there is surprisingly little if any dependency of a third interacting site on pairwise atomistic statistical potentials. Also the protein structure prediction performance of these quasi-three-body potentials is comparable with their corresponding two-body counterparts. The scoring functions developed in this study showed better or comparable performances compared to some widely used scoring functions for protein structure prediction.

A conserved epitope is an epitope retained by multiple strains of influenza as the key target of a broadly neutralizing antibody. Identification of conserved epitopes is of strong interest to help design broad-spectrum vaccines against influenza. Conservation score measures the evolutionary conservation of an amino acid position in a protein based on the phylogenetic relationships observed amongst homologous sequences. Here, Average Amino Acid Conservation Score (AAACS) is proposed as a method to identify HA's conserved epitopes. Our analysis shows that there is a clear distinction between conserved epitopes and nonconserved epitopes in terms of AAACS. This method also provides an excellent classification performance on an independent dataset. In contrast, alignment-based comparison methods do not work well for this problem, because conserved epitopes to the same broadly neutralizing antibody are usually not identical or similar. Location-based methods are not successful either, because conserved epitopes are located at both the less-conserved globular head (HA1) and the more-conserved stem (HA2). As a case study, two conserved epitopes on HA are predicted for the influenza A virus H7N9: One should match the broadly neutralizing antibodies CR9114 or FI6v3, while the other is new and requires validation by wet-lab experiments.

Several algorithms and software have been developed for inferring phylogenetic trees. However, there exist some biological phenomena such as hybridization, recombination, or horizontal gene transfer which cannot be represented by a tree topology. We need to use phylogenetic networks to adequately represent these important evolutionary mechanisms. In this article, we present a new efficient heuristic algorithm for inferring hybridization networks from evolutionary distance matrices between species. The famous Neighbor-Joining concept and the least-squares criterion are used for building networks. At each step of the algorithm, before joining two given nodes, we check if a hybridization event could be related to one of them or to both of them. The proposed algorithm finds the exact tree solution when the considered distance matrix is a tree metric (i.e. it is representable by a unique phylogenetic tree). It also provides very good hybrids recovery rates for large trees (with 32 and 64 leaves in our simulations) for both distance and sequence types of data. The results yielded by the new algorithm for real and simulated datasets are illustrated and discussed in detail.

Network is a powerful structure which reveals valuable characteristics of the underlying data. However, previous work on evaluating the predictive performance of network-based biomarkers does not take nodal connectedness into account. We argue that it is necessary to maximize the benefit from the network structure by employing appropriate techniques. To address this, we aim to learn a weight coefficient for each node in the network from the quantitative measure such as gene expression data. The weight coefficients are computed from an optimization problem which minimizes the total weighted difference between nodes in a network structure; this can be expressed in terms of graph Laplacian. After obtaining the coefficient vector for the network markers, we can then compute the corresponding network predictor. We demonstrate the effectiveness of the proposed method by conducting experiments using published breast cancer biomarkers with three patient cohorts. Network markers are first grouped based on GO terms related to cancer hallmarks. We compare the predictive performance of each network marker group across gene expression datasets. We also evaluate the network predictor against the average method for feature aggregation. The reported results show that the predictive performance of network markers is generally not consistent across patient cohorts.

Recent evidences suggest that a substantial amount of genome is transcribed more than that was anticipated, giving rise to a large number of unknown or novel transcripts. Identification of novel transcripts can provide key insights into understanding important cellular functions as well as molecular mechanisms underlying complex diseases like cancer. RNA-Seq has emerged as a powerful tool to detect novel transcripts, which previous profiling techniques failed to identify. A number of tools are available for enabling identification of novel transcripts at different levels. Read mappers such as TopHat, MapSplice, and SOAPsplice predict novel junctions, which are the indicators of novel transcripts. Cufflinks assembles novel transcripts based on alignment information and Oases performs de novo construction of transcripts. A common limitation of all these tools is prediction of sizable number of spurious or false positive (FP) novel transcripts. An approach that integrates information from all above sources and simultaneously scrutinizes FPs to correctly identify authentic novel transcripts of high confidence is proposed.

The discovery of common RNA secondary structure motifs is an important problem in bioinformatics. The presence of such motifs is usually associated with key biological functions. However, the identification of structural motifs is far from easy. Unlike motifs in sequences, which have conserved bases, structural motifs have common structure arrangements even if the underlying sequences are different. Over the past few years, hundreds of algorithms have been published for the discovery of sequential motifs, while less work has been done for the structural motifs case. Current structural motif discovery algorithms are limited in terms of accuracy and scalability. In this paper, we present an incremental and scalable algorithm for discovering RNA secondary structure motifs, namely IncMD. We consider the structural motif discovery as a frequent pattern mining problem and tackle it using a modified a priori algorithm. IncMD uses data structures, trie-based linked lists of prefixes (LLP), to accelerate the search and retrieval of patterns, support counting, and candidate generation. We modify the candidate generation step in order to adapt it to the RNA secondary structure representation. IncMD constructs the frequent patterns incrementally from RNA secondary structure basic elements, using nesting and joining operations. The notion of a motif group is introduced in order to simulate an alignment of motifs that only differ in the number of unpaired bases. In addition, we use a cluster beam approach to select motifs that will survive to the next iterations of the search. Results indicate that IncMD can perform better than some of the available structural motif discovery algorithms in terms of sensitivity (Sn), positive predictive value (PPV), and specificity (Sp). The empirical results also show that the algorithm is scalable and runs faster than all of the compared algorithms.

A metabolic network model provides a computational framework to study the metabolism of a cell at the system level. Due to their large sizes and complexity, rational decomposition of these networks into subsystems is a strategy to obtain better insight into the metabolic functions. Additionally, decomposing metabolic networks paves the way to use computational methods that will be otherwise very slow when run on the original genome-scale network. In the present study, we propose FCDECOMP decomposition method based on flux coupling relations (FCRs) between pairs of reaction fluxes. This approach utilizes a genetic algorithm (GA) to obtain subsystems that can be analyzed in isolation, i.e. without considering the reactions of the original network in the analysis. Therefore, we propose that our method is useful for discovering biologically meaningful modules in metabolic networks. As a case study, we show that when this method is applied to the metabolic networks of barley seeds and yeast, the modules are in good agreement with the biological compartments of these networks.