Genome Sequencing with Graph Elements

Abstract

DNA sequencing is the process of ordering the nucleotides in a piece of DNA. Each of the four existing nucleotides is identified with one of the four letters A, C, G, T. Sequencing a genome is quite challenging. It requires breaking the DNA of the genome into many smaller pieces, aligning and merging the pieces, and reconstructing them into a one long genome in proper order. Since the completion of the human genome project, technological improvements have accelerated the speed of genome sequencing and made it less expensive. This study presents a method of reconstructing the genome from its smaller sequences or reads using algorithms based on graph theory. Reconstructing a genome is an important step in understanding the pattern of letters of the genome sequence, functions of genes, relation between genes, and how they all work together. This understanding of the genome sequence of different species, including plants leads to many applications, medicines, and vaccines as seen in the current Covid-19 pandemic.