CPSC536A - Solution to Surprise Quizz 1

---

Multiple Sequence Alignment (MSA) / Iterative Refinement [7 marks]

Which of the following statements are true (T) or false (F)? Use '?'
to indicate that you don't know an answer.


[F] The CLUSTALW algorithm is based on a probabilistic model of evolution
    and always computes an optimal multiple sequence alignment (MSA).

CLUSTALW is a progressive alignment algorithm heavily based on heuristics.
In general, progressive alignment algorithms are not guaranteed to find
optimal alignments. (CLUSTALW is based on a - very simple - probabilistic model 
of DNA evolution (the Kimura model).
 

[F] MSA algorithms like CLUSTALW compute good phylogenetic trees as
    a side product.

The guide trees used by progressive alignment algorithms are in general
not suitable for serious phylogenetic analysis. The are generated
in a 'quick and dirty' way based on the intuition that a rough approximation
of an evolutionary tree can be sufficient to guide the progressive alignment.

 
[F] Provided a meaningful score is optimised, iterative refinement MSA
    is guaranteed to always find the maximum score.

Under certain conditions (see Durbin et al., p. 148),
Iterative refinement MSA is guaranteed to find  alocally optimal score.


[*] Provided a meaningful score is optimised, iterative refinement MSA
    finds the optimal score with some bounded probability.

Apologies for that one. What I meant was 'with some bounded probability > 0',
and for this the answer would have been 'F'. But as the question is posed here,
the answer could be trivially 'T', if you argue the bound can be 0.
Because of the unclear formulation of the question, I decided to not
count this one for any student.


[F] Provided a meaningful score is optimised, iterative refinement MSA
    will never find the optimal score.

There is nothing that says it cannot find the optimal score, but unless
one is looking at very specific variants, the probability that it may find
the optimal score might be arbitrarily close to 0.


[T] The Barton-Sternberg Algorithm will take at least as much time to
    compute an MSA than the dynamic programming algorithm for 
    global pairwise alignment.

Pairwise sequence alignment is done in step (1) of Barton-Sternberg.
Additionally, each sequence-to-profile alignment performed in steps
(ii) and iii) is at least as time-consuming as pairwise sequence alignment.


[F] The Barton-Sternberg Algorithm sometimes takes less time to
    compute an MSA than the dynamic programming algorithm for 
    global pairwise alignment.

Again, apologies - this should have been deleted. Since it is only
redundant, not misleading or unreasonably hard, this one was counted
as a normal question.


[T] The Barton-Sternberg Algorithm does not use profile-profile alginment,
    but only the special cases of sequence-sequence and sequence-profile 
    alignment.

(Look at the algorithm outline in Durbin et al., p.149)