一种关于蛋白质模体的自动识别算法

随着生物信息学的发展,模体识别已经成为一种能够从生物序列中提取有用生物信息的方法.文中介绍了有关模体的一些概念,讨论了模体识别算法(MEME)的基础,即EM(expectation maximization)算法,由于MEME算法是建立在EM算法的基础上的,所以又由此引出了MEME算法,并对MEME算法的一些基本问题比如时间复杂度、算法性能等进行了详细讨论,对算法的局限性和有待改进的地方作了说明.实践证明,MEME是一个较好的模体识别算法,它能够识别出蛋白质或者DNA序列中单个或多个模体,具有很大的灵活性.     

(l,d)-模体识别问题的遗传优化算法

转录因子结合位点识别在基因表达调控过程中起着重要的作用.文中提出了一种贝叶斯模型驱动的模体识别的遗传优化算法GOBMD(Genetic Optimization with Bayesian Model for Motif Discovery).GOBMD首先使用一个基于位置加权散列的投影过程,将输入序列中的l-mers投影到k维(k相似文献   

BioIndex：一种生物序列相似性查询的高效索引

有效管理生物数据并提供高效的查询方法是生物信息处理的重要研究内容.BioSeg是一个新的生物序列数据模型.查询优化研究是生物数据库管理系统开发的重要内容之一.研究当前生物数据索引技术,针对BioSeg数据模型的特点和生物序列相似性查询需求设计了一种新的生物序列数据索引BioIndex,并设计相应的查询算法.首先,使用MEME(Multiple EM for Moeif Elicitation)算法挖掘生物序列集中的序列模式作为索引建立索引序列库;之后,在索引序列库中查找与查询序列最相似的索引序列,将其对应的序列集作为候选集;再在候选集中查找与查询序列最相似的序列.在真实生物序列数据集上的实验表明使用新的生物序列数据索引BioIndex的序列查询算法提高了序列查询的效率.     

基于Gibbs采样与遗传算法的模体识别

借鉴Gibbs采样思想,将序列峰值所对应的候选模体作为遗传算法的初始种群,提出一种改进的模体识别算法。将模体在序列中的出现次数作为变量加入到适应度函数中,使其更符合生物数据的特性。在算法变异操作中加入IUPAC简并码保持种群的多样性。对DBTSS数据库中的真实数据进行测试,结果表明该算法具有较高的识别精度和较快的搜索速度。     

改进的KMP算法在生物序列模式自动识别中的应用

介绍了改进后的KMP算法在生物序列模式自动识别中的应用以及关于生物序列中模式的概念和表示方法，并对生物序列中有关模式匹配的知识作了介绍，阐述了如何将生物序列转换为字符串，以及如何编程实现此算法，成功地对KMP算法作了一些改进，实现了生物序列中模式的自动识别，实验结果表明，该算法具有较好的可行性。     

转录调控网络模块和模体识别算法研究进展

转录调控网络是生物体遗传信息传递的整体表示,是人们理解基因表达过程的重要内容。识别转录调控网络的模块和模体是分析网络拓扑结构和组织方式的重要方法,是揭示转录调控机制、生物发育与进化过程的重要环节之一。通过分析比较近年来用于转录调控网络模块识别的三类典型算法,阐述了它们各自的优势和不足。介绍了一种被广泛使用的转录调控网络模体识别算法。以此为基础,提出了转录调控网络模块和模体识别算法未来的研究方向。     

基于在线分裂合并EM算法的高斯混合模型分类方法*

为了解决传统高斯混合模型中期望值EM处理必须具备足够数量的样本才能开始训练的问题,提出了一种新的高斯混合模型在线增量训练算法。本算法在Ueda等人提出的Split-and-Merge EM方法基础上对分裂合并准则的计算进行了改进,能够有效避免陷入局部极值并减少奇异值出现的情况;通过引入时间序列参数提出了增量EM训练方法,能够实现增量式的期望最大化训练,从而能够逐样本在线更新GMM模型参数。对合成数据和实际语音识别应用的实验结果表明,本算法具有较好的运算效率和分类准确性。     

基于迁徙差分进化算法集成的模体识别

为了克服微分进化的局部收敛问题,通过模拟游牧民族的迁徙机制,提出一种迁徙策略,将其与差分进化算法相结合,得到一种迁徙差分进化算法新范式,利用集成技术,发挥各种差分进化算法的优点,提高算法的全局搜索能力。通过生物序列模体识别实验,验证了该算法的有效性。     

一种新的序列集保守信号识别算法

模体发现是计算机科学中的一个较为重要且具有一定挑战的问题,主要用于定位DNA序列集中的保守信号。首先,分析了已有的基于图聚类的模体发现算法MCL-WMR,讨论了它存在的两个缺陷。其次,针对这两个缺陷提出了MCL-WMR的改进算法iMCL-WMR。实验结果表明,所提DNA模体发现算法的时间性能好于所比较的算法MCL-WMR和qPMS9,能够在1个小时以内处理数百条输入序列,而且能够应对某些输入序列不含模体实例的测试数据。     

基于密度检测的EM算法

期望最大化(Expectation Maximization,EM)算法在聚类过程中无法识别噪声点,最终的收敛效果也依赖于初始值的选择。本文提出的基于密度检测的EM算法(DDEM)通过基于密度的方法来检测噪声点,利用基于密度和距离的方法进行初始值选择,改善了EM算法收敛效果。实验结果表明新算法可有效识别噪声点,降低初始值选择对收敛效果的影响,明显提高了聚类准确率和稳定性。     

Unsupervised Learning of Multiple Motifs in Biopolymers Using Expectation Maximization

The MEME algorithm extends the expectation maximization (EM) algorithm for identifying motifs in unaligned biopolymer sequences. The aim of MEME is to discover new motifs in a set of biopolymer sequences where little or nothing is known in advance about any motifs that may be present. MEME innovations expand the range of problems which can be solved using EM and increase the chance of finding good solutions. First, subsequences which actually occur in the biopolymer sequences are used as starting points for the EM algorithm to increase the probability of finding globally optimal motifs. Second, the assumption that each sequence contains exactly one occurrence of the shared motif is removed. This allows multiple appearances of a motif to occur in any sequence and permits the algorithm to ignore sequences with no appearance of the shared motif, increasing its resistance to noisy data. Third, a method for probabilistically erasing shared motifs after they are found is incorporated so that several distinct motifs can be found in the same set of sequences, both when different motifs appear in different sequences and when a single sequence may contain multiple motifs. Experiments show that MEME can discover both the CRP and LexA binding sites from a set of sequences which contain one or both sites, and that MEME can discover both the –10 and –35 promoter regions in a set of E. coli sequences.     

基于不同算法的Motif预测比较分析与优化

研究转录因子结合位点（TFBs）的主要预测模型及其预测的算法,通过基于调控元件预测的3种代表性的算法MEME、Gibbs采样和Weeder预测拟南芥基因组。比较结果表明,Gibbs采样算法和Weeder算法预测长、短motif效率较高。重点分析MEME算法,提出结合不同算法查找motif的优化方法,并以实验验证该方法能有效提高预测效率。     

EM算法与K-Means算法比较

聚类是广泛应用的基本数据挖掘方法之一,它按照数据的相似性和差异性将数据分为若干簇,并使得同簇的尽量相似,不同簇的尽量相异.目前存在大量的聚类算法,本文仅考察了划分方法中的两个常用算法:EM算法和K-Means算法,并重点剖析了EM算法,对实验结果进行了分析.最后对算法进行了总结与讨论.     

Efficient automatic exact motif discovery algorithms for biological sequences

ObjectiveThis paper presents an algorithm for the solution of the motif discovery problem (MDP).Methods and materialsMotif discovery problem can be considered in two cases: motifs with insertions/deletions, and motifs without insertions/deletions. The first group motifs can be found by stochastic and approximated methods. The second group can be found by using stochastic and approximated methods, but also deterministic method. We proved that the second group motifs can be found with a deterministic algorithm, and so, it can be said that the second motifs finding is a P-type problem as proved in this paper.Results and conclusionsAn algorithm was proposed in this paper for motif discovery problem. The proposed algorithm finds all motifs which are occurred in the sequence at least two times, and it also finds motifs of various sizes. Due to this case, this algorithm is regarded as Automatic Exact Motif Discovery Algorithm. All motifs of different sizes can be found with this algorithm, and this case was proven in this paper. It shown that automatic exact motif discovery is a P-type problem in this paper. The application of the proposed algorithm has been shown that this algorithm is superior to MEME, MEME3, Motif Sampler, WEEDER, CONSENSUS, AlignACE.     

A refined EM algorithm for PH distributions

This paper proposes an improved computation method of maximum likelihood (ML) estimation for phase-type (PH) distributions with a number of phases. We focus on the EM (expectation-maximization) algorithm proposed by Asmussen et al. [27] and refine it in terms of time complexity. Two ideas behind our method are a uniformization-based procedure for computing a convolution integral of the matrix exponential and an improvement of the forward-backward algorithm using time intervals. Compared with the differential-equation-based EM algorithm discussed in Asmussen et al. [27], our approach succeeds in the reduction of computation time for the PH fitting with a moderate to large number of phases. In addition to the improvement of time complexity, this paper discusses how to estimate the canonical form by applying the EM algorithm. In numerical experiments, we examine computation times of the proposed and differential-equation-based EM algorithms. Furthermore, the proposed EM algorithm is also compared with the existing PH fitting methods in terms of computation time and fitting accuracy.     

一种对预测Motifs算法的评价策略

主要研究了如何评价蛋白质家族Motifs预测算法的预测结果,目的是在对传统的算法预测问题分析优化的基础上,制定新的评价策略。主要方法是通过对MEME算法和PKG算法预测结果的比较分析,计算同一家族中Motifs的敏感性和特异性并比较它们对应的ROC曲线,确定真实的Motifs,进而获得该蛋白质家族的最佳Motifs的模型。实验结果表明这种评价策略可用于算法对蛋白质家族Motifs预测结果的评价,还可利用确定的最佳Motifs搜索数据库来预测蛋白质家族中其他的Motifs。     

A hybrid of electromagnetism-like mechanism and back-propagation algorithms for recurrent neural fuzzy systems design

This article introduces a novel hybrid evolutionary algorithm for recurrent fuzzy neural systems design in applications of nonlinear systems. The hybrid learning algorithm, IEMBP-improved electromagnetism-like (EM) with back-propagation (BP) technique, combines the advantages of EM and BP algorithms which provides high-speed convergence, higher accuracy and less computational complexity (computation time in seconds). In addition, the IEMBP needs only a small population to outperform the standard EM that uses a larger population. For a recurrent neural fuzzy system, IEMBP simulates the ‘attraction’ and ‘repulsion’ of charged particles by considering each neural system parameters as a charged particle. The EM algorithm is modified in such a way that the competition selection is adopted and the random neighbourhood local search is replaced by BP without evaluations. Thus, the IEMBP algorithm combines the advantages of multi-point search, global optimisation and faster convergence. Finally, several illustration examples for nonlinear systems are shown to demonstrate the performance and effectiveness of IEMBP.     

零一膨胀二项混合回归模型的改进EM算法

首先对存在过多0和1的观测数据提出了零一膨胀混合回归模型,由于EM算法一般会使得估计收敛到局部最优解上,所以提出了一种修正EM算法,对具有有限混合成分的零一膨胀二项回归模型（ZOIB）的参数进行估计。最后通过模拟研究说明该方法的有效性。     

基于GOS的国家网格集成环境及应用实例开发*

中国国家网格作为国内最主要的网格为用户提供了良好的计算服务.详细讨论了网格中间件系统软件GOS的功能和结构,以及基于GOS的中国国家网格集成环境,给出了生物信息软件MEME在国家网格环境下的集成实现,并提出了今后的工作方向.     

贝叶斯网络参数的在线学习算法及应用

以EM算法为基础，在给定贝叶斯网络结构情况下。研究分析了Voting EM算法并利用该算法对防洪决策贝叶斯网络进行在线参数学习，将该算法与EM算法的学习结果进行了比较分析，结果表明Voting EM算法不但能够进行在线参数学习，而且也具有较高的学习精度．