IN PYTHON Question $3(10$ marks$)$

You should be able to answer most of this question after you have attempted Question $1($which requires study up to Chapter $4$ on Sequences and iteration$)$ and all of it after you have attempted Question $2($which requires study up to Chapter $23$ on Dynamic programming$).$

This question is quite open$-$ended but assesses some or all of the learning outcomes:

Develop and apply algorithms and data structures to solve computational problems.

Analyse the complexity of algorithms to support software design choices.

Explain how an algorithm or data structure works, in order to communicate with relevant stakeholders.

In comparing DNA sequences and sometimes other strings, it can be useful to allow slightly inexact matches. For example, DNA sequences that are essentially the same may differ in a small number of characters due to processes such as mutation, deletion or insertion.

In their simplest form these involve a change of one character $$ a mutation involves a base $(\text{'}$A$\text{'},\text{'}$C$\text{'},\text{'}$G$\text{'}$ or $\text{'}$T$\text{'})$ that changes to a different base $($e$.$g$.$ 'ACTG' becomes 'ATTG'$),$ a deletion means one base is removed from the DNA sequence $($e$.$g$.$ 'ACTG' becomes 'ATG'$)$ and an insertion means one additional base is added to the sequence at a particular point $($e$.$g$.$ 'ACTG' becomes 'ACTCG'$)$

Q$3($a$)(7$ marks$)$

Discuss in general terms whether and how it might be possible to adapt your 'brute$-$force' algorithm from Question $1,$ to allow for some limited effects of mutation, deletion or insertion in identifying longest common substrings, and whether this could be expected to have an impact on the performance. We do not expect you to write or modify any code for this question.

Write your answer here

Q$3($b$)(3$ marks$)$

Give one idea for how your dynamic programming solution to Question $2,$ could be adapted for the same sort of inexact matching to allow for mutation $($only$).$ This could be a similar adaptation to what you proposed in Q$3($a$)$ for the Question $1$ solution, or it might be different. In either case, explain why this is appropriate.

Very briefly explain any effect you would expect on the complexity or performance of the dynamic programming solution from your proposed adaptation