黄影

摘 要 生物序列模体发现是从生物序列集合找出具有特定功能子序列的问题，它是生物信息学中最重要问题之一。OOPS模型是一种简单常用的模体发现的序列模型，它表示每条序列中有一个模体出现。本文提出了一种适用于OOPS序列模型的EM算法，用于查找每条序列中所出现的模体。实验结果表示，所提出的算法的时间性能和识别准确率均好于经典的Project算法。

关键词 模体发现 生物序列 EM算法

中图分类号：TP181 文献标识码：A DOI：10.16400/j.cnki.kjdkx.2015.08.010

EM Algorithm of OOPS Model in Motif Discovery Problem

HUANG Ying

（School of Information Engineering， Xi'an University， Xi'an， Shaanxi 710065）

Abstract Biological sequence motif discovery from biological sequence set to find out having a problem specific functional sub-sequence， it is one of the most important issues in bioinformatics. OOPS model series model is a simple common motif finding， which represents each sequence has a motif appears. This paper presents a suitable OOPS series model EM algorithm， for finding that appears in each sequence motif. The results indicated that the time performance of the algorithm and the recognition accuracy rate of the proposed algorithm is better than the classical Project.

Key words motif discovery; biological sequence; EM algorithm

1背景

EM（expectation-maximization）算法是Dempster， Laird和Rubin（DLR）三个人在1977年正式提出的。主要是用于在不完全数据的情况下计算最大似然估计。在EM算法正式提出以来，人们对EM算法的性质有更加深入的研究;并且在此基础上，提出了很多改进的算法，在数理统计，数据挖掘，机器学习以及模式识别等领域有广泛的应用。

生物序列模体（motif）发现问题是从一个从相关生物序列集合找出具有某种特定功能的子序列的问题，它是生物信息学中最重要问题之一，也是最基本问题之一。针对motif在每条序列中出现或不出现或者出现多次，有三种对应的模型，即：若每条序列中有且仅有一个motif出现，则被称为OOPS模型，这是最简单的模型;若每条序列中至多有一个motif出现，则被称为ZOOPS模型;若每条序列允许多个motif出现或者没有motif出现，则被称为TCM模型，这是最复杂的模型。

本文实现基于最简单的OOPS模型实现EM算法，来查找每条序列中所出现的motif。

2模体发现的EM算法

在最大化似然的问题中，给定被称为数……