Algorithm of graph isomorphism with threedimensional DNA graph structures

ResearchonDNAcomputingwasinitializedin1994 ,whenAdleman[1] proposedamethodofsolvingasmallinstanceoftheHamiltonianPathproblembyalaboratoryexperimentinvolvingDNAmolecules .Later,Lipton[2 ] demonstratedhowalargeclassofNP completeproblemscouldbesolvedbyencodingtheprobleminDNAmolecules .Inparticular ,LiptonshowedonefamousNP problem ,theso called“satisfiability”problem (SAT)andsubsequentlytheotherNP problemscouldbeencodedandsolvedusingmolecules .TheadvantagesofDNAcomputingareitsmassivepa…     

Algorithm of graph isomorphism with three dimensional DNA graph structures

An algorithm for solving the graph isomorphism problem with 3-D DNA structures is proposed in this paper. The karmed branched junction molecules are used to code k-degree vertices. Double stranded molecules are used to code edges. Then the molecules are mixed in a tube to be ligated. The result can be detected by gel electrophoresis. The time complexity of the algorithm is O(n2), where n is the number of vertices of the graph.     

样条几何形变模型及其在CT图像分割上的应用

根据医学图像分割的特点，建立了一种样条几何形变模型，它表示为一个有序的用边线连接的顶点集合，其有序的顶点集合组成顶点模型，有序的边线集合组成边线模型，两者通过形变模型的二阶连续性紧密地结合在一起，样条几何形变模型能够获得平滑而连续的对象描述，适合于形状复杂的解剖结构，将其用于肝脏CT图像分割，结果表明，模型具有很好的收敛性和描述效果。     

异形纤维的多尺度形状描述方法

为了实现异形纤维形态定量描述,对图形的几何特性及边界描述方法进行讨论,对图形的几何特征进行计算,并应用于异形纤维形态识别和黏连判断.在图像的闭合边界上顺序选择平均分布的三点作为顶点组成三角形,并计算三角形的面积.通过改变顶点间的分布(称为步长),计算对应三角形面积表示(TAR)值.三角形三条边的绕行方向决定了三角形面积值的正负.TARN和TARP分别表示TAR负值面积和正值面积,用于表征图形边界的凹凸特性.边沿上凹点的大小由TARN的长度测量,纤维的黏连度由不同步长的TARP或者TARN之间的关系检测.实验结果表明该方法能有效地自动识别异形纤维形态,并通过正常纤维以及黏连纤维的特征参数分布区间进行黏连判断.     

一种有效的图像边缘修正方法

在实验的基础上,从视觉心理学出发,对边缘检测结果中的不理想情况进行分析和归纳,提出适合于边缘修正处理的链表型数据结构,并说明了边缘图像映射到数据结构中去的过程.根据目标域的线性、平行及封闭约束和图像边缘的长度约束以及边缘出错类型,形成修正规则与算法.最后给出了修正处理的实验结果.     

最小生成树的又一种生成法

提出一种关于最小生成树的生成法, 此方法是在一个给定的网络中,首先找到一条权最大的边,判断此边的 2个结点在不经过此边的情况下是否有另路相通,若相通则删除此边.否则, 保留此边,再寻找所剩余的权最大的边, 作类似的处理,直到在原网络中剩下的边为顶点数减 1 为止, 由此即得最小生成树.与传统的 Prim 算法及 Kruskal 算法相比较, 此法在点多而边数相对较少的网络中,能迅速地找到它的最小生成树.     

基于图学习的本体概念相似度计算

根据边的类型、顶点深度、边的密度和强度以及边关联的两顶点的属性计算有向边的权重,通过图学习正则化模型得到优化函数.将本体结构图中每个顶点映射成一个实数,通过比较实数间的差值判断两概念的相似程度.实验表明该方法对于计算本体概念间的相对相似度是有效的.     

Formation and branch migration of Holliday junctions mediated by eukaryotic recombinases

Holliday junctions (HJs) are key intermediates in homologous recombination and are especially important for the production of crossover recombinants. Bacterial RecA family proteins promote the formation and branch migration of HJs in vitro by catalysing a reciprocal DNA-strand exchange reaction between two duplex DNA molecules, one of which contains a single-stranded DNA region that is essential for initial nucleoprotein filament formation. This activity has been reported only for prokaryotic RecA family recombinases, although eukaryotic homologues are also essential for HJ production in vivo. Here we show that fission yeast (Rhp51) and human (hRad51) RecA homologues promote duplex-duplex DNA-strand exchange in vitro. As with RecA, a HJ is formed between the two duplex DNA molecules, and reciprocal strand exchange proceeds through branch migration of the HJ. In contrast to RecA, however, strand exchange mediated by eukaryotic recombinases proceeds in the 3'-->5' direction relative to the single-stranded DNA region of the substrate DNA. The opposite polarity of Rhp51 makes it especially suitable for the repair of DNA double-strand breaks, whose repair is initiated at the processed ends of breaks that have protruding 3' termini.     

图的各种一般全染色

图G的正常全染色是指若干颜色给G的顶点和边的分配,使任意2个相邻顶点、2条相邻边和任一顶点与它的关联边得到的颜色不同.将正常全染色的限制条件减弱,得到了各种一般全染色,并讨论了它们的色数.     

-K3V Kn 的Smarandachely邻点可区别正常边染色

图的染色问题是图论研究的主要内容之一,起源于著名的"四色猜想"问题.图G的一个正常边染色f称为是Smarandachely邻点可区别的,如果对G中任何相邻的两个顶点u与v,与u关联的边的颜色的集合和与v关联的边的颇色构成的集合互不包含.对一个图G进行Smarandachely邻点可区别正常边染色所用的最少颜色数称为G的...     

图K3,3∨Kt 的点可区别正常边染色1

 图G的正常边染色称为是点可区别的, 如果对G的任意两个不同的顶点u,v, 与u关联的边的颜色构成的集合异于与v关联的边的颜色构成的集合。 对图G进行点可区别正常边染色所需要的最少颜色数称为是G的点可区别正常边色数, 记为χ′s(G)。讨论了图K_3,3∨Kt 的点可区别正常边染色。     

A 1.7-kilobase single-stranded DNA that folds into a nanoscale octahedron

Molecular self-assembly offers a means of spontaneously forming complex and well-defined structures from simple components. The specific bonding between DNA base pairs has been used in this way to create DNA-based nanostructures and to direct the assembly of material on the subnanometre to micrometre scale. In principle, large-scale clonal production of suitable DNA sequences and the directed evolution of sequence lineages towards optimized behaviour can be realized through exponential DNA amplification by polymerases. But known examples of three-dimensional geometric DNA objects are not amenable to cloning because they contain topologies that prevent copying by polymerases. Here we report the design and synthesis of a 1,669-nucleotide, single-stranded DNA molecule that is readily amplified by polymerases and that, in the presence of five 40-mer synthetic oligodeoxynucleotides, folds into an octahedron structure by a simple denaturation-renaturation procedure. We use cryo-electron microscopy to show that the DNA strands fold successfully, with 12 struts or edges joined at six four-way junctions to form hollow octahedra approximately 22 nanometres in diameter. Because the base-pair sequence of individual struts is not repeated in a given octahedron, each strut is uniquely addressable by the appropriate sequence-specific DNA binder.     

图K_（3,3）∨K_t的点可区别正常边染色

图G的正常边染色称为是点可区别的,如果对G的任意两个不同的顶点u,v,与u关联的边的颜色构成的集合异于与v关联的边的颜色构成的集合。对图G进行点可区别正常边染色所需要的最少颜色数称为是G的点可区别正常边色数,记为χ＇s（G）。讨论了图K3,3∨Kt的点可区别正常边染色。     

Covalently closed circles of adenovirus 5 DNA

The genome of adenoviruses is a double-stranded linear DNA molecule with inverted terminal repeats about 100 base pairs (bp) in length and a terminal protein covalently linked to the 5' nucleotide of each strand. Both of these features permit the formation of DNA circles, the inverted repeats allowing the circularization of single-stranded DNA and the terminal protein the joining of one or more molecules to yield double-stranded circles or concatemers. However, although the existence of covalently closed circles has been postulated, double-stranded viral DNA purified from virions or infected cells by conventional methods (that is, using proteases and phenol or chloroform) has always been obtained in a linear form. Here, we present evidence for the existence in adenovirus 5 (Ad5) infected cells of novel structures resulting from covalent head-to-tail joining of viral DNA molecules and show that these structures are due at least in part to the formation of covalently closed circles.     

一类六点八边图的图设计

设Kv是一个v个点的完全图,G为Kv的一个不含孤立点的简单子图.Kv的一个G-设计,常记为(v,G,1)-GD,是指一个二元组(X,B),其中X为Kv的顶点集,B是Kv的一些子图(亦称为区组)构成的集合,使得每一个区组与G同构,且Kv的任何一条边恰在B的一个区组中出现.文章讨论了一类六点八边图中尚未解决的3个图Gi(i=1,2,3)的图设计存在性问题,并证明了(v,G,1)-GD(i=1,2,3)存在的必要条件v=0,1(mod 16)且≥16也是充分的.从而给出了这类六点八边图图设计存在的完全解.     

条件故障下3-元n-立方体的容错分析

研究了条件边故障下3-元n-立方体中较大连通分支点的数目,进而证明了3-元n-立方体是(4n－6)-条件边故障强Menger边连通的。最后通过一个反例说明该结果是最优的。     

序列图的一些必要条件与非序列图类

为纠错码问题提供理论基础,在运用同余、奇偶性方法的基础上,给出了用点边二种观点分析边标号的方法。使用这种方法,得到了一般序列图、正则序列图、Euler序列图、圈的粘接序列图和圈的并序列图的必要条件,证明了边数为2k,k是奇数的Euler图是非序列图类,讨论了m个n圈的粘接图中的非序列图类：分析偶圈的特征,构造了偶圈的具有同顶点集的序列母图并给出其序列标号表达式。这些结果在通讯、军事等领域有重要应用价值。     

图mP2∪mCt（3≤t≤10）的点可区别正常边染色

图G的正常边染色称为是点可区别的,如果对G的任意两个不同的顶点u,v,与u关联的边的颜色构成的集合异于与v关联的边的颜色构成的集合.对图G进行点可区别正常边染色所需要的最少颜色数称为是G的点可区别正常边色数,记为χ′s(G).通过将路和圈填装到完全图,我们给出了mP2∪mCt的点可区别正常边色数的一个刻画,并利用递归染色的方式,得到了χ′s(mP2∪mCt)(3≤t≤10).     

基于概念匹配的本体映射算法

本体映射是解决本体异构的通用方法.根据边的类型、顶点深度、边的密度和强度以及边关联的两顶点的属性计算有向边的权重.选择最优路径构建对应本体有向层次图的无向生成树,分别定义其Laplace矩阵,并通过分析该矩阵的特征值及特征向量来构造匹配矩阵.最后根据匹配矩阵元素的大小和位置信息来实现顶点匹配,并由此生成本体映射.实验表明该方法是有效的.     

油藏任意约束平面域PEBI网格的生成算法

针对油藏任意约束平面多边形区城提出了一种实用的局部正交化网格(PEBI)生成葬法。首先对边界顶点和区域内部散乱点按扫描方式排序,依次扫描各点生成新的三角形,再扫描新生成的三角形中不满足Delaunay准则的三角形,进而不断的处理这些不合理三角形最终完成整个区域的三角网格化,最后连接每个三角形的外接圈固心生成PEBI网格。剖分过程中采用了弹性平清和对角线交换优化方法,很容易实现局部区域的最优化剖分。通过平面映射法就可以应用到油藏的三维PEBI网格剖分,因此本算法具有很好的可操作性和实用性。