title: Clustering-based approach for predicting motif pairs from protein interaction data.
abstract: Predicting motif pairs from a set of protein sequences based on the protein-protein interaction data is an important, but difficult computational problem. Tan et al. proposed a solution to this problem. However, the scoring function (using chi(2) testing) used in their approach is not adequate and their approach is also not scalable. It may take days to process a set of 5000 protein sequences with about 20,000 interactions. Later, Leung et al. proposed an improved scoring function and faster algorithms for solving the same problem. But, the model used in Leung et al. is complicated. The exact value of the scoring function is not easy to compute and an estimated value is used in practice. In this paper, we derive a better model to capture the significance of a given motif pair based on a clustering notion. We develop a fast heuristic algorithm to solve the problem. The algorithm is able to locate the correct motif pair in the yeast data set in about 45 minutes for 5000 protein sequences and 20,000 interactions. Moreover, we derive a lower bound result for the p-value of a motif pair in order for it to be distinguishable from random motif pairs. The lower bound result has been verified using simulated data sets.
  
  
  BACKGROUND
  http://alse.cs.hku.hk/motif_pair.
authors.affiliation: Department of Computer Science, The University of Hong Kong, Pokfulam Road, Hong Kong, China. cmleung2@cs.hku.hk
authors.forename: Henry Chi-Ming
authors.initials: HC
authors.lastname: Leung
authors.forename: Man-Hung
authors.initials: MH
authors.lastname: Siu
authors.forename: Siu-Ming
authors.initials: SM
authors.lastname: Yiu
authors.forename: Francis Yuk-Lun
authors.initials: FY
authors.lastname: Chin
authors.forename: Ken Wing-Kin
authors.initials: KW
authors.lastname: Sung
mesh_terms: D000465:Algorithms; D020816:Amino Acid Motifs; D000595:Amino Acid Sequence; D001665:Binding Sites; D016000:Cluster Analysis; D008969:Molecular Sequence Data; D010363:Pattern Recognition, Automated / Q000379:methods*; D011485:Protein Binding; D025941:Protein Interaction Mapping / Q000379:methods*; D017434:Protein Structure, Tertiary; D011506:Proteins / Q000737:chemistry* / Q000378:metabolism*; D020539:Sequence Analysis, Protein / Q000379:methods*
chemical_list: D011506:Proteins