GeneRAGE: a robust algorithm for sequence clustering and domain detection.
BACKGROUND
Efficient, accurate and automatic clustering of large protein sequence datasets, such as complete proteomes, into families, according to sequence similarity. Detection and correction of false positive and negative relationships with subsequent detection and resolution of multi-domain proteins.


RESULTS
A new algorithm for the automatic clustering of protein sequence datasets has been developed. This algorithm represents all similarity relationships within the dataset in a binary matrix. Removal of false positives is achieved through subsequent symmetrification of the matrix using a Smith-Waterman dynamic programming alignment algorithm. Detection of multi-domain protein families and further false positive relationships within the symmetrical matrix is achieved through iterative processing of matrix elements with successive rounds of Smith-Waterman dynamic programming alignments. Recursive single-linkage clustering of the corrected matrix allows efficient and accurate family representation for each protein in the dataset. Initial clusters containing multi-domain families, are split into their constituent clusters using the information obtained by the multi-domain detection step. This algorithm can hence quickly and accurately cluster large protein datasets into families. Problems due to the presence of multi-domain proteins are minimized, allowing more precise clustering information to be obtained automatically.


BACKGROUND
GeneRAGE (version 1.0) executable binaries for most platforms may be obtained from the authors on request. The system is available to academic users free of charge under license.
Enright
A J
AJ
Computational Genomics Group, Research Programme, The European Bioinformatics Institute, EMBL Cambridge Outstation, Cambridge CB10 1SD, UK.
Ouzounis
C A
CA
D000465:Algorithms; D000595:Amino Acid Sequence; D001426:Bacterial Proteins / Q000737:chemistry / Q000235:genetics; D016000:Cluster Analysis; D016208:Databases, Factual; D005656:Fungal Proteins / Q000737:chemistry / Q000235:genetics; D016680:Genome, Bacterial; D016681:Genome, Fungal; D017434:Protein Structure, Tertiary; D011506:Proteins / Q000737:chemistry* / Q000235:genetics*; D016415:Sequence Alignment / Q000379:methods* / Q000706:statistics & numerical data
D001426:Bacterial Proteins; D005656:Fungal Proteins; D011506:Proteins