## 1 Introduction
This is the reason why the resulting assembly of all fragments is a set of _contigs_ or subsequences and almost never the entire sequence of the problem. It is the job of specialized biologists to fill in the gaps and correct assembly errors made during the automated process. DNA fragment sequencing technology has continued to advance while costs continue to go down. The original _shotgun_ technology has been called \"long reads\" because the fragments would normally have more than 500 bases. Using new technologies, commonly known as Next Generation Sequencing, \begin{table}
\begin{tabular}{c c c c} \hline
**n** & **Observed** & **Probability** & **Expected Value** \\ \hline  
\hline \end{tabular}
\end{table} 
Table 1: Observed frequency on \(n\) bases A _vs._ expected value for p = 0.3249 and 5,324,340 fragments. Figure 1: Some fragments from the _S. aureus_ strain MW2 problem. the cost to sequence a million bases is about $1 [6]. Unfortunately, the length of the fragments is shorter using this newer technology. Today, 150 bases reads are common with the Illumina sequencers. To compensate for the problems derived from the short size of each fragment, coverage of about 40 is needed instead of a coverage of about 10 in the case of long reads. If we consider the number of fragments to be sequenced with newer technologies, we need to assemble three to four million fragments to sequence a bacterium, while using long reads, only 50,000 fragments were enough. These are really bad news due to the combinatorial nature of the solutions to the problem. Since the very beginning of DNA fragment sequencing, greedy algorithms have been used; for instance, we pick a random fragment and connect to it the one that has the longest overlap. This process is repeated until no overlapping fragments are available. Nowadays, this technique would be difficult to use, since fragments are too short, which often produces several different fragments with the same overlap size. Another popular technique is the use of De Bruijn graphs [7]. In order to build these graphs, all possible _k-mers_ (subsequence of \(k\) consecutive bases) of each fragment are used to find all possible overlaps among them. Using these graphs, several problems can be solved by using heuristics; for instance, given a _k-mer_, there might be two parallel paths to other _k-mer_, creating what is called a bubble. The bubble is then popped by removing the shortest side or projecting one side onto the other when they have the same length. Short sequences that originate from long ones are eliminated. It is common to use a value of \(k\) close to 20 in order to obtain the _k-mers_. An approach based on genetic algorithm optimization was suggested by [PERSON] in 1993 [8]. Later, other scientists applied similar metaheuristics [9; 10; 11; 12], but their results were based on very small benchmarks, the largest had about 1000 fragments, and even though results were improving slowly, they were still far from real problems, including the long reading ones, with tens of thousands of fragments. In 2013, a reduction from fragment DNA sequencing to the Traveling Salesman Problem (TSP) was used [13]. Taking advantage of formal heuristics and algorithms for the TSP, optimal values were found for the most commonly used benchmarks, and, for the first time, a real life problem was solved using optimization. The remainder of this paper is organized as follows: Section 2 provides the basic ideas on the use of graph theory for the solution of DNA sequencing problems; Section 3 explains those algorithms that are necessary to tackle the problem; Section 4 illustrates the use of our algorithms on real life problem benchmarks; and, in Section 5, we give our conclusions and future work.