$($b$)$ In this part, we continue from the problems in Question $1.$ In Question $1($b$),$ we were told

that we were missing exactly one subsequence. Unfortunately, we can never be sure about the

number of subsequences that we have lost after noisy DNA reads. Furthermore, we may be able

to turn any graph Eulerian by adding multiple edges; however, we should opt to add as few

edges as possible to turn it Eulerian.

Consider a directed graph $G(V,E)($not necessarily obtained from DNA sequencing$)$ and assume

it is not Eulerian. Can we find the smallest number of edges that need to be added in order for

the graph to become Eulerian? Formulate this problem as an optimization problem by

carefully defining your data, variables, constraints, and objective function as we saw in class.

No need to add this problem to Gurobi; simply the mathematical formulation will do$.$

Recall the DNA sequencing problem we discussed during class and the Eulerian path problem

that was associated with it$.$ A bioinformatics group, motivated by the same lecture material,

decided to put this to the test. Alas, the graph they ended up with is not Eulerian. They believe

the issue to be with their DNA reads, which ended up being noisy and hence they lost exactly

one of the subsequences they should have obtained.

Recommend an algorithm for them to render the obtained graph Eulerian by adding

the necessary edge$($s$).$ For testing purposes, you can use your algorithm with the following

set of subsequences of $k=3,s$ :

$s=\{GGT,GTC,CCT,CTC,TCG,GCT,CGC,$CTA,TAA,AAC$\}$

The constructed network would be as in Figure $2$:

Figure $2$: The graph created with one missing subsequence.