Answers.Body: <p>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.<br>
  The alignment between the sequences changes, and thus the relative distance between them changes too. </p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-07-24T14:06:02.363Z
Answers.LastActivityDate: 2018-07-24T14:06:02.363Z
Answers.UserDisplayName: llrs
Body: <p>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. <a href="https://www-bimas.cit.nih.gov/clustalw/clustalw.html" rel="nofollow noreferrer">Clustalw algorithm description here</a> </p>
  
  <p>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 <em>new</em> clustal alignment, seqA and seqB may not remain paired.</p>
  
  <p>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.</p>
  
  <p>So... what am I missing?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-05-28T07:23:45.093Z
Comments.Text: 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!
Comments.UserDisplayName: llrs
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-07-24T13:43:18.113Z
Comments.Text: @Llopis should this not be the answer, rather than a comment?
Comments.UserDisplayName: Matt Bashton
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-07-24T14:00:19.383Z
Comments.Text: @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.
Comments.UserDisplayName: llrs
Tags: <phylogenetics>
Title: Why aren't clustal alignments stable under deletion of some of the sequences?
ThreadText: # Why aren't clustal alignments stable under deletion of some of the sequences?
  
  (Asked by: username_0 on 2018-05-27)
  
  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](https://www-bimas.cit.nih.gov/clustalw/clustalw.html)
  
  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?
  
  **Tags:** phylogenetics
  
  > **Comments:**
  > **username_1**: 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!  
  > **username_2**: @Llopis should this not be the answer, rather than a comment?  
  > **username_1**: @username_2 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.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-07-24. Score: 3 | Accepted answer
  
  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.
  
  
  ---
  
  