## 2 Use of Graph Theory
### Objective Function  
In the literature, using nature inspired algorithms to solve the DNA fragment assembly problem published after [PERSON] [8], the associated graph has been considered to be an undirected graph. Other literature considered bi-directed graphs, especially when De Bruijn graphs were proposed. It is common to use a Hamiltonian path, even though sometimes Eulerian paths have been used too [7]. In any case, it is not entirely clear how many times each one of the fragments should be used, since, from the physical point of view, it is feasible for a sequence to repeat in different sections of the DNA, and for identical fragments to come from different places. Thinking that a fragment and it reverse-complement are the same, creates too much complexity from the algorithmic point of view as well as from the programming one, and would only be justified as long as it was strictly required to  
\begin{table}
\begin{tabular}{l r r r r r r r r r r r r} \hline \hline  & **1** & **2** & **3** & **4** & **5** & **6** & **7** & **8** & **9** & **10** & **11** & **12** & **13** \\ \hline
1 & & & & 20 & & & & & & & & \\
2 & & & 24 & & & & & & & & \\
3 & & & & 20 & & 24 & & & & & \\
4 & & & & & & & & 24 & & & \\
5 & & & & 20 & 20 & & & & & & \\
6 & & & & & & & 24 & & 20 & \\
7 & & & & & & & & & & 17 \\
8 & & & & & & 20 & & & & & \\
9 & & & & & & & 24 & 20 & & \\
10 & & & & 22 & & & & & & \\
11 & & & & & & & & & & & \\
12 & & & & & & & & & & 20 \\
13 & & & & & & & & & & & \\ \hline \hline \end{tabular}
\end{table}
Table 3: Graph example: overlaps matrix.  
Figure 2: Graph example: graph.  
consider Hamiltonian paths. Hence, we consider each reverse-complement fragment as an independent fragment. Another possibility might be to trust the huge cover that is customary in Next Generation Sequencing (NGS) and not use reverse-complements.  
With respect to the objective function for the optimization, in many papers, the sum of the overlaps of each fragment with the next one is used, which has probably been inherited from the use of some greedy algorithms. In addition to this objective function, we propose to maximize the sum of the lengths of the _contigs_. This can be achieved by considering that each time that a new fragment is added at the end of a _contig_, its length is incremented by an amount equal to the length of the fragment minus the overlap length. So we would have the following objective functions:  
\[\max F_{1}=\sum_{i=1}^{n-1}w(i,i+1) \tag{1}\]  
\[\max F_{2}=\sum_{i=1}^{n-1}(L-w(i,i+1)) \tag{2}\]  
where \(w(i,\,i+1)\) is the number of overlapped bases between fragment \(i\) and the next one in the sequence, \(n\) is the number of fragments, and \(L\) is the length of the fragment. Notice that Equation (2) can easily be transformed into a minimization:  
\[\min F_{2}^{{}^{\prime}}=\sum_{i=1}^{n-1}w(i,i+1) \tag{3}\]  
Because  
\[F_{2}=(n-1)L-F_{2}^{{}^{\prime}} \tag{4}\]  
The boundary between _contigs_ appears because there are values of _w(i, \(i+1\))_ that are equal to 0. Since there is usually some contamination with foreign DNA and there might be chimeras, some of the obtained _contigs_ do not belong to the original DNA, and, at some point, which is not within the scope of this paper, useful _contigs_ must be separated from the useless ones.  
In order to obtain each _contig_, an agreement must be reached (computed) for each base, _i.e._, since we know that there might be redundancy for each base (due to the original cover) and that there might be sequencing errors in the fragments, it is possible for each base in each _contig_ to have several versions, from which the most frequent value must be accepted, even if it is the minimum acceptable value. Since most of the errors in the _contigs_ are at the ends, due to chemical problems in the sequencing equipment or because of the lack of enough redundancy, it might be necessary to cut them off.