APPLICATION OF GRAPH THEORY TO BIOLOGICAL PROBLEMS

Nafiseh  JAFARZADEH; Ali  IRANMANESH

Authors

Nafiseh JAFARZADEH Department of Mathematics, Faculty of Mathematical Sciences, Tarbiat Modares University, Tehran, Iran. Corresponding Author: iranmanesh@modares.ac.ir. https://orcid.org/0000-0002-1816-2994
Ali IRANMANESH Department of Mathematics, Faculty of Mathematical Sciences, Tarbiat Modares University, Tehran, Iran. Email: iranmanesh@modares.ac.ir.

Keywords:

Fragment assembly, Overlap graphs, sequence comparison, Alignment-free method, Weighted directed graph

Abstract

In this paper, we investigate application of graph theory to some biological problems, specially reconstructing strings based on information about their substrings and sequence comparison by using overlap graphs and also weighted directed graph.

References

R.M. Ludry, M.S. Waterman, A new algorithm for DNA sequencing assembly. J. Comput. Biol., 1995, 2, 291.

P.A. Pevzner, H. Tang, M.S. Waterman, A new approach to fragment assembly in DNA sequencing. RECOMB., 2001, 1, 256.

J. Blazewicz, M. Bryja, M. Figlerowicz, P. Gawron, M. Kasprzak, E. Kirton, D. Platt,

J. Przybytek, A. Swiercz, L. Szajkowski, Whole genome assembly from 454 sequencing output via modified DNA graph concept, Comput. Biol. Chem., 2009, 33, 224.

N. Jafarzadeh, A. Iranmanesh, Application of DNA graphs to whole genome sequencing, International Journal of Green Nanotechnology, 2014, 2, 373.

J. Pesek, A. Zerovnik, Numerical Characterization of Modified Hamori Curve Representation of DNA Sequences, MATCH Commun. Math. Comput. Chem., 2008, 60, 301.

Y. Zhang, W. Chen, New Invariant of DNA Sequences, MATCH Commun. Math. Comput. Chem., 2007, 58, 197.

N. Jafarzadeh, A. Iranmanesh, A Novel Graphical and Numerical Representation for Analyzing DNA Sequences Based on Codons, MATCH Commun. Math. Comput. Chem., 2012, 68, 611.

J. Yu, J. Wang, X. Sun, Analysis of similarities/dissimilarities of DNA sequences based on a novel graphical representation, MATH Commun. Math. Comput. Chem., 2010, 63, 493.

J. Blazewicz, A. Hertz, D. Kobler, On some properties of DNA graphs, Discrete Appl Math., 2003, 1, 98.

P.A. Pevzner, /-tuple DNA sequencing: a computer analysis, J. Biota. Struct. Dyn., 1989, 7, 63.

T. van Aardenne Ehrenfest, N.G. de Bruijn, Circuits and Trees in Oriented Linear Graphs, Simon Stevin., 1951, 28, 203.

W.T. Tutte, C.A.B. Smith, On Unicursal Paths in a Network of Degree 4, Amer. Math. Monthly, 1941, 48, 233.

J. Kaptcianos, A graph theoretical approach to fragment assembly, American Journal of Undergraduate Research, 2008, 7, 311.

W. Imrich, S. Klavžar, “Product Graphs: Structure and Recognition”, John Wiley & Sons, New York, 2000.

E. Hamori, Graphical representation of long DNA sequences by methods of H curves, current results and future aspects, Biotechniques, 1989, 7, 710.

X. Qi, Q. Wu, Y. Zhang, E. Fuller, C. Zhang, A Novel Model for DNA Sequence Similarity Analysis Based on Graph Theory, Evolutionary Bioinformatics, 2011, 7, 149.