1. The following are the socalled Sankoff sequences, that are often used
for benchmarking multiple alignment. The sequences are given in the
socalled FASTA format.

>Human
GTCTACGGCCATACCACCCTGAACGCGCCCGATCTCGTCTGATCTCGGAAGCTAAGCAG
GGTCGGGCCTGGTTAGTACTTGGATGGGAGACCGCCTGGGAATACCGGGTGCTGTAGGCTT
>Chicken
GCCTACGGCCATCCCACCCCTGTAACGCCCGATCTCGTCTGATCTCGGAAGCTAAGCAG
GGTCGGGCCTGGTTAGTACTTGGATGGGAGACCTCCTGGGAATACCGGGTGCTGTAGGCTT
>Xenopus
GCCTACGGCCACACCACCCTGAAAGTGCCCGATCTCGTCTGATCTCGGAAGCCAAGCAG
GGTCGGGCCTGGTTAGTACTTGGATGGGAGACCGCCTGGGAATACCAGGTGTCGTAGGCTT
>Chlorella
ATGCTACGTTCATACACCACGAAAGCACCCGATCCCATCAGAACTCGGAAGTTAAACGT
GGTTGGGCTCGACTAGTACTGGGTTGGGAGGATTACCTGAGTGGGAACCCCGACGTAGTGT
>S.carlsbergensis
GGTTGCGGCCATACCATCTAGAAAGCACCGTTCTCCGTCCGATAACCTGTAGTTAAGCT
GGTAAGAGCCTGACCGAGTAGTGTAGTGGGTGACCATACGCGAAACCTAGGTGCTGCAATCT
>T.utilis
GGTTGCGGCCATATCTGAGCAGAAAGCACCGTTCTCCGTCCGATCAACTGTAGTTAAGCT
GCTAAGAGCCTGATCGAGTAGTGTAGTGGGTGACCATACGCGAAACTCAGGTGCTGCAATCT
>E.coli
TGCCTGGCGGCCGTAGCGCGGTGGTCCCACCTGACCCCATGCCGAACTCAGAAGTGAAACGC
CGTAGCGCCGATGGTAGTGTGGGGTCTCCCCATGCGAGAGTAGGGAACTGCCAGGCAT
>P.fluorescens
TGTTCTTTGACGAGTAGTAGCATTGGAACACCTGATCCCATCCCGAACTCAGAGGTGAAACGA
TGCATCGCCGATGGTAGTGTGGGGTTTCCCCATGTCAAGATCTCGACCATAGAGCAT
>B.stearothermophilus
CCTAGTGACAATAGCAGGAGAGAAACACCCGTCTCCATCCCGAACACGAAGGTTAAGCTC
TCCCAGCGCCGATGGTAGTTGGGGCCAGCGCCCCTGCAAGAGTAGGTTGTCGCTAGGC

Perform a multiple alignment on these sequences by using ClustalW, which
can be executed on-line from

http://www.ebi.ac.uk/clustalw/index.htm

Try to figure out which cost scheme is used by default by ClustalW, and
document the obtained alignment (including its cost/score) and the computed
guide tree.

2. Implement the standard quadratic-time pairwise alignment algorithm, and
test it on the Sankoff sequences. Use the same cost scheme as ClustalW.

3. Implement the uniform-lifting tree alignment algorithm by Wang and
Gusfield. Pairwise distances should be computed using the implementation
from exercise 2. Test the algorithm on the Sankoff sequences, using the
guide tree output from ClustalW. Compare the obtained solution with the
one from ClustalW.

Deadline: March 2, 2005.