Describe the time and space complexity for finding the global alignment between two DNA sequences when they are very similar
Discuss how a local alignment algorithm allows identification of internal sequence duplications
March 21, 2023Discuss with one example how the stiffness parameter affects soft k-means clustering
March 21, 2023Describe the time and space complexity for finding the global alignment between two DNA sequences when they are very similar
COMPUTER SCIENCE TRIPOS Part II – 2020 – Paper 8
Bioinformatics (pl219)
(a) Describe the time and space complexity for finding the global alignment between
two DNA sequences when they are very similar. [4 marks]
(b) Describe how match, mismatch and gap penalty (initiation and elongation) affect
the score in global sequence alignment. [4 marks]
(c) Describe, with one example, how the number of mutations affects the
phylogenetic analysis using the distance algorithm. [4 marks]
(d) Describe the differences in algorithmic complexity between the distance and
parsimony phylogenetic methods. [4 marks]
(e) Describe why the Viterbi algorithm can help identify protein structural parts
(alpha helix, beta sheet, coil) in a sequence of amino acids and describe how it
works. [4 marks]
