Transcript Clarifications_for_tutorials_03_04

Clarifications and Corrections
.
Multiple Sequence Alignment
Approximation Algorithm
The ‘star’ algorithm (tutorial #3 slide 13) can be implemented with the
following modification:
Instead of step (a) in the loop:
a.
Align Si to S’1 to produce S’i and S’’1 aligned
Do:
a1. Align Si to S1 to produce S’i and S’’1 aligned
a2. add gaps (to S’i and S’’1 ) where gaps of S’1 do not appear in S’’1.
•
This is slightly more efficient since iteration i takes O(n2+i·n) time instead of O(i·n2).
•
It is more evident now that d(1,i)=D(S1 ,Si) for the approximation-ration analysis.
•
Notice that steps (a1,a2) result in an optimal alignment of Si and
S’1 .
(Why is this?)
2
S4
Lifted Tree Alignments
Algorithm
S4
S2
S1 S2 S3
S5
S4 S5 S6
There was a slight error in the phrasing of the DP algorithm for
optimal Lifted Alignment (tutorial #4 slide 11).
Modifications are highlighted in red below:
Xv - the set of labels on leaves of the subtree rooted in v.
d(v,S) - the optimal cost of v’s subtree when it is labeled by S
0 | S  S v
 | S  S v
Initialization: for leaf v labeled Sv - d (v, S )  
Recurrence: for internal node v with daughters
u1,…ul l
if S  X v then
d (v, S )   min D( S , S ' )  d (u i , S ' )
otherwise
d (v, S )  
i 1
S ' X
Note: the original phrasing allows construction of tree alignments
which are not lifted.
3