Pipenbacher, Peter, Schliep, Alexander, Schneckener, Sebastian, Schönhuth, Alexander, Schomburg, Dietmar and Schrader, Rainer (2002). ProClust: Improved clustering of protein sequences with an extended graph-based approach. Bioinformatics, 18 (Sup. 2). S182-S191. Oxford University Press.

[img]
Preview
PDF
zaik2002-430.pdf - Submitted Version

Download (136kB) | Preview

Abstract

The problem of finding remote homologues of a given protein sequence via alignment methods is not fully solved. In fact, the task seems to become more difficult with more data. As the size of the database increases, so does the noise level; the highest alignment scores due to random similarities increase and can be higher than the alignment score between true homologues. Comparing two sequences with an arbitrary alignment method yields a similarity value which may indicate an evolutionary relationship between them. A threshold value is usually chosen to distinguish between true homologue relationships and random similarities. To compensate for the higher probability of spurious hits in larger databases, this threshold is increased. Increasing specificity however leads to decreased sensitivity as a matter of principle. Sensitivity can be recovered by utilizing refined protocols. A number of approaches to this challenge have made use of the fact that proteins are often members of some larger protein family. This can be exploited by using position-specific substitution matrices or profiles, or by making use of {em transitivity} of homology. Transitivity refers to the concept of concluding homology between proteins A and C based on homology between A and a third protein B and between B and C . It has been demonstrated that transitivity can lead to substantial improvement in recognition of remote homologues particularly in cases where the alignment score of A and C is below the noise level. A natural limit to the use of transitivity is imposed by domains. Domains, compact independent sub-units of proteins, are often shared between otherwise distinct proteins, and can cause substantial problems by incorrectly linking otherwise unrelated proteins. We extend a graph-based clustering algorithm which uses an asymmetric distance measure, scaling similarity values based on the length of the protein sequences compared. Additionally, the significance of alignment scores is taken into account and used for a filtering step in the algorithm. Post-processing, to merge further clusters based on profile HMMs is proposed. SCOP sequences and their super-family level classification are used as a test set for a clustering computed with our method for the joint data set containing both SCOP and SWISS-PROT. Note, the joint data set includes all multi-domain proteins, which contain the SCOP domains that are a potential source of incorrect links. Our method compares at high specificities very favorably with PSI-Blast, which is probably the most widely-used tool for finding remote homologues. We demonstrate that using transitivity with as many as twelve intermediate sequences is crucial to achieving this level of performance. Moreover, from analysis of false positives we conclude that our method seems to correctly bound the degree of transitivity used. This analysis also yields {em explicit} guidance in choosing parameters. The heuristics of the asymmetric distance measure used neither solve the multi-domain problem from a theoretical point of view, nor do they avoid all types of problems we have observed in real data. Nevertheless, they do provide a substantial improvement over existing approaches.

Item Type: Journal Article
Creators:
CreatorsEmailORCIDORCID Put Code
Pipenbacher, PeterUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Schliep, AlexanderUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Schneckener, SebastianUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Schönhuth, AlexanderUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Schomburg, DietmarUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Schrader, RainerUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
URN: urn:nbn:de:hbz:38-548621
Journal or Publication Title: Bioinformatics
Volume: 18
Number: Sup. 2
Page Range: S182-S191
Date: 2002
Publisher: Oxford University Press
Language: English
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: Data processing Computer science
Refereed: No
URI: http://kups.ub.uni-koeln.de/id/eprint/54862

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item