一个新的核酸序列比对算法及其在序列全局比对中的应用

目前在序列比对中所广泛使用的动态规划算法,虽然能达到最优比对结果,但却由于具有高计算复杂度O(N_2)而极大地降低了计算效率。将多阶段动态规划决策算法用于两两序列比对并用Visual BASIC编程实现,结果发现该新算法在将计算复杂度减小到O(N)的同时,也能够获得较为理想的计算精度,预期将在序列全局比对中起重要作用。     

基于动态规划的快速序列比对算法

序列比对算法是生物信息学中重要的研究方向之一,而动态规划法是序列比对算法中最有效最基本的方法．由于原有的基本动态规划方法时间和空间复杂度大,不适合实际的生物序列比对,因此本文在分析介绍几种相关动态规划算法的基础上,提出了一种基于动态规划的快速序列比对算法UKK_FA．实验结果表明,该算法有效地降低了时间复杂度,具有一定的实用性。     

基于复杂性度量的表面肌电信号分类方法

提取表面肌电信号的复杂性测度信息,利用原始数据的复杂度指标构造特征矢量对四种前臂动作进行分类,取得了较好的识别效果.通过比较,发现基于原始数据的复杂度指标在分类性能上要优于基于重构序列的复杂度.肌电信号的复杂度算法简单,适合短数据运算,能够满足实时处理的要求.作为一种新的肌电信号特征,复杂性测度也为生理与病理分析提供了新的思路.     

一种有效的重复序列识别算法

重复序列的分析是基因组研究中的一个重要课题,进行这一研究的基础则是从基因组序列中快速有效地找出其中的重复序列。一种投影拼接算法,即利用随机投影获得候选片断集合,利用片断拼接对候选片断进行拼接,以发现基因组中的重复序列。分析了算法的计算复杂度,构造了半仿真测试数据,对算法的测试结果表明了其有效性。     

基于Progressive多序列比对方法的求解多序列比对的启发式算法

在生物信息学研究中,生物序列比对问题占有重要的地位。多序列比对问题是一个NPC问题,由于时间和空间的限制不能够求出精确解。文中简要介绍了Feng和Doolittle提出的多序列比对算法的基本思想,并改进了该算法使之具有更好的比对精度。实验结果表明,新算法对解决一般的progressive多序列比对方法中遇到的局部最优问题有较好的效果。     

蛋白质序列中的关联规则发现及其应用

随着蛋白质序列-结构分析中使用的机器学习算法越来越复杂,其结果的解释和发现过程也随之复杂化,因此有必要寻找简单且理论上可靠的方法。通过引入原理简单、理论可靠、结果具有很强实际意义的关联规则发现算法,找到了蛋白质序列中数以万计的模式。结合实例演示了如何将这些模式应用于蛋白质序列分析中,如保守区域发现、二级结构预测等。同时根据这些结果构建了一个二级结构规则库和一种简单的二级结构预测算法,实验结果表明,约81%的二级结构可以由至少一条关联规则预测得到。     

脑电图复杂度分析中的粗粒化问题II.量化对复杂度计算的影响

在对生物医学信号时间序列进行复杂度分析时,粗粒化预处理有可能会造成丢失原始信号中所蕴含的信息,甚至在某些情况下根本改变原信号的动力学性质.用计算机计算时的量化过程也是一种粗粒化,因此也有这类问题.通过对近似熵和我们所定义的C0复杂度这两种复杂度在不同量化精度下对一些典型时间序列复杂度分析的比较研究,发现一般说来量化精度对复杂度分析的影响不是很大,仅当对原始信号进行二值化等极端情况下,才会显著改变原信号的复杂性.对脑电信号进行计算表明上述结论是实际可取的.     

基于局部茎搜索的RNA二级结构预测算法

RNA的二级结构预测是生物信息学中一个已经有30多年历史的经典问题,基于最小自由能模型(MFE)的优化算法是使用最为广泛的方法．但RNA结构中假结的存在使MFE问题理论上成为一个NP-hard问题,即使采用动态规划等优化算法也会面临时间复杂度高的困难,同时研究还发现,由于受RNA折叠动力学机制以及环境因素的影响,真实的RNA二级结构往往并不处于自由能最小状态．根据RNA折叠的特点,提出了一种启发式搜索算法来预测带假结的RNA二级结构．该算法以RNA的茎为基本单元,采用启发式搜索策略在茎的组合空间中搜索自由能最小并且出现频率最高的RNA二级结构,该算法不仅能显著降低搜索RNA二级结构的时间复杂度,还有助于弥补单纯依赖能量预测RNA二级结构的不足．在多种类型的RNA标准数据集上进行了检验,结果表明,该算法在预测的精度上优于目前国际上几个著名的RNA二级结构预测算法并且具有较高的运行效率．     

生物序列比对算法的研究现状

序列比对是生物信息学研究的一个重要工具,它在序列拼接、蛋白质结构预测、蛋白质结构功能分析、系统进化分析、数据库检索以及引物设计等问题的研究中被广泛使用。本文详细介绍了在生物信息学中常用的一些序列比对算法,比较了这些算法所需的计算复杂度,优缺点,讨论了各自的使用范围,并指出今后序列比对研究的发展方向。     

拽线法:一个构建系统发育树的新算法

这篇文章要讨论的拽线法（DL）是贪婪算法的一种。和Fitch—Margoliash（FM）一样,DL也是基于距离矩阵构建系统发育树,但是和FM算法相比,DL具有低复杂度、较高的容错性和准确度高的优点。当存在误差时,DL算法只是加大了不在同一个父节点下的基因序列的距离,但能够准确的判断序列的亲缘关系,进而得到完美的进化树拓扑结构;相比之下,FM算法让各个基因序列间的距离均摊了这种误差,从而有可能将本应该具有相同父节点的基因序列分到不同的分支。     

Speeding up the Consensus Clustering methodology for microarray data analysis

Background

Position-specific priors (PSP) have been used with success to boost EM and Gibbs sampler-based motif discovery algorithms. PSP information has been computed from different sources, including orthologous conservation, DNA duplex stability, and nucleosome positioning. The use of prior information has not yet been used in the context of combinatorial algorithms. Moreover, priors have been used only independently, and the gain of combining priors from different sources has not yet been studied.

Results

We extend RISOTTO, a combinatorial algorithm for motif discovery, by post-processing its output with a greedy procedure that uses prior information. PSP's from different sources are combined into a scoring criterion that guides the greedy search procedure. The resulting method, called GRISOTTO, was evaluated over 156 yeast TF ChIP-chip sequence-sets commonly used to benchmark prior-based motif discovery algorithms. Results show that GRISOTTO is at least as accurate as other twelve state-of-the-art approaches for the same task, even without combining priors. Furthermore, by considering combined priors, GRISOTTO is considerably more accurate than the state-of-the-art approaches for the same task. We also show that PSP's improve GRISOTTO ability to retrieve motifs from mouse ChiP-seq data, indicating that the proposed algorithm can be applied to data from a different technology and for a higher eukaryote.

Conclusions

The conclusions of this work are twofold. First, post-processing the output of combinatorial algorithms by incorporating prior information leads to a very efficient and effective motif discovery method. Second, combining priors from different sources is even more beneficial than considering them separately.     

Finding subtle motifs by branching from sample strings

Many motif finding algorithms apply local search techniques to a set of seeds. For example, GibbsDNA (Lawrence et al. 1993, Science, 262, 208-214) applies Gibbs sampling to random seeds, and MEME (Bailey and Elkan, 1994, Proceedings of the Second International Conference on Intelligent Systems for Molecular Biology (ISMB-94), 28-36) applies the EM algorithm to selected sample strings, i.e. substrings of the sample. In the case of subtle motifs, recent benchmarking efforts show that both random seeds and selected sample strings may never get close to the globally optimal motif. We propose a new approach which searches motif space by branching from sample strings, and implement this idea in both pattern-based and profile-based settings. Our PatternBranching and ProfileBranching algorithms achieve favorable results relative to other motif finding algorithms. Availability: http://www-cse.ucsd.edu/groups/bioinformatics/software.html     

iGibbs: improving Gibbs motif sampler for proteins by sequence clustering and iterative pattern sampling

The motif prediction problem is to predict short, conserved subsequences that are part of a family of sequences, and it is a very important biological problem. Gibbs is one of the first successful motif algorithms and it runs very fast compared with other algorithms, and its search behavior is based on the well-studied Gibbs random sampling. However, motif prediction is a very difficult problem and Gibbs may not predict true motifs in some cases. Thus, the authors explored a possibility of improving the prediction accuracy of Gibbs while retaining its fast runtime performance. In this paper, the authors considered Gibbs only for proteins, not for DNA binding sites. The authors have developed iGibbs, an integrated motif search framework for proteins that employs two previous techniques of their own: one for guiding motif search by clustering sequences and another by pattern refinement. These two techniques are combined to a new double clustering approach to guiding motif search. The unique feature of their framework is that users do not have to specify the number of motifs to be predicted when motifs occur in different subsets of the input sequences since it automatically clusters input sequences into clusters and predict motifs from the clusters. Tests on the PROSITE database show that their framework improved the prediction accuracy of Gibbs significantly. Compared with more exhaustive search methods like MEME, iGibbs predicted motifs more accurately and runs one order of magnitude faster.     

遗传算法在转录因子结合位点识别中的应用

遗传算法是模拟生物进化过程的计算模型,是一种全局优化搜索算法。将遗传算法与转录因子结合位点识别问题相结合的新方法,以一致性序列模型作为保守motif的描述模型,通过对motif序列与待测序列的比对问题进行编码,将其转化成搜索空间中的优化问题,利用遗传算法来搜索最优解,预测转录因子的结合位点。实验结果表明,这种新的方法是有效的,它在占用少量内存的情况下能够准确地识别出待测转录因子结合位点。     

Apples to apples: improving the performance of motif finders and their significance analysis in the Twilight Zone

MOTIVATION: Effective algorithms for finding relatively weak motifs are an important practical necessity while scanning long DNA sequences for regulatory elements. The success of such an algorithm hinges on the ability of its scoring function combined with a significance analysis test to discern real motifs from random noise. RESULTS: In the first half of the paper we show that the paradigm of relying on entropy scores and their E-values can lead to undesirable results when searching for weak motifs and we offer alternate approaches to analyzing the significance of motifs. In the second half of the paper we reintroduce a scoring function and present a motif-finder that optimizes it that are more effective in finding relatively weak motifs than other tools. AVAILABILITY: The GibbsILR motif finder is available at http://www.cs.cornell.edu/~keich.