1
$\begingroup$

I need to find dissimilar proteins. Looking through the PDB I found the weekly BLASTClust results of proteins that are 30% similar. However, I do not know if protein A in cluster 1 is guaranteed to be less than 30% similar to protein B in cluster 2.

The best and only documentation I can find for BLASTClust is here (link).

It states:

The program begins with pairwise matches and places a sequence in a cluster if the sequence matches at least one sequence already in the cluster.

That's good, but consider a set of three proteins (A, B, and C). A is 40% similar to B and 40% similar to C. B is 20% similar to C. Say that the algorithm places B in cluster 1 and then C in cluster 2 as they are dissimilar. What happens when it tries to place A? Because A is similar to both B and C will they be joined into one cluster (this would be the best result for me) or is A just placed into one cluster even though it is similar to a protein in another cluster?

Improve this question
$\endgroup$
4
  • $\begingroup$ what do you mean "dissimilar"? Do you mean "unrelated and non-homologous" or do you mean "homologous but highly diverged"? $\endgroup$
    – Maximilian Press
    Nov 19, 2020 at 19:00
  • $\begingroup$ see also here for more documentation: extras.csc.fi/blast/doc/blastclust.html $\endgroup$
    – Maximilian Press
    Nov 19, 2020 at 19:04
  • $\begingroup$ @MaximilianPress Sequence identity is the measure I'm using. $\endgroup$
    – lazer-guided-lazerbeam
    Nov 20, 2020 at 12:45
  • $\begingroup$ sure, identify is a measure you can use, but it doesn't tell us what question you want to ask with these proteins. pick any two random proteins from uniprot, and they will be dissimilar 99.99+% of the time, because they are simply unrelated. why not do that? $\endgroup$
    – Maximilian Press
    Nov 20, 2020 at 19:46

1 Answer 1

Reset to default
2
$\begingroup$

Based on the documentation (that I linked to in comment), it seems that the clustering algorithm used by blastclust is single-linkage hierarchical clustering.

SO what you can expect is that A will be placed with the protein to which it is most similar. And then the last protein will be added as an outgroup to that cluster due to its similarity to A (assuming that there are no other proteins).

So if your goal is "I want clusters that are guaranteed to contain dissimilar proteins", then you might not be able to naively take blastclust output and interpret it as such. You could either postprocess it to find the set of clusters in which no protein is more than 30% similar to a protein in any other cluster (which may just be one big cluster!), or find another clustering algorithm that is more suited to your task.

Update

It does look like blastclust uses a minimum similarity (not identity) threshold (from blastclust docs). So they use an implementation of single-linkage clustering that stops before merging everything into a single cluster:

If the coverage is above a certain threshold
 AND
the score density is above a certain threshold,

these two sequences are considered to be neighbored.

Thus determined neighbor relationships is considered symmetric and provides
the base for clustering by a single-linkage method (which puts a sequence
to a cluster if the sequence is a neighbor to at least one sequence in the
cluster)."

I don't think that this is a general property of the generic clustering algorithm though (see the "Naive algorithm" section).

Improve this answer
$\endgroup$
4
  • $\begingroup$ From your link: "In single-linkage clustering, the distance between two clusters is determined by a single pair of elements: those two elements (one in each cluster) that are closest to each other. The shortest of these pairwise distances that remain at any step causes the two clusters whose elements are involved to be merged." So it looks like all three proteins in my example will be in the same cluster at the end. This means that any proteins in another cluster will be guaranteed to be less than 30% similar to my example cluster. $\endgroup$
    – lazer-guided-lazerbeam
    Nov 20, 2020 at 12:52
  • $\begingroup$ @lazer-guided-lazerbeam i'm not sure that i follow that argument. yes, all of your proteins will eventually be joined into one "cluster" by hierarchical clustering- the output of a classic hclust algorithm is not a set of clusters but a tree, where you can "cut" at different heights to select different intensities of clustering. so you can just select the root, and it's all one cluster! blastclust presumably implements some heuristic to choose where to cut (silhouette analysis is one such approach). i am not sure that you can guarantee the 30% threshold outside of artificial examples. $\endgroup$
    – Maximilian Press
    Nov 20, 2020 at 19:41
  • $\begingroup$ The single linkage article states that two clusters will only be merged if their two closest elements are are close enough (in this case more than 30% similar). Therefore every element in one of two separate clusters must be less than 30% similar to every element in the other cluster, right? $\endgroup$
    – lazer-guided-lazerbeam
    Nov 21, 2020 at 19:32
  • 1
    $\begingroup$ @lazer-guided-lazerbeam I don't see that in the wiki article, quite possible I am missing something. I am specifically looking at the "Naive Algorithm" section and the worked example. I do actually see that something similar is in the blastclust docs- which argues that you are right. $\endgroup$
    – Maximilian Press
    Nov 21, 2020 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.