Explainable clustering has become increasingly important as it presents the clustering results in a manner that can be easily understood by the end-users. However, most existing explainable clustering approaches generate only a single explanation such as a decision tree for the given clustering result, overlooking that multiple valid interpretations may exist. To address this limitation, we propose the CME (Clustering with Multiview Explanations) algorithm. This method constructs a diverse set of candidate decision trees by retaining multiple splitting points at each node, where each splitting point is valid in a statistical sense. The tree similarity based on optimal path matches across corresponding clusters is then used to build a similarity graph. A subset of representative decision trees are selected by solving the minimum dominating set problem defined on the corresponding similarity graph. Experiments on 10 real-world categorical datasets demonstrate that CME provides multiple complementary explanations that may be missed by existing algorithms. Moreover, these additional decision trees can be more accurate and interpretable than those ones identified by baseline methods.

Sequence classification is a fundamental research issue in data mining and machine learning. However, existing sequence classification methods primarily focus on improving the prediction performance. Although a few methods attempt to enhance the interpretability, they often fail to provide intuitive model explanations and come with high computational costs. To fill this gap, we propose an interpretable sequence classification algorithm based on decision set. Each rule in the decision set is only associated with one discriminative pattern (subsequence) and the classification decision is made based on one best-matched rule. Hence, the proposed method has good interpretablility since the classification decision is solely determined by one simple intuitive rule. Experimental results on real-world data sets demonstrate that our algorithm outperforms the state-ofthe- art interpretable sequence classification methods in terms of both interpretability and classification accuracy.

Clustering validation is a fundamental task in cluster analysis. While many clustering validity indices have been proposed, most existing internal validity indices are typically defined heuristically, lacking solid statistical foundation and interpretation. To address this limitation, we introduce a new internal validity index that employs hypothesis testing to determine whether two samples belong to the same cluster and defines the index as the proportion of correctly identified sample pairs based on their cluster memberships. To demonstrate the advantages of proposed validity index, we conduct experiments on various synthetic and real-world data sets. The experimental results indicate that our validation index can beat both classic and state-of-the-art internal validation indices.

Histone modifications play a crucial role in transcriptional regulation and are essential targets for genome annotation and gene expression modeling. However, experimentally profiling histone modifications across species, tissues, and cellular states is costly and often impractical. While numerous deep learning models have been proposed to predict histone modifications, most operate at relatively low resolution (128 bp), limiting their utility in fine-scale genomic analysis. In this study, we present MambaHM (Mamba for predicting Histone Modifications), a novel deep learning framework built upon Mamba architecture. MambaHM integrates DNA sequence features with chromatin accessibility data (ATAC-seq) to predict ten histone modifications. Leveraging the linear computational complexity of Mamba's state-space modeling, our model avoids excessive compression of feature length during embedding. This enables the model to retain sufficient contextual information while simultaneously achieving 16-bp resolution, thereby enhancing the granularity and accuracy of prediction. Experiments demonstrate that MambaHM achieves a mean Pearson correlation of 0.836 (± 0.063) on the K562 cell line test set. Furthermore, the model generalizes well across cell types, tissues, and species, with a mean cross-context correlation of$0.557 (\pm 0.105)$, approaching the reliability of experimental assays. Compared to state-of-the-art models, MambaHM achieves a$\mathbf{7. 0 3 3 \%}(\mathbf{\pm 0. 0 4 1})$improvement in cross-cell-type performance and over a 58.978 % (877 bp) improvement in prediction deviation evaluation for peak calling. Overall, MambaHM provides a powerful, cost-effective, and fineresolution tool for histone modification prediction, offering precise epigenomic references for downstream analysis and potential applications in drug discovery. The source code is available at https://github.com/zhichunlizzx/MambaHM.

The detection of communities from a graph is a key issue in network science and graph data mining . However, existing community detection algorithms can always partition a given network/graph into different communities/subgraphs, even when no community structure exists. Obviously, it will lead to fruitless efforts and erroneous conclusions if we conduct the community detection procedure on a network without a community structure. Hence, prior to community detection, it is a must to test whether the community structure is present in the target network. Unfortunately, the community structure testing issue is still not revolved and existing solutions have some limitations. Therefore, we present a new test, which is called FCN (Frequent Common Neighbor) test to tackle the community structure testing problem . In FCN test, the number of FCN sets is employed as the test statistic, which will approximately follows a Poisson distribution when the support threshold is sufficiently large under the null hypothesis that the graph is generated according to the Erdős-Rényi model. We compare the proposed FCN test with existing community structure testing methods on both real networks and simulated networks. The experimental results demonstrate the effectiveness and advantage of our method.

Categorical data clustering is a fundamental data mining problem, which has been extensively studied during the past decades. To date, many effective clustering algorithms for categorical data are available in the literature. However, almost all existing categorical data clustering algorithms did not address the issue of the statistical significance of detected clusters. In particular, how to assess the statistical significance of a set of non-overlapping categorical clusters still remains unaddressed. In this article, we formulate the categorical data clustering problem as a multiple hypothesis testing problem, where the null hypothesis is that each attribute is independent of the given partition of clusters. Then, all individual \(p\) -values from different attributes are integrated to obtain a consensus \(p\) -value through statistical meta-analysis. Thereafter, a significance-based clustering algorithm is proposed in which the combined \(p\) -value is efficiently optimized in an indirectly and incremental manner. Experimental results on 25 real-world datasets demonstrate that our method is capable of achieving comparable performance to state-of-the-art categorical data clustering algorithms. Furthermore, our method has a good capability of determining whether there really exists a clustering structure and assessing whether a given set of clusters is statistically significant.

Accurately predicting the secondary structure of Non-coding RNAs is crucial for understanding their biological roles. However, current methods face challenges in accuracy and computational efficiency, particularly for long RNA sequences. Here, we present a novel three-step framework for RNA secondary structure prediction, PPA (Partition, Predict, and Assemble). It first partitions the RNA sequence into independent fragments based on exterior loops, then independently predicts the secondary structure of each fragment, and finally assembles them to construct the complete RNA secondary structure. Following the PPA framework, we introduce ELPBert, a model for RNA exterior loop prediction. We partition the RNA sequence at the central nucleotide of the predicted exterior-loop bases. The performance of six state-of-the-art RNA secondary structure prediction methods with and without RNA partition using our ELPBert were compared. Results demonstrate a great improvement of these methods with RNA partition, especially for long sequences. We believe our PPA framework could serve as an universal framework for RNA secondary structure prediction, particularly for long RNA sequences. Data and code are provided at https://github.com/Kali-ym/PPAwithELPBert.

Seizure detection and type classification from electroencephalogram (EEG) has the potential to improve the diagnosis and treatment of epilepsy. Although the task of seizure detection has been well-investigated, seizure type classification remains largely unexplored. The intricate nature of seizure dynamics presents a significant challenge in effectively extracting distinguishing features from noisy and high-dimensional EEG signals. Previous studies mainly focus on extracting features from temporal, spectral or special domain. Extracting temporal-spatial-spectral features simultaneously from EEG remains challenging. In this paper, we introduce an attention-based neural network to effectively extract temporal-spatial-spectral EEG features, for seizure type classification. It utilizes an attention module with one-shot aggregation to extract multi-level temporal-spatial-spectral EEG features, aiming to differentiate the complex patterns of various seizure types. Specifically, we construct the 3-dimensional representation of EEG by stacking the time-frequency matrices obtained from short time Fourier transform. The attention module consists of paralleled temporal and spatial-spectral attention blocks, allowing the model to focus on the most distinctive time stamps, sensor locations, and frequency bands. The proposed approach is validated on the largest public seizure EEG database, TUSZ v1.5.2. Five-fold cross validation demonstrates that our framework achieved 0.951 weighted F1 score on seizure type classification, achieving state-of-the-art performance. Ablation study confirmed the effectiveness of the temporal and spatial-spectral attention blocks.

Histone modifications (HMs) play a critical role in various biological processes, but annotating histone modifications across different cell types using experimental methods alone is extremely challenging. Although many deep learning methods have been developed to predict histone modifications, most rely solely on DNA sequences and do not incorporate novel cell-specific features. In this study, we propose KAS-former, a transformer-based model that integrates DNA sequences with cell-specific features derived from KAS-seq data, enabling effective prediction of histone modifications. Leveraging this transformer architecture coupled with dilated convolution, KAS-former achieves a broad receptive field, effectively capturing cell type-specific specificity from KAS-seq data. Our results demonstrate that KAS-former achieves high accuracy in predicting histone modifications across multiple cell types and shows strong potential for transcription factor prediction. By capturing cell-specific features, this approach not only improves the accuracy of histone modification predictions but also offers valuable insights into the interplay between histone modifications and transcription regulation. The code for KAS-former is available on GitHub at https://github.com/wzhy2000/KAS-former.

Identifying essential proteins is vital for deciphering the intricacies of disease mechanisms and devising efficacious therapeutic strategies. Over the past several decades, a plethora of algorithms have been proposed, aimed at synthesizing topological and biological information to address the complex challenge of essential protein identification. Nevertheless, a critical examination of the current methodologies reveals certain limitations: (1) the aggregation of diverse features in various methods often requires parameter tuning to maintain balance, potentially introducing instability and increasing complexity in practical scenarios; (2) traditional methods commonly combine various features without in-depth mathematical or physical interpretation, possibly falling short of fully revealing the principles behind the observed phenomena. Hence, we propose a new algorithm for essential protein detection, which is named ITBSE. The basic idea behind this method is to reconstruct the PPI network by removing false positive edges and the subsequent allocation of a protein score. This scoring process integrates both the topological attributes of the reconstructed PPI network and biological data, utilizing the computational framework of Shannon entropy for a comprehensive assessment. To evaluate the effectiveness of our method, we conduct the experiments on real PPI networks and compare with 10 popular methods including DC, BC, CC, LID, PR, DMNC, LAC, NC, PeC and esPOS. The comparison results demonstrate that ITBSE is able to achieve better performance than those competing algorithms.

Identifying essential proteins is crucial for understanding disease mechanisms and developing therapeutic strategies. During the past several decades, numerous algorithms have been introduced to integrate topological and biological information to tackle the challenge of identifying essential proteins. However, existing methods still have some drawbacks: (1) the lack of rigorous mathematical interpretation for the parameters that determine their respective weights when integrating topological and biological information; (2) the lack of flexibility for adding or removing topological and biological information from integration process in real applications. To overcome these limitations, we propose a novel essential protein discovery method, called EPSIF, which assigns weights to PPI network interactions and integrates diverse topological and biological information via a statistical ensemble model. To assess the performance of EPSIF, we conduct experiments on real PPI networks and compare with eight state-of-the-art algorithms, which confirm the effectiveness and flexibility of EPSIF.

As one of the most important issues in data mining and network science, the community detection problem has been extensively investigated during the past decades. Despite of the success achieved by existing methods, how to directly access the statistical significance of an individual community in a weighted network remains unsolved. To address this issue, we present a new method to calculate the analytical p-value of an individual community in weighted networks. The proposed analytical p-value is able to assess the statistical significance that one target community appears in a random weighted graph in a straightforward manner. To verify the effectiveness of the proposed p-value in community evaluation, it is utilized as the objective function in a local search procedure to derive a new community detection algorithm. Experimental results show that the new algorithm is able to achieve comparable performance to those state-of-the-art algorithms for identifying communities from weighted networks. The source codes of our method are available at: https://github.com/chenwenfang/MSSC.

The community structure typically refers to the existence of a network partition in terms of a set of non-overlapping dense sub-graphs, where each sub-graph is called a community and there are few links between different communities. The detection of community structure is able to provide additional knowledge on the organization mechanism of the network and its characteristics. Despite decades of developments in community detection algorithms, how to determine whether a given community structure is true or not in a statistically sound manner still remains unresolved. In this paper, we present an analytical upper bound on thep-value of a community structure under the configuration model. To demonstrate its effectiveness on community structure validation, we further develop a community detection algorithm in which thep-value upper bound is used as the objective function. Experimental results on both real networks and simulated networks show that our algorithm outperforms prior state-of-the-art community detection methods.

Current decision trees such as C4.5 and CART are widely used in different fields due to their simplicity, accuracy and intuitive interpretation. Similar to other popular classifiers, these tree-based classification algorithms are developed for fixed-length vector data and suffer from intrinsic limitations in handling complex data such as sequences. To tackle the discrete sequence classification task, the dominant strategy is to adopt a two-step procedure: first transform the sequential dataset into a vector dataset and then apply existing tree-based classifiers on the new vector data. However, such methods are highly dependent on the feature generation procedure and some features that are critical to the tree construction may be missed. To alleviate these issues, we present a new tree-based sequence classification method, which is able to construct a concise decision tree from the feature space that is composed of all subsequences present in the training sequences. Experimental results on fourteen real datasets show that our method can achieve better performance than those state-of-the-art sequence classification algorithms. The source codes of our method are available at: https://github.com/ZiyaoWu/SeqDT.

The identification of essential proteins is an important problem in bioinformatics. During the past decades, many centrality measures and algorithms have been proposed to address this issue. However, existing methods still deserve the following drawbacks: (1) the lack of a context-free and readily interpretable quantification of their centrality values; (2) the difficulty of specifying a proper threshold for their centrality values; (3) the incapability of controlling the quality of reported essential proteins in a statistically sound manner. To overcome the limitations of existing solutions, we tackle the essential protein discovery problem from a significance testing perspective. More precisely, the essential protein discovery problem is formulated as a multiple hypothesis testing problem, where the null hypothesis is that each protein is not an essential protein. To quantify the statistical significance of each protein, we present a p-value calculation method in which both the degree and the local clustering coefficient are used as the test statistic and the Erdös-Rényi model is employed as the random graph model. After calculating the p-value for each protein, the false discovery rate is used as the error rate in the multiple testing correction procedure. Our significance-based essential protein discovery method is named as SigEP, which is tested on both simulated networks and real PPI networks. The experimental results show that our method is able to achieve better performance than those competing algorithms.

Community detection is a key data analysis problem across different fields. During the past decades, numerous algorithms have been proposed to address this issue. However, most work on community detection does not address the issue of statistical significance. Although some research efforts have been made towards mining statistically significant communities, deriving an analytical solution of$p$-value for one community under the configuration model is still a challenging mission that remains unsolved. The configuration model is a widely used random graph model in community detection, in which the degree of each node is preserved in the generated random networks. To partially fulfill this void, we present a tight upper bound on the$p$-value of a single community under the configuration model, which can be used for quantifying the statistical significance of each community analytically. Meanwhile, we present a local search method to detect statistically significant communities in an iterative manner. Experimental results demonstrate that our method is comparable with the competing methods on detecting statistically significant communities.

Essential protein plays a vital role in understanding the cellular life. With the advance in high-throughput technologies, a number of protein-protein interaction (PPI) networks have been constructed such that essential proteins can be identified from a system biology perspective. Although a series of network-based essential protein discovery methods have been proposed, these existing methods still have some drawbacks. Recently, it has been shown that the significance-based method SigEP is promising on overcoming the defects that are inherent in currently available essential protein identification methods. However, the SigEP method is developed under the unrealistic Erdös-Rényi (E-R) model and its time complexity is very high. Hence, we propose a new significance-based essential protein recognition method named EPCS in which the essential protein discovery problem is formulated as a community significance testing problem. Experimental results on four PPI networks show that EPCS performs better than nine state-of-the-art essential protein identification methods and the only significance-based essential protein identification method SigEP.

The detection of protein complexes from protein-protein interaction network is a fundamental issue in bioinformatics and systems biology. To solve this problem, numerous methods have been proposed from different angles in the past decades. However, the study on detecting statistically significant protein complexes still has not received much attention. Although there are a few methods available in the literature for identifying statistically significant protein complexes, none of these methods can provide a more strict control on the error rate of a protein complex in terms of family-wise error rate (FWER). In this paper, we propose a new detection method SSF that is capable of controlling the FWER of each reported protein complex. More precisely, we first present a p-value calculation method based on Fisher's exact test to quantify the association between each protein and a given candidate protein complex. Consequently, we describe the key modules of the SSF algorithm: a seed expansion procedure for significant protein complexes search and a set cover strategy for redundancy elimination. The experimental results on five benchmark data sets show that: (1) our method can achieve the highest precision; (2) it outperforms three competing methods in terms of normalized mutual information (NMI) and F1 score in most cases.

Affinity Purification-Mass Spectrometry (AP-MS) is one of the most important technologies for constructing protein-protein interaction (PPI) networks. In this paper, we propose an ensemble method, Reinforce, for inferring PPI network from AP-MS data set. The new algorithm named Reinforce is based on rank aggregation and false discovery rate control. Under the null hypothesis that the interaction scores from different scoring methods are randomly generated, Reinforce follows three steps to integrate multiple ranking results from different algorithms or different data sets. The experimental results show that Reinforce can get more stable and accurate inference results than existing algorithms. The source codes of Reinforce and data sets used in the experiments are available at: https://sourceforge.net/projects/reinforce/.

BACKGROUND: Identifying protein complexes from protein-protein interaction (PPI) network is one of the most important tasks in proteomics. Existing computational methods try to incorporate a variety of biological evidences to enhance the quality of predicted complexes. However, it is still a challenge to integrate different types of biological information into the complexes discovery process under a unified framework. Recently, attributed network embedding methods have be proved to be remarkably effective in generating vector representations for nodes in the network. In the transformed vector space, both the topological proximity and node attributed affinity between different nodes are preserved. Therefore, such attributed network embedding methods provide us a unified framework to integrate various biological evidences into the protein complexes identification process. RESULTS: In this article, we propose a new method called GANE to predict protein complexes based on Gene Ontology (GO) attributed network embedding. Firstly, it learns the vector representation for each protein from a GO attributed PPI network. Based on the pair-wise vector representation similarity, a weighted adjacency matrix is constructed. Secondly, it uses the clique mining method to generate candidate cores. Consequently, seed cores are obtained by ranking candidate cores based on their densities on the weighted adjacency matrix and removing redundant cores. For each seed core, its attachments are the proteins with correlation score that is larger than a given threshold. The combination of a seed core and its attachment proteins is reported as a predicted protein complex by the GANE algorithm. For performance evaluation, we compared GANE with six protein complex identification methods on five yeast PPI networks. Experimental results showes that GANE performs better than the competing algorithms in terms of different evaluation metrics. CONCLUSIONS: GANE provides a framework that integrate many valuable and different biological information into the task of protein complex identification. The protein vector representation learned from our attributed PPI network can also be used in other tasks, such as PPI prediction and disease gene prediction.

Since the discovery of the regulatory function of microRNA (miRNA), increased attention has focused on identifying the relationship between miRNA and disease. It has been suggested that computational method are an efficient way to identify potential disease-related miRNAs for further confirmation using biological experiments. In this paper, we first highlighted three limitations commonly associated with previous computational methods. To resolve these limitations, we established disease similarity subnetwork and miRNA similarity subnetwork by integrating multiple data sources, where the disease similarity is composed of disease semantic similarity and disease functional similarity, and the miRNA similarity is calculated using the miRNA-target gene and miRNA-lncRNA (long non-coding RNA) associations. Then, a heterogeneous network was constructed by connecting the disease similarity subnetwork and the miRNA similarity subnetwork using the known miRNA-disease associations. We extended random walk with restart to predict miRNA-disease associations in the heterogeneous network. The leave-one-out cross-validation achieved an average area under the curve (AUC) of 0:8049 across 341 diseases and 476 miRNAs. For five-fold cross-validation, our method achieved an AUC from 0:7970 to 0:9249 for 15 human diseases. Case studies further demonstrated the feasibility of our method to discover potential miRNA-disease associations. An online service for prediction is freely available at http://ifmda.aliapp.com.

Discriminative pattern mining is one of the most important techniques in data mining. This challenging task is concerned with finding a set of patterns that occur with disproportionate frequency in data sets with various class labels. Such patterns are of great value for group difference detection and classifier construction. Research on finding interesting discriminative patterns in class-labeled data evolves rapidly and lots of algorithms have been proposed to specifically address this problem. Discriminative pattern mining techniques have proven their considerable value in biological data analysis. The archetypical applications in bioinformatics include phosphorylation motif discovery, differentially expressed gene identification, discriminative genotype pattern detection, etc. In this article, we present an overview of discriminative pattern mining and the corresponding effective methods, and subsequently we illustrate their applications to tackling the bioinformatics problems. In the end, we give a general discussion of potential challenges and future work for this task.

Protein-protein interaction is of primary importance to understand protein functions. In recent years, the high-throughput AP-MS experiments have generated a large amount of bait-prey data, posing great challenges on the computational analysis of such data for inferring true interactions and protein complexes. To date, many research efforts have been devoted to developing novel computational methods to analyze these AP-MS data sets. In this article, we review and classify the key computational methods developed for the inference of protein-protein interactions and the detection of protein complexes from the AP-MS experiments. We hope that our review as well as the challenges highlighted in the article will provide valuable insights into driving future research for further advancing the state-of-the-art technologies in computational prediction, characterization and analysis of protein-protein interactions and protein complexes from the AP-MS data.

Protein phosphorylation is one of the most pervasive post-translational modifications, regulating diverse cellular processes in various organisms. As mass spectrometry-based experimental approaches for identifying phosphorylation events are resource-intensive, many computational methods have been proposed, in which phosphorylation site prediction is formulated as a classification problem. They differ in several ways, and one crucial issue is the construction of training data and test data for unbiased performance evaluation. In this article, we categorize the existing data construction methods and try to answer three questions: (i) Is it equivalent to use different data construction methods in the assessment of phosphorylation site prediction algorithms? (ii) What kind of test data set is unbiased for assessing the prediction performance of a trained algorithm in different real world scenarios? (iii) Among the summarized training data construction methods, which one(s) has better generalization performance for most scenarios? To answer these questions, we conduct comprehensive experimental studies for both non-kinase-specific and kinase-specific prediction tasks. The experimental results show that: (i) different data construction methods can lead to significantly different prediction performance; (ii) there can be different test data construction methods that are unbiased with respect to different real world scenarios; and (iii) different data construction methods have different generalization performance in different real world scenarios. Therefore, when developing new algorithms in future research, people should concentrate on what kind of scenario their algorithm will work for, what the corresponding unbiased test data are and which training data construction method can generate best generalization performance.

MOTIVATION: Statistical validation of protein identifications is an important issue in shotgun proteomics. The false discovery rate (FDR) is a powerful statistical tool for evaluating the protein identification result. Several research efforts have been made for FDR estimation at the protein level. However, there are still certain drawbacks in the existing FDR estimation methods based on the target-decoy strategy. RESULTS: In this article, we propose a decoy-free protein-level FDR estimation method. Under the null hypothesis that each candidate protein matches an identified peptide totally at random, we assign statistical significance to protein identifications in terms of the permutation P-value and use these P-values to calculate the FDR. Our method consists of three key steps: (i) generating random bipartite graphs with the same structure; (ii) calculating the protein scores on these random graphs; and (iii) calculating the permutation P value and final FDR. As it is time-consuming or prohibitive to execute the protein inference algorithms for thousands of times in step ii, we first train a linear regression model using the original bipartite graph and identification scores provided by the target inference algorithm. Then we use the learned regression model as a substitute of original protein inference method to predict protein scores on shuffled graphs. We test our method on six public available datasets. The results show that our method is comparable with those state-of-the-art algorithms in terms of estimation accuracy. AVAILABILITY: The source code of our algorithm is available at: https://sourceforge.net/projects/plfdr/

Phosphorylation motifs represent position-specific amino acid patterns around the phosphorylation sites in the set of phosphopeptides. Several algorithms have been proposed to uncover phosphorylation motifs, whereas the problem of efficiently discovering a set of significant motifs with sufficiently high coverage and non-redundancy still remains unsolved. Here we present a novel notion called conditional phosphorylation motifs. Through this new concept, the motifs whose over-expressiveness mainly benefits from its constituting parts can be filtered out effectively. To discover conditional phosphorylation motifs, we propose an algorithm called C-Motif for a non-redundant identification of significant phosphorylation motifs. C-Motif is implemented under the Apriori framework, and it tests the statistical significance together with the frequency of candidate motifs in a single stage. Experiments demonstrate that C-Motif outperforms some current algorithms such as MMFPh and Motif-All in terms of coverage and non-redundancy of the results and efficiency of the execution. The source code of C-Motif is available at: https://sourceforge. net/projects/cmotif/.

MicroRNA (miRNA) plays an important role as a regulator in biological processes. Identification of (pre-) miRNAs helps in understanding regulatory processes. Machine learning methods have been designed for pre-miRNA identification. However, most of them cannot provide reliable predictive performances on independent testing data sets. We assumed this is because the training sets, especially the negative training sets, are not sufficiently representative. To generate a representative negative set, we proposed a novel negative sample selection technique, and successfully collected negative samples with improved quality. Two recent classifiers rebuilt with the proposed negative set achieved an improvement of ~6 percent in their predictive performance, which confirmed this assumption. Based on the proposed negative set, we constructed a training set, and developed an online system called miRNApre specifically for human pre-miRNA identification. We showed that miRNApre achieved accuracies on updated human and non-human data sets that were 34.3 and 7.6 percent higher than those achieved by current methods. The results suggest that miRNApre is an effective tool for pre-miRNA identification. Additionally, by integrating miRNApre, we developed a miRNA mining tool, mirnaDetect, which can be applied to find potential miRNAs in genome-scale data. MirnaDetect achieved a comparable mining performance on human chromosome 19 data as other existing methods.

In a shotgun proteomics experiment, proteins are the most biologically meaningful output. The success of proteomics studies depends on the ability to accurately and efficiently identify proteins. Many methods have been proposed to facilitate the identification of proteins from peptide identification results. However, the relationship between protein identification and peptide identification has not been thoroughly explained before. In this paper, we devote ourselves to a combinatorial perspective of the protein inference problem. We employ combinatorial mathematics to calculate the conditional protein probabilities (protein probability means the probability that a protein is correctly identified) under three assumptions, which lead to a lower bound, an upper bound, and an empirical estimation of protein probabilities, respectively. The combinatorial perspective enables us to obtain an analytical expression for protein inference. Our method achieves comparable results with ProteinProphet in a more efficient manner in experiments on two data sets of standard protein mixtures and two data sets of real samples. Based on our model, we study the impact of unique peptides and degenerate peptides (degenerate peptides are peptides shared by at least two proteins) on protein probabilities. Meanwhile, we also study the relationship between our model and ProteinProphet. We name our program ProteinInfer. Its Java source code, our supplementary document and experimental results are available at: >http://bioinformatics.ust.hk/proteininfer.

Assembling peptides identified from tandem mass spectra into a list of proteins, referred to as protein inference, is a critical step in proteomics research. Due to the existence of degenerate peptides and 'one-hit wonders', it is very difficult to determine which proteins are present in the sample. In this paper, we review existing protein inference methods and classify them according to the source of peptide identifications and the principle of algorithms. It is hoped that the readers will gain a good understanding of the current development in this field after reading this review and come up with new protein inference algorithms.

Abstract Contact: [email protected]

MOTIVATION: Assembling peptides identified from tandem mass spectra into a list of proteins, referred to as protein inference, is an important issue in shotgun proteomics. The objective of protein inference is to find a subset of proteins that are truly present in the sample. Although many methods have been proposed for protein inference, several issues such as peptide degeneracy still remain unsolved. RESULTS: In this article, we present a linear programming model for protein inference. In this model, we use a transformation of the joint probability that each peptide/protein pair is present in the sample as the variable. Then, both the peptide probability and protein probability can be expressed as a formula in terms of the linear combination of these variables. Based on this simple fact, the protein inference problem is formulated as an optimization problem: minimize the number of proteins with non-zero probabilities under the constraint that the difference between the calculated peptide probability and the peptide probability generated from peptide identification algorithms should be less than some threshold. This model addresses the peptide degeneracy issue by forcing some joint probability variables involving degenerate peptides to be zero in a rigorous manner. The corresponding inference algorithm is named as ProteinLP. We test the performance of ProteinLP on six datasets. Experimental results show that our method is competitive with the state-of-the-art protein inference algorithms. AVAILABILITY: The source code of our algorithm is available at: https://sourceforge.net/projects/prolp/. CONTACT: [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics Online.

Searching tandem mass spectra against a protein database has been a mainstream method for peptide identification. Improving peptide identification results by ranking true Peptide-Spectrum Matches (PSMs) over their false counterparts leads to the development of various reranking algorithms. In peptide reranking, discriminative information is essential to distinguish true PSMs from false PSMs. Generally, most peptide reranking methods obtain discriminative information directly from database search scores or by training machine learning models. Information in the protein database and MS1 spectra (i.e., single stage MS spectra) is ignored. In this paper, we propose to use information in the protein database and MS1 spectra to rerank peptide identification results. To quantitatively analyze their effects to peptide reranking results, three peptide reranking methods are proposed: PPMRanker, PPIRanker, and MIRanker. PPMRanker only uses Protein-Peptide Map (PPM) information from the protein database, PPIRanker only uses Precursor Peak Intensity (PPI) information, and MIRanker employs both PPM information and PPI information. According to our experiments on a standard protein mixture data set, a human data set and a mouse data set, PPMRanker and MIRanker achieve better peptide reranking results than PetideProphet, PeptideProphet+NSP (number of sibling peptides) and a score regularization method SRPI. The source codes of PPMRanker, PPIRanker, and MIRanker, and all supplementary documents are available at our website: http://bioinformatics.ust.hk/pepreranking/. Alternatively, these documents can also be downloaded from: http://sourceforge.net/projects/pepreranking/.

BACKGROUND: Phosphorylation motifs represent common patterns around the phosphorylation site. The discovery of such kinds of motifs reveals the underlying regulation mechanism and facilitates the prediction of unknown phosphorylation event. To date, people have gathered large amounts of phosphorylation data, making it possible to perform substrate-driven motif discovery using data mining techniques. RESULTS: We describe an algorithm called Motif-All that is able to efficiently identify all statistically significant motifs. The proposed method explores a support constraint to reduce search space and avoid generating random artifacts. As the number of phosphorylated peptides are far less than that of unphosphorylated ones, we divide the mining process into two stages: The first step generates candidates from the set of phosphorylated sequences using only support constraint and the second step tests the statistical significance of each candidate using the odds ratio derived from the whole data set. Experimental results on real data show that Motif-All outperforms current algorithms in terms of both effectiveness and efficiency. CONCLUSIONS: Motif-All is a useful tool for discovering statistically significant phosphorylation motifs. Source codes and data sets are available at: http://bioinformatics.ust.hk/MotifAll.rar.

Peptide identification from tandem mass spectrometry (MS/MS) data is one of the most important problems in computational proteomics. This technique relies heavily on the accurate assessment of the quality of peptide-spectrum matches (PSMs). However, current MS technology and PSM scoring algorithm are far from perfect, leading to the generation of incorrect peptide-spectrum pairs. Thus, it is critical to develop new post-processing techniques that can distinguish true identifications from false identifications effectively. In this paper, we present a consistency-based PSM re-ranking method to improve the initial identification results. This method uses one additional assumption that two peptides belonging to the same protein should be correlated to each other. We formulate an optimization problem that embraces two objectives through regularization: the smoothing consistency among scores of correlated peptides and the fitting consistency between new scores and initial scores. This optimization problem can be solved analytically. The experimental study on several real MS/MS data sets shows that this re-ranking method improves the identification performance. The score regularization method can be used as a general post-processing step for improving peptide identifications. Source codes and data sets are available at: http://bioinformatics.ust.hk/SRPI.rar .

BACKGROUND: In genome-wide association studies (GWAS), the number of single-nucleotide polymorphisms (SNPs) typically ranges between 500,000 and 1,000,000. Accordingly, detecting gene-gene interactions in GWAS is computationally challenging because it involves hundreds of billions of SNP pairs. Stage-wise strategies are often used to overcome the computational difficulty. In the first stage, fast screening methods (e.g. Tuning ReliefF) are applied to reduce the whole SNP set to a small subset. In the second stage, sophisticated modeling methods (e.g., multifactor-dimensionality reduction (MDR)) are applied to the subset of SNPs to identify interesting interaction models and the corresponding interaction patterns. In the third stage, the significance of the identified interaction patterns is evaluated by hypothesis testing. RESULTS: In this paper, we show that this stage-wise strategy could be problematic in controlling the false positive rate if the null distribution is not appropriately chosen. This is because screening and modeling may change the null distribution used in hypothesis testing. In our simulation study, we use some popular screening methods and the popular modeling method MDR as examples to show the effect of the inappropriate choice of null distributions. To choose appropriate null distributions, we suggest to use the permutation test or testing on the independent data set. We demonstrate their performance using synthetic data and a real genome wide data set from an Aged-related Macular Degeneration (AMD) study. CONCLUSIONS: The permutation test or testing on the independent data set can help choosing appropriate null distributions in hypothesis testing, which provides more reliable results in practice.

Protein identification is a key and essential step in mass spectrometry (MS) based proteome research. To date, there are many protein identification strategies that employ either MS data or MS/MS data for database searching. While MS-based methods provide wider coverage than MS/MS-based methods, their identification accuracy is lower since MS data have less information than MS/MS data. Thus, it is desired to design more sophisticated algorithms that achieve higher identification accuracy using MS data. Peptide Mass Fingerprinting (PMF) has been widely used to identify single purified proteins from MS data for many years. In this paper, we extend this technology to protein mixture identification. First, we formulate the problem of protein mixture identification as a Partial Set Covering (PSC) problem. Then, we present several algorithms that can solve the PSC problem efficiently. Finally, we extend the partial set covering model to both MS/MS data and the combination of MS data and MS/MS data. The experimental results on simulated data and real data demonstrate the advantages of our method: 1) it outperforms previous MS-based approaches significantly; 2) it is useful in the MS/MS-based protein inference; and 3) it combines MS data and MS/MS data in a unified model such that the identification performance is further improved.

Traditional network configuration managements for users' QoS can achieve well performance to some extent, but all of them could not be applied to the next generation network (NGN) directly, such as integrated services (Intserv) and differentiated services (Diffserv) typically. To solve this issue, we propose a framework of dynamic QoS self-configuration (FDQS) in this paper. Utility function and interruption mechanism are integrated into FDQS where utility function is utilized to express the priorities of users' QoS and interruption mechanism to dynamically correct those priorities during transmission of data packets. Simulation results show that the proposed FDQS holds the same QoS level with Diffserv in well network state, however when network congestion happens, the level of QoS of FDQS is higher than Diffserv almost by 10%.

MOTIVATION: Database searching is the major peptide identification method in shotgun proteomics. It searches tandem mass spectrometry (MS/MS) spectra against a protein database to identify target peptides. The success of such a database searching method relies on a scoring algorithm that can evaluate the quality of peptide-spectrum matches (PSMs) accurately. However, current scoring algorithms frequently generate inaccurate assignments due to variations and noises in the MS/MS spectra. To address this issue, we like to improve peptide identification by using additional information from other data sources. RESULTS: Single-stage MS data is complementary to MS/MS data in the sense that it provides broader mass coverage but less sequence information. In this article, we show that single-stage MS data can be used to re-rank PSMs. The proposed method explores a linear combination of scores between MS and MS/MS data to perform re-ranking. Experimental results on real data show that such a re-ranking strategy improves the identification performance significantly. AVAILABILITY: http://bioinformatics.ust.hk/ReRankPSMwMS1.rar

MOTIVATION: Hundreds of thousands of single nucleotide polymorphisms (SNPs) are available for genome-wide association (GWA) studies nowadays. The epistatic interactions of SNPs are believed to be very important in determining individual susceptibility to complex diseases. However, existing methods for SNP interaction discovery either suffer from high computation complexity or perform poorly when marginal effects of disease loci are weak or absent. Hence, it is desirable to develop an effective method to search epistatic interactions in genome-wide scale. RESULTS: We propose a new method SNPHarvester to detect SNP-SNP interactions in GWA studies. SNPHarvester creates multiple paths in which the visited SNP groups tend to be statistically associated with diseases, and then harvests those significant SNP groups which pass the statistical tests. It greatly reduces the number of SNPs. Consequently, existing tools can be directly used to detect epistatic interactions. By using a wide range of simulated data and a real genome-wide data, we demonstrate that SNPHarvester outperforms its recent competitor significantly and is promising for practical disease prognosis. AVAILABILITY: http://bioinformatics.ust.hk/SNPHarvester.html.

BACKGROUND: In mass spectrometry (MS) based proteomic data analysis, peak detection is an essential step for subsequent analysis. Recently, there has been significant progress in the development of various peak detection algorithms. However, neither a comprehensive survey nor an experimental comparison of these algorithms is yet available. The main objective of this paper is to provide such a survey and to compare the performance of single spectrum based peak detection methods. RESULTS: In general, we can decompose a peak detection procedure into three consequent parts: smoothing, baseline correction and peak finding. We first categorize existing peak detection algorithms according to the techniques used in different phases. Such a categorization reveals the differences and similarities among existing peak detection algorithms. Then, we choose five typical peak detection algorithms to conduct a comprehensive experimental study using both simulation data and real MALDI MS data. CONCLUSION: The results of comparison show that the continuous wavelet-based algorithm provides the best average performance.

MOTIVATION: Mass Spectrometry (MS)-based protein identification via peptide mass fingerprinting (PMF) is a key component in high-throughput proteome research. While PMF was the first commonly used protein identification method, provided higher throughput than the tandem MS-based method, its accuracy is lower than that of the tandem MS method. Thus, it is desirable to develop PMF-based algorithm with higher protein identification accuracy to facilitate proteome research. RESULTS: We propose a peak bagging method for single MS-based protein identification. It combines results from multiple PMF algorithms, where each PMF algorithm takes a random peak subset as input. Evaluation with a set of real MALDI-TOF MS spectra shows that the new peak bagging method provides consistent improvements over the single PMF algorithm.

This correspondence describes extensions to the k-modes algorithm for clustering categorical data. By modifying a simple matching dissimilarity measure for categorical objects, a heuristic approach was developed in [4], [12] which allows the use of the k-modes paradigm to obtain a cluster with strong intrasimilarity and to efficiently cluster large categorical data sets. The main aim of this paper is to rigorously derive the updating formula of the k-modes clustering algorithm with the new dissimilarity measure and the convergence of the algorithm under the optimization framework.

Clustering is a widely used technique in data mining applications for discovering patterns in underlying data. Most traditional clustering algorithms are limited to handling datasets that contain either numeric or categorical attributes. However, datasets with mixed types of attributes are common in real life data mining applications. In this article, we present two algorithms that extend the Squeezer algorithm to domains with mixed numeric and categorical attributes. The performance of the two algorithms has been studied on real and artificially generated datasets. Comparisons with other clustering algorithms illustrate the superiority of our approaches. © 2005 Wiley Periodicals, Inc. Int J Int Syst 20: 1077–1089, 2005.