Why do we use dynamic programming algorithms for sequence alignment problems?
Describe with the aid of examples two different techniques for phylogeny
March 21, 2023Discuss the space–time complexity of dynamic programming algorithms in sequence alignment
March 21, 2023Why do we use dynamic programming algorithms for sequence alignment problems?
COMPUTER SCIENCE TRIPOS Part II – 2012 – Paper 9
Bioinformatics (PL)
(a) Considerable recent research has focused on alignment of sequences.
(i) Why do we use dynamic programming algorithms for sequence alignment
problems? [3 marks]
(ii) Describe what needs to be taken into account for gaps in DNA sequence
alignment. [3 marks]
(b) Considerable recent research has focused on sequence database search methods.
(i) What are the most important differences between PatternHunter, BLAST,
Smith-Waterman and Needleman-Wunsch algorithms? [9 marks]
(ii) Compare the heuristic used by Clustal with a dynamic programming
algorithm for multiple alignment. [5 marks]
