Explain the uses of Eulerian and Hamiltonian graphs in the context of genome assembly
For problems involving hidden Markov models (HMM), when would you use the Baum-Welsh algorithm and when the Viterbi algorithm and why?
March 21, 2023Explain the steps and the complexity of the Hirschberg algorithm and illustrate them with an example
March 21, 2023Explain the uses of Eulerian and Hamiltonian graphs in the context of genome assembly
COMPUTER SCIENCE TRIPOS Part II – 2016 – Paper 7
Bioinformatics (PL)
(a) Explain the uses of Eulerian and Hamiltonian graphs in the context of genome
assembly. [4 marks]
(b) Discuss, giving an example, how to apply de Bruijn graphs to genome assembly.
[6 marks]
(c) Discuss how the choice of different K-mer length affects the accuracy of genome
reconstruction. [3 marks]
(d) Discuss the additive property in phylogeny. [3 marks]
(e) Show one example of additive and one of non-additive matrices. [4 marks]
