Shortest Path Problem for a Graph of DNA String using Adenine and Guanine in Purine Bases as the Vertex

Abstract

In the field of research on Deoxyribonucleic acid (DNA), graph theory can be applied to model the structure of a DNA molecule. In particular, the shortest path problem in graph theory can be used to identify the shortest path between vertices of a graph. Hence, it is possible to apply the shortest path problem for minimization of a DNA string so that the time taken for computation of genome assembly can be reduced. This paper presents a method to represent a DNA string graphically where the shortest path is calculated for the graph generated from the DNA string, and the shortest path is then used to minimize the DNA string. In this research, a DNA string is presented in graphical form by using base pairs of length two as the vertices where the initial bases used are Adenine (A) and Guanine (G) which are the main bases in purine. The number of base pairs between adjacent vertices in the DNA string is represented by the edges. The graph is then reduced by following a given set of rules where the shortest path is calculated for all start and end vertices of the reduced graph. Next, the simplification of the graph is done based on the shortest paths obtained by removing all the untraversed paths where the Euler path for the simplified graph is used to form a minimized DNA string. The result shows that a minimized DNA string can be obtained by simplifying the graph of the DNA string using the shortest path problem