Clustering protein sequences—structure prediction by transitive homology

Open Access
Publisher Website
Google Scholar
Abstract
Motivation: It is widely believed that for two proteins Aand Ba sequence identity above some threshold implies structural similarity due to a common evolutionary ancestor. Since this is only a sufficient, but not a necessary condition for structural similarity, the question remains what other criteria can be used to identify remote homologues. Transitivity refers to the concept of deducing a structural similarity between proteins Aand Cfrom the existence of a third protein B, such that Aand Bas well as Band Care homologues, as ascertained if the sequence identity between Aand Bas well as that between Band Cis above the aforementioned threshold. It is not fully understood if transitivity always holds and whether transitivity can be extended ad infinitum. Results: We developed a graph-based clustering approach, where transitivity plays a crucial role. We determined all pair-wise similarities for the sequences in the SwissProt database using the Smith–Waterman local alignment algorithm. This data was transformed into a directed graph, where protein sequences constitute vertices. A directed edge was drawn from vertex Ato vertex Bif the sequences Aand Bshowed similarity, scaled with respect to the self-similarity of A, above a fixed threshold. Transitivity was important in the clustering process, as intermediate sequences were used, limited though by the requirement of having directed paths in both directions between proteins linked over such sequences. The length dependency—implied by the self-similarity—of the scaling of the alignment scores appears to be an effective criterion to avoid clustering errors due to multi-domain proteins. To deal with the resulting large graphs we have developedan efficient library. Methods include the novel graph-based clustering algorithm capable of handling multi-domain proteins and cluster comparison algorithms. Structural Classification of Proteins (SCOP) was used as an evaluation data set for our method, yielding a 24% improvement over pair-wise comparisons in terms of detecting remote homologues. Availability: The software is available to academic users on request from the authors. Contact: e.bolten@science-factory.com; schliep@zpr.uni-koeln.de; s.schneckener@science-factory.com; d.schomburg@uni-koeln.de; schrader@zpr.uni-koeln.de Supplementary information: http://www.zaik.uni-koeln.de/~schliep/ProtClust.html

This publication has 4 references indexed in Scilit: