多序列比对问题的并行近似算法

基于中心方法的思想,采用分治策略,在SIMD-CREW模型上设计了一个使用O(k2m)个处理器(其中k为序列个数,m为最长的序列长度),时间复杂度为O(m logk)的并行近似算法.在实际情况中,由于logk远远小于m,相对于时间复杂度为O(m2k2)的串行中心方法,该算法在理论上达到线性加速.与现有的并行算法相比,它可以适用于任意情况,且易于分析时间复杂度.利用LARPBS模型的特点和并行求前缀和的方法,调用LARPBS模型上求和与最大(小)值的并行算法,首次给出了在LARPBS模型上的多序列比对问题的并行近似算法.该算法使用O(k2m)个处理器,时间复杂度为O(m log log D),其中D为序列两两比对的代价值的最大值.该算法同样适用于任何情况,由于log log D通常远小于m,所以它在理论上也是线性加速的.     

生物序列比对算法的简述

基因组和蛋白质组的研究极大地依赖于数据库的搜索,寻求更快更灵敏的生物序列相似性比对算法一直是生物信息学研究的热点,文章介绍了相似性比对的得分算法和各种数据库搜索工具,并对各种算法的优缺点进行了讨论与比较.     

针对基因选择性剪接的多序列比对算法研究

为对真核基因的选择性剪接形式进行准确、快速、有效的研究 ,提出了一种启发式多序列比对算法。该算法借助引导树启发序列之间的两两段对段比对 ,通过建立序列相似性估计模型 ,给出了一种由序列间相同词数估计序列相似程度的方法。利用这种方法构造引导树 ,大大缩短了其构造时间。通过采用序列间的段对段比对 ,克服了间隙罚分问题 ,更准确地反映了真核基因的选择性剪接形式。引导树构造方法的改进和快速局部比对算法的采用 ,使得算法运行速度大大高于一般算法。该算法为真核基因的选择性剪接研究提供了一种新的有效途径     

基于A*算法的启发式算法求解多序列比对问题

通过分析动态规划算法及A^*算法的特点，针对多序列比对问题提出一种基于A^*算法的启发式算法。该算法采用了多个优化搜索机制。通过对此算法的理论分析，证明了它能够在有效地减小搜索的空间、节约搜索的时间的同时，保证得到比较好的比对结果。此算法不仅能够在多序列比对问题中得到应用，还能够用于其他有向无环图的最短路径问题的求解。     

两种带约束的序列比对算法

通过理论证明,得出了当距离函数中惩罚因子φ=0时的解应满足的条件,并在此基础上改进两种最长公共子序列的优化算法,使之能够求解出带约束的序列比对问题.这两种改进算法的时间复杂度分别为O(nmr)和O(nm(r+1)),空间复杂度分别为O(nmr)和O((n+m)(r+1)).推导出算法应满足在两序列中插入的空位符数目分别为(m-l)和(n-l),使比对结果中不会出现错配,保证了比对的质量.实现了基于回溯的改进算法,验证了其求解带约束的序列比对问题的有效性.     

生物序列比对算法分析与比较

序列比对是生物信息学的一个非常重要的操作．它可以预测生物序列的功能、结构和进化过程等．文中首先介绍双序列比对的基本算法;接着分析和比较多序列比对的四个常用模型和三类算法以及并行比对算法;最后,给出一些研究问题．     

SARS-CoV-2病毒全基因组序列比对及进化分析

SARS-CoV-2病毒株是β属冠状病毒,它包括S、N、E、M4个主要编码蛋白,是造成中国湖北省武汉市爆发重大公共卫生事件的罪魁祸首,目前对该病毒的系统性研究分析并不是很多.运用计算机辅助软件工具来对筛选自NCBI基因文库中的36条来自不同国家地区的SARS-CoV-2病毒株序列进行全序列比对分析,从而找出SARS-C...     

生物信息学中基于启发式的多序列比对算法

序列比对是生物信息学中一项重要的基础性研究课程,其基本任务之一就是进行多重序列比对,但是如何优化多重序列比对算法目前生物信息学面临的一个核心课题,本文介绍了多重序列比对研究所涉及的基本问题,对当前多重序列比对启发式算法的几种经典算法进行描述,并对多重序列比对算法的前景进行了展望。     

基于置换距离度量的蛋白质多序列比对算法性能评估

 蛋白质多序列比对是一种重要的生物信息学工具,在生物的进化分析以及蛋白质的结构预测方面有着重要的应用。各种比对算法在这个领域都取得了很大的成功,但是每种算法都有其固有的缺陷。提出置换距离法,对当前流行的几种蛋白质多序列比对算法进行对比评价。由于置换距离法仅关注于不同蛋白质间进化距离的相对次序,而不考虑这些进化距离之间的细微差异,因而得到的评价结论更具有鲁棒性。另外,采用最长公共子序法度量置换距离可以比较准确的反映不同置换之间的差异性。基于该算法,对Dialign, Tcoffee, ClustalW和Muscle多序列比对算法进行了性能评估。     

Solving the multiple sequence alignment problem based on simulated annealing algorithm

The multiple sequence alignment problem (MSAP) is one of the most difficult problems in computational molecular biology. In this paper, we describe the optimization model and the neighborhood structure on the MSAP, then propose a scheme to solve the MSAP using Simulated Annealing Algorithm. Experiment shows that the scheme is effcient.     

Identification of true EST alignments and exon regions of gene sequences

Expressed sequence tags (ESTs), which have piled up considerably so far, provide a valuable resource for finding new genes, disease-relevant genes, and for recognizing alternative splicing variants, SNP sites, etc. The prerequisite for carrying out these researches is to correctly ascertain the gene-sequence-related ESTs. Based on analysis of the alignment results between some known gene sequences and ESTs in public database, several measures including Identity Check, Gap Check, Inclusion Check and Length Check have been introduced to judge whether an EST alignment is related to a gene sequence or not. A computational program EDSAcl.0 has been developed to identify true EST alignments and exon regions of query gene sequences. When tested with human gene sequences in the standard dataset HMR195 and evaluated with the standard measures of gene prediction performance, EDSAel.0 can identify proteincoding regions with specificity of 0.997 and sensitivity of 0.88 at the nucleotide level, which outperform that of the counterpart TAP. A web server of EDSAcl.0 is available at http://infosci.hust.edu.cn.     

产生适用于CDMA系统最佳扩频序列的新方法

在多用户CDMA系统中,为了提高扩频通信的抗多址干扰(MAI)能力,改善系统容量.提出了方便实用的能产生最佳扩频序列的系统模型,该模型由两级多层前馈网络(2-MFNN)级联组成,前级网络用于重建混沌吸引子,后级网络对前级网络输出的混沌序列进行变换,所得序列具有良好的相关性.模型产生序列的方法满足MAI最小的最佳扩频序列的要求.MFNN的学习算法采用具有对复杂的多峰值函数进行全局优化能力的克隆选择算法,以提高网络的学习能力,最后,应用柏内庭Lyapunov指数对该网络产生的序列是否具有混沌性态进行检验,并对网络输出的序列性能通过对整个序列集合的相关函数的均方值取平均进行了评估.计算结果表明,由该网络产生的序列不但具有混沌性态而且具有优良的相关特性,可以将其作为良好的混沌扩频序列发生器,适合于大容量CDMA通信系统.     

mRNA序列与蛋白序列对比

生物序列的对比是计算生物学中的一个基本问题．目前已有许多算法对DNA序列或蛋白序列之间进行对比,多是对同种生物序列进行对比．为得到mRNA序列和蛋白序列之间的对比,采用动态规划算法,提供了寻求mRNA序列和蛋白序列的局部对比和全局对比,解决了核酸与氨基酸之间的对比问题．算法的时间复杂度为O(nm)．     

交织多址接入系统定点Logistic交织序列生成算法

交织多址接入(interleave division multiple access, IDMA)技术作为典型的非正交多址接入技术,受到学术界和产业界的广泛关注。为降低IDMA系统多用户检测过程存储空间和计算复杂度,采用双极性化的定点Logistic序列与待(解)交织序列对应相乘方式完成(解)交织;同时,为降低任意量化比特长度的定点Logistic序列生成过程时延,采用现场可编程逻辑门阵列进行生成。利用Logistic系统李雅普诺夫指数,确定处于混沌状态的定点Logistic序列量化比特长度;基于平衡度和互相关门限,确定定点Logistic序列开始位置和初值;采用查表法构建非对称基本乘法器,并采用移位相加法计算总乘法器。仿真结果表明,所提算法可以充分利用Logistic序列混沌、平衡度、相关等特性,具有较好的误码率性能。     

基于模拟退火遗传算法的多序列比对方法

针对MSA问题提出了将遗传算法与模拟退火算法结合在一起的混合算法.该算法充分发挥了遗传算法和模拟退火算法的优越性,可提高求解多序列比对MSA问题的计算精度和计算速度,整个算法模拟了自然界进化的周期性,较好的解决了群体的多样性和收敛深度的矛盾.实验表明,该方法算法是有效的.