# DNA Paired Fragment Assembly Using Graph Theory
## 1 Introduction  
Each monomer comprising the DNA polymer is formed with a pentose, a phosphate group and one of four nitrogenous bases: adenine, guanine, cytosine and thymine. In 1953, scientists [PERSON] and [PERSON] [1] discovered the double-helix spatial structure of the DNA molecule. This double chain is coiled around a single axis, and the strands are attached by hydrogen bridges between pairs of opposite bases. The direction of the polymer chain is determined by the pentose carbon atoms \(5^{\prime}\) and \(3^{\prime}\) (the beginning and ending positions of a DNA strand are denoted as \(5^{\prime}\) and \(3^{\prime}\), respectively; a DNA strand is read in the \(5^{\prime}\) to \(3^{\prime}\) direction, and the complementary strand runs in the opposite direction). The bases in each pair are complementary. The content of adenine (**A**) is the same as the content of thymine (**T**), and the cytosine (**C**) content is the same as that of guanine (**G**) (Figure 1). In 1975, [PERSON] [2] proposed a DNA sequencing technique that involved detecting small dark bands in a thin gel using electrophoresis. [PERSON] proposed cutting the DNA molecule at specific points in the sequence with restriction enzymes [3]. This method is slow and costly; with each digestion, the sample must be divided, and each new division must be cloned to obtain a sufficient amount of material. To reduce processing time, [PERSON] et al. [4; 5] proposed splitting the DNA sequences at random points. The disadvantage of this method is that the order of the fragments is unknown, generating an NP-Complete (Non-deterministic polynomial time) [6] computational problem. This method is known as the _shotgun technique_. [PERSON] [7] proposed a method to assemble the genome using a computer. As the DNA fragments are produced from many copies of the original genome, more than one fragment comes from the same region. The DNA fragments should be processed while looking for overlaps, coincidences in the extremes of the fragments. The total number of bases in the fragments divided by the total number of bases in the complete genome is called the _coverage_. If the _coverage_ is high enough, it is possible to rebuild the genome, but it is difficult to obtain high-quality results because false overlaps can be generated due to sequencing errors, sample contamination with foreign DNA and chimeras (the cloning process is carried out using host bacteria, and sometimes the DNA of the sample is concatenated with that of the host bacteria, producing what is known as a _chimera_). In our experiments, we noticed that some DNA sections might not be sampled and that complete genome reconstruction would therefore not be possible. What can be obtained is a set of _contigs_ covering most of the genome, and it is the job of a molecular biologist to assemble the _contigs_ using other techniques. Later, [PERSON] and [PERSON] [4] proposed the generation of paired fragments in the _shotgun_ process. Traditional sequencing starts from the 5\({}^{\prime}\) end of each piece of DNA, and only a limited number of bases can be sequenced. In NGS (Next-Generation Sequencing), the number of bases is always the same, yielding fixed-size fragments; however, the DNA pieces sequenced are generally longer. The goal of the paired fragments procedure is to obtain a sequence from the 3\({}^{\prime}\) end as well as one from the 5\({}^{\prime}\) end, obtaining two fragments from the same piece of DNA. This would help to establish an interval in the DNA sequence associated with the paired fragments. Unfortunately, sequencing from the 3\({}^{\prime}\) end is difficult and produces a relatively large number of sequencing errors. DNA sequencing technology has advanced, decreasing costs and process time. Today, there are databases with information about many genomes, including the human genome and those of many disease-causing microorganisms [8].