摘要:在分子生物学中,DNA链的杂交测序的计算和重构阶段可用DNA图作为数学模型,因此,DNA图广泛的研究.为了读取DNA序列,Blazewicz等人了可(κ,α)-标号有向图的,并称有向图D是DNA图,如果D是可(κ,4)-标号的.2008年,原军等证明了可(κ,α)-标号的有向路和有向圈的充要条件.证明了有向路和有向圈可(κ,α)-标号的一个性质,并利用有向线图的理论证明了所指的伪二部单向完全图D0(A,B)、κ部广义路P(V0,V1,…,Vκ-1)、κ部广义圈C(V0,V1,…,Vκ-1)以及κ部广义树T(V0,V1,…,Vκ-1)均是DNA标号图.进而给出并证明了二部单向完全图D(V1,V2)和κ部广义路P(V0,V2,…,Vκ-1)为DNA图的充要条件.2007年,Wang等(中国科学(A),37(9))了关于不包含环的DNA标号图的一个结果,在此基础上推广到一般有向图上,即任何无孤立点的有向图在友关系下恰有一个等价类的充要条件,并几个相应的改进结果.还给出了一个定理的反例,进而定理的修正和完善.容易推出Wang等的一个定理的必要条件也是充分的.,给出了DNA图与DNA标号图之间关系的一个特征刻画.关键词:DNA图论文DNA标号图论文有向线图论文友关系论文
摘要3-4
Abstract4-5
目录5-6
1 引言6-8
2 预备知识8-17
2.1 基本9-15
2.2 已知主要结果15-17
3 DNA图及其标号图的主要结果(14个)17-24
4 DNA标号图与DNA图关系的刻画及其算法24-28