“装错信封问题”数学模型的求解及推广

本文给出了全错位排列问题数学模型的通解，全错位排列推广问题的通解．     

基于Hash建立索引和Kmp快速匹配算法的DNA序列查找方法

研究了DNA序列片段的查找问题,针对DNA数据量大和DNA序列碱基排列的特点提出了DNA序列检索的问题.在对DNA序列检索中,基于Hash建立了索引表以提高在大数据中检索的速度和效率,同时在平衡树的数据存储模型上使用了改进的Kmp快速匹配算法,提高了在索引上的检索效率.介绍了Hash索引的建立、Kmp的优化以及平衡树的再平衡.利用软件评估实验得出的实验结果表明了该算法的有效性.     

全错位排列

定义 编号为1、2、3、…、n的n个元素a1,a2,a3,…,an分别排编号为1、2、3、…、n的n个位置,要求元素ai（i=1,2,…,n）不能排在与其对应的第i个位置,这样的排列称为n个元素的全错位排列;所有排列的个数称全错位排列数.     

全错位排列

定义编号为1、2、3、…、n的n个元素a1,a2,a3,…,an分别排编号为1、2、3、…、n的n个位置,要求元素ai(i=1,2,…,n)不能排在与其对应的第i个位置,这样的排列称为n个元素的全错位排列;所有排列的个数称全错位排列数.     

全错位排列的一种新解

回自同空四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡，地四张贺年卡不同的分配方式有（A）6秆（B）9科（C）11种（D）23种（1993年全国高考题）以上题目属全价位排列问题，其解法甚多，本文利用“分类”的方法给出一种新颖的解法．解四个元素全排列可分成以下四类：4个元素全措位排列；恰有3个元素全错位排fo；恰有2个元素全错位排列；没有元素错位排列．于是有：引一at十q·a3十q·3：＋1（。）其中a；（2＜i＜4）表示i个元素全错位排列数，易有a：一1，as—2，故由（。）式有：a．＝41－q·a。－－q·a。－1…     

具有错位限制且工件可退化的单机重新排序问题

重新排序问题是在原始工件已经按照某种最优规则排列时有一批新的工件到达,新工件的安排使得原始工件重新排序而产生错位.考虑了加权序列错位以及加权时间错位限制条件下具有退化工件,目标函数为最小化总完工时间和最小化总延误时间问题.工件的位置错位和时间错位限制条件下具有退化工件,目标函数为最小化总完工时间和最小化最大延迟问题.其中退化效应是指其实际加工时间是开工时间的非减函数,工件的位置错位是指重新排序过程中原始工件在原始最优序列与新到达工件所构成的新序列的加工位置之差,工件的时间错位是指重新排序过程中原始工件在原始最优序列与新到达工件所构成的新序列的完工时间之差.对以上两类问题,当权重系数或者错位限制满足特殊情况时,最优排序是原始工件集和新工件集中的工件按照退化率非减的序列排列,基于动态规划方法给出了以上几个问题的多项式时间算法或者是拟多项式算法.     

排列与组合诗一首

排列组合两大法 ,日常生活用处大 .美丽图案巧组合 ,中文英文排列法 .顺序有关属排列 ,顺序无关组合法 .分类分步细分辨 ,加法乘法计算它 .特殊元素和位置 ,首先就要考虑它 .“大于”“小于”排列题 ,从高到低若干类 .“含”与“不含”属一类 ,直接间接方法明 .“在”与“不在”“邻”“非邻” ,错位排列逆思法 .重复排列乘法算 ,穿插捆绑排列法 .分堆均分有区别 ,后面除以全排列 .隔板原理方法巧 ,组合问题不可少 .排列组合综合题 ,先组后排加乘算 .整体减去部分差 ,间接思考单记它 .世界美丽又奇妙 ,排列组合显奇效 .排列与组合诗一首$湖…     

循环码译码的Dixon结式方法

针对纠错码译码就是非线性方程组的求解问题,提出利用Dixon结式方法对译码方程进行消元以得到接收数据中的错位多项式.首先,根据纠错码的纠错能力和接收数据得到伴随式矩阵并通过该矩阵的秩确定接收码字中错误位的个数.然后,根据错位个数和伴随多项式构造译码方程.译码时,将其中一个错位变元作为隐藏变元,利用Dixon结式方法进行消元.最后,得到的Dixon结式就是关于隐藏变元的多项式.该多项式去掉多余因子后就是错位多项式,利用Chien搜索法即可求解出错误位置.当错位较多时,采用逐次计算结式的方法以筛除计算过程中的多余因子和重因子.另外,根据不同错位个数得到的错位多项式,提出了构造一类循环码错位多项式符号解的猜想,该猜想可以大大提高译码效率.实验验证了结式理论在纠错码译码方面的应用是有效的且有助于降低对芯片性能的要求.     

基于贝叶斯统计方法的两总体基因表达数据分类

在疾病的诊断过程中,对疾病的精确分类是提高诊断准确率和疾病治愈率至 关重要的一个环节,DNA芯片技术的出现使得我们从微观的层次获得与疾病分类及诊断 密切相关的基因功能信息．但是DNA芯片技术得到的基因的表达模式数据具有多变量小 样本特点,使得分类过程极不稳定,因此我们首先筛选出表达模式发生显著性变化的基因 作为特征基因集合以减少变量个数,然后再根据此特征基因集合建立分类器对样本进行分 类．本文运用似然比检验筛选出特征基因,然后基于贝叶斯方法建立了统计分类模型,并 应用马尔科夫链蒙特卡罗(MCMC)抽样方法计算样本归类后验概率．最后我们将此模型 应用到两组真实的DNA芯片数据上,并将样本成功分类．     

m-扰排问题计数公式简证

文［１］推广了文［２］、［３］中提出的错位排列或扰排（ｄｅｒａｎｇｅｍｅｎｔ）计数问题，求得了计数公式．本文给出一个简炼严谨的证明．问题在１，２，…，ｎ的全排列ｉ１ｉ２…ｉｎ中，如果有某ｍ（ｍ≤ｎ）个ｊ使得ｉｊ≠ｊ，则ｉ１ｉ２…ｉｎ称为ｎ元ｍ—扰排．...     

允许长度估计误差的SBH最优重构问题及其算法

本文讨论了允许长度估计误差和杂交错误的更实际SBH(Sequencing by Hybridization)最优重构问题.通过对SBH谱集中k-tuple之间的相关信息的分析和最优重构性质的讨论,我们得到若干非最优解的删除法则和最优解的判定法则,并获得了一个能够极大地减少最优解重构随意性的动态规划计算方法.由此,我们给出了该SBH问题的一个新重构算法.该算法既允许SBH谱集含有一般杂交实验中可能出现的探针错配所产生的正错误,也允许目标DNA序列长度有估计误差,所以本文的算法具有更一般的适应性和实用性.模拟计算结果表明我们的算法也是十分有效的(即使在谱集有多达100%的正错误情况).     

基于DNA计算的Hamilton图

DNA computing is a novel method for solving a class of intractable computationalproblems in which the computing can grow exponentially with problem size. Up to now, manyaccomplishments have been achieved to improve its performance and increase its reliability.Hamilton Graph Problem has been solved by means of molecular biology techniques. A smallgraph was encoded in molecules of DNA, and the “operations” of the computation wereperformed with standard protocols and enzymes. This work represents further evidence forthe ability of DNA computing to solve NP-complete search problems.     

Computational complexity of isothermic DNA sequencing by hybridization

In the paper, the computational complexity of several variants of the problem of isothermic DNA sequencing by hybridization, is analyzed. The isothermic sequencing is a recent method, in which isothermic oligonucleotide libraries are used during the hybridization with an unknown DNA fragment. The variants of the isothermic DNA sequencing problem with errors in the hybridization data, negative ones or positive ones, are proved to be strongly NP-hard. On the other hand, the polynomial time algorithm for the ideal case with no errors is proposed.     

对称群上Cayley图的DNA计算

有一类图称为Cayley图或群图.猜想每个Cayley图都是Hamilton图.求Cayley图和有向Cayley图中的Hamilton圈和路自然产生在计算科学里.这篇文章研究了对称群上Cayley图的DNA计算和给出了求它的Hamilton圈的DNA算法.     

Evolutionary Approaches to DNA Sequencing with Errors

In the paper, two evolutionary approaches to the general DNA sequencing problem, assuming both negative and positive errors in the spectrum, are compared. The older of them is based on the idea of genetic approach and is enhanced by a greedy algorithm. The newly proposed algorithm combines the tabu search and the scatter search methods. After conducting experiments with random and coding DNA sequences, our results suggest that the tabu and scatter search algorithm finds solutions of higher quality and more reliably than the genetic algorithm.     

Hybrid Genetic Algorithm for DNA Sequencing with Errors

In the paper, a new hybrid genetic algorithm solving the DNA sequencing problem with negative and positive errors is presented. The algorithm has as its input a set of oligonucleotides coming from a hybridization experiment. The aim is to reconstruct an original DNA sequence of a known length on the basis of this set. No additional information about the oligonucleotides nor about the errors is assumed. Despite that, the algorithm returns for computationally hard instances surprisingly good results, of a very high similarity to original sequences.     

DNA labelled graphs with DNA computing

Let k≥2, 1≤i≤k andα≥1 be three integers. For any multiset which consists of some k-long oligonucleotides, a DNA labelled graph is defined as follows: each oligonucleotide from the multiset becomes a point; two points are connected by an arc from the first point to the second one if the i rightmost uucleotides of the first point overlap with the i leftmost nucleotides of the second one. We say that a directed graph D can be(k, i;α)-labelled if it is possible to assign a label(l_1(x),..., l_k(x))to each point x of D such that l_j(x)∈{0,...,a-1}for any j∈{1,...,k}and(x,y)∈E(D)if and only if(l_k-i 1(x),..., l_k(x))=(l_1(y),..., l_i(y)). By the biological background, a directed graph is a DNA labelled graph if there exist two integers k, i such that it is(k, i; 4)-labelled. In this paper, a detailed discussion of DNA labelled graphs is given. Firstly, we study the relationship between DNA labelled graphs and some existing directed graph classes. Secondly, it is shown that for any DNA labelled graph, there exists a positive integer i such that it is(2i, i; 4)-labelled. Furthermore, the smallest i is determined, and a polynomial-time algorithm is introduced to give a(2i, i; 4)-labelling for a given DNA labelled graph. Finally, a DNA algorithm is given to find all paths from one given point to another in a(2i, i; 4)-labelled directed graph.     

On error-tolerant DNA screening

Given n clones with some positive ones, the problem of DNA screening is to identify all positive clones with a set of tests each on a subset of clones, called a pool and the outcome is either the pool contains a positive clone or not. In this paper, we show that for a class of designs, if we apply those for samples with d positive clones to samples with at most d-1 positive clones, the error-tolerant property will have an interesting improvement. We also make a remark on decoding method for k-error-correcting d-disjunct matrix.     

Linear optimization over permutation groups

For a permutation group given by a set of generators, the problem of finding “special” group members is NP-hard in many cases, e.g., this is true for the problem of finding a permutation with a minimum number of fixed points or a permutation with a minimal Hamming distance from a given permutation. Many of these problems can be modeled as linear optimization problems over permutation groups. We develop a polyhedral approach to this general problem and derive an exact and practically fast algorithm based on the branch & cut-technique.     

An optimization approach to the reconstruction of positional DNA sequencing by hybridization with errors

Positional DNA sequencing by hybridization (PSBH) is a recently proposed enhancement of DNA sequencing by hybridization (SBH, potentially a powerful alternative to the DNA sequencing by gel electrophoresis). It has been discussed in many papers and applied to large scale sequencing by hybridization. However, the computational part of PSBH reconstruction is a difficult problem, especially for the occurrence of hybridization errors. So far the problem has not been solved well. Taking PSBH as a combinatorial optimization problem, a novel reconstruction approach to PSBH is presented in this paper. The proposed approach accepts both the negative and positive errors and can greatly reduce ambiguities in the reconstruction of PSBH. The computational experiment shows that our algorithm works satisfactorily and correctly on the test data, especially for the positive errors and k-tuple repetitions.