<p>Based on the documentation (that I linked to in comment), it seems that the clustering algorithm used by blastclust is <a href="https://en.wikipedia.org/wiki/Single-linkage_clustering" rel="nofollow noreferrer">single-linkage hierarchical clustering</a>.</p>
<p>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).</p>
<p>So if your goal is &quot;I want clusters that are guaranteed to contain dissimilar proteins&quot;, 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.</p>
<p><strong>Update</strong></p>
<p>It does look like blastclust uses a minimum <em>similarity</em> (not identity) threshold (from blastclust docs). So they use an implementation of single-linkage clustering that stops before merging everything into a single cluster:</p>
<pre><code>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).&quot;
</code></pre>
<p>I don't think that this is a general property of the generic clustering algorithm though (see the &quot;Naive algorithm&quot; section).</p>

CC BY-SA 4.0
2020-11-20T12:52:31.853Z
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.
lazer-guided-lazerbeam
CC BY-SA 4.0
2020-11-20T19:41:02.753Z
@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.
Maximilian Press
CC BY-SA 4.0
2020-11-21T19:32:58.803Z
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?
lazer-guided-lazerbeam
CC BY-SA 4.0
2020-11-21T21:39:04.293Z
@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.
Maximilian Press
CC BY-SA 4.0
2020-11-19T19:09:14.583Z
2020-11-21T21:41:57.070Z
2020-11-21T21:41:57.070Z
Maximilian Press
<p>I need to find dissimilar proteins. Looking through the PDB I found the weekly BLASTClust results of proteins that are 30% <em>similar</em>. 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.</p>
<p>The best and only documentation I can find for BLASTClust is here <a href="https://www.ncbi.nlm.nih.gov/Web/Newsltr/Spring04/blastlab.html" rel="nofollow noreferrer">(link)</a>.</p>
<p>It states:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>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?</p>

CC BY-SA 4.0
2020-11-19T19:00:51.157Z
what do you mean "dissimilar"? Do you mean "unrelated and non-homologous" or do you mean "homologous but highly diverged"?
Maximilian Press
CC BY-SA 4.0
2020-11-19T19:04:08.410Z
see also here for more documentation: https://extras.csc.fi/blast/doc/blastclust.html
Maximilian Press
CC BY-SA 4.0
2020-11-20T12:45:41.250Z
@MaximilianPress Sequence identity is the measure I'm using.
lazer-guided-lazerbeam
CC BY-SA 4.0
2020-11-20T19:46:34.667Z
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?
Maximilian Press
<blast>
Does BLASTClust guarantee that proteins in different clusters are dissimilar?
# Does BLASTClust guarantee that proteins in different clusters are dissimilar?

(Asked by: username_0 on 2020-11-18)

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)](https://www.ncbi.nlm.nih.gov/Web/Newsltr/Spring04/blastlab.html).

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?

**Tags:** blast
> **Comments:**
> **username_1**: what do you mean "dissimilar"? Do you mean "unrelated and non-homologous" or do you mean "homologous but highly diverged"?  
> **username_1**: see also here for more documentation: https://extras.csc.fi/blast/doc/blastclust.html  
> **username_0**: @MaximilianPress Sequence identity is the measure I'm using.  
> **username_1**: 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?  

---

## 1 answers

### Answer by username_1 on 2020-11-19. Score: 2 | Accepted answer

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).

> **Comments:**
> **username_0**: 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.  
> **username_1**: @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.  
> **username_0**: 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?  
> **username_1**: @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.  

---

