ITR: Machine learning approaches to protein sequence comparison: discriminative, semi-supervised, scalable algorithms

Columbia University, New York NY

Investigators

Abstract

PI: Christina Leslie Co-PI: William Stafford Noble Collaborator: Jason Weston Collaborator: Andre Elisseeff ITR: Machine learning approaches to protein sequence comparison: discriminative, semi-supervised, scalable algorithms Research Goals. Pairwise sequence comparison is the ``killer app'' of bioinformatics. In this task, the user queries a protein database with a single sequence, and the algorithm returns a ranked list of sequences that are likely to be evolutionarily related to the query. Two sequences that are descended from a common ancestral sequence - even though their sequence similarity may be subtle -- are likely to have similar three-dimensional structures and fill similar functional roles in the cell. Hence, recognizing subtle sequence similarities is useful for inferring protein evolution, function and structure. Almost all existing algorithms for pairwise sequence comparison fall into one of two categories: heuristic alignment algorithms that are scalable to large databases but can fail to capture subtle protein similarities; and approaches based on protein family models, which are accurate for determining whether a sequence fits a particular family model but cannot evaluate similarity between two unannotated proteins. The popular PSI-BLAST algorithm is a hybrid of the two approaches: it tries to iteratively build a model from a single query sequence on the fly and then searches the database for sequences that fit the model. While efficient, PSI-BLAST is known not to be the most accurate method for detecting more remote protein relationships. The approach that we pursue in this proposal is fundamentally new: we use machine learning algorithms to train offline on examples from the full space of proteins, both those with family annotations and unannotated sequences, so that at run-time, our trained model can accurately predict which database sequences are related to the query. In other words, we want to introduce learning into the general sequence comparison problem, without resorting to a more limited family-based model approach. One primary goal of this research is the development of algorithms that exploit the additional or hidden structure of the problem. To this end, we experiment with a number of learning algorithms, including constrained clustering, neighborhood averaging, use of hierarchical labels and ensembles of classifiers, techniques for dimensionality reduction like non-negative matrix factorization, and kernel-based semi-supervised approaches. In addition to algorithm development, we plan to produce a software implementation and web interface that will make our techniques available to the biological community. Throughout our research, we will emphasize techniques that are scalable. We want the actual prediction time to be fast, so that a user can enter a new query sequence and retrieve a ranked list of related sequences from the database in real time via a web interface. Thus we focus on two features: training offline, which allows us to take advantage of more expensive computation in the training process so that the predictions can be fast; and use of fast string kernels, a technique from our work on protein classification that will enable run-time speed-up. Broader Impacts. Pairwise sequence comparison is a central problem in bioinformatics and genomics, and our techniques for improving performance and scalability of protein sequence comparison through state-of-the-art machine learning techniques will be broadly useful to biologists and bioinformaticians. The software implementation and web interface that we will produce as part of our proposal will make our techniques available to the biological community. All specifications, datasets, and results from our research will be made publicly available via our web site. All new algorithms will also be described in publications for dissemination to the machine learning community. Finally, we note that the learning challenges of our sequence comparison problem -- for example, learning in a setting with a large amount of unlabelled data and only a small amount of labelled data -- occur in many other applied areas of machine learning, such as text classification and information retrieval. Thus our research will have impact in many applied learning and data-driven fields.