title: Graph-based clustering for finding distant relationships in a large set of protein sequences.
abstract: BACKGROUND
  Clustering of protein sequences is widely used for the functional characterization of proteins. However, it is still not easy to cluster distantly-related proteins, which have only regional similarity among their sequences. It is therefore necessary to develop an algorithm for clustering such distantly-related proteins.
  
  
  RESULTS
  We have developed a time and space efficient clustering algorithm. It uses a graph representation where its vertices and edges denote proteins and their sequence similarities above a certain cutoff score, respectively. It repeatedly partitions the graph by removing edges that have small weights, which correspond to low sequence similarities. To find the appropriate partitions, we introduce a score combining the normalized cut and a locally minimal cut capacities. Our method is applied to the entire 40,703 human proteins in SWISS-PROT and TrEMBL. The resulting clusters shows a 76% recall (20,529 proteins) of the 26,917 classified by InterPro. It also finds relationships not found by other clustering methods.
  
  
  BACKGROUND
  The complete result of our algorithm for all the human proteins in SWISS-PROT and TrEMBL, and other supplementary information are available at http://motif.ics.es.osaka-u.ac.jp/Ncut-KL/
authors.affiliation: Department of Bioinformatic Engineering, Graduate School of Information Science and Technology, Osaka University, 1-3 Machikaneyama, Toyonaka, Osaka 560-8531, Japan.
authors.forename: Hideya
authors.initials: H
authors.lastname: Kawaji
authors.forename: Yoichi
authors.initials: Y
authors.lastname: Takenaka
authors.forename: Hideo
authors.initials: H
authors.lastname: Matsuda
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D016000:Cluster Analysis; D030562:Databases, Protein; D000089622:Doublecortin Domain Proteins; D008040:Genetic Linkage / Q000235:genetics; D008869:Microtubule-Associated Proteins; D008969:Molecular Sequence Data; D009479:Neuropeptides / Q000737:chemistry / Q000235:genetics; D011494:Protein Kinases / Q000737:chemistry / Q000235:genetics; D011506:Proteins / Q000737:chemistry* / Q000145:classification* / Q000235:genetics; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D017386:Sequence Homology, Amino Acid
chemical_list: D000089622:Doublecortin Domain Proteins; D008869:Microtubule-Associated Proteins; D009479:Neuropeptides; D011506:Proteins; D011494:Protein Kinases