基于图形硬件加速的生物序列比对算法研究

生物序列比对是生物信息学的基础,是当今功能基因组学研究中最常用、最重要的研究方法之一。本文对各类序列比对算法优缺点进行分析,对图形硬件的优势进行挖掘。在此基础上,将各类序列比对算法中准确性最高的动态规划算法予以实现,并将其映射到图形硬件上,以实现算法加速。通过实例进行性能评测,结果表明该加速算法在保证比对准确性的同时,能较大地提高比对速度。     

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

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

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

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

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

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

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

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

系统发育研究中多重序列比对常见问题分析

在简单介绍序列比对原理的基础上,结合自己的经验,对经常出现的问题进行总结分析,以期在将来的序列比对工作中避免此类问题的发生.     

动态规划算法对GenoCAD设计结果的优化

GenoCAD(www.genocad.com)是一种基于Web的免费合成生物学设计软件,用它可以进行表达载体及人工基因网络设计。持续点击代表各种合成生物学标准“零件”的图标,以一种语法进行设计,最后就可以得到由数十个功能片段组成的复杂质粒载体。但是在GenoCAD中,每一类的合成生物学标准“零件”数量众多。随着这些标准“零件”的不断开发,其数量也在进一步增加,目前选择合适的“零件”组装成功能性的质粒载体费时费力并且容易发生错误。在进行载体设计的最后阶段,从众多的“零件”中选择合适的往往比较困难。为解决这一问题,本文采用了自然语言处理的统计语言模型,它最初用于自然语言识别,用来估算一组词串成为一个正确语句的概率的大小。本文最后以该模型为基础应用动态规划算法优化质粒载体设计,从众多的选项中找出最优者。利用这一方法可以减少进行生物学实验的冗余操作,从而减少载体构建过程中的花费。     

基于结构信息的RNA多序列比对

多序列比对是生物信息学中重要的基础研究内容,对各种RNA序列分析方法而言,这也是非常重要的一步。不像DNA和蛋白质,许多功能RNA分子的序列保守性要远差于其结构的保守性,因此,对RNA的分析研究要求其多序列比对不仅要考虑序列信息,而且要充分考虑到其结构信息。本文提出了一种考虑了结构信息的同源RNA多序列比对算法,它先利用热力学方法计算出每条序列的配对概率矩阵,得到结构信息,由此构造各条序列的结构信息矢量,结合传统序列比对方法,提出优化目标函数,采用动态规划算法和渐进比对得到最后的多序列比对。试验证实该方法的有效性。     

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

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

生物序列局部联配中的马赛克问题的一种解决方法

生物信息学中，Smith Waterman算法用于同源长序列的局部联配时，经常会出现马赛克问题（相似度很低的保守区域夹在两个相似度很高的区域中间）。在分析问题成因的基础上，提出利用动态加速扣分策略解决马赛克问题，即在计算得分矩阵的过程中．如果存在保守区域，则加大扣分的力度，争取在离开保守区域前让得分为0，从而将保守区域切断。实验结果表明，动态加速扣分策略顺利解决了序列局部联配中的马赛克问题，并且没有显著增加算法的时间复杂度和空间复杂度。     

Prediction of protein secondary structure based on residue pair types and conformational states using dynamic programming algorithm

We have used a statistical approach for protein secondary structure prediction based on information theory and simultaneously taking into consideration pairwise residue types and conformational states. Since the prediction of residue secondary structure by one residue window sliding make ambiguity in state prediction, we used a dynamic programming algorithm to find the path with maximum score. A score system for residue pairs in particular conformations is derived for adjacent neighbors up to ten residue apart in sequence. The three state overall per-residue accuracy, Q3, of this method in a jackknife test with dataset created from PDBSELECT is more than 70%.     

参数序列比对算法研究

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

A rapid protein structure alignment algorithm based on a text modeling technique

Structural alignment of proteins is widely used in various fields of structural biology. In order to further improve the quality of alignment, we describe an algorithm for structural alignment based on text modelling techniques. The technique firstly superimposes secondary structure elements of two proteins and then, models the 3D-structure of the protein in a sequence of alphabets. These sequences are utilized by a step-by-step sequence alignment procedure to align two protein structures. A benchmark test was organized on a set of 200 non-homologous proteins to evaluate the program and compare it to state of the art programs, e.g. CE, SAL, TM-align and 3D-BLAST. On average, the results of all-against-all structure comparison by the program have a competitive accuracy with CE and TM-align where the algorithm has a high running speed like 3D-BLAST.     

BCL::Align—Sequence alignment and fold recognition with a custom scoring function online

BCL::Align is a multiple sequence alignment tool that utilizes the dynamic programming method in combination with a customizable scoring function for sequence alignment and fold recognition. The scoring function is a weighted sum of the traditional PAM and BLOSUM scoring matrices, position-specific scoring matrices output by PSI-BLAST, secondary structure predicted by a variety of methods, chemical properties, and gap penalties. By adjusting the weights, the method can be tailored for fold recognition or sequence alignment tasks at different levels of sequence identity. A Monte Carlo algorithm was used to determine optimized weight sets for sequence alignment and fold recognition that most accurately reproduced the SABmark reference alignment test set. In an evaluation of sequence alignment performance, BCL::Align ranked best in alignment accuracy (Cline score of 22.90 for sequences in the Twilight Zone) when compared with Align-m, ClustalW, T-Coffee, and MUSCLE. ROC curve analysis indicates BCL::Align's ability to correctly recognize protein folds with over 80% accuracy. The flexibility of the program allows it to be optimized for specific classes of proteins (e.g. membrane proteins) or fold families (e.g. TIM-barrel proteins). BCL::Align is free for academic use and available online at http://www.meilerlab.org/.     

Efficient clustering in collaborative filtering recommender system: Hybrid method based on genetic algorithm and gravitational emulation local search algorithm

The ultimate goal of the Recommender System (RS) is to offer a proposal that is very close to the user's real opinion. Data clustering can be effective in increasing the accuracy of production proposals by the RS. In this paper, single-objective hybrid evolutionary approach is proposed for clustering items in the offline collaborative filtering RS. This method, after generating a population of randomized solutions, at each iteration, improves the population of solutions first by Genetic Algorithm (GA) and then by using the Gravitational Emulation Local Search (GELS) algorithm. Simulation results on standard datasets indicate that although the proposed hybrid meta-heuristic algorithm requires a relatively high run time, it can lead to more appropriate clustering of existing data and thus improvement of the Mean Absolute Error (MAE), Root Mean Square Error (RMSE) and Coverage criteria.     

Performance evaluation of a new algorithm for the detection of remote homologs with sequence comparison

A detailed analysis of the performance of hybrid, a new sequence alignment algorithm developed by Yu and coworkers that combines Smith Waterman local dynamic programming with a local version of the maximum-likelihood approach, was made to access the applicability of this algorithm to the detection of distant homologs by sequence comparison. We analyzed the statistics of hybrid with a set of nonhomologous protein sequences from the SCOP database and found that the statistics of the scores from hybrid algorithm follows an Extreme Value Distribution with lambda approximately 1, as previously shown by Yu et al. for the case of artificially generated sequences. Local dynamic programming was compared to the hybrid algorithm by using two different test data sets of distant homologs from the PFAM and COGs protein sequence databases. The studies were made with several score functions in current use including OPTIMA, a new score function originally developed to detect remote homologs with the Smith Waterman algorithm. We found OPTIMA to be the best score function for both both dynamic programming and the hybrid algorithms. The ability of dynamic programming to discriminate between homologs and nonhomologs in the two sets of distantly related sequences is slightly better than that of hybrid algorithm. The advantage of producing accurate score statistics with only a few simulations may overcome the small differences in performance and make this new algorithm suitable for detection of homologs in conjunction with a wide range of score functions and gap penalties.     

Factors influencing route choice by avian migrants: a dynamic programming model of Pacific brant migration

We used stochastic dynamic programming to investigate a spectacular migration strategy in the black brant Branta bernicla nigricans, a species of goose. Black brant migration is well suited for theoretical analysis since there are a number of existing strategies that easily can be compared. In early autumn, almost the entire population of the black brant gathers at Izembek Lagoon on the Alaska Peninsula to stage and refuel before the southward migration. There are at least three distinct strategies, with most geese making a spectacular direct migration more than 5000km across the Gulf of Alaska to their wintering grounds in southern Baja California or mainland Mexico. This is a potentially dangerous strategy since foraging is not possible during the overseas passage. Some individuals instead use shorter flights to make a detour along the coast, a longer route that all individuals use for northwards migration in spring. Since flight costs accelerate with increasing body mass, migration by short flights is energetically cheaper than long-distance flights. A small but increasing part of the population has recently begun to winter at Izembek. We investigated this migration under two different suppositions using a dynamic state variable model. First, if the geese are free to make a strategic choice, under what assumptions should they prefer direct migration and under what assumptions should they prefer detour migration/winter residency? Second, provided that the dominating direct migration strategy is optimal, what conditions will force the geese to go for detour migration/winter residency? In the second case the geese may try to follow an optimal direct migration strategy, but stochastic events may force them to choose a suboptimal policy. We also simulated possible effects of global warming. The model suggests that the fuel level at arrival in Izembek and fuel gain rates are key factors and that tail winds must have been reliable in the past, otherwise direct migration could not have evolved. It also suggests that a change to milder winters may promote an unexpectedly abrupt change from long-distance to short-distance migration or winter residency. Finally, it produced a number of predictions that might be testable in the field.     

A substitution matrix for structural alphabet based on structural alignment of homologous proteins and its applications

Analysis of protein structures based on backbone structural patterns known as structural alphabets have been shown to be very useful. Among them, a set of 16 pentapeptide structural motifs known as protein blocks (PBs) has been identified and upon which backbone model of most protein structures can be built. PBs allows simplification of 3D space onto 1D space in the form of sequence of PBs. Here, for the first time, substitution probabilities of PBs in a large number of aligned homologous protein structures have been studied and are expressed as a simplified 16 x 16 substitution matrix. The matrix was validated by benchmarking how well it can align sequences of PBs rather like amino acid alignment to identify structurally equivalent regions in closely or distantly related proteins using dynamic programming approach. The alignment results obtained are very comparable to well established structure comparison methods like DALI and STAMP. Other interesting applications of the matrix have been investigated. We first show that, in variable regions between two superimposed homologous proteins, one can distinguish between local conformational differences and rigid-body displacement of a conserved motif by comparing the PBs and their substitution scores. Second, we demonstrate, with the example of aspartic proteinases, that PBs can be efficiently used to detect the lobe/domain flexibility in the multidomain proteins. Lastly, using protein kinase as an example, we identify regions of conformational variations and rigid body movements in the enzyme as it is changed to the active state from an inactive state.