Clustering protein sequences-structure prediction by transitive homology

Motivation: It is widely believed that for two proteins A and B a sequence identity above some threshold implies structural similarity due to a common evolutionary ancestor. Since this is only a sufficient, but not a necessar y condition for structural similarity, the question remains what other crit eria can be used to identify remote homologues. Transitivity refers to the concept of deducing a structural similarity betw een proteins A and C from the existence of a third protein B, such that A a nd B as well as B and C are homologues, as ascertained if the sequence iden tity between A and B as well as that between B and C is above the aforement ioned threshold. It is not fully understood if transitivity always holds an d 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 seq uences in the SwissProt database using the Smith-Waterman local alignment a lgorithm. This data was transformed into a directed graph, where protein se quences constitute vertices. A directed edge was drawn from vertex A to ver tex B if the sequences A and B showed 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 tho ugh by the requirement of having directed paths in both directions between proteins linked over such sequences. The length dependency-implied by the s elf-similarity-of the scaling of the alignment scores appears to be an effe ctive criterion to avoid clustering errors due to multi-domain proteins. To deal with the resulting large graphs we have developed an efficient libr ary. Methods include the novel graph-based clustering algorithm capable of handling multi-domain proteins and cluster comparison algorithms. Structura l 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.