TL;DR
This paper introduces a novel data-mining approach combining inductive logic programming (ILP) and rule learning to predict protein functional classes directly from sequence. The method successfully identifies biologically interpretable rules that can predict functions for previously unassigned genes in M. tuberculosis and E. coli, even in the absence of detectable sequence homology, offering insights into evolutionary history.
What Problem Does This Paper Address?
The rapid generation of genomic data has outpaced our ability to assign functions to the vast number of predicted genes. While sequence homology is a standard method for inferring function, it often fails when homology is remote or absent. This leaves a significant portion of genes with "unknown" or "hypothetical" functions, hindering our understanding of cellular processes. The paper addresses this gap by developing a data-mining approach to predict protein function directly from sequence features, aiming to automate functional annotation and uncover deeper biological relationships.
Methods
The authors propose a hybrid data-mining methodology that leverages both inductive logic programming (ILP) and propositional rule learning. The process involves:
- Sequence Description Generation: For each Open Reading Frame (ORF), a comprehensive set of descriptors is computed based solely on its sequence. These include amino acid composition, sequence similarity search results (PSI-BLAST), protein keywords from SWISS-PROT, molecular weight, phylogenetic information, and predicted secondary structure. This descriptor set is more general than a typical "phylogenic profile."
- ILP Clustering: Inductive Logic Programming (ILP) is used with the WARMR program to identify frequent patterns within the sequence descriptors. This step aims to improve the representation of the data by clustering similar ORFs based on these patterns.
- Propositional Rule Learning: The frequent patterns identified by ILP are converted into Boolean indicator attributes. Then, a propositional rule learning algorithm (C4.5/C5 decision trees) is employed to learn rules that map these attributes to protein functional classes.
- Rule Selection and Validation: Rules are selected based on their performance on a validation set, balancing accuracy with the coverage of unassigned genes.
- Prediction: The selected rules are then applied to predict the functional classes of ORFs that were not initially assigned a function.
This approach is novel in its combination of ILP for feature representation enhancement and propositional rule learning for direct functional prediction, aiming for more interpretable and generalizable rules.
Datasets
The study utilizes the publicly available genome sequences and functional assignments for two model organisms:
- Escherichia coli: 4289 ORFs from the GenProtEC database.
- Mycobacterium tuberculosis: 3924 ORFs from the Sanger Centre's TB_gene_list.
The functional assignments are organized into hierarchical trees, which the authors use as the target for their prediction task. No new benchmark datasets were introduced; rather, existing annotated genomes were used.
Key Insights and Ideas
- Beyond Homology: The most striking insight is the ability to predict protein function even in the absence of detectable sequence or structural homology. This suggests that functional relationships can be inferred from broader sequence characteristics and evolutionary patterns.
- Interpretable Rules: The data-mining approach yields biologically interpretable rules, offering insights into the underlying reasons for functional assignments. These rules can reveal patterns related to remote homology, convergent evolution, and horizontal gene transfer.
- Evolutionary Clues: The learned rules provide a window into the evolutionary history of these organisms, highlighting how functional relationships might have been shaped by gene duplication, convergent evolution, or gene transfer events.
- Hierarchical Prediction: The method successfully predicts functions at various levels of the functional hierarchy, from broad categories to more specific ones, demonstrating its versatility.
- The Power of Combined Methods: The synergy between ILP for pattern discovery and propositional rule learning for prediction proved effective, enhancing both the accuracy and coverage of functional assignments.
Key Results
- Prediction Coverage: The rules predicted functions for 65% of unassigned ORFs in M. tuberculosis and 24% in E. coli.
- Estimated Accuracy: The estimated accuracy of the learned rules ranged from 60% to 80%, depending on the level of functional assignment.
- Rule Effectiveness: The paper presents examples of rules (e.g., TB_C50_1_26, TB_C50_3_3, EC_C50_2_CSH_44) that are highly accurate on test sets and predict functions for sets of proteins that are not homologous to each other, demonstrating their generality.
- ILP's Contribution: For E. coli, using ILP descriptors increased the accuracy of learned rules and the coverage of unannotated ORFs compared to using propositional methods alone.
Limitations and Future Work
- Rule Complexity: Some of the learned rules, while accurate, are quite complicated and their biological basis is not immediately intuitive.
- Functional Hierarchy Ambiguity: The current functional hierarchies often assign only one function per gene, which can lead to "errors of commission" when a gene has multiple roles.
- Organism-Specific Rules: The rules presented are organism-specific. The authors suggest that as functional hierarchies become more standardized and annotated across more species, it will be possible to derive pan-specific rules.
- Time-Dependency: The rules are noted as being time-dependent; as more sequences become available, the validity of certain rules might change.
- Future Directions: The authors express a desire to develop automatic methods for testing their rules and hope that future work will refine the background knowledge used to describe sequences, potentially leading to simpler explanatory rules. They also emphasize the need for explicit semantics in functional genomics and the potential for integrating their approach with other data mining techniques (e.g., expression profiles, pathway analysis) for more powerful predictions.
Summary updated