模糊灰关联在QAR故障数据检测中的应用

针对传统的灰色关联故障诊断算法无法解决大样本数据的问题,提出一种基于模糊分割灰关联的QAR（quick ac‐cess recorder）故障数据检测算法。鉴于QAR数据是数据结构复杂、维数高的时间序列数据,利用模糊分割将QAR数据分割成不重叠的子序列,从中提取出待检测故障序列,计算待检测序列与标准序列间的灰关联度,根据最大关联度原则进行故障模式识别并确定诊断结果。仿真结果表明,该算法的预测结果与实际情况基本一致,具有简单可靠、诊断精度高等优点。     

基于格代数的最长公共子序列近似求解

多条序列的最长公共子序列可以代表多条序列的公共信息,其在诸多领域里有着重要的应用,如信息检索、基因序列匹配等。求解多条序列的最长公共子序列是著名的NP难问题,本质为多解问题。一些近似算法虽然时间复杂度较低,但只能求出单解,对于有多解的序列集合,求得的结果信息量损失较大。因此提出一个新的近似算法来解决最长公共子序列问题。算法引入了代数结构“格”,通过动态规划求解出两条序列的公共格,并递归求解当前格与当前序列的公共格。公共格中的路径保存了多条公共子序列使得最终求解出的最长公共子序列为多个。对算法的相关定理给出了理论证明,并通过实验验证了算法的正确性。     

带变异算子粒子群算法在多序列比对中的应用

多序列比对(Multiple Sequence Alignment)是进行生物序列分析的最基本任务之一。在对已有的多序列比对算法进行对比分析的基础上,提出了一种新的多序列比对优化算法—带变异算子粒子群多序列比对算法。带变异算子的粒子群算法提高了原有算法跳出局部收敛的能力,将其应用于多序列比对问题中,提高了已有的基于粒子群算法的多序列比对方法的性能,拓展了粒子群算法在多序列比对研究领域中的应用。实验证明,带变异算子粒子群多序列比对算法是有效、可行的。     

基于代价地图和最小树的移动机器人多区域覆盖方法

提出一种基于代价地图和最小树的多区域覆盖方法.首先,确定先验静态地图的栅格代价,并将静态地图转化成动态代价地图;然后,将代价地图分割成若干个区域块,对区域块再作Boustrophedon单元分割处理,得到子区域信息;最后,根据子区域间的邻接关系构建图,图中的各节点代表一个子区域.将基于最小树的子区域规划算法应用于该图得到子区域规划序列,应用基于代价地图和Dijkstra算法的区域转移算法得到区域间转移路径,子区域内使用往返覆盖策略,以此实现区域的全覆盖.将本文提出的多区域覆盖方法在线应用于多种结构场景中,实验结果表明,相对于传统的区域覆盖方法,本文方法可以有效提高移动机器人区域覆盖的效率.     

基于分割模式的时间序列矢量符号化算法

针对符号化聚合近似算法(SAX)中时间序列必须等长分割的缺陷,提出一种基于分割模式的时间序列符号化算法(SMSAX)。利用三角阈值法对随机抽样的时间序列进行特征提取,计算时间序列最大压缩比,将其作为时间窗宽提取分割点,进而求出时间序列的分割模式。利用得到的分割模式对时间序列进行分割降维,通过均值和波动率对分割后的子序列进行向量符号化。根据时间序列特征对其进行不等长分割,并加入波动率消除奇异点的影响。实验结果表明,SMSAX能获得比SAX更精确的结果。     

Dijkstra算法在蛋白质序列比对中的研究

提出一种基于Dijkstra算法的序列比对方法,该算法主要用于求最短路径,而序列比对可以转化为在有向无环图中寻找最短路径问题。对于少量序列比对,使用该算法可以求出最优解。对于多序列比对,可将在N维空间求解最短路径问题转化为在二维空间求解最短路径。该算法可以简化问题复杂度,能求得相对最优解。     

多变量时间序列例外模式的识别

多变量时间序列(MTS)在金融、医学、科学、工程等领域是非常普遍的.本文提出一种在MTS中识别异常模式的方法.采用自底向上的分割算法将MTS分割成互不重叠的子序列,使用扩展的Frobenius范数来计算2个MTS子序列之间的相似性,通过K-均值聚类将MTS子序列分为若干个类.根据异常模式的定义,从这若干个类中识别出异常模式.在2个实际数据集上进行实验,实验结果验证算法的有效性.     

多序列比对问题的粒子群优化算法求解

文章提出了一新的算法,利用粒子群优化算法求解多序列比对的问题,这是粒子群优化算法在生物信息学方面的一个新的应用。文章从粒子群算法的原理和多序列比对问题模型入手,来提出怎样改造粒子群优化算法使其可以解决多序列比对问题,最后给出利用粒子群优化算法求解多序列比对的算法,及其测试结果。     

基于多阈值分割算法的发动机羽焰图像序列分析

提出一种基于对比度和相似性度量的多阈值分割算法.算法引入人类视觉系统感知光强度变化的非线性和适应性原理,将图像的灰度级区间分成几个互不相交的子区间,使得子区间的内部像素的共性以及子区间之间的像素对比度都尽可能大,综合共性和对比度之后获取图像的分割门限.将算法应用到发动机羽焰序列图像的分割并进行序列分析,实验结果表明算法是有效的.     

基于多策略人工蜂群的多序列比对算法

多序列比对是生物信息学中最重要和最具挑战性的任务之一.基于多序列比对是NP 完全组合优化问题,引入Tent 混沌初始化种群策略、不同蜂种的邻域搜索策略和锦标赛选择策略等,提出一种基于多策略人工蜂群的多序列比对算法.该算法应用Tent混沌初始化种群策略以使初始个体多样化并获取较好初始解;针对不同蜂种的特性设计不同的邻域搜索策略以平衡算法的全局探索和局部开发能力.同时引入序列比对的蜜源编码方法以适应多序列比对的离散性.实验结果表明,所提出算法的鲁棒性较强,能获取较好的比对性能和生物特性.     

一种新的迭代渐进多序列比对算法

该文提出一种新的迭代渐进多序列比对算法IPMSA。该算法先用渐进方法进行多序列比对,然后通过迭代策略,利用上一轮多序列比对结果修正指导树,产生新一轮比对。重复这一过程,直到指导树不再发生变化或满足事先设定的迭代次数为止。以比对数据库BAliBASE中多蛋白质家族1idy为例,对IPMSA算法和ClustalW算法进行的比较研究表明,该算法能更有效地比对分歧较大的序列,并改进其系统发育树。     

Genetic algorithm with ant colony optimization (GA-ACO) for multiple sequence alignment

Multiple sequence alignment, known as NP-complete problem, is among the most important and challenging tasks in computational biology. For multiple sequence alignment, it is difficult to solve this type of problems directly and always results in exponential complexity. In this paper, we present a novel algorithm of genetic algorithm with ant colony optimization for multiple sequence alignment. The proposed GA-ACO algorithm is to enhance the performance of genetic algorithm (GA) by incorporating local search, ant colony optimization (ACO), for multiple sequence alignment. In the proposed GA-ACO algorithm, genetic algorithm is conducted to provide the diversity of alignments. Thereafter, ant colony optimization is performed to move out of local optima. From simulation results, it is shown that the proposed GA-ACO algorithm has superior performance when compared to other existing algorithms.     

Approximation algorithms for tree alignment with a given phylogeny

We study the following fundamental problem in computational molecular biology: Given a set of DNA sequences representing some species and a phylogenetic tree depicting the ancestral relationship among these species, compute an optimal alignment of the sequences by the means of constructing a minimum-cost evolutionary tree. The problem is an important variant of multiple sequence alignment, and is widely known astree alignment. We design an efficient approximation algorithm with performance ratio 2 for tree alignment. The algorithm is then extended to a polynomial-time approximation scheme. The construction actually works for Steiner trees in any metric space, and thus implies a polynomial-time approximation scheme for planar Steiner trees under a given topology (with any constant degree). To our knowledge, this is the first polynomial-time approximation scheme in the fields of computational biology and Steiner trees. The approximation algorithms may be useful in evolutionary genetics practice as they can provide a good initial alignment for the iterative method in [23].Supported in part by NSERC Operating Grant OGP0046613.Supported in part by NSERC Operating Grant OGP0046613 and a Canadian Genome Analysis and Technology Research Grant.Supported in part by US Department of Energy Grant DE-FG03-90ER6099.     

一种新型求解多序列比对问题的方法

多序列比对问题是生物信息科学中一个非常重要且具挑战性的课题,并已经被证明属于问题.为了克服以往算法中的求解速度慢的缺点,本文提出了一种基于遗传算法和蚁群算法的算法来求解的新方法,在单独使用遗传算法的基础上再使用蚁群算法来进行局部搜索以便更快速地求得解.实验结果表明,遗传-蚁群算法能有效地求解多序列比对问题.     

Multiple sequence alignment by a pairwise algorithm

An algorithm is described that processes the results of a conventional pairwise sequence alignment program to automatically produce an unambiguous multiple alignment of many sequences. Unlike other, more complex, multiple alignment programs, the method described here is fast enough to be used on almost any multiple sequence alignment problem.     

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

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

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 …     

Multiple protein sequence alignment using double-dynamic programming

A method of multiple sequence alignment is described based on the double dynamic programming (DDP) algorithm previously used for treating structural constraints encountered in structure comparison and threading. Following these applications, the inconsistencies that emerge when trying to combine pair-wise alignments into a multiple alignment are reconciled by summing all the, possibly inconsistent, paths (low-level alignments) into a matrix which is then used to provide a final (high-level) alignment. This process is applied to all sequence pairs and the pair-wise results combined in a simple multiple sequence alignment program. From this alignment, further constraints are selected to bias the low-level alignments in the DDP algorithm and the process iterated. The results, however, showed that this overall iteration was not needed and one-pass gave results at least as good as the 'standard' progressive method of multiple sequence alignment. Further applications of the method are discussed.