COMPUTER SCIENCE TRIPOS Part II – 2022 – Paper 9
Bioinformatics (pl219)
(a) Compute the global and local alignments for the following aminoacid sequences:
SEPPT, CAPPR. Use the following scores: match = +2, mismatch = −2,
gap penalty = −2. Then in the global alignment change to match = +4,
mismatch = −4, gap penalty = −4. Compare and discuss the results. What is
the general effect of the gap penalty? [5 marks]
(b) Describe in outline the Four Russians algorithm. Give expressions for
computational complexity as the number of tiles, t, is changed and compare
the growth order with that of a tile-less approach. [6 marks]
(c) Discuss with one example how an algorithm for RNA folding could use a dynamic
programming approach. What are the cases when this will not work?
[4 marks]
(d) Is it possible to remove or add just one node (a species) from/to a phylogenetic
tree without actually making the tree again? Discuss using different phylogenetic
methodologies.