环F2+uF2上de Bruijn序列的一个有效升级算法

通过定义环F2+uF2上的n级de Bruijn-Good图到n-1级de Bruijn-Good图的满同态映射D,证明了一个由环F2+uF2上n-1级de Bruijn序列的反馈函数产生n级de Bruijn序列的反馈函数的升级算法定理;进而利用D同态的计算公式给出由m级de Bruijn序列的反馈函数产生n级(m相似文献   

一类k阶分圆矩阵的计算

令n是正整数,k是素数,k|2~n-1,并且2是模k的原根,文章给出有限域F2 n上这类k阶分圆矩阵的元素表达式.这些结果可用来计算相应的一类de Bruijn序列的个数.     

产生二元M序列的一个新算法

de Bruijn序列是一类最长的非线性移位寄存器序列,也称它为M序列。文章在纯轮换移位寄存器的状态图中,定义了圈的“夫妻数”,并利用“夫妻数”的特性,给出了二元M序列的一个新的生成算法,其算法能生成2s.g(n,s)个n级M序列。     

Lower Bound on de Bruijn Graphs Out-degree for Lower Traffic Load in Peer-to-peer Networks

Designers search for N-nodes peer-to-peer networks that can have O （1） out-degree with O （log2 N） average distance. Peer-to-peer schemes based on de Bruijn graphs are found to meet this requirement. By defining average load to evaluate the traffic load in a network, we show that in order to decrease the average load, the average distance of a network should decrease while the out-degree should increase. Especially, given out-degree k and N nodes, peer-to-peer schemes based on de Bruijn graphs have lower average load than other existing systems. The out-degree k of de Bruijn graphs should not be O（1） but should satisfy a lower bound described by an inequality κ^κ≥N^2, to ensure that the average load in peer-to-peer schemes based on de Bruijn graphs will not exceed that in Chord system.     

产生k元de Bruijn序列的一个递归算法

通过合并纯轮换移位寄存器状态图中的所有圈,给出了生成k元de Bruijn序列的一个递归算法,不再采用“主圈并一个圈”的经典并圈法,而是利用了“主圈并一组共轭圈”的新方法,减少了选择桥状态的次数;同时,给出了新的选择桥状态的规则,简化了判断一个状态是否是桥状态的计算,从而加快了并圈的速度。     

二元de Bruijn序列的一个生成算法

文章在纯轮换移位寄存器的状态图中,定义了圈的"比重",并利用"比重"的特性,给出了2元deBruijn序列的一个生成算法,其算法速度较快;同时该算法能生成2s.g(n,s)个n级de Bruijn序列,其中1≤s≤2(n-24),g(n,s)=n-2l-6-[n-l 2 l1-6]。     

无向de Bruijn图和Kautz图的k元控制

在无向图G中,对于正整数k≥1,图G的一个k元控制集D是顶点集V(G)的一个子集,并且使得G中的每一个顶点至少被D中k个点控制.文章给出了在无向de Bruijn图和Kautz图中最小k元控制集的基数.     

k=2m-1阶分圆数的计算(英文)

令n=2m是偶数,k=2^m-1,文章给出了有限域䦶Euclid Math TwoFAp_2ⁿ上所有k阶分圆数的计算公式,研究了这些分圆数的值分布规律。这些结果可用于构造一类de Bruijn序列,构造方式是对通过合并不可约线性移位寄存器的状态圈得到的,这类de Brjijn序列,合并的状态圈数是最多的。     

有向de Bruijn图与广义有向de Bruijn图的罗马控制数

文章研究了有向de Bruijn图与广义有向de Bruijn图的控制结构，通过构造同态映射给出了有向de Bruijn图的控制数，进而利用数学归纳法完整地刻画了有向de Bruijn图的罗马控制数。在此基础上，运用分类分析法进一步给出了广义有向de Bruijn图的罗马控制数的紧界。     

有向de Bruijn图的限制边连通度

证明了对有向de Bruijn图DB（d，n），当d≥3，n≥3或d=2,n≥3或≥3，n=时，它的限制边连通度λ^DB（d，n））=2d-2.     

广义de Bruijn图中Euler回路和Hamilton圈的计数

讨论了广义de Bruijn图G_B(n.d)的线图的Euler回路的个数,从而给出G_B(n.d)的Hamilton圈的计数定理。     

De Novo Assembly Methods for Next Generation Sequencing Data

The recent breakthroughs in next-generation sequencing technologies, such as those of Roche 454,Illumina/Solexa, and ABI SOLID, have dramatically reduced the cost of producing short reads of the genome of new species. The huge volume of reads, along with short read length, high coverage, and sequencing errors, poses a great challenge to de novo genome assembly. However, the paired-end information provides a new solution to these problems. In this paper, we review and compare some current assembly tools, including Newbler, CAP3, Velvet,SOAPdenovo, AllPaths, Abyss, IDBA, PE-Assembly, and Telescoper. In general, we compare the seed extension and graph-based methods that use the overlap/lapout/consensus approach and the de Bruijn graph approach for assembly. At the end of the paper, we summarize these methods and discuss the future directions of genome assembly.     

关于de Bruijn图中限长路的注记

Imase等人证明了：对于de Bruijn有向图B（d,k）中任何两个不同的面点x和y，存在d-1条内点不交且长度都不超过k 1的（x,y）路。但证明很长而且包含许多令人厌烦的验证。本文给出它的简单证明。     

一类特殊de Bruijn有向图的谱

分析了一类特殊de Bruijn有向图-B(2，n)的结构，获得了B(2，n)的谱．B(2，n)的特征值为0与2，且它们所对应的重数分别为2^n-1与1．     

无向二元De Bruijn图的边割计数

利用无向二元De Bruijn图UB(2，n)的极大限制边连通性计算了它的边割数，确定了阶至多为3的边割数，同时，给出了4阶边割数的一个上界，认为此上界是紧的。     

基于混合策略的de novo序列拼接算法构造

在对3种de novo(从头)序列拼接的基本策略进行分析的基础上,该文研究了混合策略序列拼接算法的构造过程,从而整合多个单一策略优点; 再利用形式化方法和形式化平台方面的优势,结合领域分析建模和产生式编程的方法,构造了2个基于OLC策略的算法(OLC_assembly_1,OLC_assembly_2)及1个基于DBG策略的算法(DBG_assembly),进一步组装出在(OLC+DBG)→OLC混合模式下的算法(简称ODO算法); 最后,从GenBank中选取了3个实验样本,从N50、Contigs number、Coverage等角度,比较了在3个单一策略下的算法和ODO构造算法的拼接结果,分析了coverage depth和k值的变化对拼接结果的影响.实验结果表明:该文实现的ODO算法比单一策略在序列拼接时所产生的结果在N50和Coverage等参数上均有一定的优势.     

产生2元M序列的一个新算法

M序列是非常重要的伪随机序列.给出了2元n级M序列的一个新的递归算法,该算法所需存储空间约为4n比特.而且只要经过一些修改便可生成大量的M序列.     

焊接结构装配顺序的自动生成

本文采用问题归约方法的思想，认为图论割集算法和ＡＮＤ／ＯＲ图ＡＯ搜索算法是装配顺序生成理想的通用算法。但是，制约其实用化的关键问题是产品建模、约束类型的确定和各类型约束的求解。这方面与具体应用领域有关，必须具有开放式结构。同时，任何约束都不能仅仅认为是绝对约束和绝对不约束这两种情况，而应对约束附加约束程度系数。本文就此提出了构造焊接结构扩展关系图（ＥＲＧ）的建模方法和影响焊接结构生产工艺过程设计的七种约束类型及其约束程度系数求解方法。