A Survey of the Research on Similarity Query Technique of Sequence Data
Zhu Yangyo ng , Dai Do ngbo , and Xio ng Yun
( S chool of Com p uter S cience , Fu dan U ni versit y , S han g hai 200433)
序列相似性查询的基础就是相似性的度量问 题. 设有两条长度分别为 m常见的序列距离函数 :
计算机研究与发展 Jo urnal of Co mp uter Research and Develop ment
ISSN 100021239ΠCN 1121777ΠTP 47 (2) : 2642276 , 2010
序列数据相似性查询技术研究综述
朱扬勇 戴东波 熊 赟
(复旦大学计算机科学技术学院 上海 200433) (daidongbo @f udan. edu. cn)
1) 序列具有序关系信息 ,这些序关系信息是以 元素位置或时间先后关系来体现. 为了保证查询结 果的质量 ,在选用序列的相似性度量或设计算法时 除了要考虑元素值外 ,还需要考虑元素间的序关系.
2) 序列特征难以抽取和紧凑地表达. 文本一般 用关键单词 ( key wo rd) 来表征其特征 ,而 DNA 序 列或蛋白质序列没有明显的单词概念 ,简单而紧凑 地表达其特征十分困难.
中图法分类号 TP274
收稿日期 :2009 - 01 - 23 ;修回日期 :2009 - 06 - 23 基金项目 :国家自然科学基金项目 (60573093) ; 国家“八六三”高技术研究发展计划基金项目 (2006AA02Z329)
朱扬勇等 :序列数据相似性查询技术研究综述
265
序列数据是一种重要的数据类型 ,在许多应用 领域普遍 存在[123] , 如 文本 中的 单词 ( wo rd) 序列 、 Web 日志文件中的用户访问事件 (access event ) 序 列以及生物数据库中的 DNA 序列和蛋白质序列 等. 序列数据由值元素和对应的序关系两部分组成 , 这两部分信息对分析和挖掘各种序列数据缺一不可.
3) 事件序列 ( event sequence) . 电视和广播所 产生的视频流和音频流以及 Web 上用户的访问序 列等都可看作是事件序列. 此序列所隐含的序信息 是时间序 ,且各序列元素值是某时刻所发生事件的 描述信息 (可用关系模式来表示) .
4) 时间序列 ( time series) . 虽然时间序列的序 信息也是时间序 ,但和事件序列不同的是时间序列 各元素一般是数值类型. 所以 ,时间序列中各元素可 以进行各种数学运算和数学变换 ,如由于 Parseval 定理的保证 ,可以在时间序列上进行 D F T 变换或 FF T 变换等[6] . 时间序列在金融 、天气预报等领域 中普遍存在.
5) 数据流 (data st ream) . 数据流是指高速到达 的数据信息 ,一般是对到达数据一遍扫描且不保存 在本地的方式进行处理和分析[7] . 在保持序信息的 数据流中 ,如文本流 、传感器网络产生的数值流、监测 设备产生的视频流 ,由于数据的高度动态性和数据流 处理方式的苛刻性 ,对这种序列数据的分析一般要综 合数据流处理 、文本处理和视频处理等多种方法.
Abstract Sequence data is ubiquito us in many do mains such as text , Web access log and biological database. Similarit y query in sequence data is a very important means fo r ext racting usef ul informatio n. Recently , wit h t he develop ment of vario us scientific co mp uting and t he generatio n of large scale sequence data , similarit y query o n sequence data is beco ming a hot research topic. So me important issues related to it are : similarit y met rics used in different applicatio n fields and t he mut ual co nnectio ns bet ween t hem ; statistical informatio n of distance dist ributio n o n rando m sequence collectio ns as well as it s f unctio n for analyzing t he performance of query algorit hms ; different kinds of key techniques fo r efficiently answering similarit y queries in large scale dataset s and t he co mpariso ns bet ween t heir merit s and demerit s. In t his survey , t he classificatio n and characteristics of sequence data is summarized. So me kinds of similarit y met rics and statistical informatio n abo ut distance bet ween rando m sequences are al so p resented and t he relatio nship s amo ng t hese similarit y met rics are f urt her analyzed. Then , so me t ypes of similarit y query and key issues in point are int roduced. Based o n t hese fo undatio ns , t his paper focuses o n t he classificatio n and evaluatio n of key techniques o n sequence similarit y search. Finally , so me challenges o n similarit y query of sequence data are discussed and f ut ure research t rends are also summarized. Key words sequence data ; similarit y met ric ; distance dist ributio n ; filtering technique ; similarit y query
根据不同的应用领域 , 序列数据可以分为以下 几类 :
1) 文本 (text) . 各种语言的文本都是单词序列 的集合体 ,在各种电子新闻 、邮件系统和 Web 页面
中广泛存在. 由于文本可以通过分词 (英文等语言不 必分词) 预处理提取有语义的最小构成单元 ,所以文 本一般以单词频率向量来表征其语义特征 ,如 TF2 IDF 加权方法[4] . 但这种方法基本丢失了单词之间 的序信息.
3) 序列一般长度很长 ,且其相似性度量计算很 费时.
因此 ,在海量的序列数据中快速找到所需信息 是一项重要的研究工作. 目前 ,对序列数据进行高效 查询成为研究热点.
1 序列相似性度量及其距离分布的统计信息
1. 1 序列数据的基本概念及其分类 序列数据可以定义如下 :给定字母表 Σ, 一条序
列 S 是 (值 , 序) 信息对的有序链表 , 记作 S = { ( s1 , o1 ) , ( s2 , o2 ) , …, ( sn , on ) } , 其中 , si 是序列 S 的第 i 个元素 值 , 且 si ∈Σ, oi 是元 素 s i 对 应 的 序 信 息 值 (1 ≤i ≤n) . 序列 S 的长度记作| S| , 即| S| = n. 对于 任意的 1 ≤i ≤j ≤n , S [ i , j ] = { ( si , oi ) , …, ( sj , oj ) } 称为序列 S 的子串 ,也称为q2gram ,其中 , q = j - i + 1. 序列 S 所有的 n - q + 1 个 q2gram可以通过在序 列 S 上每次移动一个大小为 q 的窗口来获得. { ( si1 , oi1 ) , ( si2 , oi2 ) , …, ( sik , oik ) } 称为序列 S 的子序列 , 其中 1 ≤I1 ≤I2 ≤…≤Ik , k ≤n. S [ 1 , i ]和 S [ j , n ] (1 ≤i , j ≤n) 分别称为序列 S 的前缀和后缀.
事件序列中元素值可 以是 多种 数据 类型 , 且 序信息是时间序 ,与文本 、生物序列等字符序列本质 不同 ,且时间序列和数据流是属于两个比较独立的 研究领域 ,都有自己独特的模型构建方式和分析方 法 ,本文只对字符序列如文本和生物序列等相似性 查询技术的各个方面进行综述. 如不作特别说明 ,本 文以后论述的序列就是字符序列. 1. 2 序列相似性度量
2) 生物序列 ( biological sequence) . DNA ( RNA) 和蛋白质是最基本的两种生物序列 ,分别由核苷酸 和氨基酸排列组成. DNA 序列的字母表是Σ= { A , G , C , T} ,蛋白质序列的字母表大小为 20. DNA 和 蛋白质可以看作是很长的字串 ,没有明显的“单词” 概念. 生物序列中的 motif (有一定生物学功能的序 列片段) 可以用来表征序列特征 ,但在生物信息领域 寻找 motif 本身就是一个很有挑战的问题[5] ,且不 同序列的 motif 有可能不同 ,这使得抽取生物序列 的特征十分困难.