关于几类DNA标号图和DNA图的结果

在分子生物学中，DNA链的杂交测序的计算和重构阶段可用DNA图作为数学模型，因此，DNA图得到广泛的研究^1.2]．为了读取DNA序列，Blazewicz等人提出了可（α，k）-标号有向图的概念，并称有向图D是DNA图，如果D是可（4，k）-标号的．2008年，原军等证明了可（α，k）-标号的有向路和有向圈的充要条件．本文证明了有向路和有向圈可（α，k）-标号的一个性质，并利用有向线图的理论证明了本文所指的伪二部单向完全图D0（A，B）、k部广义路P（V0，V1，…，VK-1）、k部广义圈C（V0，V1，…，Vk-1）以及k部广义树T（V0，V1，…，Vk-1）均是DNA标号图．进而给出并证明了二部单向完全图D（V1，V2）和k部广义路P（V0，V1，…，Vk-1）为DNA图的充要条件．

On Results about Several Types of DNA Labeling Graphs and DNA 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^1.2].In order to read a DNA sequence, Blazewicz et al. propose the definition of （α, k）-labeled digraphs. A digraph D is called a DNA graph if D is （4, k）-labeled. In 2008, Yuan Jun et al. proved the sufficient and necessary conditions for the directed paths and directed cycles that are （α, k） -labeled. We prove a property of the directed paths and directed cycles that are （α, k） -labeled and we also prove that the completely bipartite one-way pseudo-graphs D0（A,B） , k generalized path P（V0,V1,…,Vk-1） k generalized circle C（V0,V1,…,Vk-1） and k generalized tree T（V0,V1,…,Vk-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,…,Vk-1） are the sufficient and necessary conditions for DNA graphs.