Studies On DNA Graphs And DNA Labeling Graphs

In Molecular Biology, the phase of calculation of sequencing by hybridization and reconstruction for DNA chain can use DNA graphs as a mathematical model. As a result, DNA graphs have been researched widely.In order to read a DNA sequence, Blazewicz et al. propose the definition of (κ,α)—labeled digraphs. A digraph D is called a DNA graph if D is (κ,4)—labeled. In 2008, Yuan Jun et al. proved the sufficient and necessary conditions for the directed paths and directed cycles that are (κ,α)—labeled. We prove a property of the directed paths and directed cycles that are (κ,α)—labeled and we also prove that the completely bipartite one-way pseudo-graphs D0 (A, B),κgeneralized path P(V0,V1,…,Vκ-1),κgeneralized circle C(V0,V1,…,Vκ-1) andκgeneralized tree T(V0,V1,…,Vκ-1), which are referred in this paper, are DNA labeled graphs by the theory of directed line-graph. Further more we show and prove that complete bipartite one-way graphs D(V1,V2) and k generalized path P(V0,V1,…,Vκ-1) are the sufficient and necessary conditions for DNA graphs.In 2007,Wang(Science China (A),37(9)) obtained a result about DNA labeling graphs which do not contain loops.On this basis, we generalized a sufficient and necessary condition for general directed graphs.We conclude that the sufficient and necessary condition for any directed graphs,which do not contain isolated vertices have and only have a equivalence class under the friend relationship and we draw some improved results accordingly.A counterexample of a theorem is given, too. Furthermore, we modified and completed this theorem.It is easy to deduce that the necessary condition for the theorem in Wang's research is also a sufficient condition.Finally, we give a description of characterization of the relationship between DNA graphs and DNA labeling graphs.