（计算机软件与理论专业论文）基于异构数据的复杂关联比对方法的研究与应用.pdf

沈阳理工大学硕士学位论文 摘要 由于历史原因，各部门、行业、领域先后保存了大量数据，这些数据因为体 系结构、操作系统、数据库、数据结构等方面的异构，导致信息不能自动地实现 共享与交换，需要靠人工与外界进行联系。随着信息化时代的到来，尤其是互联 网技术的蓬勃发展，这些信息越来越迫切地需要能够最大限度地相互共享、交换、 集成和再利用。这就需要对不同部门之间的数据进行集成和比对整合，实现部门 间数据的共享和重复利用。 据此社会现状，为了将各部门分散、异构的数据进行关联，比对出尽可能多 的相同、相似信息，将同源信息加以整合，提高信息的唯一性和时效性，本文对 异构数据的复杂关联比对方法进行了研究，研究结果在“辽宁信用数据交换中心 项目中得到了应用。 本文首先介绍了本课题的来源、研究目的及意义、国内外研究现状及技术发 展趋势等。其次，为了解决目前异构数据复杂关联比对结果成功率太低的问题， 研究了针对字段关联比对的字符串序列比对算法，找出了一条提高比对成功率的 途径，并对使用字符串序列比对算法前后的成功率情况进行了分析。然后，结合 项目要求建立异构数据复杂关联比对模型，并根据字段特征制定异构数据复杂关 联比对的数据流程。最后，结合项目的实际情况，根据建立的异构数据复杂关联 比对模型，阐述了异构数据复杂关联比对的具体实现情况。 关键词：异构数据；数据；字符串序列；比对 沈阳理t 大学硕士学位论文 a b s t r a c t b e c a u s eo fh i s t o r i c a lr e a s o n s ，d e p a r t m e n t sa n dt r a d e sh a v er e s e r v e de n o r m o u sd a t a , w h i c hi sc a n n o tb es h a r e da n de x c h a n g e da u t o m a t i c a l l yb e c a u s es o m ec o n s t r u c t i o n d i f f e r e n c e si n s i d eo fs y s t e mc o n s t r u c t i o n ，o p e r a t i o ns y s t e m ，d a t a b a s e ，a n dd a t a c o n s t r u c t i o n t h ed a t ae x c h a n g eo fo u t s i d ei sa r t i f i c i a l l y t h ei n f o r m a t i o ns o c i e t yi s c o m i n g ，e s p e c i a l l yt h ef l o u r i s ho fi n t e m e tt e c h n o l o g y , t h e s ed a t ai su r g e n tt ob es h a r e d ， e x c h a n g e d ，i n t e g r a t e da n dr e u s e d t h ed a t ai n t e g r a t i o no fd i f f e r e n td e p a r t m e n t si s n e e d e d u p o nt h i s s o c i a lc i r c u m s t a n c e s ，i no r d e rt om a k e d i s p e r s e a n dd i f f e r e n t c o n s t r u c t i o n a ld a t ad e p a r t m e n t si n t e g r a t e da n db e c o m et oaw h o l eo n e t h i si s s u eh a sa d e e pr e s e a r c ho nt h ec o m p i l a t i o no fd i f f e r e n tc o n s t r u c t i o n a ld a t a a n dt h es t u d yi s a p p l i e df o r t h ep r o g r a mo f l i a o n i n gc r e d i td a t ae x c h a n g ec e f i t e r f i r s t l y , t h ea r t i c l ep r e s e n t st h es o u r c e ，r e s e a r c hp u r p o s e ，a n dt h em e a n i n go ft h e i s s u ea sw e l la st h ec u r r e n ts t u d ys i t u a t i o ni nh o m ea n di na b r o a d ，a n dt h et e c h n o l o g y d e v e l o p m e n tt r e n d s e c o n d l y , t h ei s s u em a k e sa na n a l y s i sa n dh a sr e s e a r c h e da r i t h m e t i c o fc h a r a c t e rr e l e v a n c yc o m p a r e dw i t hs t r i n gs e q u e n c ea n df i n do u ta ne f f e c t i v ew a yt o m a k ed a t ar e l a t e ds u c c e s s f u l l y t h e na c c o r d i n gt ot h ep r o g r a mr e q u i r e m e n t si t e s t a b l i s h e dt h em o d e lt or e s o l v et h ed i f f e r e n tc o n s t r u c t i o n a ld a t ar e l e v a n c y f i n a l l y , t h e i s s u ea c c o r d i n gt ot h ea c t u a l l yp r o g r a mc i r c u m s t a n c e st om a k eu pt h em o d e lo fd i f f e r e n t c o n s t r u c t i o n a ld a t ac o m p l e xr e l e v a n c y , a l s oi te x p a t i a t e st h ec o n c r e t em e a s u r e st o r e a l i z et h i sm o d e l k e y w o r d s ：d i f f e r e n tc o n s t r u c t i o n a ld a t a ；d a t a ；s t r i n go fc h a r a c t e rs e q u e n c e ；c o m p a r e 沈阳理工大学 硕士学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由作者本 人独立完成的。有关观点、方法、数据和文献的引用已在文中指出， 并与参考文献相对应。除文中已注明引用的内容外，本论文不包含任 何其他个人或集体己经公开发表的作品成果。对本文的研究做出重要 贡献的个人和集体，均己在文中以明确方式标明。本人完全意识到本 声明的法律结果由本人承担。 作者( 签字) ： 刮、磁i 趁 日期：脚歹月6 日 学位论文版权使用授权书 本学位论文作者完全了解沈阳理工大学有关保留、使用学位论文 的规定，即：沈阳理工大学有权保留并向国家有关部门或机构送交学 位论文的复印件和磁盘，允许论文被查阅和借阅。本人授权沈阳理工 大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 一签氨麓爹多秽币镶黝 日 期：细嘭弓多日 期：钐剜 第1 章绪论 第1 章绪论 1 1 课题来源 近年来，各部门、行业、领域根据各自不同的应用需求、业务流程、信息结 构和计算机软硬件环境等特点分别在不同历史时期先后保存了各种各样的历史数 据，它们绝大部分都是采用各自不同的开发工具、硬件平台、操作系统、网络协 议、数据库管理系统( d b m s ) 开发的，其所承载的海量信息绝大部分都是采用各自 不同的数据结构、数据类型、编码方式、表示形式和检索方法等。这时，信息化 建设过程中潜在的一些问题开始渐渐显露出来。这些数据因为体系结构、操作系 统、数据库、数据结构等方面的异构，导致信息无法交互，形成了一个个的信息 孤岛，不能自动地实现信息共享与交换，需要靠人工与外界进行联系。随着信息 化时代的到来，尤其是互联网技术的蓬勃发展，各部门、行业和领域的各类信息 越来越迫切地需要能最大限度地相互共享、交换、集成和再利用。如何完成不同 部门之间的数据集成和比对整合，实现部门问数据共享和重复利用已经成为一个 热门话题。 本课题据此社会现状，结合“辽宁信用数据交换中心 项目，研究如何对大 量异构数据进行复杂关联比对，找出尽量多的相同、相似信息，将同源信息整合 到一起，打破信息孤岛现象，使现有的数据信息可以得到更有效的共享、交换、 集成和再利用。 “辽宁信用数据交换中心”项目的数据来源十分广泛，共包括4 4 个省级部门 信源单位和1 4 个市级部门信源单位。这些信源单位使用前置机通过信息交换系统 将大量异构信息集成到统一的数据平台。各信源单位提供的数据可分为企业基础 信息和企业信用信息两部分，它们的数据结构根据本部门的业务特征各不相同。 如国税提供的信息中包括税务登记信息，而大连海关提供的信息中包括进出口产 品等。其中企业基础信息是进行复杂关联比对的关键。本课题的主要工作就是通 过对来自各信源单位的企业基础信息进行关联比对，形成的企业基础信息数据库， 并附加企业信用信息，形成统一的企业信用信息库。 1 沈阳理1 ：大学硕士学位论文 1 2 课题研究目的及意义 1 2 1 目前存在的问题 在“辽宁信用数据交换中心”项目的建设过程中，发现由于历史原因，目前 各部门提供的基础信息存在着不少数据质量问题，以企业举例，主要体现在以下 几个方面： 企业代码不一致：每个部门的业务系统采用了不同的编码来表示一个企业， 如工商局业务系统中的企业注册登记号，税务系统中的纳税人识别号，质监系统 中的企业组织机构代码等，这些系统根据自己的业务特征以各自的编码规则组织、 管理企业信息，编号仅在本系统中有明确的含义，到了别的系统中则可能没有意 义。 数据量不一致：由于目前各个业务系统之间尚未实现实时的数据交换，存在 着企业注册后，没有办理组织机构代码、税务登记等业务，造成了各系统之间数 据的差别。 数据项数据不合法：比如企业名称、注册日期等。 数据项数据不一致：各个业务部门记录的同一数据项的内容不同，主要体现 在企业名称、注册登记号、注册地等数据项。 代码标准不一致：比如民族、性别等，在不同的系统中采用不同的代码。 原始数据不真实：比如录入错误、恶意谎报等。 此外，还存在多词同义、恶意注册等现象，这些都给信息的数据比对工作造 成很大困难，使得在将分布的数据集中到统一的数据平台后，难以取得数据交换 的应有效果，这就失去了数据共享的意义。 1 2 2 研究目的 鉴于目前存在的上述问题，本课题主要研究将分散的数据集中到统一的数据 平台后，如何对数据结构不同的数据信息进行比对。 针对“辽宁信用数据交换中心”项目，本课题的研究目的是通过将各部门分 散、异构的数据进行关联，找出尽量多的相同、相似信息，将同源信息整合到一 起，建立辽宁省跨地区、跨部门的信用数据交换平台，建立立体开放的联合征信 服务体制，收集、整合、查询、发布各种政府机构、企业和个人的信用信息，实 现全省信用数据的交换与共享，为各级政府及其部门和社会公众提供信用信息服 2 第1 章绪论 务。 对其它现有的与“辽宁信用数据交换中心 项目中类似的信息孤岛现象，通 过本课题的研究也可以提供一个异构数据复杂关联比对的模型，为使现有大量分 散、异构的数据信息得到更有效的共享、交换、集成和再利用提供一条有效途径。 1 2 3 研究意义 对异构数据的复杂关联比对有利于发现信息的异同，以实现分散、异构数据 信息的共享、交换、集成和再利用。 以“辽宁信用数据交换中心 项目为例，在政府部门问数据交换的基础上， 根据各部门业务的需要，对来自不同部门的基础信息进行比对，可以根据比对结 果，找出部门间数据的差异和问题，更好地服务于各部门的业务工作。例如，税 务部门将从工商部门交换来的企业注册登记信息和税务登记信息比较，找出已办 理工商开业登记但未办理税务登记的企业，再剔除不需要办理税务登记的企业， 对剩下的企业就可以进行重点监控和检查，达到加强税源监控的目的。但实现这 些功能都是以好的比对方法为前提的，如果比对方法不好，就会产生大量的冗余 甚至错误数据，反而增加工作人员的工作量。因此，本课题的研究对提升政府信 息化应用水平、优化环境、促进经济社会发展有着重大的意义。 本课题的研究成果还具有很强的应用性，凡有“信息孤岛 现象存在的地方 都有其用武之地。 1 3 国内外研究现状及技术发展趋势 随着电子商务和电子政务在我国各行各业的广泛应用，各部门、行业和领域 的各类信息越来越迫切地需要能最大限度地相互共享、交换、集成和再利用。如 何完成不同部门之间的数据比对和整合，实现部门间数据共享和重复利用已经成 为一个热门话题。为了实现异构数据的共享，首先要解决的就是异构数据的转换 问题。一般来说，异构数据的转换主要包括两部分： 首先将分布式的不同或相同数据库的数据集成到统一的数据平台上，然后将 统一数据平台上的数据进行比对，把数据结构不同的数据进行关联，比对出尽量 多的相同、相似信息。 数据集成系统结构目前通常采用联邦式、基于中间件模型和数据仓库等结构， 这些结构分别在不同的着重点和应用上来解决数据共享问题，为企业提供决策支 沈阳理工大学硕士学位论文 持，这三种方法在一定程度上都解决了数据共享和互通的问题。但对于异构数据 比对的研究极少，通常采用的方法即为根据一个或多个关联字段对所有数据进行 比对，相符则认为是同源数据，这就造成了比对的速度和成功率很低，而对于本 文1 2 1 中提到的问题，不管是国内还是国外，目前都还没有被广泛推广使用的成 功案例。 针对这一情况，如果把要比对的文字信息看作字符串序列，那么，对相似文 字信息的同源性判断实际上就是对字符串序列的相似性判断。 目前对于字符串序列比对的问题并没有被广泛使用的成功算法，但字符串序 列比对与生物学上的d n a 序列比对有很大的相似性，可以借鉴其中的一些经典算 法，解决字符串序列比对成功率较低的问题。 生物d n a 序列比对算法发展的历史已经有了4 0 多年了。根据同时比对序列 数目的不同，序列比对分为双序列比对算法和多序列比对算法。 双序列比对( p a i r w i s ea l i g e m e n t ) 是指通过一定算法对两个序列进行比较，找出 两者之间最大相似性匹配。双序列比对是序列分析的常用方法之一，是多序列比 对和数据库搜索的基础。已有的双序列比对的算法有： 1 9 7 0 年g i b b s 提出的点阵法n ，点阵法是一种图像显示方法；之后m a i z e l 利 用带颜色的点阵法来识别各种相似区域幢，更加复杂的点阵图可基于不同的计分规 则而构建。虽然现在己经拥有许多更复杂更精确的方法来寻求相似性，但点阵描 述方法仍然是一个很流行很有效的描述方法。它是双序列比对的最基本方法，是 一个局部比对方法。 动态规划算法，是一种最优算法，典型的有1 9 7 0 年n e e d l e m a n 和w u n s c h 提 出的n e e d l e m a n w u n s c h 算法m ，适用于全局水平上和相似性程度较高的两个序列， 本质上是与点阵图类似。1 9 8 1 年s m i t h 和w a t e r m a n 提出了s m i t h w a t e r m a n 算法“1 ， 这是一种用来寻找并比较具有局部相似性的动态规划算法，在识别局部相似性时， 具有很高的灵敏度，一直是局部比对算法的基础。 动态规划算法所需的时间和空间复杂度太高，不适应于数据库的搜索，因此 又出现了各种启发式算法。应用最广的有：f a s t a 算法隋，是1 9 8 5 年由p e a r s o n 和 l i p m a n 提出的，基本思想是：一个能揭示出真实序列关系的比对至少包含一个两 个序歹0 都拥有的字( 片断) ，把查询序列中的所有字编成h a s h 表，然后再数据库 第1 章绪论 搜索时查询这个h a s h 表，以检索出可能的匹配。这样那些命中的字就能很快地被 鉴定出来。b l a s t 算法m ，由a l t s c h u l 等人在1 9 9 0 年提出，采用一种片断匹配算法 和一种有效的统计模型来找出目的序列和数据库之间的最佳局部比对效果。基本 思想是：通过产生数量更少的但质量更好的增强点来提取速度。之后d e l c h e r 于 1 9 9 9 年提出了全基因组比对的m u m m e r 算法n ，是一种基于后缀树数据结构的方 法，它在速度方面比b l a s t 算法快得多，缺点是仅能处理具有较高相似性的全基因 组序列的比对。b i nm a 等人在2 0 0 2 年提出了序列搜索的p a t t e r n h u n t e r 算法，该 算法创建了一个新颖的匹配模型，不仅提高了匹配的敏感度，而且大大降低了同 源搜索的匹配时间。无论对于双序列比对还是多序列比对都有一些经典的比对算 法。 多序列比对就是把两条以上可能有关系的序列进行比对的方法。已有的多序 列比对算法大体分三类：精确比对算法、渐进比对算法、迭代比对算法。 精确比对算法最为经典的是多维n e e d i m a n w u n s c h 算法、但其可行的计算维 数为3 , c a r r i l l o l i p m a n 算法n ，通过减小计算空间，将计算维数提高到l o 。 渐进比对算法由h o g e w e g 首先提出，f e n g 和t a y l o 又加以完善。m u l t a l i n 方 法n o l 是基于用一系列双序列比对开始的思想，然后基于双序列比对的打分值进行一 个分层次的聚类。当序列都分成类后，开始进行多序列比对，计算出多序列中的 两个序列比对的新值，重新构建一棵树。这个过程不断进行，直到分值不再上升， 此时多序列比对也就结束了。非常著名的、被广泛使用的多序列比对软件包 c l u s t a l w c “，( 其w i n d o w s 版本为c l u s t a l x ) 基于渐进比对思想构建，基本思想是基于 相似序列通常具有进化相关性这一假设，此算法敏感性较差。 目前基于迭代的算法越来越多的使用到多序列比对中，取到了不错的比对结 果。基于模拟退火、遗传算法、h m m s 、g i b b s 抽样等的多序列比对算法被广泛应 用于多序列比对问题的求解，其中s a g a 基于遗传算法构建，共设计了2 2 种不同 的遗传算子，其比对结果的准确性与c l u s t a l w 相近“”，提出的基于粒子群优化算 法的多序列比对优化算法也是迭代比对算法。但目前还没有一个最佳的多序列比 对算法。 随着信息化的不断发展，对数据共享的要求越来越高，异构数据的同源比对 方法的研究已经提上日程，并将向多关联性、智能化的方向发展。 沈弭 理工大学硕十学位论文 1 4 本文主要工作和内容安排 本课题的研究主要结合“辽宁信用数据交换中心项目，对异构数据库的复 杂关联比对方法进行研究。主要工作包括两方面的内容：首先，结合项目要求建 立异构数据复杂关联比对模型，并根据字段特征制定异构数据复杂关联比对的数 据流程。但由于1 2 1 提出的各种问题，造成比对成功率较低，不能很好地达到数 据集成的目的。针对这一现象，着重研究了在对选定字段进行比对时，如何提高 成功率的问题，引入了比对相似率的概念，使用字符串序列比对算法处理要进行 关联的字段，使比对成功率得到一定程度的提高。该方法已在项目中得到具体应 用。 论文内容具体安排如下： 第一章主要介绍课题的背景来源、研究目的及意义、国内外研究现状及技术 发展趋势等。 第二章主要就如何提高异构数据复杂关联比对的成功率的问题，研究了针对 字段关联比对的字符串序列比对算法，找出了提高比对成功率的一条有效途径， 并对实际应用中使用字符串序列比对算法前后的比对成功率情况进行了比较分 析。 第三章结合项目要求建立异构数据复杂关联比对模型，并根据数据结构特征 制定异构数据复杂关联比对的数据流程。 第四章结合项目的实际情况，根据建立的异构数据复杂关联比对模型，说明 了异构数据复杂关联比对的具体实现情况。 最后对全文进行总结并指出不足之处和今后的研究方向。 第2 章字符串序列比对算法研究 第2 章字符串序列比对算法研究 2 1 研究目的及方法概述 将分布式的不同或相同数据库的数据集成到统一的数据平台后，主要问题集 中在如何将统一数据平台上的大量数据进行关联比对，把数据结构不同的数据进 行关联，找出尽量多的相同、相似信息，将同源信息整合到一起，使现有数据得 到最有效的利用。 由于历史原因，一般各部门中的信息存在着不少数据质量问题，以企业举例， 主要体现在以下几个方面： 企业代码不一致：每个部门的业务系统采用了不同的编码来表示一个企业， 如工商局业务系统中的企业注册登记号，税务系统中的纳税人识别号，质监系统 中的企业组织机构代码等，这些系统根据自己的业务特征以各自的编码规则组织、 管理企业信息，编号仅在本系统中有明确的含义，到了别的系统中则可能没有意 义。 数据量不一致：由于目前各个业务系统之间尚未实现实时的数据交换，存在 着企业注册后，没有办理组织机构代码、税务登记等业务，造成了各系统之问数 据的差别。 数据项数据不合法：比如企业名称、注册日期等。 数据项数据不一致：各个业务部门记录的同一数据项的内容不同，主要体现 在企业名称、注册登记号、注册地等数据项。 代码标准不一致：比如民族、性别等，在不同的系统中采用不同的代码。 原始数据不真实：比如录入错误、恶意谎报等。 此外，还存在多词同义、恶意注册等现象，这些都给信息的数据比对工作造 成很大困难，使得在将分布的数据集中后，比对成功率较低，难以取得数据比对 的应有效果，这就失去了数据共享的意义。 以上列举的问题中，企业代码不一致、代码标准不一致等问题可以根据具体 沈研1 理工大学硕十学位论文 需求确定该数据对数据集成是否有实际意义。在比对完成后可以对数据量不一致、 恶意注册、恶意谎报等情况进行处理：对来自不同部门的基础信息进行比对，根 据比对结果，找出部门间数据的差异和问题，并更好地服务于本部门的业务工作。 例如，税务部门将从工商部门交换来的企业开业注册登记信息和税务登记信息比 较，找出已办理工商开业登记但未办理税务登记的企业，再剔除不需要办理税务 登记的企业，对剩下的企业就可以进行重点监控和检查，达到加强税源监控的目 的。数据性数据不合法等问题可以在非法数据处理中解决。但对数据项数据不一 致、录入错误等造成的比对成功率较低的问题，目前还没有被广泛推广使用的成 功案例。 针对这一情况，本章着重研究确定了异构数据复杂关联比对的字段关联性后， 在对选定要进行关联比对的具体字段进行比对时，如何找出相似文字信息的同源 性，提高比对成功率的问题。这是本课题研究的重点也是难点。 如果把要比对的文字信息看作字符串序列，那么，对相似文字信息的同源性 判断实际上就是对字符串序列的相似性判断。 目前对于字符串序列比对的问题并没有被广泛使用的成功算法，本课题在对 生物学上的d n a 序列比对算法进行了研究后，发现字符串序列比对与d n a 序列 比对有很大的相似性，于是决定借鉴其中的一些经典算法，解决字符串序列比对 问题，并在此基础上提出了字符串序列比对相似率的概念，使比对成功率得到一 定程度的提高。 关于序列比对，首先有一点要加以关注：对于相似性问题没有一个单一的、 精确的和统一的概念。例如以下单词：b e e r 、h e r e 和h e a r ，它们在发音和拼写上 很相似，但在意义上却是毫不相干! 所以通常说到一个相似问题，只能针对某一 具体方面。同样的，在文字比对问题上，一般不考虑发音和字义，序列可以看成 是一条字符串，对文字的比对实际上就是字符串的比对。因此，本章的重点就是 研究如何使用字符串序列比对算法得出字符串序列的比对相似率，以判断文字信 息的同源性。 2 2 字母表与序列 本小结主要介绍字符串序列比对中的一些基本概念。 一般而言，字母表是一些字母的组合，序列就是在字母表的基础上组成的。 第2 苹字符串序列比对算法研究 对于序列搜索，有一些重要的字母表，但是，序列搜索技术并不完全依赖某一特 定的字母表。 在算法中用到以下一些定义： a 是字母表。 a 是a 中所有有限字母序列的集合。 a ，b ，c 表示各个不同的单个字母。 s ，t ，u ，v 表示a 中各条序列。 isl 表示序列的长度。 子序列：为了表示序列中的子序列以及单个的字母，将序列s = a c c a c g t a 表示为：s = o a ! c 2 c 3 a 4 c s g 6 t t a 8 。这样，用i ：s j 表示s 中在i 和j 中的子序列。 当然，0 i j isi 。子序列0 ：s ：i 称为前缀，子序列i ：s ：lsl 称为s 的后缀。 特别的，当i - j 时，i ：s ：j 表示空串；当i = j - 1 时，i ：s ：j 表示s 中的第j 个字符， 可以缩写为s j 。两个序列s 和t 串联起来用s + + t 表示。例如：a c c + + c t a = a c c c t a 。 2 3 处理距离 有两个方法可以用来定量两条序列的相似性。一个方法为将一个数值与一对 序列联系起来，一个较高的值表示其具有较大的相似性。用此方法，由于所使用 的相似性计算方法各不相同，在解释相似性时就会各不相同。 距离( e d i td i s t a n c e ) 的概念与相似性有关联性。它将序列表示成矩阵空间中的 点。用距离作为测量方法也就是将一个数值和一对序列联系起来，距离越大，相 似性越小，反之亦然。距离方法满足矩阵的数学公理，距离值永远也不会是负值。 在大多数情况下，距离和相似性方法在意义上是可以互通的，距离越小，意 味着相似性越大，反之亦然。有时候相似性方法更具有灵活性。 2 3 1h a r e m i n g 足巨离法 最简单的距离计算法是h a m m i n g 距离法。该算法对于两条具有相等长度的字 符串序列，累计其在各个位置上具有不同文字的个数。 例如： 序列s ：似ra g c a aa g c a c a c a 序歹0t：tj气aa c a t aa c a c a c t a 9 沈研 理： 大学硕士学位论文 h a m m i n g 距离( s ，t ) ： 2 36 这种距离计算法在所使用的字符串序列中有错别字的情况下非常有用，但它 的灵活性不够。首先，比对的字符串序列具有不同的长度；其次，在两条字符串 序列之间，它们的文字位置上并没有固定的对应关系，在漏字、添字的情况下就 会由于位置偏移导致距离值夸大。例如以上的例子中最右边的序列，h a m m i n g 距 离值表明s 与t 相差了6 个字母，但另一方面，如果从s 中减少g 并且从t 中减少 t ，则它们都变成了a c a c a 以，从这个意义上说，它们仅仅差了两个字母。 2 3 2l e v e n s h t e in 足巨离法 另一种计算距离的算法是l e v e n s h t e i n 距离法。该算法对两条序列进行比对工 作时考虑将s 变成t 要进行的操作值，即计算将一条字符串序列变成另一条字符串 序列时进行插入、删除、替换操作的权值。在这里，引入了间隙字母“ ，计算两 条字符串序列s 、t 的距离，如果要将s 变成t ，有可能进行的操作共有四种： ( a ，a ) 表示字符匹配，s 变成t 时不需要做改变； ( a ，) 表示在s 中删除字符a ； 瓴b ) 表示当a 与b 不同时，用b 替换a ； ( ，b ) 表示在s 中插入字母b 。 由于s 和t 具有对称性，在s 中的删除动作相当于在t 中的插入动作，反之 亦然。 两条序列s 与t 的比对是在相对位置上的比对，s 与t 可以通过使用间隙符号 “ 得到相同的长度： 例如字符串s ( a g c a c a c a ) 和字符串t ( a c a c a c t a ) - s ：agcacac as ：a g cacaca t ：a cacac ta或t ：acacact a 按列对应的比对，根据下面所描述的操作将s 变成t ： 左边： 匹配( a ，a ) 右边： 匹配( a ，a ) 删除( g 一) 置换( gc ) 匹配( c ，c )插入( - ，a ) 匹配( a ，a )匹配( c ，c ) 匹配( c ，c ) 匹配( a ，a ) 第2 苹字符串序列比对算法研究 匹配( a ，a )匹配( c ，c ) 匹配( c ，c )置换( 八t ) 插入( ，t )删除( c ，- ) 匹配( a ，a )匹配( a ，a ) 左边的比对表明采取的动作为一个删除，一个插入，其他均为匹配。右边的 比对表明采取的动作为个删除，一个插入，两个置换，其他为匹配，与左边的 操作有些区别。 对这些操作给定一定的权值f 0 ： ( i ) ra ) = o ； t 0 b ) = l ( a ! - b 时) ； ( ) ( 如- ) = ( 1 ) ( ，b ) = 1 。 这个方案被称为l e v e n s h t e i n 距离法，也称为单位取值模型。它的主要好处就是 简单性。 这里使用序列分析的一些原则： 两条字符串序列s 与t 比对的取值是将s 变成t 的所有操作的取值的总和。 两条字符串序列s 与t 的最优比对是在所有比对中具有最小取值的比对。 s 与t 的操作距离( e d i td i s t a n c e ) 是在某一取值函数6 0 时s 与t 的最优比对的取 值，用d ( s ，t ) 表示。 对于前面例子使用单位取值模型，得到以下的取值： s ：agcacac a s ：ag cacaca t ：a c a c a c t a或t ：a c a c a c t a 取值：2取值：4 这里很容易看出左边的取值在单位取值模型下是最优的，操作距离d ( s ， 0 = 2 。单字节和双字节字符处理方法是相同的。 2 4 利用动态规划法处理序列比对 显而易见，在两条序列间的可能的比对的数目极其巨大，除非权值函数很简 单，否则要挑选出其中的最优的比对还是相当困难的。如何挑选出其中的最优比 。 沈阳理n t 大学硕七学位论文 对? 在这里，采用动态规划算法来解决这个问题。 考虑两个前缀o ：s ：i 和o ：t ：j ，其中i ，j l 。假设已经知道s 和t 所有的更短 的前缀的最优比对，也就是： 0 ：s ：( i 1 ) 和o ：t ：( j - 1 ) o ：s ：( i 1 ) 和o ：t ：j o ：s ：i 和o ：t ：( j 1 ) 这样o ：s ：i 和o ：t ：j 的最优比对肯定是从以上所描述的比对的其中一个扩展开来 的，采取以下某种操作： 置换操作( s i ，1 ；j ) ，或者匹配操作( s i ，1 ；j ) ，看是否s i 黾 删除操作( s i ，- ) 插入操作( - ，1 ；j ) 仅选择其中的最小值： 吃( o ：s ：f ，0 ：t ：d = r n i n d 印( o ：s ：( f 一1 ) ，o t ：u 一1 ) ) + d 墨，0 ) ， 丸( o ：j - ( i 1 ) ，o ：t ：) + 从邑，- - ) ， ( 2 1 ) 以( o ：s ：f ，0 ：t ：u o ) + c o ( - , t j ) ) 当其中某一前缀为空时，例如i = 0 或j = o 时，则有： d 国( o ：s ：o ，0 ：t ：0 ) = 0 ( 2 2 ) 屯( o ：s ：f ，o ：t ：o ) = 吃( o ：s ：o 一1 ) ，o ：t - 0 + 烈& ，- - ) f o ri _ 1 ，isl ( 2 - 3 ) 丸( o ：s ：o ，0 ：t ：力= 吃( o ：s ：o ，0 ：f - ( j 1 ) + 缈( 一，t j ) f o r j = l ，ltl ( 2 4 ) 根据( 2 1 ) ( 2 2 ) ( 2 3 ) 和( 2 4 ) ，对某一给定( ) 函数，所有前缀i 或j 的操 作距离( e d i td i s t a n c e ) 定义为一个大小为( is | + 1 ) 木( itl + 1 ) 的距离矩阵d = ( d i ，j ) ，其中d i ， j - do ) ( o ：s ：i ，0 ：t ：j ) 。 对于d i ，j 的最小化公式中的三个选择导致了在矩阵成员间有如下的依赖关系： 第2 章字符串序列比对算法研究 d “i - ! j 一1 _ 吐1 ，歹 l d i j jd i j 距离矩阵的右下角成员包含了所需的结果： q 批i = 丸( o ：s ：i si ，0 ：t ：lti ) 丸( s ，t ) ( 2 5 ) 对于前面所描述的比对示例：字符串s ( a g c a c a c a ) 和字符串 t ( a c a c a c t a ) ，得到距离矩阵如下图2 1 ： 毒上 士 adacacr a oi2 3 4 5678 a101 23 4 56 h ， g211234567 e32 l22 3 4 56 a432122345 c5432 122 34 a654321233 ch6 543 2123， a87 6543 2 22 图2 。1 距离矩阵 可以在距离矩阵中画一条路径表示当取最小值时选择了那些操作，如图2 2 。 对角线表示置换或匹配操作，垂直线表示删除操作，水平线表示插入操作。这样， 这条路径表示最优比对的操作距离值即d q ( s ，0 = 2 。值得注意的是：在某些情况下， 最小值选择并不唯一，可以画出各种不同的路径表示其他可选的最优比对。 a a 秽a dra a g d 五 口 a 口 1 哇 图2 2 最优比对路径 1 3 沈阳理工大学硕士学位论文 动态规划算法是用来求解最短路径问题常用算法。它是一个完备算法，通过 它可以得到任何一个具有非负边有向图的最短路径。d i j k s t r a 是应用动态规划求解 最短路径问题的经典算法。它依照图中的每个点到起点的最短路径长度的由小到 大的顺序依次求出图中每个点到起点的最短路径。这里所列的算法对原始的 d i j k s t r a 作了适当修改：当找到了起点s 到终点t 的最短路径后就终止搜索。 d i j k s t r a 算法： 输入：网络图n = ( g = ( v ，e ) ，j ) ，对于任一边( u ，v ) e ，l ( u ，v ) o ；起点：s ；终 点：t 输出：s 到t 的最短路径 b e g i n s 一由；s 一 s ；p ( s ) - - - 0 ；p ( s ) 一巾； r e p e a t 令u 为s 中具有p 值最小的点； s s u u ) ；s 一s7 u ： u = tt h e nr e t u r np ( t ) ； f o r 任- - ( u ，v ) e ed o i f v ! s o rp ( u ) + l ( u ，v ) ； s 一s u v ； e n d i f u n t i lf a l s e ； e n d 集合s7 中存放的点到起点s 的路径( 不一定是最短路径) 已被找到，在以 后的运算中有可能被转移到s 中。而集合s 中存放的点s 的最短路径都已被找到， 并且会一直被保留在集合中。p ( u ) 表示一条从s 到u 的路径；p ( u ) 表示这条路径的 长度。d i j k s t r a 算法不断更新s 中点的p 和p 值。当s 中的点t l 到s 的最短路径 被找到后，就把u 放入集合s 中并对u 的后继点进行访问，称之为“扩展点u ， 即把u 的所有尚未放入s 中的后继点放入s ，或修改u 的已在s 中的那些后继 点的p ( u ) 和p ( u ) 值。如此循环，越来越多的点被放入s 或s ，直到点t 被放入s 。 第2 苹字符串序列比对算法研究 此时程序停止。p ( t ) 即为s 到t 最短路径。在最坏的情况下，图中的每个节点都被 “扩展一次。这种算法在求解两条或三条序列的比对时能够得到较为满意的结 果。但是当序列的条数稍稍增加这种方法就不能应付了，因为当序列的条数d 稍 稍增加图中节点总数兀：。( 朋，+ 1 ) 会迅速增长。 容易证明以下两点： 第一，对于在d i j k s t r a 算法中任一属于集合s 的点u ，有：p ( u ) = p ( s ，u ) ，其 中l 聿( s ，u ) 表示图中起点s 到点u 的最短路径长。 证明：s 集合中具有p ( v ) 值最小的点v 被放入s 集合以后，s 中具有p 值 最小的点的p 值大于v 的p 值，因为： 首先，s 集合中其它任一点的p 值都大于点v 的p 值 另外，由点v 产生或修改的点的p 值有： p ( u ) = p ( v ) + 1 ( v ；u ) p ( v ) 因此，s 中具有p 值最小的点虽然不断地更替，但它们的p 值在不断地增大。 所以p ( u ) p ( v ) ，p ( u ) 4 - l “u ) p ( v ) ，又因为点的p 值有可能被s 中具有p 值 最小的点修改，所以v 不会在以后的计算中被任何s 中的点修改。 证毕。 第二，当d i j k s t r a 算法把任一点u 放入集合s 中时，对于任一v ( v s ) ：l 木( s ， u ) l 幸( s ，v ) 。 证明：当ves 时，已知u 是s 中p 值最小的点，即：p ( u ) p ( v ) 。又由 上面已证明的第一点可知，当u 被放入集合s 中时，p ( s ，u ) = p ( u ) 且由它修改的后 继点的p 值都比它大，因此已在或即将进入s 集合中的点的p 值都会大于u 的p 值即l 宰( s ，u ) 。直至v 进入s 时它的p 值都大于l 奉( s ，u ) ，即l 木( s ，u ) p ( s ，v ) 。 证毕。 这两点说明从起点s 到s 集合中任一点的最短路径都不可能经过除s 以外的 任何一个点。并证明了d i j k s t r a 算法的正确性。它是建立在网络中的边长都是非负 数这个条件之上的。这个条件对于d i j k s t r a 算法非常重要。 第二点还说明了d i j k s t r a 算法得到最短路径的过程：在每一次循环过程中， 不断的把除s 中点以外的最接近起始点s 的点加入集合s 中。这就意味着，这个 算法会按照图中点到起始点最短路径长度的次序，依次把图中点放入集合s ，也 沈阳理工大学硕士学位论文 就是求出这些点到起始点的最短路径及其长度，直到终点t 也被放入。 2 5 利用斛算法处理序列比对 2 5 1 算法需要解决的问题及意义 对于多序列比对的问题，由前面的分析知道，如果用传统的动态规划算法， 时间和空间复杂度都很高为o ( n 4 ) 。当d 增大时，时间空间复杂度成爆炸趋势增长。 因此，对于条数较高的序列比对问题，使用动态规划算法是不切实际的。a 宰改进 算法能够保证求解精度的同时大幅度的减小搜索区域的大小。这个算法也是在动 态规划的基础上改进后得到的。它的关键是引入了对搜索点到终点t 的最短路径进 行合适的估计，把这个估计作为整个搜索过程的一个参考因素。这样，就避免了 搜索那些理论上根本不可能出现在最短路径上的点。但是，以前的a 幸算法没有充 分利用这个到终点t 的最短路径值的估计。本节对到终点t 的最短路径值进行估计 的方法进行改进，使得a 宰算法的优点得以充分实现n ”。 2 5 2 斛算法及其特点 2 5 2 1 动态规划的搜索机制 a 木算法仍然采用动态规划的搜索思想，即不断的根据已搜索到的点的信息对 未扩展到的点进行搜索。把未进入集合的点中具有最好解的点放入已求出最优解 的集合，同时对与这个点有关系的后继的解的信息进行修改。这样，求出了最优 解的集合中的点不断增多，直到终点也进入这个集合后，算法结束。与原始动态 规划算法不同的是：a 木算法对最优解的定义有所不同。原始的动态规划定义当一 个点到起始点的最短路径长p ( v ) 为这个点是否进入最优解集合s 的标准。在这个 点进入最优解集合s 之前，它到起始点的路径及其长度不断的被修改，直到求出 了一个最小值，然后被放入集合s ，同时修改它的后继点的到起始点路径p ( v ) 及其 值p ( v ) 。而a 木算法则引入了一个到终点t 的最短路径长的估计参数h ( v ) 。规定点 到起始点s 最短路径长与到终点t 的最短路径长的估计值之和：p ( v ) + h ( v ) 为这个点 是否进入最优解集合s 的标准。与原始的动态规划相同，在这个点进入最优解集 合s 之前，它到起始点的路径及其长度