Exercises - alignment and phylogenetic trees - kb207 H02

1. Progressive Alignment Problem:
   In progressive alignment, first the pairs of sequences which are most similar to each other, are aligned. Next, the resulting alignments are aligned to produce bigger alignments and finally one alignment is obtained containing all sequences in the set. A pairwise alignment is never changed in the later rounds of alignments (once a gap, always a gap). What will happen in the following case? We have sequences A, B, and C. All three sequences contain the sequence acdef. Additionally, sequences A and B share an 80 letter long sequence, that is
   A=acdefMSAAAYMDFVAAQCLVSISNRAAVPEHGGAPDAERLRLPEREVTKEHGDPGDTWKDYCTL
   B=MSAAAYMDFVAAQCLVSISNRAAVPEHGGAPDAERLRLPEREVTKEHGDPGDTWKDYCTLacdef
   C=acdef
   
   In FastA format:

   >A
   acdefMSAAAYMDFVAAQCLVSISNRAAVPEHGGAPDAERLRLPEREVTKEHGDPGDTWKDYCTL
   >B
   MSAAAYMDFVAAQCLVSISNRAAVPEHGGAPDAERLRLPEREVTKEHGDPGDTWKDYCTLacdef
   >C
   acdefDLRRSQSAGS
   

   1. What will happen when the three sequences are aligned using the progressive method?
   2. Is it likely that local multiple sequence alignment methods or pattern discovery methods do a better job in this case? Try MEME and Pratt on this sequence set (in Pratt you should switch off pattern refinement when so few sequences are analysed). Do not be intimidated by the size of the output from MEME and Pratt, look for the alignments corresponding to the highest ranked patterns/local alignments (one from Pratt and one from MEME), and paste into your report the description of these.

2. Motif discovery
   Try out MEME and Pratt on the sequences given in this fasta format sequence file (all the proteins contain classical zinc fingers). Can you use the programs to discover a motif shared by them all?
3. Trees -- number of topologies
   The equation giving the number of unrooted trees for n OTUs is
   T(n)=(2n-5)!/(2^(n-3)*(n-3)!)
   1. Draw bifurcating, unrooted trees covering all possible topologies for 4 and 5 OTUs (e.g. taxa or genes). Check that the number you get agrees with what equation 7.1 gives for n=4 and n=5.
   2. Use equation 7.1 to calculate the number of different topologies (unrooted, bifurcating trees) for n=10 (10 OTUs). Will the number of rooted trees with 10 OTUs be larger or smaller? Can you estimate the number of rooted trees with 10 OTUs?

4. Maximum parsimony
   Informative sites are defined as columns in an alignment that favours one tree topology over another. Find the number of informative sites in the following alignment:

   1 ATGTA
   2 TAGTA
   3 CGCTG
   4 GCCTG
   

   Which tree would be found by the maximum parsimony for this alignment?