基于双序列比对算法的立体图像匹配方法*

在分析现有立体匹配方法的基础上,提出一种基于双序列比对算法的立体图像匹配方法。将立体图像对中同名极线上的像素灰度值看做是一对字符序列,使用基于动态规划思想的双序列比对算法对这些对字符序列进行匹配,以获取立体图像视差。为验证该方法的可行性和适用性,采用人脸立体图像对进行实验。实验结果表明,使用该方法进行立体图像匹配能获得光滑的、稠密的视差图。基于动态规划思想的双序列比对算法能够有效地解决立体图像匹配问题,从而为图像的立体匹配提供了一个实用有效的方法。     

渐进方法结合蚁群算法求解多序列比对问题

在所有多重序列比对算法中,渐进比对方法由于简单的算法和高效的计算在生物信息学中得到了广泛的应用。但是渐进方法最大的缺点是在早期阶段形成的错误不能在后期的计算中纠正过来。针对这个问题,我们设计了ProAnt比对算法,即渐进方法和蚁群算法相结合来求解多重序列比对问题。首先,对输入的多个序列进行预处理,用蚁群算法和概率一致性更新计算出所有字符对在最终比对中出现的概率,称为“后验概率”,计算后验概率是为了预防早期错误的发生。然后我们将后验概率作为字符对之间的匹配得分,用渐进方法得到最终的比对结果。用BAliBASE数据库对算法进行测试,实验结果显示,该算法能够在保持合理的运算时间的前提下显著改善渐进比对方法的正确性。     

求解多重序列比对问题的蚁群算法*

多重序列比对是生物信息学特别是生物序列分析中一个重要的基本操作。提出求解多重序列比对问题的蚁群算法,利用人工蚂蚁逐个选择各个序列中的字符进行配对。在算法中,蚂蚁根据信息素、字符匹配得分以及位置偏差等信息决定选择各序列中字符的概率,通过信息素的更新与调节相结合的策略较为有效地解决了局部收敛的问题,加强了算法寻求全局最优解的能力。另外在该算法的基础上,提出了基于分治策略的多序列比对蚁群求解算法,不但减少了原算法的计算时间,而且显著改善了算法所求得的解的质量。     

多重序列比对的蚁群算法

序列多重比对是生物信息学特别是生物序列分析中的一个重要的操作.提出了一种解决多重序列比对的蚁群算法,利用了人工蚂蚁逐个选择各个序列中的字符进行配对.在算法中,蚂蚁根据信息素、字符匹配得分以及位置偏差等信息决定选择各序列中的字符的概率,通过信息素的更新与调节相结合的策略,以及参数的动态自适应调节方法,较为有效地解决了局部收敛的问题,加强了算法寻求全局最优解的能力.实验显示,该算法可以有效解决多重序列比对问题.     

基于滴水算法的验证码中粘连字符分割方法

众多研究表明,如果能将验证码中的字符分割开来,用现有的机器学习算法一般都能取得比较好的识别效果。针对字符粘连情况下的验证码的识别问题,提出了一种粘连字符的分割方法。该方法将字符的宽度统计值和竖直投影直方图中的投影极小值点相结合找到分割点,以这些分割点作为滴水算法的起始滴落点对粘连字符进行分割。实验结果证明,该方法用于分割验证码中的粘连字符具有一般性,能够提高验证码识别率。     

复杂背景下的车辆牌照字符提取方法研究

针对复杂背景中字符难于提取的问题，提出了 一种通用的提取字符的方法．该方法很好地利用了字符固有的特性，先对图像进行基于变分 法的自适应二值化，再用一种快速区域标号算法求取连通域，然后对连通域进行处理，提取 出字符行，最后进行倾斜校正．实验结果表明，该方法简单可行，成功率达到了96%以上．     

一种视频中字符的集成型切分与识别算法

视频文本行图像识别的技术难点主要来源于两个方面: 1)粘连字符的切分与识别问题; 2)复杂背景中字符的切分与识别问题. 为了能够同时切分和识别这两种情况中的字符, 提出了一种集成型的字符切分与识别算法. 该集成型算法首先对文本行图像二值化, 基于二值化的文本行图像的水平投影估计文本行高度. 其次根据字符笔划粘连的程度, 基于图像分析或字符识别对二值图像中的宽连通域进行切分. 然后基于字符识别组合连通域得到候选识别结果, 最后根据候选识别结果构造词图, 基于语言模型从词图中选出字符识别结果. 实验表明该集成型算法大大降低了粘连字符及复杂背景中字符的识别错误率.     

一种基于二值图像的鲁棒字符特征提取方法

随着自动识别的应用与发展，光学字符识别被广泛应用到各种领域，而特征提取是字符识别的关键一步。本文对汽车牌照自动识别系统进行了论述，针对二值图像的字符特征提取，提出了一种基于距离变换的字符点阵特征提取算法。该算法通过距离变换方法来增加二值图像的前景与背景像素之间的距离，降低笔画边界的影响。从而提高车牌字符点阵特征的鲁棒性。实验结果表明我们的算法是有效的。     

基于字符图像分割的打印文件识别方法

针对目前的打印文件识别方法受限于样本中必须有相同字符的问题,提出一种基于字符图像分割的打印文件识别方法。通过k-means算法对字符图像进行分割,分别对不同区域提取局部二值模式纹理特征,从而消除字符结构对识别结果的影响。研究了单一区域的特征集和组合特征集的分类识别效果,实验结果表明,该方法在样本中无相同字符的情况下,能够得到较高的识别准确率。     

基于联合两种特征的手写体维文字符识别

提出一种联合两种特征的手写体维文字符识别算法。该算法对手写体维文字符图像进行实值Gabor能量特征和方向线素网格特征的提取,将实值Gabor滤波器的128维能量特征和方向线素的128维网格特征结合起来,使用KNN分类器对两种特征进行联合分类。对手写体维文字符数据库中的样本分别进行手写体维文字符特征识别和维文字符笔迹特征识别。实验结果表明,和采用一种特征的识别算法比较,进一步提高了手写体维文字符的识别率。该算法也可用于手写体阿拉伯文字符的识别。     

A platform for biological sequence comparison on parallel computers

We have written two programs for searching biological sequence databases that run on Intel hypercube computers. PSCANLIB compares a single sequence against a sequence library, and PCOMPLIB compares all the entries in one sequence library against a second library. The programs provide a general framework for similarity searching; they include functions for reading in query sequences, search parameters and library entries, and reporting the results of a search. We have isolated the code for the specific function that calculates the similarity score between the query and library sequence; alternative searching algorithms can be implemented by editing two files. We have implemented the rapid FASTA sequence comparison algorithm and the more rigorous Smith-Waterman algorithm within this framework. The PSCANLIB program on a 16 node iPSC/2 80386-based hypercube can compare a 229 amino acid protein sequence with a 3.4 million residue sequence library in approximately 16 s with the FASTA algorithm. Using the Smith-Waterman algorithm, the same search takes 35 min. The PCOMPLIB program can compare a 0.8 million amino acid protein sequence library with itself in 5.3 min with FASTA on a third-generation 32 node Intel iPSC/860 hypercube.     

生物信息学中的序列比对算法

序列比对是生物信息学中基本的信息处理方法,对于发现生物序列中的功能、结构和进化信息具有重要的意义。该文对典型的双序列比对算法Smith-Waterman、FASTA、BLAST以及多序列比对算法CLUSTAL进行了描述和评价;针对目前序列比对算法普遍存在的不足,简单介绍了应用KDD技术进行序列相似性发现的定义及其处理过程。     

Improving retrieval performance of translation memories using morphosyntactic analyses and generalized suffix arrays

Since the 1990s, translation memory (TM) systems have been one of the most widely-used tools in the field of computer-aided translation. However, most of the commercially available systems still consider two segments to be compared similar if the sequence of characters is identical or differ only marginally in spelling. Instead, linguistic similarities are disregarded so that semantically identical or similar segments, which have different (morpho)syntactic structures, are retrieved with a lower similarity value as expected or not at all. The iMem (iMem is an abbreviation for Intelligent Translation Memories) research project aimed at improving the retrieval of those very segments by analyzing their (morpho)syntactic structure and identifying the longest common substrings (LCS) between two sentences by means of generalized suffix arrays. The results of the morphosyntactic analysis are stored in the so-called iMem-TM, an independent relational database which is connected to a commercial, non-linguistically enhanced TM via its API. Base words were used for building the suffixes to increase the probability of finding a larger number of LCS between both sentences. Furthermore, an existing algorithm for generalized suffix arrays was enhanced by an additional array in order to distinguish which suffixes derive from which sentence. In this way, identical repeating LCS within the same sentence are ignored, whereas identical repeating LCS between two different sentences are still considered. If more than one identical repeating LCS between the sentences exist, the best matching LCS is given by calculating positional differences for the identical repeating LCS and choosing the one with the minimal positional difference.     

用动态扣分策略消除序列局部联配中的马赛克问题

The local alignment problem for two sequences requires determining similar regions, one from each sequence, and aligning those regions. The Smith-Waterman algorithm for local sequence alignment is one of the most well-known algorithm in computational molecular biology. This ingenious dynamic programming approach is designed to reveal the highly conserved fragments by discarding poorly conserved initial and terminal segments. However, the local alignment sometimes produces a mosaic of well conserved fragments artificially connected by poorly conserved or even unrelated fragments. This may lead to problems in comparison of long genomic sequences and comparative gene prediction. In this paper we propose a new strategy of dynamic penalty strategy to {ix this problem. In the process of computing similarity matrix, if similarity value is larger than the pre-specified threshold X then starting our strategy, when related character mismatches, then penalizing more than others until similarity value is 0 or the process ends. Test results show that this algorithm has better performance by comparison to the standard Smith-Waterman while dose not increase signally the computational complexity both in time and space.     

多序列的近似LCS改进算法

提出2种针对3条源序列的近似LCS算法,近似因子均为1/|?|。其中,线性近似LCS算法的时空复杂度均为 , 为最长源序列的长度,适于解决大规模问题。递归近似LCS算法时空复杂度均为O(nlogn),适于要求高精度问题。同时,这2种算法都能用于解决多序列的LCS和CLCS问题。实验验证了这2种算法的有效性。     

Smith-Waterman算法OpenMP并行化

基因比对可以实现对诲量生物信息的分析和处理,其中Smith—Waterman算法实现的比对信息精确度较高,但是处理速度慢。本文利用共享存储编程的工业标准OpenMPX;ySmith-Waterman算法进行了并行化实现。在一个拥有四个双核CPU的SMP节点上的测试表明,共享并行化使得该局部比对算法的速度提高了40％。     

DNA双序列比对问题的算法

随着生物序列数据库中序列数据的激增, 开发兼有高度生物敏感性和高效率的算法显得极为迫切. 通过对生物序列比对问题中Needleman-Wunsch算法和Smith-Waterman算法深入分析, 提出了Smith-Waterman算法的改进算法, 并通过实验验证该算法, 对改进前后的运行性能进行比较分析. 实验证明, 改进后的算法实现了双序列局部最优解个数的优化, 有效降低了生物序列比对算法时间与空间的复杂性, 提高序列比对的得分率和准确率.     

Parallel divide and conquer bio-sequence comparison based on Smith-Waterman algorithm

Biological sequence (e.g. DNA sequence) can be treated as strings over some fixed alphabet of characters (a, c, t and g)[1]. Sequence alignment is a procedure of comparing two or more sequences by searching for a series of individual characters that are in the same order in the sequences. Two-sequence alignment, pair-wise alignment, is a way of stacking one sequence above the other and matching characters from the two sequences thaat lie in the same column: identical characters are placed in …     

基于SSE2的Smith-Waterman算法

Smith-Waterman动态规划算法是生物信息学使用最广泛的序列匹配算法,由于存在严重的数据依赖关系,该算法的细粒度数据并行性开发受到了很大限制。文章从简化数据依赖关系出发,采用前驱计算思想,提出了基于X86处理器多媒体指令集SSE2的Smith-Waterman细粒度并行算法SWSSE2,在相似性显著的情况下比普通的SW算法性能提高5倍,且与测试集无关。一般相似性不显著的情形下,同目前最好的动态规划细粒度并行算法SWMMX相比可以获得1.5倍的加速比。     

基于前缀计算的序列比对研究

为了提高Smith-Waterman算法处理速度,同时不改变原算法的准确性,本文利用前缀计算方法修改Smith-Waterman算法,并进行OpenMP并行化。在多核机上测试表明,前缀计算的共享并行化使得该局部比对算法的速度得到很大的提高。