Why aren't clustal alignments stable under deletion of some of the sequences?

Question

I'm new to pairwise and multiple sequence alignment in general, but I thought I understood how clustal works -- k-tuple distance is a cheap metric that's 'probably approximately' monotonic in the real global pairwise-alignment score, so we can just calculate it between all C(n, 2) sequences and do a simple UPGMA. Clustalw algorithm description here

But I'm observing odd results. Suppose I have a file with 60 sequences and run clustal on it, and observe that seqA and seqB are paired terminal child nodes. If I then delete a handful (say 10) of the sequences, but keep seqA and seqB, then in the new clustal alignment, seqA and seqB may not remain paired.

This is strange to me, because if Clustal was actually doing the k-tuple distance + UPGMA thing I thought it was doing, then all terminal pairings should always be stable under deletions of other sequences.

So... what am I missing?

Answer 1

As the graph of sequences depends on the sequences in the input, if you change the input sequences (by deleting some sequences) you change the graph.
The alignment between the sequences changes, and thus the relative distance between them changes too.

The deletion of some sequences won't cause any change on other sequences only if the full space of the C(n 2) pairwise comparisons would be done. However for a large number (and long) of sequences, this would require too much computational effort and time, making such methods as the k-tuple distance competitive.