DNA paired fragment assembly using graph theory (Q1662696)

Summary: DNA fragment assembly requirements have generated an important computational problem created by their structure and the volume of data. Therefore, it is important to develop algorithms able to produce high-quality information that use computer resources efficiently. Such an algorithm, using graph theory, is introduced in the present article. We first determine the overlaps between DNA fragments, obtaining the edges of a directed graph; with this information, the next step is to construct an adjacency list with some particularities. Using the adjacency list, it is possible to obtain the DNA \textit{contigs} (group of assembled fragments building a contiguous element) using graph theory. We performed a set of experiments on real DNA data and compared our results to those obtained with common assemblers (\textit{Edena} and \textit{Velvet}). Finally, we searched the \textit{contigs} in the original genome, in our results and in those of \textit{Edena} and \textit{Velvet}.