Search

With the development of biomedical techniques in the past decades, causal gene identification has become one of the most promising applications in human genome-based business, which can help doctors to evaluate the risk of certain genetic diseases and provide further treatment recommendations for potential patients. When no controlled experiments can be applied, machine learning techniques like causal inference-based methods are generally used to identify causal genes. Unfortunately, most of the existing methods detect disease-related genes by ranking-based strategies or feature selection techniques, which generally return a superset of the corresponding real causal genes. There are also some causal inference-based methods that can identify a part of real causal genes from those supersets, but they are just able to return a few causal genes. This is contrary to our knowledge, as many results from controlled experiments have demonstrated that a certain disease, especially cancer, is usually related to dozens or hundreds of genes. In this work, we present an effective approach for identifying causal genes from gene expression data by using a new search strategy based on non-linear regression-based independence tests, which is able to greatly reduce the search space, and simultaneously establish the causal relationships from the candidate genes to the disease variable. Extensive experiments on real-world cancer datasets show that our method is superior to the existing causal inference-based methods in three aspects: 1) our method can identify dozens of causal genes, and 1/3  ∼ 1/2 of the discovered causal genes can be verified by existing works that they are really directly related to the corresponding disease; 2) The discovered causal genes are able to distinguish the status or disease subtype of the target patient; 3) Most of the discovered causal genes are closely relevant to the disease variable.

Clustering analysis has been widely used in analyzing single-cell RNA-sequencing (scRNA-seq) data to study various biological problems at cellular level. Although a number of scRNA-seq data clustering methods have been developed, most of them evaluate the similarity of pairwise cells while ignoring the global relationships among cells, which sometimes cannot effectively capture the latent structure of cells. In this paper, we propose a new clustering method SPARC for scRNA-seq data. The most important feature of SPARC is a novel similarity metric that uses the sparse representation coefficients of each cell in terms of the other cells to measure the relationships among cells. In addition, we develop an outlier detection method to help parameter selection in SPARC. We compare SPARC with nine existing scRNA-seq data clustering methods on twelve real datasets. Experimental results show that SPARC achieves the state of the art performance. By further analyzing the cell similarity data derived from sparse representations, we find that SPARC is much more effective in mining high quality clusters of scRNA-seq data than two traditional similarity metrics. In conclusion, this study provides a new way to effectively cluster scRNA-seq data and achieves more accurate clustering results than the state of art methods.

Cellular programs often exhibit strong heterogeneity and asynchrony in the timing of program execution. Single-cell RNA-seq technology has provided an unprecedented opportunity for characterizing these cellular processes by simultaneously quantifying many parameters at single-cell resolution. Robust trajectory inference is a critical step in the analysis of dynamic temporal gene expression, which can shed light on the mechanisms of normal development and diseases. Here, we present TiC2D, a novel algorithm for cell trajectory inference from single-cell RNA-seq data, which adopts a consensus clustering strategy to precisely cluster cells. To evaluate the power of TiC2D, we compare it with three state-of-the-art methods on four independent single-cell RNA-seq datasets. The results show that TiC2D can accurately infer developmental trajectories from single-cell transcriptome. Furthermore, the reconstructed trajectories enable us to identify key genes involved in cell fate determination and to obtain new insights about their roles at different developmental stages.

Link weight prediction is an important subject in network science and machine learning. Its applications to social network analysis, network modeling, and bioinformatics are ubiquitous. Although this subject has attracted considerable attention recently, the performance and interpretability of existing prediction models have not been well balanced. This article focuses on an unsupervised mixed strategy for link weight prediction. Here, the target attribute is the link weight, which represents the correlation or strength of the interaction between a pair of nodes. The input of the model is the weighted adjacency matrix without any preprocessing, as widely adopted in the existing models. Extensive observations on a large number of networks show that the new scheme is competitive to the state-of-the-art algorithms concerning both root-mean-square error and Pearson correlation coefficient metrics. Analytic and simulation results suggest that combining the weight consistency of the network and the link weight-associated latent factors of the nodes is a very effective way to solve the link weight prediction problem.

Background: Protein-DNA interaction governs a large number of cellular processes, and it can be altered by a small fraction of interface residues, i.e., the so-called hot spots, which account for most of the interface binding free energy. Accurate prediction of hot spots is critical to understand the principle of protein-DNA interactions. There are already some computational methods that can accurately and efficiently predict a large number of hot residues. However, the insufficiency of experimentally validated hot-spot residues in protein-DNA complexes and the low diversity of the employed features limit the performance of existing methods., Results: Here, we report a new computational method for effectively predicting hot spots in protein-DNA binding interfaces. This method, called PreHots (the abbreviation of Predicting Hotspots), adopts an ensemble stacking classifier that integrates different machine learning classifiers to generate a robust model with 19 features selected by a sequential backward feature selection algorithm. To this end, we constructed two new and reliable datasets (one benchmark for model training and one independent dataset for validation), which totally consist of 123 hot spots and 137 non-hot spots from 89 protein-DNA complexes. The data were manually collected from the literature and existing databases with a strict process of redundancy removal. Our method achieves a sensitivity of 0.813 and an AUC score of 0.868 in 10-fold cross-validation on the benchmark dataset, and a sensitivity of 0.818 and an AUC score of 0.820 on the independent test dataset. The results show that our approach outperforms the existing ones., Conclusions: PreHots, which is based on stack ensemble of boosting algorithms, can reliably predict hot spots at the protein-DNA binding interface on a large scale. Compared with the existing methods, PreHots can achieve better prediction performance. Both the webserver of PreHots and the datasets are freely available at: http://dmb.tongji.edu.cn/tools/PreHots/ .

Single-cell transcriptomic assays have enabled the de novo reconstruction of lineage differentiation trajectories, along with the characterization of cellular heterogeneity and state transitions. Several methods have been developed for reconstructing developmental trajectories from single-cell transcriptomic data, but efforts on analyzing single-cell epigenomic data and on trajectory visualization remain limited. Here we present STREAM, an interactive pipeline capable of disentangling and visualizing complex branching trajectories from both single-cell transcriptomic and epigenomic data. We have tested STREAM on several synthetic and real datasets generated with different single-cell technologies. We further demonstrate its utility for understanding myoblast differentiation and disentangling known heterogeneity in hematopoiesis for different organisms. STREAM is an open-source software package.

Background: Studies have shown that enhancers are significant regulatory elements to play crucial roles in gene expression regulation. Since enhancers are unrelated to the orientation and distance to their target genes, it is a challenging mission for scholars and researchers to accurately predicting distal enhancers. In the past years, with the high-throughout ChiP-seq technologies development, several computational techniques emerge to predict enhancers using epigenetic or genomic features. Nevertheless, the inconsistency of computational models across different cell-lines and the unsatisfactory prediction performance call for further research in this area., Results: Here, we propose a new Deep Belief Network (DBN) based computational method for enhancer prediction, which is called EnhancerDBN. This method combines diverse features, composed of DNA sequence compositional features, DNA methylation and histone modifications. Our computational results indicate that 1) EnhancerDBN outperforms 13 existing methods in prediction, and 2) GC content and DNA methylation can serve as relevant features for enhancer prediction., Conclusion: Deep learning is effective in boosting the performance of enhancer prediction.

Background: Since traditional drug research and development is often time-consuming and high-risk, there is an increasing interest in establishing new medical indications for approved drugs, referred to as drug repositioning, which provides a relatively low-cost and high-efficiency approach for drug discovery. With the explosive growth of large-scale biochemical and phenotypic data, drug repositioning holds great potential for precision medicine in the post-genomic era. It is urgent to develop rational and systematic approaches to predict new indications for approved drugs on a large scale., Results: In this paper, we propose the two-pass random walks with restart on a heterogenous network, TP-NRWRH for short, to predict new indications for approved drugs. Rather than random walk on bipartite network, we integrated the drug-drug similarity network, disease-disease similarity network and known drug-disease association network into one heterogenous network, on which the two-pass random walks with restart is implemented. We have conducted performance evaluation on two datasets of drug-disease associations, and the results show that our method has higher performance than six existing methods. A case study on the Alzheimer's disease showed that nine of top 10 predicted drugs have been approved or investigational for neurodegenerative diseases. The experimental results show that our method achieves state-of-the-art performance in predicting new indications for approved drugs., Conclusions: We proposed a two-pass random walk with restart on the drug-disease heterogeneous network, referred to as TP-NRWRH, to predict new indications for approved drugs. Performance evaluation on two independent datasets showed that TP-NRWRH achieved higher performance than six existing methods on 10-fold cross validations. The case study on the Alzheimer's disease showed that nine of top 10 predicted drugs have been approved or are investigational for neurodegenerative diseases. The results show that our method achieves state-of-the-art performance in predicting new indications for approved drugs.

Nucleosomes and the free linker DNA between them assemble the chromatin. Nucleosome positioning plays an important role in gene transcription regulation, DNA replication and repair, alternative splicing, and so on. With the rapid development of ChIP-seq, it is possible to computationally detect the positions of nucleosomes on chromosomes. However, existing methods cannot provide accurate and detailed information about the detected nucleosomes, especially for the nucleosomes with complex configurations where overlaps and noise exist. Meanwhile, they usually require some prior knowledge of nucleosomes as input, such as the size or the number of the unknown nucleosomes, which may significantly influence the detection results. In this paper, we propose a novel approach DPNuc for identifying nucleosome positions based on the Dirichlet process mixture model. In our method, Markov chain Monte Carlo (MCMC) simulations are employed to determine the mixture model with no need of prior knowledge about nucleosomes. Compared with three existing methods, our approach can provide more detailed information of the detected nucleosomes and can more reasonably reveal the real configurations of the chromosomes; especially, our approach performs better in the complex overlapping situations. By mapping the detected nucleosomes to a synthetic benchmark nucleosome map and two existing benchmark nucleosome maps, it is shown that our approach achieves a better performance in identifying nucleosome positions and gets a higher F-score. Finally, we show that our approach can more reliably detect the size distribution of nucleosomes.

Genomic science is now facing an explosive increase of data thanks to the fast development of sequencing technology. This situation poses serious challenges to genomic data storage and transferring. It is desirable to compress data to reduce storage and transferring cost, and thus to boost data distribution and utilization efficiency. Up to now, a number of algorithms / tools have been developed for compressing genomic sequences. Unlike the existing algorithms, most of which treat genomes as one-dimensional text strings and compress them based on dictionaries or probability models, this paper proposes a novel approach called CoGI (the abbreviation of Compressing Genomes as an Image) for genome compression, which transforms the genomic sequences to a two-dimensional binary image (or bitmap), then applies a rectangular partition coding algorithm to compress the binary image. CoGI can be used as either a reference-based compressor or a reference-free compressor. For the former, we develop two entropy-based algorithms to select a proper reference genome. Performance evaluation is conducted on various genomes. Experimental results show that the reference-based CoGI significantly outperforms two state-of-the-art reference-based genome compressors GReEn and RLZ-opt in both compression ratio and compression efficiency. It also achieves comparable compression ratio but two orders of magnitude higher compression efficiency in comparison with XM--one state-of-the-art reference-free genome compressor. Furthermore, our approach performs much better than Gzip--a general-purpose and widely-used compressor, in both compression speed and compression ratio. So, CoGI can serve as an effective and practical genome compressor. The source code and other related documents of CoGI are available at: http://admis.fudan.edu.cn/projects/cogi.htm.

Background: With the rapid development of high-throughput technologies, researchers can sequence the whole metagenome of a microbial community sampled directly from the environment. The assignment of these metagenomic reads into different species or taxonomical classes is a vital step for metagenomic analysis, which is referred to as binning of metagenomic data., Results: In this paper, we propose a new method TM-MCluster for binning metagenomic reads. First, we represent each metagenomic read as a set of "k-mers" with their frequencies occurring in the read. Then, we employ a probabilistic topic model -- the Latent Dirichlet Allocation (LDA) model to the reads, which generates a number of hidden "topics" such that each read can be represented by a distribution vector of the generated topics. Finally, as in the MCluster method, we apply SKWIC -- a variant of the classical K-means algorithm with automatic feature weighting mechanism to cluster these reads represented by topic distributions., Conclusions: Experiments show that the new method TM-MCluster outperforms major existing methods, including AbundanceBin, MetaCluster 3.0/5.0 and MCluster. This result indicates that the exploitation of topic modeling can effectively improve the binning performance of metagenomic reads.

Background: Protein function prediction is an important problem in the post-genomic era. Recent advances in experimental biology have enabled the production of vast amounts of protein-protein interaction (PPI) data. Thus, using PPI data to functionally annotate proteins has been extensively studied. However, most existing network-based approaches do not work well when annotation and interaction information is inadequate in the networks., Results: In this paper, we proposed a new method that combines PPI information and protein sequence information to boost the prediction performance based on collective classification. Our method divides function prediction into two phases: First, the original PPI network is enriched by adding a number of edges that are inferred from protein sequence information. We call the added edges implicit edges, and the existing ones explicit edges correspondingly. Second, a collective classification algorithm is employed on the new network to predict protein function., Conclusions: We conducted extensive experiments on two real, publicly available PPI datasets. Compared to four existing protein function prediction approaches, our method performs better in many situations, which shows that adding implicit edges can indeed improve the prediction performance. Furthermore, the experimental results also indicate that our method is significantly better than the compared approaches in sparsely-labeled networks, and it is robust to the change of the proportion of annotated proteins.

Background: Since the initial annotation of microRNAs (miRNAs) in 2001, many studies have sought to identify additional miRNAs experimentally or computationally in various species. MiRNAs act with the Argonaut family of proteins to regulate target messenger RNAs (mRNAs) post-transcriptionally. Currently, researches mainly focus on single miRNA function study. Considering that members in the same miRNA family might participate in the same pathway or regulate the same target(s) and thus share similar biological functions, people can explore useful knowledge from high quality miRNA family architecture., Results: In this article, we developed an unsupervised clustering-based method miRCluster to automatically group miRNAs. In order to evaluate this method, several data sets were constructed from the online database miRBase. Results showed that miRCluster can efficiently arrange miRNAs (e.g identify 354 families in miRBase16 with an accuracy of 92.08%, and can recognize 9 of all 10 newly-added families in miRBase 17). By far, ~30% mature miRNAs registered in miRBase are unclassified. With miRCluster, over 85% unclassified miRNAs can be assigned to certain families, while ~44% of these miRNAs distributed in ~300novel families., Conclusions: In short, miRCluster is an automatic and efficient miRNA family identification method, which does not require any prior knowledge. It can be helpful in real use, especially when exploring functions of novel miRNAs. All relevant materials could be freely accessed online (http://admis.fudan.edu.cn/projects/miRCluster).

Protein structure prediction is an important but far from being well-resolved problem in computational biology. It is generally regarded that the native structures of proteins correspond to minimum-energy states. Potential functions are useful in protein structure prediction. To obtain the optimal parameters of protein potential functions, we introduced several strategies to improve the basic Genetic Algorithm (GA). The improved GA was employed in statistical potential function design and protein structure prediction, and experimental results validate the effectiveness and efficiency of the proposed algorithm.

An important step in unveiling the relation between network structure and dynamics defined on networks is to detect communities, and numerous methods have been developed separately to identify community structure in different classes of networks, such as unipartite networks, bipartite networks, and directed networks. Here, we show that the finding of communities in such networks can be unified in a general framework-detection of community structure in bipartite networks. Moreover, we propose an evolutionary method for efficiently identifying communities in bipartite networks. To this end, we show that both unipartite and directed networks can be represented as bipartite networks, and their modularity is completely consistent with that for bipartite networks, the detection of modular structure on which can be reformulated as modularity maximization. To optimize the bipartite modularity, we develop a modified adaptive genetic algorithm (MAGA), which is shown to be especially efficient for community structure detection. The high efficiency of the MAGA is based on the following three improvements we make. First, we introduce a different measure for the informativeness of a locus instead of the standard deviation, which can exactly determine which loci mutate. This measure is the bias between the distribution of a locus over the current population and the uniform distribution of the locus, i.e., the Kullback-Leibler divergence between them. Second, we develop a reassignment technique for differentiating the informative state a locus has attained from the random state in the initial phase. Third, we present a modified mutation rule which by incorporating related operations can guarantee the convergence of the MAGA to the global optimum and can speed up the convergence process. Experimental results show that the MAGA outperforms existing methods in terms of modularity for both bipartite and unipartite networks.

The prediction of protein function is a difficult and important problem in computational biology. In this study, an efficient method is presented to predict protein function with sequence composition information. Four kinds of basic building blocks of protein sequences are investigated, including N-grams, binary profiles, PFAM domains and InterPro domains. The protein sequences are mapped into high-dimensional vectors by using the occurrence frequencies of each kind of building blocks. The resulting vectors are then taken as input to support vector machine to predict their function based on gene ontology. Experiments are conducted over the subset of GOA database. The experimental results show that the protein function can be predicted from primary sequence information. The method based on InterPro domains outperforms the other building blocks, and gets an overall accuracy of 0.87 and ROC score is 0.93. We also demonstrate that the use of feature extraction algorithms such as latent semantic analysis and nonnegative matrix factorization, can efficiently remove noise and improve the prediction efficiency without significantly degrading the performance. The results obtained here are helpful for the prediction of protein function by using only sequence information.

The family of Vicsek fractals is one of the most important and frequently studied regular fractal classes, and it is of considerable interest to understand the dynamical processes on this treelike fractal family. In this paper, we investigate discrete random walks on the Vicsek fractals, with the aim to obtain the exact solutions to the global mean-first-passage time (GMFPT), defined as the average of first-passage time (FPT) between two nodes over the whole family of fractals. Based on the known connections between FPTs, effective resistance, and the eigenvalues of graph Laplacian, we determine implicitly the GMFPT of the Vicsek fractals, which is corroborated by numerical results. The obtained closed-form solution shows that the GMFPT approximately grows as a power-law function with system size (number of all nodes), with the exponent lies between 1 and 2. We then provide both the upper bound and lower bound for GMFPT of general trees, and show that the leading behavior of the upper bound is the square of system size and the dominating scaling of the lower bound varies linearly with system size. We also show that the upper bound can be achieved in linear chains and the lower bound can be reached in star graphs. This study provides a comprehensive understanding of random walks on the Vicsek fractals and general treelike networks.

In general, the power-law degree distribution has profound influence on various dynamical processes defined on scale-free networks. In this paper, we will show that power-law degree distribution alone does not suffice to characterize the behavior of trapping problems on scale-free networks, which is an integral major theme of interest for random walks in the presence of an immobile perfect absorber. In order to achieve this goal, we study random walks on a family of one-parameter (denoted by q) scale-free networks with identical degree sequence for the full range of parameter q, in which a trap is located at a fixed site. We obtain analytically or numerically the mean first-passage time (MFPT) for the trapping issue. In the limit of large network order (number of nodes), for the whole class of networks, the MFPT increases asymptotically as a power-law function of network order with the exponent obviously different for different parameter q, which suggests that power-law degree distribution itself is not sufficient to characterize the scaling behavior of MFPT for random walks at least trapping problem, performed on scale-free networks.

The mining missing links and predicting upcoming links are two important topics in the link prediction. In the past decades, a variety of algorithms have been developed, the majority of which apply similarity measures to estimate the bonding probability between nodes. And for these algorithms, it is still difficult to achieve a satisfactory tradeoff among precision, computational complexity, robustness to network types, and scalability to network size. In this article, we propose a chaotic ant colony optimized (CACO) link prediction algorithm, which integrates the chaotic perturbation model and ant colony optimization. The extensive experiments on a wide variety of unweighted and weighted networks show that the proposed algorithm CACO achieves significantly higher prediction accuracy and robustness than most of the state-of-the-art algorithms. The results demonstrate that the chaotic ant colony effectively takes advantage of the fact that most real networks possess the transmission capacity and provides a new perspective for future link prediction research. [ABSTRACT FROM AUTHOR]

Community structure is a typical property of real-world networks, and has been recognized as a key to understand the dynamics of the networked systems. In most of the networks overwhelming nodes apparently live in a community while there often exists a few nodes straddling several communities. Hence, an ideal algorithm for community detection is that which can identify the overlapping communities in these networks. We present an evolutionary method for detecting overlapping community structure in the network. To represent an overlapping division of a network, we develop an encoding scheme composed of two segments, the first one represents a disjoint partition and the second one represents an extension of the partition that allows of multiple memberships. We give two measures for the informativeness of a node, and present a coevolutionary scheme between two segments over the population for solving the overlapping partition of the network. Experimental results show this method can give a better solution to a network. It is also revealed that a best overlapping partition of the network might not be rooted from a best disjoint partition. [ABSTRACT FROM AUTHOR]

The rapid development of high-throughput technologies enables researchers to sequence the whole metagenome of a microbial community sampled directly from the environment. The assignment of these sequence reads into different species or taxonomical classes is a crucial step for metagenomic analysis, which is referred to as binning of metagenomic data. Most traditional binning methods rely on known reference genomes for accurate assignment of the sequence reads, therefore cannot classify reads from unknown species without the help of close references. To overcome this drawback, unsupervised learning based approaches have been proposed, which need not any known species’ reference genome for help. In this paper, we introduce a novel unsupervised method called MCluster for binning metagenomic sequences. This method uses N-grams to extract sequence features and utilizes automatic feature weighting to improve the performance of the basic K-means clustering algorithm. We evaluate MCluster on a variety of simulated data sets and a real data set, and compare it with three latest binning methods: AbundanceBin, MetaCluster 3.0, and MetaCluster 5.0. Experimental results show that MCluster achieves obviously better overall performance (F-measure) than AbundanceBin and MetaCluster 3.0 on long metagenomic reads (\ge800 bp); while compared with MetaCluster 5.0, MCluster obtains a larger sensitivity, and a comparable yet more stable F-measure on short metagenomic reads (<300 bp). This suggests that MCluster can serve as a promising tool for effectively binning metagenomic sequences. [ABSTRACT FROM PUBLISHER]

Abstract: In this paper, we propose an evolving Sierpinski gasket, based on which we establish a model of evolutionary Sierpinski networks (ESNs) that unifies deterministic Sierpinski network [Z.Z. Zhang, S.G. Zhou, T. Zou, L.C. Chen, J.H. Guan, Eur. Phys. J. B 60 (2007) 259] and random Sierpinski network [Z.Z. Zhang, S.G. Zhou, Z. Su, T. Zou, J.H. Guan, Eur. Phys. J. B 65 (2008) 141] to the same framework. We suggest an iterative algorithm generating the ESNs. On the basis of the algorithm, some relevant properties of presented networks are calculated or predicted analytically. Analytical solution shows that the networks under consideration follow a power-law degree distribution, with the distribution exponent continuously tuned in a wide range. The obtained accurate expression of clustering coefficient, together with the prediction of average path length reveals that the ESNs possess small-world effect. All our theoretical results are successfully contrasted by numerical simulations. Moreover, the evolutionary prisoner’s dilemma game is also studied on some limitations of the ESNs, i.e., deterministic Sierpinski network and random Sierpinski network. [Copyright &y& Elsevier]

Abstract: Recently, histograms have been considered as an effective way to produce quick approximate answers to decision support queries. They are also taken as a basic tool for data visualization and analysis. In this paper, we propose a new approach to constructing histograms for selectivity estimation in query processing optimization. Our approach uses a new criterion, i.e., aggregate error minimization, to direct the construction of the target histogram. We develop the algorithm of aggregate error minimization based histogram construction, and demonstrate the effectiveness and efficiency of the proposed approach by experiments over both real-world and synthetic datasets. [Copyright &y& Elsevier]

Abstract: The frequent closed itemsets determine exactly the complete set of frequent itemsets and are usually much smaller than the later. However, mining frequent closed itemsets from a landmark window over data streams is a challenging problem. To solve the problem, this paper presents a novel algorithm (called FP-CDS) that can capture all frequent closed itemsets and a new storage structure (called FP-CDS tree) that can be dynamically adjusted to reflect the evolution of itemsets’ frequencies over time. A landmark window is divided into several basic windows and these basic windows are used as updating units. Potential frequent closed itemsets in each basic window are mined and stored in FP-CDS tree based on some proposed strategies. Extensive experiments are conducted to validate the proposed method. [Copyright &y& Elsevier]

Abstract: We propose a deterministic weighted scale-free small-world model for considering pseudofractal web with the co-evolution of topology and weight. Considering the fluctuations in traffic flow constitute a main reason for congestion of packet delivery and poor performance of communication networks, we suggest a recursive algorithm to generate the network, which restricts the traffic fluctuations on it effectively during the evolutionary process. We provide a relatively complete view of topological structure and weight dynamics characteristics of the networks such as weight and strength distribution, degree correlations, average clustering coefficient and degree-cluster correlations as well as the diameter. [Copyright &y& Elsevier]