title: Prediction of Protein-Protein Interaction via co-occurring Aligned Pattern Clusters.
abstract: Predicting Protein-Protein Interaction (PPI) is important for making new discoveries in the molecular mechanisms inside a cell. Traditionally, new PPIs are identified through biochemical experiments but such methods are labor-intensive, expensive, time-consuming and technically ineffective due to high false positive rates. Sequence-based prediction is currently the most readily applicable and cost-effective method. It exploits known PPI Databases to construct classifiers for predicting unknown PPIs based only on sequence data without requiring any other prior knowledge. Among existing sequence-based methods, most feature-based methods use exact sequence patterns with fixed length as features - a constraint which is biologically unrealistic. SVM with Pairwise String Kernel renders better predicting performance. However it is difficult to be biologically interpretable since it is kernel-based where no concrete feature values are computed. Here we have developed a novel method WeMine-P2P to overcome these drawbacks. By assuming that the regions/sites that mediate PPI are more conserved, WeMine-P2P first discovers/locates the conserved sequence patterns in protein sequences in the form of Aligned Pattern Clusters (APCs), allowing pattern variations with variable length. It then pairs up all APCs into a set of Co-Occurring APC (cAPC) pairs, and computes a cAPC-PPI score for each cAPC pair on all PPI pairs. It further constructs a feature vector composed of all cAPC pairs with their cAPC-PPI scores for each PPI pair and uses them for constructing a PPI predictor. Through 40 independent experiments, we showed that (1) WeMine-P2P outperforms the well-known algorithm, PIPE2, which also utilizes co-occurring amino acid sequence segments but does not allow variable lengths and pattern variations; (2) WeMine-P2P achieves satisfactory PPI prediction performance, comparable to the SVM-based methods particularly among unseen protein sequences with a potential reduction of feature dimension of 1280×; (3) Unlike SVM-based methods, WeMine-P2P renders interpretable biological features from which we observed that co-occurring sequence patterns from the compositional bias regions are more discriminative. WeMine-P2P is extendable to predict other biosequence interactions such as Protein-DNA interactions.
authors.affiliation: Systems Design Engineering, University of Waterloo, Waterloo, Canada. Electronic address: hy2szeto@uwaterloo.ca.
authors.forename: Antonio
authors.initials: A
authors.lastname: Sze-To
authors.affiliation: Systems Design Engineering, University of Waterloo, Waterloo, Canada. Electronic address: s3fung@uwaterloo.ca.
authors.forename: Sanderz
authors.initials: S
authors.lastname: Fung
authors.affiliation: Systems Design Engineering, University of Waterloo, Waterloo, Canada. Electronic address: annie.lee@uwaterloo.ca.
authors.forename: En-Shiun Annie
authors.initials: EA
authors.lastname: Lee
authors.affiliation: Systems Design Engineering, University of Waterloo, Waterloo, Canada. Electronic address: akcwong@uwaterloo.ca.
authors.forename: Andrew K C
authors.initials: AKC
authors.lastname: Wong
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence / Q000235:genetics; D019295:Computational Biology / Q000379:methods*; D025941:Protein Interaction Mapping / Q000379:methods*; D060066:Protein Interaction Maps / Q000235:genetics*; D020539:Sequence Analysis, Protein / Q000379:methods*
keywords: Co-occurring Aligned Pattern Cluster; Protein–Protein Interaction; Random Forest; Supervised learning