小 型 微 型 计 算 机 系 统
Journal of Chinese Computer Systems
2012
年
7
月 第
7
期
Vol. 33 No. 7 2012
收稿日期
: 2011-03-15
收修改稿日期
: 2011-05-09
基金项目
:
国家自然科学基金项目
( 61070047)
资助
.
作者简介
:
刘 维
,
女
,1982
年
生
,
博士
,
讲师
,
研究方向为数据挖掘和生物信息学
;
陈 崚
,
男
,1951
年生
,
教授
,
博士生导师
,
研究方向为算法设计和并行计算
.
一种新的
CpG
岛的位置识别算法
刘 维
1
,
陈 崚
1,2
1
(
扬州大学 信息工程学院计算机系
,
扬州
225127)
2
(
南京大学 计算机软件新技术国家重点实验室
,
南京
210093)
E-mail: yzliuwei @ 126. com
摘 要
:
随着多数生物基因组测序工作的完成
,
基因识别就显得尤为重要
. CpG
岛在基因组中有着重要的生物学意义
,
因此识
别
CpG
岛将有助于基因的识别
.
目前已经构建的一些识别
CpG
岛的位置的模型大都存在标注偏差
、
需要独立假设等缺点
,
为
此提出一种基于条件随机场
( CRFs)
模型的
CpG
岛的位置识别的新方法
.
该方法将识别
CpG
岛的位置的问题转化为序列标记
问题
,
并根据
CpG
岛的位置的性质设计了相应的模型构建
、
训练以及解码的算法
.
利用本文算法可以对输入序列确定最有可能
的标注序列
,
从而识别
CpG
岛的位置
.
通过对标准数据库的数据进行测试
,
其实验结果表明本文算法是可行的
、
高效的
,
比
HMM
方法有更高的准确率
.
关 键 词
:
条件随机场模型
; CpG
岛
;
序列标记
中图分类号
: TP18
文献标识码
: A
文 章 编 号
: 1000-1220( 2012) 07-1557-07
Novel Method for CpG Islands Location Identification
LIU Wei
1
,CHEN Ling
1,2
1
( Department of Computer Science,Yangzhou University,Yangzhou 225127,China)
2
( National Key Lab of No vel Software Technology,Nanjing University,Nanjing 210093,China)
Abstract: While the genomes of the organisms have been sequenced,gene prediction becomes one of the most important projects.
CpG islands are of important biological significance in the genomes. CpG islands location identification is helpful for gene prediction.
In order to overcome the shortcomings of existing models such as the strong independence assumptions which generative model must
have
,the label-bias problem exhibited by maximum entropy markov model and other non-generative models,we present a novel
method for CpG islands location identification based on conditional random fields model. The metho d transforms the problem of CpG
islands location identification into sequential data labeling. Based on the properties of CpG islands location,w e design the correspond-
ing methods of model constructing、training and decoding. In this paper,we also design the corresponding feature functions and ob-
tain the w eights from the joint distribution over the label sequence given observation through a learning procedure on training data.
Then according to the distribution model obtained,w e can determine the labeled sequence with maximum probability and thereby i-
dentify the location of CpG islands. We test our algorithm by the use of the data sets from the standard database. The experimental re-
sults show that compared with other traditional algorithms,our algorithm is more practicable and efficient than the method of HMM .
Key words: conditional random fields model; CpG islands; sequential data labeling
1
引 言
随着多数生物基因组测序工作的完成
,
基因识别就显得
尤为重要
.
在人类基因组中
,CG
二核苷酸的分布是不均匀
的
.
在基因组的某些区域内
,
二核苷酸
“CG”
出现的频率往往
要高于基因组其它的区域
,
因此
“CG”
的高含量区
(
通常长达
数百到数千碱基
)
可能意味着转录启动子的存在
,
这种
“CG”
高含量区被称为
CpG
岛
[1]
.
在大规模基因组测序计划中
,
我
们发现每一个
CpG
岛的存在
,
都预示着可能挖掘出了新基
因
[2,3]
.
此外已有研究表明
CpG
岛的研究将直接影响
DNA
甲
基化的发生
,
从而影响到肿瘤的发生发展
.
因此从挖掘识别新
基因
[4]
和肿瘤早期诊断的研究角度来说
,CpG
岛的预测
[5]
都
具有显著的生物学理论和实践意义
.
CpG
岛的识别的工作可表述为两个问题
[6]
:
1)
给定一段
DNA
序列片段
,
判别它是否是一个
CpG
岛
.
2
)
给定一个
DNA
序列
,
识别其中的
CpG
岛
.
第一个问题可用
Markov
过程来解决
.
我们所要研究的
核心问题是第二个问题
,
即
,
通过对已知为
CpG
岛的序列的
训练得到的先验知识
,
来识别所给出的
DNA
序列中的
CpG
岛
.
近二十年来
,
已出现了很多有关
CpG
岛的识别算法和判
定标准
[7-12]
. Gardiner - Garden
和
Frommer
最早于
1987
年提
出了
CpG
岛的技术标准
. Takai
[7]
等人随后对该标准进行了
部分修正
,
提出了更有利于去除
Alu
重复序列的
CpG
岛的技
术 标准
.
随后在
2006
年
,Hachenberg
等人以客观的物理距离
为基础
,
提出了一种新型识别方法
CpGCluster
[8]
.
以上提出的
CpG
岛的判定标准都是人为定义的
,
因此所识别出的
CpG
岛
的生物学意义不大
,
并且计算复杂度极高
.
为了能够正确地发
现真正具有生物学意义的
CpG
岛
,
生物学家们正在积极地寻