# DNA Paired Fragment Assembly Using Graph Theory
## 1 Introduction
[PERSON] [9] developed a comparative study of DNA sequence assemblers; tests were carried out with fragment sets obtained using Illumina equipment (_Illumina_: [[http://www.illumina.com/](http://www.illumina.com/)]([http://www.illumina.com/](http://www.illumina.com/)), Illumina, Inc., San Diego, CA, USA). The fragments' lengths were found by NGS technology to be in the range of 50 to 150 bases [10]. The [PERSON] study was developed in 2012; nevertheless, the paradigm remains the same today, and the [PERSON] study is therefore still applicable. The primary metric in the evaluation was N50 (shortest sequence length close to the median of a set of _contigs_). [PERSON] employed four organisms in the test, including a _Staphylococcus aureus_ problem. These results are particularly interesting because the tests we present in this article have been obtained using a problem with the same bacterium. [PERSON] did not include the _Edena assembler_ ([[http://www.genomic.ch/edena.php](http://www.genomic.ch/edena.php)]([http://www.genomic.ch/edena.php](http://www.genomic.ch/edena.php)), Genomic Research Institute, Geneva, Switzerland. ), developed by [PERSON] [11] in his research. In our comparative study, this assembler is an important reference. Initially, _greedy_ (Algorithmic technique that at each step tries to generate the optimal solution of that step of the problem without considering the rest of the problem) algorithms [12] were used to find the order of the fragments; later, the _de Bruijn_ graph [13] was introduced with different values for the _k-mer_ (section of k consecutive bases) [13]. Most of the assemblers available today are based on _de Bruijn_ graphs. In our comparative study, we include the _Velvet assembler_ ([[http://www.ebi.ac.uk/~zerbino/velvet/](http://www.ebi.ac.uk/~zerbino/velvet/)]([http://www.ebi.ac.uk/~zerbino/velvet/](http://www.ebi.ac.uk/~zerbino/velvet/)), EML-EBI, Cambridge, UK), developed by [PERSON] [14], which applies _de Bruijn_ graphs. Figure 1: Reading a strand in direct and inverse-complementary. [PERSON] et al. [15] proposed an optimization with a genetic algorithm to maximize the sum of the fragment overlaps, but the obtained _contigs_ were relatively short and processing speed was low. Later, [PERSON] and [PERSON] [16] suggested a reduction of the fragments' assembly problem to the traveling salesman problem (TSP) that has been studied extensively. Solution methods with relatively good efficiency exist for the TSP. Applying heuristics and algorithms, they obtained optimal solutions for several commonly used benchmarks, and for the first time, a real-world problem was solved by using optimization. Using graph theory and setting the appropriate objective functions, [PERSON] et al. [17] developed a new assembly method from the perspective of a directed graph, looking for the reduction of the algorithm's complexity. In this publication, taking [PERSON] et al. [17] as a starting point, we developed a new algorithm working with the _paired fragments_ (two records identified by \"/1\" and \"/2\", respectively, conforming to an interval of the sequence of DNA) resulting from the sequencing results of the _Illumina equipment_. In our initial tests, we found some _contigs_ that were not located in the published genome for the same organism, even though these _contigs_ were properly obtained. Empirically, we found that when these _contigs_ were split at certain points, all of the pieces could, in most cases, be found in the genome. Using the information from the paired fragments information, we could find the locations where a _contig_ should be split to increase the quality of the assembly. To obtain the overlaps between DNA fragments, we used a _Trie_[17]. Using the overlaps as edges, a directed graph has been obtained, and we could build a set of _contigs_ improving the N50 [8] of the previous release [17]. The interval of the paired fragments was a critical factor in our success.