Efficient Genome Assembly Studies Using Overlap and Hamiltonian Graphs
DOI:
https://doi.org/10.54097/ajst.v8i2.14703Keywords:
DNA, Directed graph, k-mer, Nucleotide, Sequence.Abstract
These DNA sequencing is the intricate process of deciphering the specific arrangement of nitrogenous bases, also known as nucleotides, within a DNA molecule. Each organism possesses a unique nucleotide sequence that dictates its genetic blueprint, or genome, influencing both physical traits (phenotypes) and hereditary characteristics (genotypes) at the cellular level. In the realm of mathematics, graph theory delves into the study of mathematical constructs called graphs, composed of vertices (nodes) interconnected by either directed or undirected edges. Determining the precise order in which these nucleotides are linked empowers scientists and researchers to compare DNA across organisms, shedding light on their evolutionary relationships. This research delves into the pivotal role of graph theory in genome sequencing, exploring the diverse types of graphs utilized in this process. We propose innovative methods for employing graph theory in DNA sequencing and investigate the application of graphs such as overlap graphs and Hamiltonian graphs in genome sequencing, along with their associated advantages and limitations.
Downloads
References
Watson, J. D., & Crick, F. H. (1953). Molecular structure of nucleic acids: a structure for deoxyribose nucleic acid. Nature, 171(4356), 737-738.
Wilson, R. J. (2008). Graph theory. In The Princeton companion to mathematics (pp. 602-609). Princeton University Press.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press. Chapter 22.
West, D. B. (2001). Introduction to graph theory (2nd ed.). Prentice Hall. Chapter 2.
Pevzner, P. A., Tang, H., & Waterman, M. S. (2001). An Eulerian path approach to DNA fragment assembly. Proceedings of the National Academy of Sciences of the United States of America, 98(17), 9748–9753.
Sanger, F., Nicklen, S. and Coulson, A.R. (1977) DNA Sequencing with Chain Terminating Inhibitors. Proceedings of the National Academy of Sciences of the United States of America, 74, 5463-5467.
Southern, E. (1998) Analyzing Polynucleotide Sequences. International Patent Application PCT/GB89/00460.
Khrapko KR, Lysov YuP, Khorlin AA, Ivanov IB, Yershov GM, Vasilenko SK, Florentiev VL, Mirzabekov AD. (1988) A method for DNA sequencing by hybridization with oligonucleotide matrix. DNA Seq. 1991;1(6):375-88.
Pevzner P. A. (1989). 1-Tuple DNA sequencing: computer analysis. Journal of biomolecular structure & dynamics, 7(1), 63–73.
Idury, R. M., & Waterman, M. S. (1995). A new algorithm for DNA sequence assembly. Journal of computational biology : a journal of computational molecular cell biology,
Margulies, M., Egholm, M., Altman, W. et al. (2005). Genome sequencing in microfabricated high-density picolitre reactors. Nature 437, 376–380
Goodwin, S., McPherson, J. & McCombie, W. (2016)Coming of age: ten years of next-generation sequencing technologies. Nat Rev Genet 17, 333–351.
Ashley E. A. (2015). The precision medicine initiative: a new national effort. JAMA, 313(21), 2119–2120.
Varshney RK, Terauchi R, McCouch SR (2014) Harvesting the Promising Fruits of Genomics: Applying Genome Sequencing Technologies to Crop Breeding. PLoS Biol 12(6): e1001883.
Duan, J., Shi, J., & Ge, H. (2013). Challenges in genome sequencing analysis. Genomics, Proteomics & Bioinformatics, 11(5), 317-323
Richards, S., Aziz, N., Bale, S., Bick, D., Das, S., Gastier-Foster, J., ... & Rehm, H. L. (2015). Standards and guidelines for the interpretation of sequence variants: a joint consensus recommendation of the American College of Medical Genetics and Genomics and the Association for Molecular Pathology. Genetics in Medicine, 17(5)
Myers E. W. (2005). The fragment assembly string graph. Bioinformatics (Oxford, England), 21 Suppl 2, ii79–ii85.
Zerbino, D. R., & Birney, E. (2008). Velvet: algorithms for de novo short read assembly using de Bruijn graphs. Genome research, 18(5), 821–829.
Koren, S., & Phillippy, A. M. (2015). One chromosome, one contig: complete microbial genomes from long-read sequencing and assembly. Current opinion in microbiology, 23, 110–120.
Jain, M., Olsen, H. E., Paten, B., & Akeson, M. (2016). The Oxford Nanopore MinION:
Rhoads, A., & Au, K. F. (2015). PacBio Sequencing and Its Applications. Genomics, proteomics & bioinformatics, 13(5), 278–289.
Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. Springer, New York.
Dirac, G.A. (1952), Some Theorems on Abstract Graphs. Proceedings of the London Mathematical Society, s3-2: 69-81.
Ore, O. (1960). Note on Hamilton Circuits. The American Mathematical Monthly, 67(1), 55–55.
Chvátal, V., & Erdös, P. (1972). A note on Hamiltonian circuits. Discret. Math., 2, 111-113.
Bondy, J.A. and Chvátal, V. (1976) A Mothod in Graph Theory. Discrete Mathematics, 15, 111-135.
Fan, K. (1964). Some theorems on the Hamiltonian circuits. Acta Mathematica Sinica, 14(2), 139-149.
