一种基于关键路径法的DNA计算用寡核苷酸序列设计算法

在原有的生物大分子序列比对算法的基础上,结合图论中的关健路径法,提出了一种新的计算两寡核苷酸序列间最大配对程度的算法。采用此算法结合生成并测试的方法,能够寻找给定长度的一组适用于DNA计算的寡核苷酸序列。同时采用DNA芯片杂交方法验证了用该算法设计的一组序列的杂交特异性。     

基于蚁群遗传算法的DNA序列比对方法

蚁群遗传算法是在蚁群算法的基础上用遗传算法对其参数进行优化而产生的一种改进算法。把蚁群遗传算法应用于DNA序列比对上,结果表明这种新的序列比对算法是非常有效的。     

一个新的多序列比对算法

多序列比对是生物信息学中基础而又重要的序列分析方法.本文提出一种新的多序列比对算法,该算法综合了渐进比对方法和迭代策略,采用加权函数以调整序列的有偏分布,用neighbor-joining方法构建指导树以确定渐进比对的顺序.通过对BAlibASE中142组蛋白质序列比对的测试,验证了本算法的有效性.与Multalin算法比较的结果表明,本算法能有效地提高分歧较大序列的比对准确率.     

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

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

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

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

多序列渐进式比对算法研究与比较

多序列比对是一种重要的生物信息学工具,在生物的进化分析以及蛋白质的结构预测方面有着重要的应用。以ClustalW为代表的渐进式多序列比对算法在这个领域取得了很大的成功,成为应用最为广泛的多序列比对程序。但其固有的缺陷阻碍了比对精度的进一步提高,近年来出现了许多渐进式比对算法的改进算法,并取得良好的效果。本文选取了其中比较有代表性的几种算法对其基本比对思想予以描述,并且利用多序列比对程序平台BAliBASE和仿真程序ROSE对它们的精度和速度分别进行了比较和评价。     

构建基于折叠核心的全α类蛋白取代矩阵

氨基酸残基取代矩阵是影响多序列比对效果的重要因素,现有的取代矩阵对低相似序列的比对性能较低.在已有的 BLOSUM 取代矩阵算法基础上,定义了基于蛋白质折叠核心结构的序列 结构数据块;提出一种新的基于全α类蛋白质折叠核心结构的氨基酸残基取代矩阵——TOPSSUM25,用于提高低相似度序列的比对效果.将矩阵TOPSSUM25导入多序列比对程序,对相似性小于25%的一组四螺旋束序列 结构数据块的测试结果表明,基于 TOPSSUM25的多序列比对效果明显优于BLOSUM30矩阵;基于一个BAliBASE子集的比对检验也进一步表明, TOPSSUM25在全α类蛋白质的两两序列比对上优于BLOSUM30矩阵.研究结果可为进一步的阐明低同源蛋白质序列 结构 功能关系提供帮助.     

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

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

基于DNA序列K-tuple分布的一种非序列比对分析

文章在基因组K-tuple分布的基础上, 给出了一种推测生物序列差异大小的非序列比对方法。该方法可用于衡量真实DNA序列和随机重排序列在K-tuple分布上的差异。将此方法用于构建含有26种胎盘哺乳动物线粒体全基因组的系统树时, 随着K的增大, 系统树的分类效果与生物学一致公认的结果愈加匹配。结果表明, 用此方法构建的系统进化树比用其他非序列比对分析方法构建的更加合理。     

参数序列比对算法研究

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

Cryo-EM image alignment: From pair-wise to joint with deep unsupervised difference learning

Cryo-electron microscopy (cryo-EM) single-particle analysis is a revolutionary imaging technique to resolve and visualize biomacromolecules. Image alignment in cryo-EM is an important and basic step to improve the precision of the image distance calculation. However, it is a very challenging task due to high noise and low signal-to-noise ratio. Therefore, we propose a new deep unsupervised difference learning (UDL) strategy with novel pseudo-label guided learning network architecture and apply it to pair-wise image alignment in cryo-EM. The training framework is fully unsupervised. Furthermore, a variant of UDL called joint UDL (JUDL), is also proposed, which is capable of utilizing the similarity information of the whole dataset and thus further increase the alignment precision. Assessments on both real-world and synthetic cryo-EM single-particle image datasets suggest the new unsupervised joint alignment method can achieve more accurate alignment results. Our method is highly efficient by taking advantages of GPU devices. The source code of our methods is publicly available at “http://www.csbio.sjtu.edu.cn/bioinf/JointUDL/” for academic use.     

Equivalence of two Fourier methods for biological sequences

 Two methods for defining Fourier power spectra for DNA sequences or other biological sequences are compared. The first method uses indicator sequences for each letter. The second method by Silverman and Linsker assigns to each letter a vertex of a regular tetrahedron in space, and this can be generalized to any dimension. While giving different Fourier transforms, it is shown that the power spectra of the two methods are essentially the same. This is also true if one replaces the Fourier transform in both methods with another linear transform, such as the Walsh transform. Received 4 December 1995     

A 10-min method for preparation of highly electrocompetent Pseudomonas aeruginosa cells: application for DNA fragment transfer between chromosomes and plasmid transformation

A rapid microcentrifuge-based method is described for preparation of Pseudomonas aeruginosa electrocompetent cells with up to 10,000-fold increased transformation efficiencies over existing procedures. This increased efficiency now enables the use of transformation for all applications requiring DNA transfer. These include transfer of chromosomal mutations marked with antibiotic resistance genes between P. aeruginosa strains, which solves the riddle of not having an efficient and reliable transduction procedure for this bacterium. Not surprisingly, the method also allows for very efficient transformation with replicative plasmids, with transformation efficiencies ranging from 10(7) to >10(11) transformants per microgram of DNA. Lastly, with efficiencies of up to >10(3) transformants per microgram of DNA the method replaces in most instances conjugation for the transfer of non-replicative plasmids used in gene replacement, site-specific gene integration and transposon mutagenesis experiments.     

Computational differentiation of N-terminal signal peptides and transmembrane helices

Signal peptides and transmembrane helices both contain a stretch of hydrophobic amino acids. This common feature makes it difficult for signal peptide and transmembrane helix predictors to correctly assign identity to stretches of hydrophobic residues near the N-terminal methionine of a protein sequence. The inability to reliably distinguish between N-terminal transmembrane helix and signal peptide is an error with serious consequences for the prediction of protein secretory status or transmembrane topology. In this study, we report a new method for differentiating protein N-terminal signal peptides and transmembrane helices. Based on the sequence features extracted from hydrophobic regions (amino acid frequency, hydrophobicity, and the start position), we set up discriminant functions and examined them on non-redundant datasets with jackknife tests. This method can incorporate other signal peptide prediction methods and achieve higher prediction accuracy. For Gram-negative bacterial proteins, 95.7% of N-terminal signal peptides and transmembrane helices can be correctly predicted (coefficient 0.90). Given a sensitivity of 90%, transmembrane helices can be identified from signal peptides with a precision of 99% (coefficient 0.92). For eukaryotic proteins, 94.2% of N-terminal signal peptides and transmembrane helices can be correctly predicted with coefficient 0.83. Given a sensitivity of 90%, transmembrane helices can be identified from signal peptides with a precision of 87% (coefficient 0.85). The method can be used to complement current transmembrane protein prediction and signal peptide prediction methods to improve their prediction accuracies.     

Peculiarities of cytometrical methods of DNA content determination in the nucleus

This work has proposed a new theoretical approach to analysis of histograms of DNA content, which are obtained by the method of flow cytometry, in cells of Drosophila melanogaster imaginal discs. The precision of measurements of the DNA amount in G₁ and G₂(M) phases has been shown to be limited by precision of instrument tuning of zero of the flow cytometer. Use of the calculative zero of the flow cytometer and of dividing cells as standards of the DNA content is able to increase severalfold the precision of the DNA measurements in nuclei of the species. Comparative analysis of errors of various methods of measurement of the DNA content in cell nuclei is also performed. For methods of flow fluorescent cytometry, confocal scanning, and cytophotometry of the Feulgen-stained nuclei, it has been shown that, at present, the mean square errors of the DNA content measurements are within the interval of values considered acceptable for biological studies (0.02 < CV < 0.06).     

Semiautomated improvement of RNA alignments

We have developed a semiautomated RNA sequence editor (SARSE) that integrates tools for analyzing RNA alignments. The editor highlights different properties of the alignment by color, and its integrated analysis tools prevent the introduction of errors when doing alignment editing. SARSE readily connects to external tools to provide a flexible semiautomatic editing environment. A new method, Pcluster, is introduced for dividing the sequences of an RNA alignment into subgroups with secondary structure differences. Pcluster was used to evaluate 574 seed alignments obtained from the Rfam database and we identified 71 alignments with significant prediction of inconsistent base pairs and 102 alignments with significant prediction of novel base pairs. Four RNA families were used to illustrate how SARSE can be used to manually or automatically correct the inconsistent base pairs detected by Pcluster: the mir-399 RNA, vertebrate telomase RNA (vert-TR), bacterial transfer-messenger RNA (tmRNA), and the signal recognition particle (SRP) RNA. The general use of the method is illustrated by the ability to accommodate pseudoknots and handle even large and divergent RNA families. The open architecture of the SARSE editor makes it a flexible tool to improve all RNA alignments with relatively little human intervention. Online documentation and software are available at (http://sarse.ku.dk).     

An applications-focused review of comparative genomics tools: capabilities,limitations and future challenges

A team at the Lawrence Livermore National Laboratory (LLNL) was given the task of using computational tools to speed up the development of DNA diagnostics for pathogen detection. This work will be described in another paper in this issue (see pages 133-149). To achieve this goal it was necessary to understand the merits and limitations of the various available comparative genomics tools. A review of some recent tools for multisequence/genome alignment and substring comparison is presented, within the general framework of applicability to a large-scale application. We note that genome alignments are important for many things, only one of which is pathogen detection. Understanding gene function, gene regulation, gene networks, phylogenetic studies and other aspects of evolution all depend on accurate nucleic acid and protein sequence alignment. Selecting appropriate tools can make a large difference in the quality of results obtained and the effort required.     

Use of synthetic oligonucleotides in gene isolation and manipulation

Great progress has occurred in the techniques of synthesis of DNA molecules of defined sequences in terms of speed, length of the obtained oligonucleotides, and automation of the processes. Corresponding progress also occurred in the ways of using synthetic DNA in molecular biology and recombinant DNA research. Screening of cloned DNA sequence banks with long, unique oligonucleotides, provided a new approach to isolate the genes for proteins which are present in very small quantity. This technique can present considerable advantages over the more classical use of mixtures of oligonucleotides, in reducing the number of potentially positive clones on a primary screen, and enabling cloning with a minimum of amino acid sequence data. Synthetic oligonucleotides also provide the basis of a set of techniques for site-directed mutagenesis of DNA sequences. This allows the possibility of engineering the structure of particular proteins, and the properties of new variants can be tested by expressing the protein in a heterologous host. An example of this approach is the production of variants of human alpha 1-antitrypsin. A variant where valine replaces the methionine at the active site is equally active as an antielastase, but no longer susceptible to oxidative inactivation. A second variant, where arginine replaces the methionine, now functions as an antithrombin, but no longer inhibits elastase. Total gene synthesis is now feasible for larger and larger genes, and some of the recent strategies of whole gene synthesis are presented.     

Studies on the Pathway of Incorporation of 2-Aminopurine into the Deoxyribonucleic Acid of Escherichia coli

A pathway for the incorporation of 2-aminopurine into deoxyribonucleic acid (DNA) was studied in cell-free extracts of Escherichia coli. It was demonstrated that the free base can be converted to the deoxynucleoside, and that the deoxynucleotide can be phosphorylated to the di- and triphosphates and then incorporated into the DNA. From a consideration of the individual reactions in crude extracts, it is likely that the rate-limiting step in this pathway is the formation of the deoxynucleotide. Of especial interest is the observation that 2-aminopurine may be viewed as an analogue of either guanine or adenine, depending on which enzymatic step is being considered. On the one hand, it resembles guanine in that it is specifically converted from the mono- to the diphosphate by guanylate kinase and not by adenylate kinase. On the other hand, it replaces adenine rather than guanine in the DNA synthesized with purified DNA polymerases. E. coli DNA polymerase utilizes aminopurine deoxynucleoside triphosphate as a substrate for DNA synthesis much better than does purified phage T5-induced DNA polymerase and is also much less inhibited by this analogue than the T5 enzyme. These experiments in vitro correlate with known differential effects of 2-aminopurine on E. coli and phage in vivo.     

Integration of PCR fragments at any specific site within cloning vectors without the use of restriction enzymes and DNA ligase

Here, we describe a method that offers a unique way to engineer plasmids with precision but without digestion using restriction enzymes for the insertion of DNA. The method allows the insertion of PCR fragments in between any two nucleotides within a target plasmid. The only requirement is that the amplified fragments must be embedded between DNA sequences homologous to the site in which the integration is planned. This method is an adaptation of the QuikChange Site-Directed Mutagenesis protocol. It is simpler than the existing cloning strategies and is suitable for multiparallel constructions of new plasmids. We have demonstrated its utility by constructing plasmids in which we have successfully integrated PCR fragments up to 1117 bp.