MS-kNN: protein function prediction by integrating multiple data sources

Liang Lan, Nemanja Djuric, Yuhong Guo, Slobodan VuceticBMC Bioinformatics 2013 · OpenReview

TL;DR

This paper introduces MS-kNN, a novel algorithm that improves protein function prediction by integrating data from protein sequences, protein-protein interactions, and gene expression. By combining these diverse data sources, MS-kNN significantly outperforms single-source methods, demonstrating the power of a multi-faceted approach to understanding protein roles in biological systems.

What Problem Does This Paper Address?

Determining the function of proteins is crucial for understanding biological processes, but experimental methods are slow and expensive. Computational approaches offer a cost-effective alternative, but predicting protein function accurately remains a significant challenge. Existing methods often rely on a single type of data, such as sequence similarity, which captures only one aspect of a protein's properties. This paper addresses the need for more comprehensive and accurate protein function prediction by exploring how to effectively integrate multiple, heterogeneous data sources.

Methods

The core of this work is the Multi-Source k-Nearest Neighbor (MS-kNN) algorithm. MS-kNN works by:

  1. Calculating Similarity: It computes similarity scores between a query protein and known proteins using three distinct data sources:
  2. Sequence Similarity: Based on percent identity between protein sequences.
  3. Protein-Protein Interactions (PPI): A binary score indicating whether two proteins interact.
  4. Gene Expression: Measured using Pearson correlation coefficients from microarray data.
  5. Finding Neighbors: For a given query protein, it identifies its k nearest neighbors based on these similarity measures.
  6. Predicting Function: It predicts the function of the query protein by taking a weighted average of the functions of its neighbors. The paper explores simple averaging (MS-kNN) and weighted averaging (MS-w-kNN) where weights are learned from training data.

The paper also discusses and evaluates a "lin-sim kNN" classifier, which incorporates functional relationships between Gene Ontology (GO) terms, but finds it too computationally expensive for practical use in a competition setting.

Datasets

The study utilizes data for the 2011 Critical Assessment of Function Annotation (CAFA) challenge.

  • Training Data: A dataset of 36,924 proteins with GO annotations and associated similarity scores (sequence, PPI, and microarray).
  • Test Data (CAFA Set): 48,298 proteins for which participants had to predict functions.
  • Evaluation Data: 595 proteins from the CAFA set that were experimentally annotated after the submission deadline. This set was used to evaluate the prediction accuracy.

The paper notes that for the CAFA evaluation, only a small fraction of test proteins were represented in all three data sources (10 out of 595), with many more having data from one or two sources.

Key Insights and Ideas

  • The whole is greater than the sum of its parts: Integrating multiple data sources (sequence, PPI, gene expression) significantly improves protein function prediction accuracy compared to using any single source alone. This highlights that different data types capture complementary biological information.
  • Evolutionary distance isn't always a barrier: Using training data from a wide range of organisms, including evolutionary distant ones, can lead to better prediction accuracy than using only human or mammalian data. This suggests that fundamental functional mechanisms are conserved across species.
  • Simplicity can be effective: The straightforward k-Nearest Neighbor (kNN) algorithm, when combined with multi-source integration, proved to be a powerful and efficient model, especially under time constraints.
  • Missing annotations are a challenge, not a death knell: The paper suggests that treating missing annotations as "negative" evidence (i.e., the protein doesn't have the function) can reduce accuracy. Future work should consider these as "missing labels" and explore one-class classification approaches.
  • Weighted averaging isn't always better: Surprisingly, the basic averaging MS-kNN often outperformed weighted averaging methods (MS-w-kNN, MS-CW-kNN). The authors attribute this to potential issues with the optimization problem formulation and the interpretation of zero labels.

Key Results

  • Pre-CAFA evaluation: Using only sequence similarity, MS-kNN achieved a TermAUC of 0.819 with a large training set (35,622 proteins from multiple organisms). Integrating all three sources (sequence, PPI, gene expression) further improved this to 0.848.
  • CAFA evaluation: MS-kNN outperformed baseline algorithms like Gotcha and BLAST, which relied solely on sequence similarity.
  • MF vs. BP: Improvements from multi-source integration were observed for both Molecular Function (MF) and Biological Process (BP) Gene Ontology terms.
  • Data source contribution: While sequence similarity was the strongest single predictor, PPI and microarray data provided valuable complementary information, especially when a protein lacked sufficient sequence similarity to known annotated proteins. For example, one protein ranked poorly by sequence similarity alone was significantly improved by PPI data.

Limitations and Future Work

  • Limited data representation: A significant limitation noted is that only a small fraction of CAFA test proteins were represented in all three data sources. This made it difficult to fully assess the benefit of integrating all three sources for every protein.
  • Data quality and coverage: The paper acknowledges that different data sources have varying coverage (e.g., sequence similarity covers all known proteins, while PPI and gene expression are more limited) and quality.
  • Future directions:
    • Incorporate more data sources: Include structural information, chromosomal neighborhood, disease associations, and mutation data.
  • Address missing annotations: Treat missing annotations as "missing labels" rather than negative evidence, potentially using one-class classification.
  • Mitigate sampling bias: Develop methods robust to the inherent bias in available protein and function annotations.
  • Refine integration strategies: Further explore and refine methods for learning optimal weights for integrating diverse data sources.

Summary updated

Abstract

Background Protein function determination is a key challenge in the post-genomic era. Experimental determination of protein functions is accurate, but time-consuming and resource-intensive. A cost-effective alternative is to use the known information about sequence, structure, and functional properties of genes and proteins to predict functions using statistical methods. In this paper, we describe the Multi-Source k-Nearest Neighbor (MS-k NN) algorithm for function prediction, which finds k-nearest neighbors of a query protein based on different types of similarity measures and predicts its function by weighted averaging of its neighbors' functions. Specifically, we used 3 data sources to calculate the similarity scores: sequence similarity, protein-protein interactions, and gene expressions. Results We report the results in the context of 2011 Critical Assessment of Function Annotation (CAFA). Prior to CAFA submission deadline, we evaluated our algorithm on 1,302 human test proteins that were represented in all 3 data sources. Using only the sequence similarity information, MS-k NN had term-based Area Under the Curve (AUC) accuracy of Gene Ontology (GO) molecular function predictions of 0.728 when 7,412 human training proteins were used, and 0.819 when 35,622 training proteins from multiple eukaryotic and prokaryotic organisms were used. By aggregating predictions from all three sources, the AUC was further improved to 0.848. Similar result was observed on prediction of GO biological processes. Testing on 595 proteins that were annotated after the CAFA submission deadline showed that overall MS-k NN accuracy was higher than that of baseline algorithms Gotcha and BLAST, which were based solely on sequence similarity information. Since only 10 of the 595 proteins were represented by all 3 data sources, and 66 by two data sources, the difference between 3-source and one-source MS-k NN was rather small. Conclusions Based on our results, we have several useful insights: (1) the k-nearest neighbor algorithm is an efficient and effective model for protein function prediction; (2) it is beneficial to transfer functions across a wide range of organisms; (3) it is helpful to integrate multiple sources of protein information.
BibTeX
@article{lan2013ms,
  author = {Liang Lan and Nemanja Djuric and Yuhong Guo and Slobodan Vucetic},
  title = {{MS-kNN: protein function prediction by integrating multiple data sources}},
  journal = {BMC Bioinformatics},
  year = {2013},
  url = {https://openreview.net/forum?id=3-OSJc95q36},
}
Figure