KNN is one of the most popular data mining methods for classification, but it often fails to work well with inappropriate choice of distance metric or due to the presence of numerous class-irrelevant features. Linear feature transformation methods have been widely applied to extract class-relevant information to improve kNN classification, which is very limited in many applications. Kernels have also been used to learn powerful non-linear feature transformations, but these methods fail to scale to large datasets. In this paper, we present a scalable non-linear feature mapping method based on a deep neural network pretrained with Restricted Boltzmann Machines for improving kNN classification in a large-margin framework, which we call DNet-kNN. DNet-kNN can be used for both classification and for supervised dimensionality reduction. The experimental results on two benchmark handwritten digit datasets and one newsgroup text dataset show that DNet-kNN has much better performance than large-margin kNN using a linear mapping and kNN based on a deep autoencoder pretrained with Restricted Boltzmann Machines.

Random-walk based algorithms are good choices for solving many classification problems with limited labeled data and a large amount of unlabeled data. However, it is difficult to choose the optimal number of random steps, and the results are very sensitive to the parameter chosen. In this paper, we will discuss how to better identify protein remote homology than any other algorithm using a learned random-walk kernel based on a positive linear combination of random-walk kernels with different random steps, which leads to a convex combination of kernels. The resulting kernel has much better prediction performance than the state-of-the-art profile kernel for protein remote homology identification. On the SCOP benchmark dataset, the overall mean ROC50 score on 54 protein families we obtained using the new kernel is above 0.90, which has almost perfect prediction performance on most of the 54 families and has significant improvement over the best published result; moreover, our approach based on learned random-walk kernels can effectively identify meaningful protein sequence motifs that are responsible for discriminating the memberships of protein sequences' remote homology in SCOP.

Kernel learning methods based on kernel alignment with semidefinite programming (SDP) are often memory intensive and computationally expensive, thus often impractical for problems with large-size dataset. We propose a method using label information to modify kernels based on SVD and a linear mapping. As a result, the new kernel matrix reflects the label-dependent separability of the data in a better way than the original kernel matrix. In addition, our experimental results on USPS handwritten digits and the SCOP dataset, show that the SVM classifier based on the improved kernels has better performance than the SVM classifier based on the original kernels; moreover, SVM based on the improved profile kernel with pull-in homologs (see experiment section for explanations) produced the best results for remote homology detection on the SCOP dataset compared to the published results.

BACKGROUND: Arabidopsis thaliana is the model species of current plant genomic research with a genome size of 125 Mb and approximately 28,000 genes. The function of half of these genes is currently unknown. The purpose of this study is to infer gene function in Arabidopsis using machine-learning algorithms applied to large-scale gene expression data sets, with the goal of identifying genes that are potentially involved in plant response to abiotic stress. RESULTS: Using in house and publicly available data, we assembled a large set of gene expression measurements for A. thaliana. Using those genes of known function, we first evaluated and compared the ability of basic machine-learning algorithms to predict which genes respond to stress. Predictive accuracy was measured using ROC50 and precision curves derived through cross validation. To improve accuracy, we developed a method for combining these classifiers using a weighted-voting scheme. The combined classifier was then trained on genes of known function and applied to genes of unknown function, identifying genes that potentially respond to stress. Visual evidence corroborating the predictions was obtained using electronic Northern analysis. Three of the predicted genes were chosen for biological validation. Gene knockout experiments confirmed that all three are involved in a variety of stress responses. The biological analysis of one of these genes (At1g16850) is presented here, where it is shown to be necessary for the normal response to temperature and NaCl. CONCLUSION: Supervised learning methods applied to large-scale gene expression measurements can be used to predict gene function. However, the ability of basic learning methods to predict stress response varies widely and depends heavily on how much dimensionality reduction is used. Our method of combining classifiers can improve the accuracy of such predictions - in this case, predictions of genes involved in stress response in plants - and it effectively chooses the appropriate amount of dimensionality reduction automatically. The method provides a useful means of identifying genes in A. thaliana that potentially respond to stress, and we expect it would be useful in other organisms and for other gene functions.

This paper addresses a central problem of Proteomics: estimating the amounts of each of the thousands of proteins in a cell culture or tissue sample. Although laboratory methods involving isotopes have been developed for this problem, we seek a method that uses simpler laboratory procedures. Specifically, our aim is to use data-mining techniques to infer protein levels from the relatively cheap and abundant data available from high-throughput tandem mass spectrometry (MS/MS). We have developed and evaluated several techniques for tackling this problem, including the development of three generative models of MS/MS data, and methods for efficiently fitting the models to data. In addition, we tested each method on three real-world datasets generated by MS/MS experiments performed on various tissue samples taken from Mouse. This paper outlines the biological problem and presents a selection of our results.

Proteomics - the direct analysis of the expressed protein components of a cell - is critical to our understanding of cellular biological processes. Key insights into the action and effects of a disease can be obtained by comparison of the expression of the expressed proteins in normal versus diseased tissue. Tandem mass spectrometry (MS/MS) of peptides is a central technology for Proteomics, enabling the identification of thousands of peptides from a complex mixture. With the increasing acquisition rate of tandem mass spectrometers, there is an increasing potential to solve important biological problems by applying data-mining and machine-learning techniques to MS/MS data. These problems include (i) estimating the levels of the thousands of proteins in a tissue sample, (ii) predicting the intensity of the peaks in a mass spectrum, and (iii) explaining why different peptides from the same protein have different peak intensities. In other works, we have focussed on the first two problems. In this paper, we focus on the last problem. In particular, we try to explain why some peptides produce peaks of great intensity, while others produce peaks of low intensity, and we treat this as a classification problem. That is, we experimentally evaluate and compare a variety of discrimination methods for classifying peptides into those that produce high-intensity peaks and those that produce low-intensity peaks. The methods considered include K-nearest neighbours (KNN), logistic regression, linear discriminant analysis (LDA), quadratic discriminant analysis (QDA), Naive Bayes, and hidden Markov models (HMMs). Experiments using these methods were conducted on three real-world datasets derived from tissue samples of Mouse. The methods were then evaluated using ROC curves and cross validation.

MOTIVATION: The methods for analyzing overlap data are distinct from those for analyzing probe data, making integration of the two forms awkward. Conversion of overlap data to probe-like data elements would facilitate comparison and uniform integration of overlap data and probe data using software developed for analysis of STS data. RESULTS: We show that overlap data can be effectively converted to probe-like data elements by extracting maximal sets of mutually overlapping clones. We call these sets virtual probes, since each set determines a site in the genome corresponding to the region which is common among the clones of the set. Finding the virtual probes is equivalent to finding the maximal cliques of a graph. We modify a known maximal-clique algorithm such that it finds all virtual probes in a large dataset within minutes. We illustrate the algorithm by converting fingerprint and Alu-PCR overlap data to virtual probes. The virtual probes are then analyzed using double-linkage intersection graphs and structure graphs to show that methods designed for STS data are also applicable to overlap data represented as virtual probes. Next we show that virtual probes can produce a uniform integration of different kinds of mapping data, in particular STS probe data and fingerprint and Alu-PCR overlap data. The integrated virtual probes produce longer double-linkage contigs than STS probes alone, and in conjunction with structure graphs they facilitate the identification and elimination of anomalies. Thus, the virtual-probe technique provides: (i) a new way to examine overlap data; (ii) a basis on which to compare overlap data and probe data using the same systems and standards; and (iii) a unique and useful way to uniformly integrate overlap data with probe data.

This paper develops a query language for sequence databases, such as genome databases and text databases. Unlike relational data, queries over sequential data can easily produce infinite answer sets since the universe of sequences is infinite, even for a finite alphabet. The challenge is to develop query languages that are both highly expressive and finite. This paper develops such a language as a subset of a logic for string databases called Sequence Datalog. The main idea is to use safe recursion to control and limit unsafe recursion. The main results are the definition of a finite form of recursion, called domain-bounded recursion, and a characterization of its complexity and expressive power. Although finite, the resulting class of programs is highly expressive since its data complexity is complete for the elementary functions.

Transaction Datalog (abbreviated TV) is a concurrent programming language that provides process modeling, database access, and advanced transactions.This paper illustrates the use of TV for specifying and simulating workflows, with examples based on the needs of a highthroughpnt genome laboratory.In addition to traditional database support, these needs include synchronization of work, cooperation between concurrent workflows, and nonserializable access to shared resources.After illustrating workflows, we use 7-1~ to explore their computational complexity in data-intensive applications.We show, for instance, that workflows can be vastly more complex than traditional database transactions, largely because concurrent processes can interact and communicate via the database (i.e., one process can read what another process writes).We then investigate the s,ources of this complexity, focusing on features for data modeling and process modeling.We show that by carefully controlling these features, the complexity of workflows can be reduced substantially.Finally, we develop a sub-language called fully bounded 'TV that provides a practical blend of modeling features while minimizing complexity.

MOTIVATION: STS-content data for genomic mapping contain numerous errors and anomalies resulting in cross-links among distant regions of the genome. Identification of contigs within the data is an important and difficult problem. RESULTS: This paper introduces a graph algorithm which creates a simplified view of STS-content data. The shape of the resulting structure graph provides a quality check - coherent data produce a straight line, while anomalous data produce branches and loops. In the latter case, it is sometimes possible to disentangle the various paths into subsets of the data covering contiguous regions of the genome, i.e. contigs. These straight subgraphs can then be analyzed in standard ways to construct a physical map. A theoretical basis for the method is presented along with examples of its application to current STS data from human genome centers. AVAILABILITY: Freely available on request.

This paper develops a query language for sequence databases, such as genome databases and text databases. The language, called Sequence Dataiog, extends classical Datalog with interpreted function symbols for manipulating sequences. It has both a clear operational and declarative semantics, based on a new notion called the extended active domain of a database. The extended domain contains all the sequences in the database and all their subsequences. This idea leads to a clear distinction between safe and unsafe recursion over sequences: safe recursion stays inside the extended active domain, while unsafe recursion does not. By carefully limiting the amount of unsafe recursion, the paper develops a safe and expressive subset of Sequence Datalog. As part of the development, a new type of transducer is introduced, called a generalizect sequence transducer. Unsafe recursion is allowed only within these generalized transducers. Generalized transducers extend ordinary transducers by allowing them to invoke other transducers as “subroutines.” Generalized transducers can be implemented in Sequence Datalog in a straightforward way. Moreover, their introduction into the language leads to simple conditions that guarantee safety and finiteness. This paper develops two such conditions, The first condition expresses exactly the class of PTIME sequence functions; and the second expresses exactly the class of elementary sequence functions.

This paper develops a method for reusing and modifying deductive databases. Such methods are needed when new rulebased applications differ only slightly from existing ones or when an application is to be incrementally updated. In order to facilitate reuse, we extend deductive databases by the concept of predicate substitution. In this way, during query evaluation, not only variables, but also predicates can be substituted. This paper continues our earlier work on predicate substitution in two directions: (i We extend the concept to a wider class of rulebase modifications, and (ii) we estblish tight bounds on the data complexity of Datalog augmented with substitution, showing it to be EXPTIME-complete. Predicate substitution thus increases the power of Datalog to express database queries. The paper presents a proof theory and model theory for the language, including a fixpoint semantics.

Object-oriented databases have been introduced primarily to ease the development of database applications.However, the difficulties encountered when, for instance, trying to restructure data or integrate databases demonstrate

This paper examines an extension of Horn logic in which rules can add entries to a database hypothetically. Several researchers have developed logical systems along these lines, but the complexity and expressibility of such logics is only now being explored. It has been shown, for instance, that the data-complexity of these logics is PSPACE-complete in the function-free, predicate case. This paper extends this line of research by developing syntactic restrictions with lower complexity. These restrictions are based on two ideas from Horn-clause logic: linear recursion and stratified negation. In particular, a notion of stratification is developed in which negation-as-failure alternates with linear recursion. The complexity of such rulebases depends on the number of layers of stratification. The result is a hierarchy of syntactic classes which corresponds exactly in the polynomial-time hierarchy of complexity classes. In particular, rulebases with k strata are data-complete for ΣPh. Furthermore, these rulebases provide a complete characterization of the relational queries in ΣPh. That is, any query whose graph is in ΣPh can be represented as a set of hypothetical rules with k strata. Unlike other expressibility results in the literature, this result does not require the data domain to be linearly ordered.