Describe Ruth Nussinov’s algorithm on RNA folding and its complexity
Discuss with one example how the stiffness parameter affects soft k-means clustering
March 21, 2023Describe with one example how to construct the paired de Bruijn Graph
March 21, 2023Describe Ruth Nussinov’s algorithm on RNA folding and its complexity
COMPUTER SCIENCE TRIPOS Part II – 2019 – Paper 8
Bioinformatics (pl219)
(a) Describe Ruth Nussinov’s algorithm on RNA folding and its complexity.
Illustrate with one example. [4 marks]
(b) Describe the neighbour joining algorithm for phylogenetic analysis and its
complexity. [5 marks]
(c) Hidden Markov models (HMM) are widely used in Bioinformatics.
(i) Describe how to build an HMM to identify exons and introns in genome
sequences. [5 marks]
(ii) Discuss how to assess the performance of an HMM to identify exons and
introns in genome sequences. [2 marks]
(d) Discuss the advantages and disadvantages of Leonard Adleman’s approach to
the travelling salesman problem with respect to the computational approach.
[4 marks]
