TITLE:
Genome Sequencing Using Graph Theory Approach
AUTHORS:
Shepherd Chikomana, Xiaoxue Hu
KEYWORDS:
DNA Sequencing, Hamiltonian Graph, Euler Graph, de Bruijn Graph, Nucleotide
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.13 No.2,
April
19,
2023
ABSTRACT: Genome
sequencing is the process of determining in which order the nitrogenous bases
also known as nucleotides within a DNA molecule are arranged. Every organism’s
genome consists of a unique sequence of nucleotides. These nucleotides bases
provide the phenotypes and genotypes of a cell. In mathematics, Graph theory is
the study of mathematical objects known as graphs which are made of vertices
(or nodes) connected by either directed edges or indirect edges. Determining
the sequence in which these nucleotides are bonded can help scientists and
researchers to compare DNA between organisms, which can help show how the
organisms are related. In this research, we study how graph theory plays a
vital part in genome sequencing and different types of graphs used during DNA
sequencing. We are going to propose several ways graph theory is used to
sequence the genome. We are as well, going to
explore how the graphs like Hamiltonian graph, Euler graph, and de Bruijn
graphs are used to sequence the genome and advantages and disadvantages
associated with each graph.