Although convolutional neural networks (CNN) have outperformed conventional methods in predicting the sequence specificities of protein-DNA binding in recent years, they do not take full advantage of the intrinsic weakly-supervised information of DNA sequences that a bound sequence may contain multiple TFBS(s). Here, we propose a weakly-supervised convolutional neural network architecture (WSCNN), combining multiple-instance learning (MIL) with CNN, to further boost the performance of predicting protein-DNA binding. WSCNN first divides each DNA sequence into multiple overlapping subsequences (instances) with a sliding window, and then separately models each instance using CNN, and finally fuses the predicted scores of all instances in the same bag using four fusion methods, including Max, Average, Linear Regression, and Top-Bottom Instances. The experimental results on in vivo and in vitro datasets illustrate the performance of the proposed approach. Moreover, models built on in vitro data using WSCNN can predict in vivo protein-DNA binding with good accuracy. In addition, we give a quantitative analysis of the importance of the reverse-complement mode in predicting in vivo protein-DNA binding, and explain why not directly use advanced pooling layers to combine MIL with CNN, through a series of experiments.

Although Deep learning algorithms have outperformed conventional methods in predicting the sequence specificities of DNA-protein binding, they lack to consider the dependencies among nucleotides and the diverse binding lengths for different transcription factors (TFs). To address the above two limitations simultaneously, in this paper, we propose a high-order convolutional neural network architecture (HOCNN), which employs a high-order encoding method to build high-order dependencies among nucleotides, and a multi-scale convolutional layer to capture the motif features of different length. The experimental results on real ChIP-seq datasets show that the proposed method outperforms the state-of-the-art deep learning method (DeepBind) in the motif discovery task. In addition, we provide further insights about the importance of introducing additional convolutional kernels and the degeneration problem of importing high-order in the motif discovery task.

Gene set enrichment (GSE) is a useful tool for analyzing and interpreting large molecular datasets generated by modern biomedical science. The accuracy and reproducibility of GSE analysis are heavily affected by the quality and integrity of gene sets annotations. In this paper, we propose a novel method, robust trace-norm multitask learning, to solve the optimization problem of gene set annotations. Inspired by the binary nature of annotations, we convert the optimization of gene set annotations into a weakly supervised classification problem and use discriminative logistic regression to fit these datasets. Then, the output of logistic regression can be used to measure the probability of the existence of annotations. In addition, the optimization of each row of the annotation matrix can be treated as an independent weakly classification task, and we use the multitask learning approach with trace-norm regularization to optimize all rows of annotation matrix simultaneously. Finally, the experiments on simulated and real data demonstrate the effectiveness and good performance of the proposed method.

The transcription factors (TFs) can activate or suppress gene expression by binding to specific sites, hence are crucial regulatory elements for transcription. Recently, series of discriminative motif finders have been tailored to offering promising strategy for harnessing the power of large quantities of accumulated high-throughput experimental data. However, in order to achieve high speed, these algorithms have to sacrifice accuracy by employing simplified statistical models during the searching process. In this paper, we propose a novel approach named Discriminative Motif Learning via AUC (DiscMLA) to discover motifs on high-throughput datasets. Unlike previous approaches, DiscMLA tries to optimize with a more comprehensive criterion (AUC) during motifs searching. In addition, based on an experimental observation of motif identification on large-scale datasets, some novel procedures are designed to accelerate DiscMLA. The experimental results on 52 real-world datasets demonstrate that our approach substantially outperforms previous methods on discriminative motif learning problems. DiscMLA' stability, discriminability, and validity will help to exploit high-throughput datasets and answer many fundamental biological questions.

Although discriminative motif discovery (DMD) methods are promising for eliciting motifs from high-throughput experimental data, they usually have to sacrifice accuracy and may fail to fully leverage the potential of large datasets. Recently, it has been demonstrated that the motifs identified by DMDs can be significantly improved by maximizing the receiver-operating characteristic curve (AUC) metric, which has been widely used in the literature to rank the performance of elicited motifs. However, existing approaches for motif refinement choose to directly maximize the non-convex and discontinuous AUC itself, which is known to be difficult and may lead to suboptimal solutions. In this paper, we propose Large Margin Motif Optimizer (LMMO), a large-margin-type algorithm for refining regulatory motifs. By relaxing the AUC cost function with the surrogate convex hinge loss, we show that the resultant learning problem can be cast as an instance of difference-of-convex (DC) programs, and solve it iteratively using constrained concave-convex procedure (CCCP). To further save computational time, we combine LMMO with existing techniques for improving the scalability of large-margin-type algorithms, such as cutting plane method. Experimental evaluations on synthetic and real data illustrate the performance of the proposed approach. The code of LMMO is freely available at: https://github.com/ekffar/LMMO.

The problem of object localization in image appear ubiquitously in computer vision applications including image classification, object detection and visual tracking. Recently, it is shown that multiple-instance learning (MIL) which is regarded as the fourth machine learning framework compared with supervised learning, unsupervised learning and reinforce learning has been verified that will get good effect in object localization in images. In this paper, we propose a novel method to solve the classical MIL problem, named Cross-Validated Smooth Multi-Instance learning (CVS-MIL). We treat the positiveness of instance as a continuous variable. The softmax model is used to bring a bridge between instances and bags and jointly optimize the bag label and instance label in a unified framework. The extensive experiments demonstrate that CVS-MIL consistently achieves superior performance on various MIL benchmarks. Moreover, we simply applied CVS-MIL to a challenging vision task, common object discovery. The state-of-the-art results of object discovery on Pascal VOC datasets further confirm the advantages of the proposed method.

The problem of matrix approximation appears ubiquitously in recommendation systems, computer vision and text mining. The prevailing assumption is that the partially observed matrix has a low-rank or can be well approximated by a low-rank matrix. However, this assumption is strictly that the partially observed matrix is globally low rank. In this paper, we propose a local sensitive formulation of matrix approximation which relaxes the global low-rank assumption, leading to a representation of the observed matrix as a weighted sum of low-rank matrices. We solve the problem by an efficient way based on the alternating direction method of multipliers (ADMM). Our experiments show improvements in prediction accuracy over classical approaches for recommendation tasks.

MOTIVATION: The discovery of transcription factor binding site (TFBS) motifs is essential for untangling the complex mechanism of genetic variation under different developmental and environmental conditions. Among the huge amount of computational approaches for de novo identification of TFBS motifs, discriminative motif learning (DML) methods have been proven to be promising for harnessing the discovery power of accumulated huge amount of high-throughput binding data. However, they have to sacrifice accuracy for speed and could fail to fully utilize the information of the input sequences. RESULTS: We propose a novel algorithm called CDAUC for optimizing DML-learned motifs based on the area under the receiver-operating characteristic curve (AUC) criterion, which has been widely used in the literature to evaluate the significance of extracted motifs. We show that when the considered AUC loss function is optimized in a coordinate-wise manner, the cost function of each resultant sub-problem is a piece-wise constant function, whose optimal value can be found exactly and efficiently. Further, a key step of each iteration of CDAUC can be efficiently solved as a computational geometry problem. Experimental results on real world high-throughput datasets illustrate that CDAUC outperforms competing methods for refining DML motifs, while being one order of magnitude faster. Meanwhile, preliminary results also show that CDAUC may also be useful for improving the interpretability of convolutional kernels generated by the emerging deep learning approaches for predicting TF sequences specificities. AVAILABILITY AND IMPLEMENTATION: CDAUC is available at: https://drive.google.com/drive/folders/0BxOW5MtIZbJjNFpCeHlBVWJHeW8 . CONTACT: [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

This paper addresses the problem of accounting for confounding factors and expression quantitative trait loci (eQTL) mapping in the study of SNP-gene associations. The existing convex penalty based algorithm has limited capacity to keep main information of matrix in the process of reducing matrix rank. We present an algorithm, which use nonconvex penalty based low-rank representation to account for confounding factors and make use of sparse regression for eQTL mapping (NCLRS). The efficiency of the presented algorithm is evaluated by comparing the results of 18 synthetic datasets given by NCLRS and presented algorithm, respectively. The experimental results or biological dataset show that our approach is an effective tool to account for non-genetic effects than currently existing methods.

In recent years, a remarkable amount of protein-protein interaction (PPI) data are being available owing to the advance made in experimental high-throughput technologies. However, the experimentally detected PPI data usually contain a large amount of spurious links, which could contaminate the analysis of the biological significance of protein links and lead to incorrect biological discoveries, thereby posing new challenges to both computational and biological scientists. In this paper, we develop a new embedding algorithm called local similarity preserving embedding (LSPE) to rank the interaction possibility of protein links. By going beyond limitations of current geometric embedding methods for network denoising and emphasizing the local information of PPI networks, LSPE can avoid the unstableness of previous methods. We demonstrate experimental results on benchmark PPI networks and show that LSPE was the overall leader, outperforming the state-of-the-art methods in topological false links elimination problems.

Lysine succinylation is one of most important types in protein post-translational modification, which is involved in many cellular processes and serious diseases. However, effective recognition of such sites with traditional experiment methods may seem to be treated as time-consuming and laborious. Those methods can hardly meet the need of efficient identification a great deal of succinylated sites at speed. In this work, several physicochemical properties of succinylated sites have been extracted, such as the physicochemical property of the amino acids. Flexible neural tree, which is employed as the classification model, was utilized to integrate above mentioned features for generating a novel lysine succinylation prediction framework named ILSES (identification lysine succinylation-sites with ensemble features classification). Such method owns the ability to combining diverse features to predict lysine succinylation with high accuracy and real time.

Built upon the hypergeometric distribution, the Fisher Exact Test score (FETS) and its variants offer a natural way of quantifying the level of TF binding site (TFBS) motif enrichment, and have been chosen as the objective functions of several widely used discriminant motif discovery methods, such as HOMER and DREME. In spite of its popularity and efficacy, FETS is non-smooth and non-differentiable, and is thus difficult to optimize numerically. To circumvent this limitation, existing tools that learn to optimize FETS either have to rely on discrete search strategies or indirect tuning of a few external parameters, which could hurt accuracy and fail to fully utilize the potential of input sequences to generate motifs. In this paper, we propose DirectFS, which is (to our best knowledge) the first FETS-based approach that allows direct learning of the motif parameters in continuous space. We show that when the resultant loss function is optimized in a coordinate-wise manner, the cost function of each resultant sub-problem is a piece-wise constant function, whose optimal value can be found exactly and efficiently. Further, a key step in each iteration of DirectFS requires finding the most statistically significant one among tens of thousands of Fisher's exact tests, which is solved efficiently using a novel `lookahead'-style algorithm. Experimental evaluations on ENCODE ChIP-seq data illustrate the performance of the proposed approach.

The problems of estimating missing values in visual data appear ubiquitously in computer vision applications including image inpainting, video inpainting, hyperspectral data recovery, and magnetic resonance imaging (MRI) data recovery. Recently, it is shown that tensor completion, which generalizes matrix completion to multiway data of higher order, could accurately estimate the overall data structure and achieves state-of-the-art performance for video completion. However, current tensor-based approaches implicitly assume that the partially observed video is globally low rank, which is too stringent for practical applications where the input video could include multiple heterogeneous episodes and the global correlation between frames is not high. To tackle this problem, we propose a novel local sensitive formulation of tensor learning where we assume instead that the video is inter-correlated in a local manner, leading to a representation of the observed tensor as a weighted sum of low-rank tensors. Computationally, we also design efficient scheme for solving the resulting learning problem based on the alternating direction method of multipliers (ADMM). Our experiments show improvements in prediction accuracy over classical approaches for visual data completion tasks.

Cervical cancer is the third most common malignancy in women worldwide. It remains a leading cause of cancer-related death for women in developing countries. In order to contribute to the treatment of the cervical cancer, in our work, we try to find a few key genes resulting in the cervical cancer. Employing functions of several bioinformatics tools, we selected 143 differentially expressed genes (DEGs) associated with the cervical cancer. The results of bioinformatics analysis show that these DEGs play important roles in the development of cervical cancer. Through comparing two differential co-expression networks (DCNs) at two different states, we found a common sub-network and two differential sub-networks as well as some hub genes in three sub-networks. Moreover, some of the hub genes have been reported to be related to the cervical cancer. Those hub genes were analyzed from Gene Ontology function enrichment, pathway enrichment and protein binding three aspects. The results can help us understand the development of the cervical cancer and guide further experiments about the cervical cancer.

In recent years, thanks to the efforts of individual scientists and research consortiums, a huge amount of chromatin immunoprecipitation followed by high-throughput sequencing (ChIP-seq) experimental data have been accumulated. Instead of investigating them independently, several recent studies have convincingly demonstrated that a wealth of scientific insights can be gained by integrative analysis of these ChIP-seq data. However, when used for the purpose of integrative analysis, a serious drawback of current ChIP-seq technique is that it is still expensive and time-consuming to generate ChIP-seq datasets of high standard. Most researchers are therefore unable to obtain complete ChIP-seq data for several TFs in a wide variety of cell lines, which considerably limits the understanding of transcriptional regulation pattern. In this paper, we propose a novel method called ChIP-PIT to overcome the aforementioned limitation. In ChIP-PIT, ChIP-seq data corresponding to a diverse collection of cell types, TFs and genes are fused together using the three-mode pair-wise interaction tensor (PIT) model, and the prediction of unperformed ChIP-seq experimental results is formulated as a tensor completion problem. Computationally, we propose efficient first-order method based on extensions of coordinate descent method to learn the optimal solution of ChIP-PIT, which makes it particularly suitable for the analysis of massive scale ChIP-seq data. Experimental evaluation the ENCODE data illustrate the usefulness of the proposed model.

The recently proposed family of discriminative motif finders is promising for harnessing the power of large quantities of accumulated high-throughput experimental data, however, they have to sacrifice accuracy by employing simplified statistical models during the learning process. In this paper, we propose a new approach called Discriminative Motif Learning via AUC (DiscMLA) to discover motifs on large-scale datasets. Unlike previous approaches, DiscMLA tries to optimize AUC directly during motifs searching. In addition, based on an observation, some novel processes are designed for accelerating DiscMLA. The experimental results show that our approach substantially outperforms previous methods on discriminative motif learning problems. DiscMLA' stability, discrimination and validity will help to exploit high-throughput datasets and answer many fundamental biological questions.

In recent years, thanks to the efforts of individual scientists and research consortiums, a huge amount of chromatin immunoprecipitation followed by high-throughput sequencing (ChIP-seq) experimental data have been accumulated. Although several recent studies have demonstrated that a wealth of insights can be gained by integrative analysis of these data, owing to cost, time or sample material availability, it is not always possible for researchers to obtain binding profiles for every proteins in every sample of interest, which considerably limits the power of integrative studies. In this paper, we propose a novel method called Low Rank Convex Co-Embedding (LRCCE) for imputing new ChIP-seq datasets. In LRCCE, a diverse collection of available ChIP-seq data are fused together by mapping proteins, samples, and genomic positions simultaneously into the Euclidean space, thereby making their underling associations directly evaluable using simple calculations. In contrast with previous approaches which mainly use of the local correlations between available datasets, LRCCE can better estimate the overall data structure by formulating the representation learning of all involved entities as a single unified optimization problem. Experimental evaluations on the ENCODE data illustrate the usefulness of the proposed model.

Protein-protein interactions (PPIs) play crucial roles in the execution of various cellular processes and form the basis of biological mechanisms. Although large amount of PPIs data for different species has been generated by high-throughput experimental techniques, the data produced by these techniques have high levels of spurious interactions. Hence, it is of great practical significance to develop reliable computational methods to facilitate the identification of PPIs. In this paper, we propose a new geometric approach called Leave-One-Out Logistic Metric Embedding (LOO-LME) for assessing the reliability of interactions. Unlike previous approaches which mainly seek to preserve the noisy topological information of the PPI networks in the embedding space, LOO-LME first transforms the learning task into an equivalent discriminant form, then directly deals with the uncertainty in PPI networks using a leave-one-out-style approach. The experimental results show that LOO-LME substantially outperforms previous methods on PPI assessment problems. LOO-LME could thus facilitate further graph-based studies of PPIs and may help infer their hidden underlying biological knowledge.

BACKGROUND: Identifying protein-protein interactions (PPIs) is essential for elucidating protein functions and understanding the molecular mechanisms inside the cell. However, the experimental methods for detecting PPIs are both time-consuming and expensive. Therefore, computational prediction of protein interactions are becoming increasingly popular, which can provide an inexpensive way of predicting the most likely set of interactions at the entire proteome scale, and can be used to complement experimental approaches. Although much progress has already been achieved in this direction, the problem is still far from being solved and new approaches are still required to overcome the limitations of the current prediction models. RESULTS: In this work, a sequence-based approach is developed by combining a novel Multi-scale Continuous and Discontinuous (MCD) feature representation and Support Vector Machine (SVM). The MCD representation gives adequate consideration to the interactions between sequentially distant but spatially close amino acid residues, thus it can sufficiently capture multiple overlapping continuous and discontinuous binding patterns within a protein sequence. An effective feature selection method mRMR was employed to construct an optimized and more discriminative feature set by excluding redundant features. Finally, a prediction model is trained and tested based on SVM algorithm to predict the interaction probability of protein pairs. CONCLUSIONS: When performed on the yeast PPIs data set, the proposed approach achieved 91.36% prediction accuracy with 91.94% precision at the sensitivity of 90.67%. Extensive experiments are conducted to compare our method with the existing sequence-based method. Experimental results show that the performance of our predictor is better than several other state-of-the-art predictors, whose average prediction accuracy is 84.91%, sensitivity is 83.24%, and precision is 86.12%. Achieved results show that the proposed approach is very promising for predicting PPI, so it can be a useful supplementary tool for future proteomics studies. The source code and the datasets are freely available at http://csse.szu.edu.cn/staff/youzh/MCDPPI.zip for academic use.

BACKGROUND: Protein-protein interactions (PPIs) play crucial roles in the execution of various cellular processes and form the basis of biological mechanisms. Although large amount of PPIs data for different species has been generated by high-throughput experimental techniques, current PPI pairs obtained with experimental methods cover only a fraction of the complete PPI networks, and further, the experimental methods for identifying PPIs are both time-consuming and expensive. Hence, it is urgent and challenging to develop automated computational methods to efficiently and accurately predict PPIs. RESULTS: We present here a novel hierarchical PCA-EELM (principal component analysis-ensemble extreme learning machine) model to predict protein-protein interactions only using the information of protein sequences. In the proposed method, 11188 protein pairs retrieved from the DIP database were encoded into feature vectors by using four kinds of protein sequences information. Focusing on dimension reduction, an effective feature extraction method PCA was then employed to construct the most discriminative new feature set. Finally, multiple extreme learning machines were trained and then aggregated into a consensus classifier by majority voting. The ensembling of extreme learning machine removes the dependence of results on initial random weights and improves the prediction performance. CONCLUSIONS: When performed on the PPI data of Saccharomyces cerevisiae, the proposed method achieved 87.00% prediction accuracy with 86.15% sensitivity at the precision of 87.59%. Extensive experiments are performed to compare our method with state-of-the-art techniques Support Vector Machine (SVM). Experimental results demonstrate that proposed PCA-EELM outperforms the SVM method by 5-fold cross-validation. Besides, PCA-EELM performs faster than PCA-SVM based method. Consequently, the proposed approach can be considered as a new promising and powerful tools for predicting PPI with excellent performance and less time.

In this paper, we propose a novel inverse-free iterative algorithm for efficiently solving the generalized eigenvalue problem in Canonical Correlation Analysis (CCA). Compared with the state-of-the-art approach of reformulating it as a regression problem, our method is more efficient and can find the exact solution to the original generalized eigenvalue problem under a milder condition. Numerical experiments on several large-scale datasets illustrate the superior performance of the proposed method.

BACKGROUND: Protein-protein interactions (PPIs) play crucial roles in virtually every aspect of cellular function within an organism. Over the last decade, the development of novel high-throughput techniques has resulted in enormous amounts of data and provided valuable resources for studying protein interactions. However, these high-throughput protein interaction data are often associated with high false positive and false negative rates. It is therefore highly desirable to develop scalable methods to identify these errors from the computational perspective. RESULTS: We have developed a robust computational technique for assessing the reliability of interactions and predicting new interactions by combining manifold embedding with multiple information integration. Validation of the proposed method was performed with extensive experiments on densely-connected and sparse PPI networks of yeast respectively. Results demonstrate that the interactions ranked top by our method have high functional homogeneity and localization coherence. CONCLUSIONS: Our proposed method achieves better performances than the existing methods no matter assessing or predicting protein interactions. Furthermore, our method is general enough to work over a variety of PPI networks irrespectively of densely-connected or sparse PPI network. Therefore, the proposed algorithm is a much more promising method to detect both false positive and false negative interactions in PPI networks.

In the field of pattern recognition and machine learning, many problems are involved in the tasks of dimensionality reduction and then classification. In this paper, we develop an efficient dimensionality reduction method named MiniRisk Supervised Discrimiant Projection (MRSDP), which extracts effective low-dimensional features for classification purpose. The proposed method utilizes discriminant information to guide the procedure of extracting intrinsic low-dimensional features and provides a linear projection matrix. Since MRSDP is based on minimax risk criterion, it can minimize the maximal probability of misclassification in the common borders of different classes of data by contracting within-class scatter and maximizing between-class scatter. The advantage of our method is borne out by comparison with other widely used methods. In the experiments on Yale face database and ORL face database, our method achieves constantly superior performance than those competing methods.