Discuss how a local alignment algorithm allows identification of internal sequence duplications
Describe in outline the Four Russians algorithm
March 21, 2023Describe the time and space complexity for finding the global alignment between two DNA sequences when they are very similar
March 21, 2023Discuss how a local alignment algorithm allows identification of internal sequence duplications
COMPUTER SCIENCE TRIPOS Part II – 2021 – Paper 9
Bioinformatics (pl219)
(a) Compute the local alignment between the following sequences: GATTACA,
TATACG with the following rules: match score = +5, mismatch = −3, gap
penalty = −4 and discuss how the alignment depends on the choices of match
scores, mismatch and gap penalty. [5 marks]
(b) Discuss how a local alignment algorithm allows identification of internal sequence
duplications. [3 marks]
(c) Define the UPGMA algorithm and state and justify its complexity. What is the
output of the algorithm given the distance matrix of the species X1, X2, X3, X4
below?
species X1 X2 X3
X2 2
X3 4 4
X4 6 6 6
[4 marks]
(d) Discuss a method to perform random access in DNA-based storage memory.
[4 marks]
(e) Discuss with one example the complexity of the Gillespie algorithm and comment
on the main differences with respect to a deterministic approach. [4 marks]
