禁忌搜索算法在蛋白质结构预测中应用

一种氨基酸序列只可能有一种蛋白质结构,所以在蛋白质理论预测中,正确定义能量函数、精确选用的计算机搜寻算法来寻找能量最低值,是蛋白质结构预测的关键。基于此,本文以两两残基之间距离分布和二面角分布符合玻尔兹曼定理,提出了一种抽象的蛋白质三维结构连续物理数学模型。然后应用了禁忌搜索算法很好的计算了牛胰岛素B(D)主链走向;比较计算了氨基酸序列最低能量的全局最优点。     

基于蛋白质CGR的线粒体蛋白质序列比对

利用蛋白质混沌游走表示法（PCGR）提出一种新的蛋白质序列比对方法。通过计算两序列之间的PCGR点距离,就可以找到所有的局部相似片断。根据氨基酸的化学物理性质把氨基酸分成4和7类,针对分类与无分类的各种情况进行蛋白质序列比对。为了更直观地描述比对结果,采用点阵图来表示比对数据,不仅能显示两序列间所有相同片断,还可以体现出序列的相似性。     

距离约束和二面角优化的蛋白质结构预测方法

预测蛋白质三维结构对了解其生物功能、疾病发病机理研究、药物研发等具有重大意义.为了提高蛋白质结构预测的精度,提出了一种基于距离约束和二面角优化的蛋白质结构预测方法(Distance Constraint and Dihedral Angle Optimized Protein Structure Prediction Method, DCDA).首先,对预测的残基间距离分布图进行筛选,进而构建基于残基间距离分布的构象评估模型,指导构象选择;然后,在片段组装大范围搜索构象空间的基础上,利用基于二面角差分进化采样策略增强结构灵活的Loop区域采样,进一步提高拓扑结构的精度,增强近天然态构象采样能力.在15个测试蛋白的预测结果表明,DCDA能够达到较高的预测精度,是一种有效的蛋白质结构预测方法.     

利用Alignment空间理论分析蛋白质的结构

蛋白质的结构分析对研究蛋白质的功能以及进化关系十分重要,而Alignment空间理论作为数学中一个崭新的方向,可以在蛋白质结构分析中发挥显著的作用。简要介绍了Alignment空间理论,采用基于蛋白质主链的二面角序列代表蛋白质的结构,利用Alignment空间理论,通过相应的动态规划算法得到了一种可以度量蛋白质结构相似程度的指标ρ。最后经由蛋白质序列的实例计算证明该指标的有效性。     

基于数据挖掘技术的蛋白质结构分类的研究

论文选择蛋白质二级结构数据为研究对象,应用数据挖掘技术和机器学习中的动态规划理论进行蛋白质结构分类。介绍了一种新的蛋白质结构分类方法——PSSC,该方法的核心算法是STRIDE算法和ISSA算法,关键性步骤是创建分类模型,该分类模型包括构建CATH分类树、计算蛋白质结构相似度、利用统计方法制定分类标准三步。在对蛋白质结构进行四个层次的分类中,应用已有的RMSD、Z-Score结构比对算法和论文新提出的ISSA结构比对算法获得分类参数。最后,介绍我们所开发的PSSC分类软件,并指出需要完善之处和解决方案。     

1种蛋白质Loop片段结构的概率生成模型

在计算生物学中,根据蛋白质的氨基酸序列预测蛋白质的结构是尚未解决的重要问题之一,而其中的1个难点是预测蛋白质中Loop片段的结构.本文用1阶马尔可夫模型为基础,通过对其训练,可根据氨基酸串和2级结构信息为蛋白质Loop片段概率建模和采样.其中用Ramachandmn图示法的二面角对描述蛋白质结构,模型的训练和推理通过工具包Mocapy来完成.并使用KL交叉熵和角度差异值作为实验检验标准来完成Loop分布情况的测试实验,同时在从头预测Loop结构实验中预测CASP8中8个自由建模的蛋白质结构.与最流行的方法相比,本文提出的模型因为改进了Loop段的预测精度,从而可使得到的二面角对更加接近真实Loop结构中分布,同时在从头预测中提高整个蛋白质结构的预测精度.并且由于本文的模型具有概率推理特性,故在理论上也更具有无偏见性.     

采用隐马尔科夫模型的蛋白质复合物识别研究

动态蛋白质网络的构建和复合物识别问题是生物信息学领域目前研究的热点.针对现有的算法在解决前述问题上的不足,提出了一种基于隐马尔科夫模型的蛋白质复合物识别算法(HMM-PC).首先基于蛋白质的基因共表达特性构建初始蛋白质网络,然后利用蛋白质的共享功能注释、共享结构域和连接强度等信息来对网络进行加权,得到动态蛋白质网络.在此基础上,考虑前一时刻蛋白质网络拓扑结构信息对当前时刻蛋白质网络拓扑结构信息的影响,采用隐马尔科夫模型描述蛋白质复合物与网络个体间的相互关系,进而将动态蛋白质网络中的复合物识别问题建模为隐马尔科夫模型中的最优状态序列发现问题,并采用维特比算法识别得到蛋白质复合物.最后通过理论分析证明了所提算法的复杂度较低.采用DIP数据集和MIPS数据集中的酵母蛋白质网络作为测试对象,大量的仿真实验结果也表明,HMM-PC算法的鲁棒性较强,在查全率、查准率、F-measure和效率等方面的性能都要优于现有的复合物识别算法.     

基于蛋白质相互作用界面的比对算法研究

蛋白质相互作用界面是蛋白质相互作用产生的物理载体。考虑蛋白质相互作用界面间的结构相似性对于研究蛋白质功能,信号传导网络和药物设计具有非常重要的意义,而现有的蛋白质结构比对算法仅适用于蛋白质单体的全局空间结构。我们给出了基于整数二次规划模型的方法来考虑蛋白质相互作用界面的比对问题,该方法整合了蛋白质序列的进化信息、结构信息,并用进化谱的相似性来对比对上的残基打分以衡量其进化保守性。通过计算实验,发现进化上和结构上保守的残基有可能就是对于蛋白质结合起重要作用的残基,即热点。     

基于局部梯度和二进制模式的时间序列分类算法

时间序列分类问题是时间序列数据挖掘中的一项重要任务,近些年受到了越来越广泛的关注.该问题的一个重要组成部分就是时间序列间的相似性度量.在众多相似性度量算法中,动态时间规整是一种非常有效的算法,目前已经被广泛应用到视频、音频、手写体识别以及生物信息处理等众多领域.动态时间规整本质上是一种在边界及时间一致性约束下的点对点的匹配算法,能够获得两条序列间的全局最优匹配.但该算法存在一个明显的不足,即不一定能实现序列间的局部合理匹配.具体的讲,就是具有完全不同局部结构信息的时间点有可能被动态时间规整算法错误匹配.为了解决这个问题,提出了一种改进的基于局部梯度和二进制模式的动态时间规整算法LGBDTW (local gradient and binary pattern based dynamic time warping),通过考虑时间序列点的局部结构信息来强化传统动态时间规整算法.所提算法虽然实质上是一种动态时间规整算法,但它通过考虑序列点的局部梯度和二进制模式值来进行相似性加权度量,有效避免了具有相异局部结构的点匹配.为了进行全面比较,将所提出的算法应用到了最近邻分类算法的相似性度量中,并在...     

蛋白质序列比对算法在众核结构上的并行优化

在生物信息学中,蛋白质序列比对是最为重要的算法之一,生物技术的发展使得已知的序列库变得越来越庞大,这类算法本身又具有计算密集型的特点,这导致进行序列比对所消耗的时间也越来越长,目前的单核或者数量较少的多核系统均已经难以满足对计算速度的要求.Godson-T是一个包含诸多创新结构的众核平台,在该系统上实现了对一种蛋白质序列比对算法的并行化,并且结合蛋白质比对算法以及Godson-T结构的特征,针对同步开销、存储访问竞争以及负载均衡3个方面对算法进行了细致的优化,最终并行部分整体也获得了更优的、接近线性的加速比,并且实际性能远远优于基于AMD Opteron处理器的工作站平台.     

A novel randomized iterative strategy for aligning multiple protein sequences.

The rigorous alignment of multiple protein sequences becomes impractical even with a modest number of sequences, since computer memory and time requirements increase as the product of the lengths of the sequences. We have devised a strategy to approach such an optimal alignment, which modifies the intensive computer storage and time requirements of dynamic programming. Our algorithm randomly divides a group of unaligned sequences into two subgroups, between which an optimal alignment is then obtained by a Needleman-Wunsch style of algorithm. Our algorithm uses a matrix with dimensions corresponding to the lengths of the two aligned sequence subgroups. The pairwise alignment process is repeated using different random divisions of the whole group into two subgroups. Compared with the rigorous approach of solving the n-dimensional lattice by dynamic programming, our iterative algorithm results in alignments that match or are close to the optimal solution, on a limited set of test problems. We have implemented this algorithm in a computer program that runs on the IBM PC class of machines, together with a user-friendly environment for interactively selecting sequences or groups of sequences to be aligned either simultaneously or progressively.     

Multiple DNA and protein sequence alignment on a workstation and a supercomputer

This paper describes a multiple alignment method using a workstation and supercomputer. The method is based on the alignment of a set of aligned sequences with the new sequence, and uses a recursive procedure of such alignment. The alignment is executed in a reasonable computation time on diverse levels from a workstation to a supercomputer, from the viewpoint of alignment results and computational speed by parallel processing. The application of the algorithm is illustrated by several examples of multiple alignment of 12 amino acid and DNA sequences of HIV (human immunodeficiency virus) env genes. Colour graphic programs on a workstation and parallel processing on a supercomputer are discussed.     

Parametric Sequence Alignment with Constraints

Approximate matching techniques based on string alignment are important tools for investigating similarities between strings, such as those representing DNA and protein sequences. We propose a constraint based approach for parametric sequence alignment which allows for more general string alignment queries where the alignment cost can itself be parameterized as a query with some initial constraints. Thus, the costs need not be fixed in a parametric alignment query unlike the case in normal alignment. The basic dynamic programming string edit distance algorithm is generalized to a naive algorithm which uses inequalities to represent the alignment score. The naive algorithm is rather costly and the remainder of the paper develops an improvement which prunes alternatives where it can and approximates the alternatives otherwise. This reduces the number of inequalities significantly and strengthens the constraint representation with equalities. We present some preliminary results using parametric alignment on some general alignment queries.     

基于新测序技术的比对与组装算法

针对新型超高通量测序仪Solexa测序仪所产生的测序片段read的比对与组装问题,提出一种短序列比对与组装算法SRMA,采用对参考序列进行hash的方法,将测序片段read分3段快速、准确地定位于参考序列,对不能定位的read采取从头（Denovo）组装的方法进行组装。测试结果表明SRMA算法具有较高的性能和敏感度,以及良好的应用前景。     

导向定位测序数据的甲基化序列比对算法优化

导向定位测序(GPS)是一种全基因组DNA甲基化检测的新测序技术,产生的测序数据具有成本低、没有序列偏好等优势.目前,甲基化分析中最重要的一步是将其测序产生的序列比对到参考基因组上.但是,现有导向定位测序的方法使用Smith-Waterman进行局部序列比对,时间消耗过大且容易对序列比对位置产生误判.因此,提出一种导向定位测序数据的改进比对算法,该算法利用其双端测序的优势,先用甲基化序列端数据进行序列比对,对多位置匹配的序列再利用常规数据端数据进行比对位置确定.实验结果表明:本文方法和现有方法的准确率相当,而具有更高的唯一比对比率,时间性能有3倍以上的提升.     

Improving multiple sequence alignment biological accuracy through genetic algorithms

Accuracy on multiple sequence alignments (MSA) is of great significance for such important biological applications as evolution and phylogenetic analysis, homology and domain structure prediction. In such analyses, alignment accuracy is crucial. In this paper, we investigate a combined scoring function capable of obtaining a good approximation to the biological quality of the alignment. The algorithm uses the information obtained by the different quality scores in order to improve the accuracy. The results show that the combined score is able to evaluate alignments better than the isolated scores.     

Visualizing protein conformational changes on a personal computer--alpha carbon pseudo bonding as a constraint for interpolation in internal coordinate space

A Java program has been developed to produce animations and movies of protein conformation changes. The animations, primarily intended for teaching purposes, are produced by visualizing a series of aligned structures interpolated between two forms of the same protein. To produce plausible intermediate structures, the interpolation is performed in internal coordinate space and uses a simple constraint to avoid the production of artifactual movements of the protein backbone. This constraint involves the introduction of 'pseudo' bonds linking the protein alpha carbon atoms. All of the steps from alignment of initial structures to the production of AVI movies can be performed on readily available personal computers.     

Unsupervised manifold alignment using soft-assign technique

In this paper, we propose a robust unsupervised algorithm for automatic alignment of two manifolds in different datasets with possibly different dimensionalities. The significant contribution is that the proposed alignment algorithm is performed automatically without any assumptions on the correspondences between the two manifolds. For such purpose, we first automatically extract local feature histograms at each point of the manifolds and establish an initial similarity between the two datasets by matching their histogram-based features. Based on such similarity, an embedding space is estimated where the distance between the two manifolds is minimized while maximally retaining the original structure of the manifolds. The elegance of this idea is that such complicated problem is formulated as a generalized eigenvalue problem, which can be easily solved. The alignment process is achieved by iteratively increasing the sparsity of correspondence matrix until the two manifolds are correctly aligned and consequently one can reveal their joint structure. We demonstrate the effectiveness of our algorithm on different datasets by aligning protein structures, 3D face models and facial images of different subjects under pose and lighting variations. Finally, we also compare with a state-of-the-art algorithm and the results show the superiority of the proposed manifold alignment in terms of vision effect and numerical accuracy.