马赛病毒上海分离株的分离和全基因组分析

马赛病毒是一种感染棘阿米巴的大型双链DNA病毒,在世界各地都有这类病毒的分离报道。本研究从上海地区环境土壤样品中分离了一株马赛病毒。该病毒可以高效地感染棘阿米巴,病毒颗粒呈典型的二十面体结构,直径大约在0.25μm,基因组为368kb。病毒基因组DNA序列分析结果表明,该病毒属马赛病毒科的A系马赛病毒,与欧洲、澳大利亚等地报道的病毒株相似度极高。通过与分离自全球不同地区的另外四株马赛病毒比较发现大部分病毒基因都处于负选择,说明马赛病毒的核心基因非常保守并且足以支持病毒在不同地区的适应性。     

新型图形硬件支持下的动态规划局部比对算法加速研究

为探索准确、高效、低成本、通用性并存的生物序列局部比对方法。将点阵图算法、启发式算法等各种序列局部比对算法中准确性最高的动态规划局部比对算法在计算机中实现,并通过流式模型将其映射到图形硬件上以实现算法加速,再通过实例比对搜索数据库完成比对时间和每秒百万次格点更新（MCUPS）性能值评测。结果表明,该加速算法在保证比对准确性的同时,能显著提升比对速度。与目前最快的启发式算法相比,比对平均加速为14.5倍,最高加速可达22.9倍。     

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

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

基于DTW距离的DNA序列相似性分析

在DNA序列相似性的研究中,通常采用的动态规划算法对空位罚分函数缺乏理论依据而带有主观性,从而取得不同的结果,本文提出了一种基于DTW（Dynamic Time Warping,动态时间弯曲）距离的DNA序列相似性度量方法可以解决这一问题．通过DNA序列的图形表示把DNA序列转化为时间序列,然后计算DTW距离来度量序列相似度以表征DNA序列属性,得到能够比较DNA序列相似性度量方法,并用这个方法比较分析了七种东亚钳蝎神经毒素（Buthusmartensi Karsch neurotoxin）基因序列的相似性,验证了该度量方法的有效性和准确性．     

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

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

新型粒子群优化算法在多序列联配中的应用

将粒子群优化算法应用于序列联配,提出了一种改进的粒子群优化算法,该算法在粒子群的进化过程中根据粒子的适应值动态地调整粒子群的惯性权重与粒子群飞行速度范围,提高了算法的收敛速度和收敛精度;针对PSO算法可能出现的早熟现象,引入重新初始化机制,增强了算法的搜索能力,实验表明该算法是有效的。     

线性变化参数的粒子群优化算法

针对粒子群算法容易陷入局部最优点,收敛较慢等问题,在不增加算法复杂度的前提下,提出了线性变化参数的粒子群优化(LCPPSO)算法.LCPPSO算法通过对粒子的速度更新方式进行调整,采用惯性权重和加速因子c1的值线性递减,c_2线性递增的策略加强算法的收敛能力.通过经典测试函数进行仿真实验,与标准PSO及其他改进的PSO算法进行对比,实验结果表明LCPPSO算法实现更加简单,需要调整的参数更少,不仅提高了收敛速度,也具有更好的跳出局部最优能力.     

基于HMM的齿肋赤藓VOZ转录因子的预测与分析

VOZ(Vascular plant One Zinc finger protein)作为与植物的进化与发育密切相关的基因,在极端耐旱荒漠苔藓植物齿肋赤藓(Syntrichia caninervis)中对VOZ基因进行挖掘和分析有利于更好的揭示VOZ基因的进化关系,且可作为抗逆基因进行更为深入的分子生物学研究。在VOZ转录因子蛋白中VOZ-domain是一个保守的DNA结合结构功能域,利用VOZ-domain多序列联配构建隐马尔可夫模型序列谱能够很好的进行家族成员的识别和预测。利用拟南芥、小立碗藓和水稻等植物已知的转录因子序列信息构建HMM序列谱模型,对荒漠苔藓齿肋赤藓转录组进行比对搜索。最终得到一条新的齿肋赤藓VOZ转录因子ScVOZ1(NCBI/EBI检索号:HG764415),序列长度为1 495 bp,具有完整的VOZ-domain结构域。生物信息学分析表明其具有转录调控功能和核定位潜能。多序列比对、进化和保守基序分析表明,ScVOZ1蛋白序列与小立碗藓VOZ家族和拟南芥AtVOZ1相似度较高。本研究为进一步研究ScVOZ1基因的功能以及其进化起源奠定了基础。     

基因组序列的大尺度同源分析

本文报道了一种大尺度基因组现源分析方法,利用散列检索技术和稀疏动态规划算法实现快速的序列比较。经植物叶绿体基因组,哺乳类Ｔ细胞受体基因哺乳类眼γ－晶状体基因簇等实例应用,证明了此方法可以十分快捷地提供足够精确的联配结果,可实际应用基因组序列分析。     

利用序列保守模体和局部构象信息预测转录因子结合位点

转录因子结合位点的计算预测是研究基因转录调控的重要环节,但常用的位置特异得分矩阵方法预测特异性偏低.通过深入分析结合位点的生物特征,提出了一种综合利用序列保守模体和局部构象信息的结合位点预测方法,以极大相关得分矩阵作为保守模体的描述模型,并根据二苷参数模型计算位点序列的局部构象,将两类信息得分组合为多维特征向量,在二次判别分析的框架下进行训练和滑动预测.预测过程中还引入了位置信息量以优化似然得分和过滤备选结果.针对大肠杆菌CRP和Fis结合位点数据的留一法测试结果表明,描述模型的改进和多种信息的融合能有效地改善预测方法的性能,大幅度提高特异性.     

A new approach to sequence comparison: normalized sequence alignment

The Smith-Waterman algorithm for local sequence alignment is one of the most important techniques in computational molecular biology. This ingenious dynamic programming approach was designed to reveal the highly conserved fragments by discarding poorly conserved initial and terminal segments. However, the existing notion of local similarity has a serious flaw: it does not discard poorly conserved intermediate segments. The Smith-Waterman algorithm finds the local alignment with maximal score but it is unable to find local alignment with maximum degree of similarity (e.g. maximal percent of matches). Moreover, there is still no efficient algorithm that answers the following natural question: do two sequences share a (sufficiently long) fragment with more than 70% of similarity? As a result, the local alignment sometimes produces a mosaic of well-conserved fragments artificially connected by poorly-conserved or even unrelated fragments. This may lead to problems in comparison of long genomic sequences and comparative gene prediction as recently pointed out by Zhang et al. (Bioinformatics, 15, 1012-1019, 1999). In this paper we propose a new sequence comparison algorithm (normalized local alignment ) that reports the regions with maximum degree of similarity. The algorithm is based on fractional programming and its running time is O(n2log n). In practice, normalized local alignment is only 3-5 times slower than the standard Smith-Waterman algorithm.     

A new algorithm for best subsequence alignments with application to tRNA-rRNA comparisons

The algorithm of Smith & Waterman for identification of maximally similar subsequences is extended to allow identification of all non-intersecting similar subsequences with similarity score at or above some preset level. The resulting alignments are found in order of score, with the highest scoring alignment first. In the case of single gaps or multiple gaps weighted linear with gap length, the algorithm is extremely efficient, taking very little time beyond that of the initial calculation of the matrix. The algorithm is applied to comparisons of tRNA-rRNA sequences from Escherichia coli. A statistical analysis is important for proper evaluation of the results, which differ substantially from the results of an earlier analysis of the same sequences by Bloch and colleagues.     

Adaptive Smith–Waterman residue match seeding for protein structural alignment

The POLYFIT rigid‐body algorithm for automated global pairwise and multiple protein structural alignment is presented. Smith–Waterman local alignment is used to establish a set of seed equivalences that are extended using Needleman–Wunsch dynamic programming techniques. Structural and functional interaction constraints provided by evolution are encoded as one‐dimensional residue physical environment strings for alignment of highly structurally overlapped protein pairs. Local structure alignment of more distantly related pairs is carried out using rigid‐body conformational matching of 15‐residue fragments, with allowance made for less stringent conformational matching of metal‐ion and small molecule ligand‐contact, disulphide bridge, and cis‐peptide correspondences. Protein structural plasticity is accommodated through the stepped adjustment of a single empirical distance parameter value in the calculation of the Smith–Waterman dynamic programming matrix. Structural overlap is used both as a measure of similarity and to assess alignment quality. Pairwise alignment accuracy has been benchmarked against that of 10 widely used aligners on the Sippl and Wiederstein set of difficult pairwise structure alignment problems, and more extensively against that of Matt, SALIGN, and MUSTANG in pairwise and multiple structural alignments of protein domains with low shared sequence identity in the SCOP‐ASTRAL 40% compendium. The results demonstrate the advantages of POLYFIT over other aligners in the efficient and robust identification of matching seed residue positions in distantly related protein targets and in the generation of longer structurally overlapped alignment lengths. Superposition‐based application areas include comparative modeling and protein and ligand design. POLYFIT is available on the Web server at http://polyfit.insa‐toulouse.fr . Proteins 2013; 81:1823–1839. © 2013 Wiley Periodicals, Inc.     

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.     

SANA: an algorithm for sequential and non-sequential protein structure alignment

Protein structure alignment algorithms play an important role in the studies of protein structure and function. In this paper, a novel approach for structure alignment is presented. Specifically, core regions in two protein structures are first aligned by identifying connected components in a network of neighboring geometrically compatible aligned fragment pairs. The initial alignments then are refined through a multi-objective optimization method. The algorithm can produce both sequential and non-sequential alignments. We show the superior performance of the proposed algorithm by the computational experiments on several benchmark datasets and the comparisons with the well-known structure alignment algorithms such as DALI, CE and MATT. The proposed method can obtain accurate and biologically significant alignment results for the case with occurrence of internal repeats or indels, identify the circular permutations, and reveal conserved functional sites. A ranking criterion of our algorithm for fold similarity is presented and found to be comparable or superior to the Z-score of CE in most cases from the numerical experiments. The software and supplementary data of computational results are available at .     

Computer methods for locating kinetoplastid cryptogenes.

RNA editing in the mitochondria of kinetoplastid protoza involves the insertion and/or deletion of precise numbers of uridine residues at precise locations in the numbers of uridine residues at precise locations in the transcribed RNA of certain genes. These genes are known as cryptogenes. In this paper we study computational algorithms to search for unknown cryptogenes and for the associated templates for insertion of uridines, gRNA sequences. The pairwise similarity search algorithm of Smith and Waterman (1) is modified to study this problem. The algorithm searches for unknown gRNAs given the cryptogene sequence. The method is tested on 4 known cryptogenes from L.tarentolae which are known to have 7 associated gRNAs. The statistical distribution of the longest gRNA when comparing random sequences is derived. Finally we develop an algorithm to search for cryptogenes using amino acid sequences from related proteins.     

Post-processing long pairwise alignments

MOTIVATION: The local alignment problem for two sequences requires determining similar regions, one from each sequence, and aligning those regions. For alignments computed by dynamic programming, current approaches for selecting similar regions may have potential flaws. For instance, the criterion of Smith and Waterman can lead to inclusion of an arbitrarily poor internal segment. Other approaches can generate an alignment scoring less than some of its internal segments. RESULTS: We develop an algorithm that decomposes a long alignment into sub-alignments that avoid these potential imperfections. Our algorithm runs in time proportional to the original alignment's length. Practical applications to alignments of genomic DNA sequences are described.     

Comparative Analysis of Nucleic Acid and Protein Primary Structures

The review considers the original works on the primary structure of biopolymers carried out from 1983 to 2003. Most works were supported by the Russian program Human Genome and earlier similar Russian programs. Little-known publications of 1983–1993 and recent unpublished results are described in detail. In the field of genome comparisons, these concern the OWEN hierarchic algorithm aligning syntenic regions of two genome sequences. The resulting global alignment is obtained as an ordered chain of local similarities. Alignment of megabase sequences takes several minutes. The concept of local similarity conflicts is generalized to multiple comparisons. New algorithms aligning protein sequences are described and compared with the Smith–Waterman algorithm, which is now most accurate. The ANCHOR hierarchic algorithm generates alignments of much the same accuracy and is twice as rapid as the Smith–Waterman one. The STRSWer algorithm takes into account the secondary structures of proteins under study. With the secondary structures predicted using the PSI-PRED software for pairs of proteins having 10–30% similarity, the average accuracy of alignments generated by STRSWer is 15% higher than that achieved with the Smith–Waterman algorithm.     

Seed selection strategy in global network alignment without destroying the entire structures of functional modules

Background

Network alignment is one of the most common biological network comparison methods. Aligning protein-protein interaction (PPI) networks of different species is of great important to detect evolutionary conserved pathways or protein complexes across species through the identification of conserved interactions, and to improve our insight into biological systems. Global network alignment (GNA) problem is NP-complete, for which only heuristic methods have been proposed so far. Generally, the current GNA methods fall into global heuristic seed-and-extend approaches. These methods can not get the best overall consistent alignment between networks for the opinionated local seed. Furthermore These methods are lost in maximizing the number of aligned edges between two networks without considering the original structures of functional modules.

Methods

We present a novel seed selection strategy for global network alignment by constructing the pairs of hub nodes of networks to be aligned into multiple seeds. Beginning from every hub seed and using the membership similarity of nodes to quantify to what extent the nodes can participate in functional modules associated with current seed topologically we align the networks by modules. By this way we can maintain the functional modules are not damaged during the heuristic alignment process. And our method is efficient in resolving the fatal problem of most conventional algorithms that the initialization selected seeds have a direct influence on the alignment result. The similarity measures between network nodes (e.g., proteins) include sequence similarity, centrality similarity, and dynamic membership similarity and our algorithm can be called Multiple Hubs-based Alignment (MHA).

Results

When applying our seed selection strategy to several pairs of real PPI networks, it is observed that our method is working to strike a balance, extending the conserved interactions while maintaining the functional modules unchanged. In the case study, we assess the effectiveness of MHA on the alignment of the yeast and fly PPI networks. Our method outperforms state-of-the-art algorithms at detecting conserved functional modules and retrieves in particular 86% more conserved interactions than IsoRank.

Conclusions

We believe that our seed selection strategy will lead us to obtain more topologically and biologically similar alignment result. And it can be used as the reference and complement of other heuristic methods to seek more meaningful alignment results.

     

Accelerated Profile HMM Searches

Profile hidden Markov models (profile HMMs) and probabilistic inference methods have made important contributions to the theory of sequence database homology search. However, practical use of profile HMM methods has been hindered by the computational expense of existing software implementations. Here I describe an acceleration heuristic for profile HMMs, the "multiple segment Viterbi" (MSV) algorithm. The MSV algorithm computes an optimal sum of multiple ungapped local alignment segments using a striped vector-parallel approach previously described for fast Smith/Waterman alignment. MSV scores follow the same statistical distribution as gapped optimal local alignment scores, allowing rapid evaluation of significance of an MSV score and thus facilitating its use as a heuristic filter. I also describe a 20-fold acceleration of the standard profile HMM Forward/Backward algorithms using a method I call "sparse rescaling". These methods are assembled in a pipeline in which high-scoring MSV hits are passed on for reanalysis with the full HMM Forward/Backward algorithm. This accelerated pipeline is implemented in the freely available HMMER3 software package. Performance benchmarks show that the use of the heuristic MSV filter sacrifices negligible sensitivity compared to unaccelerated profile HMM searches. HMMER3 is substantially more sensitive and 100- to 1000-fold faster than HMMER2. HMMER3 is now about as fast as BLAST for protein searches.