A New Approach to Pattern Matching in Degenerate DNA/RNA Sequences and Distributed Pattern Matching

In this paper, we consider the pattern matching problem in DNA and RNA sequences where either the pattern or the text can be degenerate, i.e., contain sets of characters. We present an asymptotically faster algorithm for the above problem that works in O(n log m) time, where n and m is the length of the text and the pattern respectively. We also suggest an efficient implementation of our algorithm, which works in linear time when the pattern size is small. Finally, we also describe how our approach can be used to solve the distributed pattern matching problem. The preliminary version of this paper appeared in [26].     

求最大匹配的一个新算法

简单无向图G的最大匹配问题分为二部图和一般图的最大匹配两类。前者主要采用可增广路的思想解决,〔1〕中已经详述;本文主要讨论有关后者的算法。 定义 设G=(V,E)是简单无向图,在G的所有匹配M′中,若M=max|M′|,则称M是G的一个最大匹配。     

A New Algorithm for Solving the Word Problem in Braid Groups

One of the most interesting questions about a group is whether its word problem can be solved and how. The word problem in the braid group is of particular interest to topologists, algebraists, and geometers, and is the target of intensive current research. We look at the braid group from a topological point of view (rather than a geometric one). The braid group is defined by the action of diffeomorphisms on the fundamental group of a punctured disk. We exploit the topological definition in order to give a new approach for solving its word problem. Our algorithm, although not better in complexity, is faster in comparison with known algorithms for short braid words, and it is almost independent of the number of strings in the braids. Moreover, the algorithm is based on a new computer presentation of the elements of the fundamental group of a punctured disk. This presentation can be used also for other algorithms.     

求最优权对集的一个对偶算法

1.引言 Edmonds给出了求一个图的最大权对集的算法它是从一个满足原始对偶可行的解出发使其逐步满足互补松驰条件。[1]描述了一个求最大权完美对集原始算法。它是从一个满足互补松驰条件的原始可行解出发,使其逐步满足对偶可行条件。我们给出一个求图的最大权完美对集的对偶算法,它是从一个满足互补松驰条件的对偶可行解出发使其逐步满足可行条件。本算法开始不要求给出图的一个完全对集,其对偶变量的改变法则也较[1]中的法则简单得多。其基本方法仍是用Edmonds的花的算法[2]。我们将说明本文的算法可用来解其他的最优对集问题。本文中采用的术语参看[2]。     

A Subquadratic Algorithm for Approximate Regular Expression Matching

The main result of this paper is an algorithm for approximate matching of a regular expression of size m in a text of size n in time O(nm/log_d+2n), where d is the number of allowed errors. This algorithm is the first o(mn) algorithm for approximate matching to regular expressions.     

一类新图的匹配唯一性

利用图的匹配多项式及其最大实数根的性质证明了树T(1,1,n,2,1)及补图匹配唯一的充要条件是n≠1,2,5,8.     

基于模式匹配的模糊控制算法

本文针对模糊控制器输入输出是非模糊量的特点,在隶属函数统一定义的情况下,提出一类新的基于模式匹配的简化推理决策算法。     

计算机代数应用中的一个半逆序算法*

为了克服计算机代数应用中出现的"中间表达式爆炸"的困难,本文提出一种半逆序算法,将中间表达式在运算过程中以符号形式冻结起来,到求解的最后阶段予以解冻,从而避免了因存贮空间不足而导致的溢出.文中简述了该算法在非线性振动、冷却塔动力优化和非线性水波问题中的应用,证实了算法的有效性.     

KMP算法的一种新的简化算法

通过对字符串模式匹配算法BF与KMP的分析,提出了一种简化KMP算法的方法,构造了一种新的计算next函数的方法,简化后的算法比KMP更清晰直观.经过复杂性分析和上机实验,得出当模式串的长度不大时,简化算法是一种高效的模式匹配算法.     

PERT问题的新算法

本文给出了一种通过求解最长路径解决 PERT问题的新算法 .其优点是 ,编制运算程序之前 ,无需做出系统作业的网络图 ,因此 ,使用起来更加方便     

A Note on Optimal Matching With Variable Controls Using the Assignment Algorithm

The assignment algorithm is an old, well-known, widely implemented, fast, combinatorial algorithm for optimal matching in a bipartite graph. This note proposes a method for using the assignment algorithm to solve the problem of optimal matching with a variable number of controls, in which there is a choice not only of who to select as a control for each treated subject, but also of how many controls to have for each treated subject. The strategy uses multiple copies of treated subjects and sinks with zero cost to absorb extra controls. Also, it is shown that an optimal matching with variable numbers of controls cannot be obtained by starting with an optimal pair matching and adding the closest additional controls. An example involving mortality after surgery in Pennsylvania hospitals is used to illustrate the method.     

基于模矢搜索和遗传算法的混合约束优化算法

近年,免梯度方法又开始引起大家的注意，由于不需要计算函数的梯度．特别适合用来求解那些无法得到梯度信息或需要花很大计算量才能得到梯度信息的问题．本文构造了一个基于模矢搜索和遗传算法的混合优化算法．在模矢搜索方法的搜索步，用一个类似于遗传算法的方法产生一个有限点集．算法是全局收敛的.     

一种求解分类问题的新算法

本文提出了基于支持向量回归机(SVR)的一种新分类算法.它和标准的支持向量机(SVM)不同:标准的支持向量机(SVM)采用固定的模度量间隔且最优化问题与参数有关.本文中我们可以用任意模度量间隔,得到的最优化问题是无参数的线性规划问题,避免了参数选择.数值试验表明了该算法的有效性.     

模糊聚类分析的新算法

提出了一种模糊聚类分析的新算法——追踪法 ,解决了以往模糊聚类分析计算量过大以及难于编程实现的问题 .该方法尤其适用于大规模数据的模糊聚类分析 ,对于模糊聚类分析的推广使用有重要意义 .     

线性规划问题的规范型算法

提出了线性规划问题的两种规范标准形式；证明了任意一个线性规划问题都可化为这两种形式之一；给出了不需引入人工变量的线性规划问题的求解算法。     

一种新的混合蚁群算法

设计一种新的混合蚁群算法,该算法以一种新的加权二进制蚁群算法为基础,将分布估计算法PB IL的概率分布模型用来指导蚂蚁路径的选择,同时对不同位置的蚂蚁采用加权系数来控制信息素散发量,根据信息素得到的转移概率、PB IL的模型概率及二者融合的概率来产生新的个体,保证了个体的多样性,从而提高了算法的快速性和全局最优解的搜索能力.通过测试函数优化表明该算法具有良好的收敛速度和稳定性,改善了蚁群算法容易陷入局部最优而早熟的缺陷.     

Multi-Dimensional Pattern Matching with Dimensional Wildcards: Data Structures and Optimal On-Line Search Algorithms

We introduce a new multidimensional pattern matching problem that is a natural generalization of string matching, a well studied problem[1]. The motivation for its algorithmic study is mainly theoretical. LetA[1:n₁,…,1:n_d] be a text matrix withN = n₁…n_dentries andB[1:m₁,…,1:m_r] be a pattern matrix withM = m₁…m_rentries, whered ≥ r ≥ 1 (the matrix entries are taken from an ordered alphabet Σ). We study the problem of checking whether somer-dimensional submatrix ofAis equal toB(i.e., adecisionquery).Acan be preprocessed andBis given on-line. We define a new data structure for preprocessingAand propose CRCW-PRAM algorithms that build it inO(log N) time withN²/n_maxprocessors, wheren_max = max(n₁,…,n_d), such that the decision query forBtakesO(M) work andO(log M) time. By using known techniques, we would get the same preprocessing bounds but anO((^d_r)M) work bound for the decision query. The latter bound is undesirable since it can depend exponentially ond; our bound, in contrast, is independent ofdand optimal. We can also answer, in optimal work, two further types of queries: (a) anenumerationquery retrieving all ther-dimensional submatrices ofAthat are equal toBand (b) anoccurrencequery retrieving only the distinct positions inAthat correspond to all of these submatrices. As a byproduct, we also derive the first efficient sequential algorithms for the new problem.