6
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Precisely that the graph of sequences depends on the sequences in the input. If you change the input sequences you change the graph, so the alignment changes too. As far as I understand the k-tuple distance has changed so the alignment too. Nice first question and welcome to the site! $\endgroup$ – llrs May 28 '18 at 7:23
  • 1
    $\begingroup$ @Llopis should this not be the answer, rather than a comment? $\endgroup$ – Matt Bashton Jul 24 '18 at 13:43
  • $\begingroup$ @Matt Thanks for the reminder. It might be, but I hoped that anyone could offer more insight on how the UPGMA works. Anyway I will write it. $\endgroup$ – llrs Jul 24 '18 at 14:00
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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