基于量子进化算法的RNA序列-结构比对

多序列比对是计算分子生物学的经典问题,也是许多生物学研究的重要基础步骤．RNA作为生物大分子的一种,不同于蛋白质和DNA,其二级结构在进化过程中比初级序列更保守,因此要求在RNA序列比对中不仅要考虑序列信息,更要着重考虑二级结构信息．提出了一种基于量子进化算法的RNA多序列-结构比对程序,对RNA序列进行了量子编码,设计了考虑进结构信息的全交叉算子,提出了适合于进行RNA序列-结构比对的适应度函数,克服了传统进化算法收敛速度慢和早熟问题．在标准数据库上的测试,证实了方法的有效性．     

MATLAB 7.X生物信息工具箱的应用——序列比对(二)

序列比对是基因序列分析中的一项重要工作.本文以人和鼠的基因为对象,介绍MATLAB 7.X生物信息工具箱中的序列比对方法,内容包括从数据库获取序列信息,查找序列的开放阅读框,将核苷酸序列转换为氨基酸序列,绘制比较两氨基酸序列的散点图,用Needleman-Wunsch算法和Smith-Waterman算法进行比对,以及计算两序列的同一性.     

霍乱弧菌N16961超级整合子重复序列及基因盒分析

目的:确定O1群El Tor型霍乱弧菌N16961超级整合子(SI)中霍乱弧菌重复序列(VCR)的序列特点,以及VCR和基因盒的数量及位置。方法:用局部序列比对软件BLAST将VCR参考序列与霍乱弧菌N16961的Ⅱ号染色体进行比对,用Artemis Comparison Tool查看比对结果获得比对区域的位置信息,并采用perl语言脚本获得霍乱弧菌N16961的Ⅱ号染色体VCR相应区域的序列;用全局比对软件Clustal W将上一步获得的所有VCR序列进行多序列比对,采用perl语言脚本处理比对结果获得一致性序列;用MEGA4.0软件查看多序列比对结果,并采用perl语言脚本计算各位置变异频率,据此分析霍乱弧菌N16961的Ⅱ号染色体上VCR和基因盒的特点。结果:在N16961的超级整合子中有158个VCR,其核苷酸长度为117～124 bp;其一致性序列有126个核苷酸,其中37个为保守核苷酸位点,89个为可变核苷酸位点;139个VCR与相邻的VCR之间至少有1个基因,19个VCR相互之间没有任何基因;N16961的SI中共存在146个基因盒,基因盒大小为390～5924 bp不等,每个基因盒中整合的基因数目为1～9个不等。结论:建立了SI中VCR和基因盒的分析流程,分析了SI中VCR的保守及变异位点,明确了霍乱弧菌N16961的SI中VCR和基因盒的信息,为霍乱弧菌和其他细菌中SI的研究提供了分析基础。     

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

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

参数序列比对算法研究

序列比对是生物信息学中的一项重要任务,通过序列比对可以发现生物序列中的功能、结构和进化的信息。序列比对结果的生物学意义与所选择的匹配、不匹配、插入和删除以及空隙的罚分函数密切相关。现介绍一种参数序列比对方法,该方法把最佳比对作为权值和罚分的函数,可以系统地得到参数的选择对最佳比对结果的影响。然后将其应用于RNA序列比对,分析不同的参数选择对序列比对结果的影响。最后指出参数序列比对算法的应用以及未来的发展方向。     

基于云计算的蛋白质折叠模拟计算

为了解决生物信息学中蛋白质折叠模拟计算的速度慢和软件老旧的问题,提出了基于云计算的蛋白质折叠并行化算法Cloud_PERM。分析了PERM算法的运行流程及其面向MapReduce的子任务划分方式。Cloud_PERM算法实现采用Hadoop云计算环境作为工作平台,其蛋白质序列数据的存储与管理、子任务调度及工作单元的执行都由MapReduce规范来透明的完成;实验结果表明:Cloud_PERM比PERM串行计算具有更快的计算速度,在吞吐量和可扩展性上也有明显的优势。Cloud_PERM可以使生物科研人员节省很多时间与精力,有益于新型蛋白质结构预测与生物特性的研究。     

GPGPU加速生物序列比对研究进展

序列比对是生物信息学中最常用和最经典的研究手段。生物序列比对需要有强大计算能力的硬件支撑,而近年快速发展起来的GPGPU正好可堪此任。本文首先介绍GPGPU的发展过程,进而讲述GPGPU硬件设备与其编程环境,然后对GPGPU做科学计算时需要的数学库函数做一介绍,最后综述近年来国内外基于GPGPU的生物序列比对软件和相关研究工作,并总结和展望其辉煌前景。     

ortholog ——— 概念、生物信息预测方法和数据库

orthologs指起源于不同物种的最近的共同祖先的一些基因。orthologous的基因,具有相近甚至相同的功能,由相似的途径调控,在不同的物种中扮演相似甚至相同的角色,因此在基因组序列的注释中,是最可靠的选择。orthologs的生物信息预测方法主要有两类：系统发生方法和序列比对方法。这两类方法都是基于序列的相似性,但又各有特点。系统发生方法通过重建系统发生树来预测orthologs,因此在概念上比较精确,但难于自动化,运算量也很大。序列比对方法在概念上比较粗糙,但简单实用,运算量相对较小,因此得到了较广泛的应用。     

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

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

蛋白质序列的矩阵图谱表达

基于经典HP模型,利用蛋白质序列的矩阵图谱表达法(MGR)及数值刻画的思想提出了一种新的蛋白质序列的比对方法,通过观察蛋白质序列的数值刻画图及计算两蛋白质序列之间的欧氏距离d,对木聚糖酶两家族的蛋白质序列进行了相似性分析.发现被划分为同一木聚糖酶家族的蛋白质序列之间的相似性更大,而且蛋白质序列的相似性程度与分子大小、结构和分子进化相关.     

Multiple alignment by sequence annealing

MOTIVATION: We introduce a novel approach to multiple alignment that is based on an algorithm for rapidly checking whether single matches are consistent with a partial multiple alignment. This leads to a sequence annealing algorithm, which is an incremental method for building multiple sequence alignments one match at a time. Our approach improves significantly on the standard progressive alignment approach to multiple alignment. RESULTS: The sequence annealing algorithm performs well on benchmark test sets of protein sequences. It is not only sensitive, but also specific, drastically reducing the number of incorrectly aligned residues in comparison to other programs. The method allows for adjustment of the sensitivity/specificity tradeoff and can be used to reliably identify homologous regions among protein sequences. AVAILABILITY: An implementation of the sequence annealing algorithm is available at http://bio.math.berkeley.edu/amap/     

An iterative method for faster sum-of-pairs multiple sequence alignment

MOTIVATION: Multiple sequence alignment is an important tool in computational biology. In order to solve the task of computing multiple alignments in affordable time, the most commonly used multiple alignment methods have to use heuristics. Nevertheless, the computation of optimal multiple alignments is important in its own right, and it provides a means of evaluating heuristic approaches or serves as a subprocedure of heuristic alignment methods. RESULTS: We present an algorithm that uses the divide-and-conquer alignment approach together with recent results on search space reduction to speed up the computation of multiple sequence alignments. The method is adaptive in that depending on the time one wants to spend on the alignment, a better, up to optimal alignment can be obtained. To speed up the computation in the optimal alignment step, we apply the alpha(*) algorithm which leads to a procedure provably more efficient than previous exact algorithms. We also describe our implementation of the algorithm and present results showing the effectiveness and limitations of the procedure.     

Super pairwise alignment (SPA): an efficient approach to global alignment for homologous sequences.

Sequence analysis is the basis of bioinformatics, while sequence alignment is a fundamental task for sequence analysis. The widely used alignment algorithm, Dynamic Programming, though generating optimal alignment, takes too much time due to its high computation complexity O(N(2)). In order to reduce computation complexity without sacrificing too much accuracy, we have developed a new approach to align two homologous sequences. The new approach presented here, adopting our novel algorithm which combines the methods of probabilistic and combinatorial analysis, reduces the computation complexity to as low as O(N). The computation speed by our program is at least 15 times faster than traditional pairwise alignment algorithms without a loss of much accuracy. We hence named the algorithm Super Pairwise Alignment (SPA). The pairwise alignment execution program based on SPA and the detailed results of the aligned sequences discussed in this article are available upon request.     

Mango: multiple alignment with N gapped oligos

Multiple sequence alignment is a classical and challenging task. The problem is NP-hard. The full dynamic programming takes too much time. The progressive alignment heuristics adopted by most state-of-the-art works suffer from the "once a gap, always a gap" phenomenon. Is there a radically new way to do multiple sequence alignment? In this paper, we introduce a novel and orthogonal multiple sequence alignment method, using both multiple optimized spaced seeds and new algorithms to handle these seeds efficiently. Our new algorithm processes information of all sequences as a whole and tries to build the alignment vertically, avoiding problems caused by the popular progressive approaches. Because the optimized spaced seeds have proved significantly more sensitive than the consecutive k-mers, the new approach promises to be more accurate and reliable. To validate our new approach, we have implemented MANGO: Multiple Alignment with N Gapped Oligos. Experiments were carried out on large 16S RNA benchmarks, showing that MANGO compares favorably, in both accuracy and speed, against state-of-the-art multiple sequence alignment methods, including ClustalW 1.83, MUSCLE 3.6, MAFFT 5.861, ProbConsRNA 1.11, Dialign 2.2.1, DIALIGN-T 0.2.1, T-Coffee 4.85, POA 2.0, and Kalign 2.0. We have further demonstrated the scalability of MANGO on very large datasets of repeat elements. MANGO can be downloaded at http://www.bioinfo.org.cn/mango/ and is free for academic usage.     

Probabilistic phylogenetic inference with insertions and deletions

A fundamental task in sequence analysis is to calculate the probability of a multiple alignment given a phylogenetic tree relating the sequences and an evolutionary model describing how sequences change over time. However, the most widely used phylogenetic models only account for residue substitution events. We describe a probabilistic model of a multiple sequence alignment that accounts for insertion and deletion events in addition to substitutions, given a phylogenetic tree, using a rate matrix augmented by the gap character. Starting from a continuous Markov process, we construct a non-reversible generative (birth-death) evolutionary model for insertions and deletions. The model assumes that insertion and deletion events occur one residue at a time. We apply this model to phylogenetic tree inference by extending the program dnaml in phylip. Using standard benchmarking methods on simulated data and a new "concordance test" benchmark on real ribosomal RNA alignments, we show that the extended program dnamlepsilon improves accuracy relative to the usual approach of ignoring gaps, while retaining the computational efficiency of the Felsenstein peeling algorithm.     

A strategy for the rapid multiple alignment of protein sequences. Confidence levels from tertiary structure comparisons

An algorithm is presented for the multiple alignment of protein sequences that is both accurate and rapid computationally. The approach is based on the conventional dynamic-programming method of pairwise alignment. Initially, two sequences are aligned, then the third sequence is aligned against the alignment of both sequences one and two. Similarly, the fourth sequence is aligned against one, two and three. This is repeated until all sequences have been aligned. Iteration is then performed to yield a final alignment. The accuracy of sequence alignment is evaluated from alignment of the secondary structures in a family of proteins. For the globins, the multiple alignment was on average 99% accurate compared to 90% for pairwise comparison of sequences. For the alignment of immunoglobulin constant and variable domains, the use of many sequences yielded an alignment of 63% average accuracy compared to 41% average for individual variable/constant alignments. The multiple alignment algorithm yields an assignment of disulphide connectivity in mammalian serotransferrin that is consistent with crystallographic data, whereas pairwise alignments give an alternative assignment.     

A sequence alignment algorithm with an arbitrary gap penalty function.

An algorithm for aligning biological sequences is presented that is an adaptation of the sequence generating function approach used in the statistical mechanics of biopolymers. This algorithm uses recursion relationships developed from a partition function formalism of alignment probabilities. It is implemented within a dynamic programming format that closely resembles the forward algorithm used in hidden Markov models (HMM). The algorithm aligns sequences or structures according to the statistically dominant alignment path and will be referred to as the SDP algorithm. An advantage of this method over previous ones is that it allows more complicated and physically realistic gap penalty functions to be incorporated into the algorithm in a facile manner. The performance of this algorithm in a case study of aligning the heavy and light chain from the variable region of an immunoglobulin is investigated.     

Pseudo-periodic partitions of biological sequences

MOTIVATION: Algorithm development for finding typical patterns in sequences, especially multiple pseudo-repeats (pseudo-periodic regions), is at the core of many problems arising in biological sequence and structure analysis. In fact, one of the most significant features of biological sequences is their high quasi-repetitiveness. Variation in the quasi-repetitiveness of genomic and proteomic texts demonstrates the presence and density of different biologically important information. It is very important to develop sensitive automatic computational methods for the identification of pseudo-periodic regions of sequences through which we can infer, describe and understand biological properties, and seek precise molecular details of biological structures, dynamics, interactions and evolution. RESULTS: We develop a novel, powerful computational tool for partitioning a sequence to pseudo-periodic regions. The pseudo-periodic partition is defined as a partition, which intuitively has the minimal bias to some perfect-periodic partition of the sequence based on the evolutionary distance. We devise a quadratic time and space algorithm for detecting a pseudo-periodic partition for a given sequence, which actually corresponds to the shortest path in the main diagonal of the directed (acyclic) weighted graph constructed by the Smith-Waterman self-alignment of the sequence. We use several typical examples to demonstrate the utilization of our algorithm and software system in detecting functional or structural domains and regions of proteins. A big advantage of our software program is that there is a parameter, the granularity factor, associated with it and we can freely choose a biological sequence family as a training set to determine the best parameter. In general, we choose all repeats (including many pseudo-repeats) in the SWISS-PROT amino acid sequence database as a typical training set. We show that the granularity factor is 0.52 and the average agreement accuracy of pseudo-periodic partitions, detected by our software for all pseudo-repeats in the SWISS-PROT database, is as high as 97.6%.     

Bayesian restoration of a hidden Markov chain with applications to DNA sequencing.

Hidden Markov models (HMMs) are a class of stochastic models that have proven to be powerful tools for the analysis of molecular sequence data. A hidden Markov model can be viewed as a black box that generates sequences of observations. The unobservable internal state of the box is stochastic and is determined by a finite state Markov chain. The observable output is stochastic with distribution determined by the state of the hidden Markov chain. We present a Bayesian solution to the problem of restoring the sequence of states visited by the hidden Markov chain from a given sequence of observed outputs. Our approach is based on a Monte Carlo Markov chain algorithm that allows us to draw samples from the full posterior distribution of the hidden Markov chain paths. The problem of estimating the probability of individual paths and the associated Monte Carlo error of these estimates is addressed. The method is illustrated by considering a problem of DNA sequence multiple alignment. The special structure for the hidden Markov model used in the sequence alignment problem is considered in detail. In conclusion, we discuss certain interesting aspects of biological sequence alignments that become accessible through the Bayesian approach to HMM restoration.