（交通信息工程及控制专业论文）Motif+Finding及其Closest+String相关问题的算法研究.pdf

摘要 生物信息学( 又称生物计算学) 是一门生物学与计算机科学以及 应用数学等学科相互交叉而形成的一门新兴学科，其主要任务是揭示 海量生物学数据中蕴含的生物学意义、探索生命活动的奥秘。m o t i f f i n d i n g 和c l o s e s ts t r i n g 问题都是生物计算中基础而重要的研究问题， 在很多领域得到了广泛的应用，甚至生物计算以外的编码理论。近年 来这两个问题得到了广泛的研究，如何应用最新的研究技术，如分布 式系统和固定参数理论，为这两个问题提出更好的解决方案是本文研 究的重点。 论文在深入分析已有算法的基础上，提出了m o t i f f i n d i n g 问题的 分布式算法，并设计与实现了分布式系统，对问题进行有效求解，实 际测试结果表明分布式算法是正确且高效的；综合已有算法的优点， 提出了计算广义c l o s e s ts t r i n g 问题最优上界的新方法，对c l o s e s t s t r i n g 问题的下界进行了推导，设计并优化了下界相关算法，弥补了 固定参数算法在d 较大且不存在结果时运行时间太长的缺憾，为判断 在下界是否存在结果和求所有解提供了快速有效的方法。 论文对算法的设计思想及实现作了详细的说明，对测试结果也作 了深入的分析，实验结果表明这些算法是可行且高效的。 关键词生物计算；m o t i f f i n d i n g 问题；c l o s e s ts t r i n g 问题；分布式 算法；固定参数算法 a b s t r a c t b i o i n f o r m a t i c s ( c o m p u t a t i o n a lb i o l o g yi na n o t h e rw o r d ) i san e w s c i e n c ef i e l d r e s e a r c hi nt h i sf i e l di n v o l v e sm u l t i - d i s c i p l i n e ss u c ha s b i o l o g y , c o m p u t e rs c i e n c e ，a p p l i e dm a t h e m a t i c s ，e t c c o m p u t a t i o n a l b i o l o g yi ss u b j e c tt oe x p o s et h eb i o l o g i c a ls i g n i f i c a t i o no fl a r g ea m o u n t o f b i o l o g i c a ld a t aa n de x p l o r et h em y s t e r yo f l i f ea c t i v i t i e s m o t i f f i n d i n g p r o b l e ma n dc l o s e s ts t r i n gp r o b l e ma r eb a s i ca n di m p o r t a n ti nt h e r e s e a r c ho fc o m p u t a t i o n a lb i o l o g y , w h i c hf i n da p p l i c a t i o n si nm a n yf i e l d s ， e v e n ，o u t s i d ec o m p u t a t i o n a lb i o l o g y , i nc o d i n gt h e o r y b o t ho ft h e ma l e w i d e l ya n dd e e p l ys t u d i e di nt h el a s tf e wy e a r s ，a n dh o wt oc r e a t eb e t t e r s o l u t i o ns t r a t e g yw i t hl a t e s tr e s e a r c ht e c h n o l o g y , s u c ha sd i s t r i b u t e d s y s t e ma n df i x e d p a r a m e t e rt h e o r y , i 8t h ek e yp o i n to f t h i st h e s i s a f t e rt h ed e e pa n a l y s i so fe x i s t e n ta l g o r i t h m s ，t h i st h e s i sp r e s e n t sa n e wd i s t r i b u t e dp a r a m e t e r i z e da l g o r i t h mt os o l v em o t i ff i n d i n gp r o b l e m ， a n dd e s i g no ft h ed i s t r i b u t e ds y s t e mc o o p e r a t i n gw i t ht h ea l g o r i t h ma s w e l l ，t h e np r o v e si t sr i g h ta n de f f i c i e n tb ya n a l y s i n gt e s tr e s u l t so nt h e d i s t r i b u t e d s y s t e m ；a n e w s t r a t e g y , c o m b i n i n ga d v a n t a g e s o fa b r a n c h a n d b o u n d a l g o r i t h ma n d af i x e d - p a r a m e t e r a l g o r i t h m ，t o c o m p u t eo p t i m a lu p p e rb o u n do fg e n e r a lc l o s e s ts t r i n gp r o b l e m ；f o r m u l a o fd e d u c i n gl o w e rb o u n da n dt h ed e s i g na n do p t i m i z a t i o no fn e w a l g o r i t h m so nl o w e rb o u n d t h ea l g o r i t h m sc o m p l e m e n tt h ec o n s u m i n g t o om u c ht i m ed i s a d v a n t a g eo f t h ef i x e d - p a r a m e t e ra l g o r i t h mw h e ndi sa l i t t l el a r g e ra n dt h e r ei sn os o l u t i o n , a n da r es u i t a b l et oc h e c kw h e t h e r t h e r ee x i s t ss o l u t i o no nt h el o w e rb o u n da n dc o m p u t ea l ls o l u t i o n sa s w e l l t h ed e s i g na n dr e a l i z a t i o no ft h e s ea l g o r i t h m sa r ep r e s e n t e di nd e t a i l i nt h i st h e s i s ，a sw e l la st h ea n a l y s i so f t e s t i n gr e s u l t s ，w h i c hi n d i c a t et h a t t h ep r o p o s e da l g o r i t h m sa r eo f h i g he f f i c i e n c ya n df e a s i b l e k e yw o r d sc o m p u t a t i o n a lb i o l o g y ；m o t i ff i n d i n gp r o b l e m ；c l o s e s t s t r i n gp r o b l e m ；d i s t r i b u t e da l g o r i t h m ；f i x e d - p a r a m e t e r a l g o d t h m 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其它人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其它单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： 圣一固 日期：j 虹年上月上日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文； 学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名； 耋鹂 导师签名 眺毕凸卫日 硕+ 学位论文第一章绪论 第一章绪论 随着现代科技的发展，生物技术与信息技术的融合成为大势所趋。人类基因 组计划的初步成功，意味着人类基因组的研究将全面进入信息提取和数据分析阶 段，即生物信息学发挥重要作用的阶段。人类基因组计划及生物信息研究过程中 产生了海量数据，如何分析这些数据，从中获得生物结构、功能的相关信息成为 基因组研究取得成果的决定性步骤。 1 1 生物信息学相关研究内容 二十世纪生物科学技术发展迅速，在数量和质量上都极大地丰富了生物科学 的数据资源。大量的生物学数据资源中蕴含着重要的生物学规律，这些规律是我 们解决许多生命之谜的关键所在，然而以人脑来分析生物数据的传统手段已经无 法满足现在的需求，我们强烈需要一种强有力的工具来协助人脑完成这些分析工 作。二十一世纪生物科学的重点和潜在的突破点已经由二十世纪的实验分析和数 据积累转移到数据分析及其指导下的实验验证上来。伴随着生物科学这一需求的 加剧，以数据处理分析为本质的计算机科学技术和网络技术同样获得了突飞猛进 的进展，自然就成为生物科学家的必然选择。计算机科学技术和网络技术日益渗 透到生物科学的方方面面，一门崭新的、拥有巨大发展潜力的生物信息学逐渐发 展和成熟起来了吲。 生物信息学( b i o i n f o r m a t i c s ，又称生物计算学) 是生物学与计算机科学以及 应用数学等学科相互交叉而形成的一门新兴学科。该学科领域包含了生物信息的 获取、处理、储存、分发、分析和解释等在内的所有方面。由于当前生物信息学 发展的主要推动力来自分子生物学，生物信息学的研究主要集中于核营酸和氨基 酸序列的存储、分类、检索和分析等方面，所以目前生物信息学可以狭义定义为 i l 】：将计算机科学和数学应用于生物大分子信息的获取、加工、存储、分类、检 索与分析，以达到理解这些生物大分子信息的生物学意义的交叉学科。 从研究内容看，生物信息学既涉及基因组信息的获取、处理、贮存、传递、 分析和解释，又涉及蛋白质组信息学如蛋白质的序列、结构、功能及定位分类、 蛋白质连锁图、蛋白质数据库的建立、相关分析软件的开发和应用等方面，还涉 及基因与蛋白质的关系如蛋白质编码基因的识别及算法研究、蛋白质结构、功能 预测等，另外，新药研制、生物进化也是生物信息学研究的热点【2 】；从研究方法 看，生物信息学涉及了生物学、数学、计算机科学和工程学，依赖于计算机科学、 硕士学位论文 第一章绪论 工程学和应用数学的基础，依赖于生物实验和衍生数据的大量储存，目标就是要 发展和利用先进的计算技术解决生物难题，最重要的任务是从海量数据中分析、 提取和发掘新知识。其中用到的计算技术包括机器学习、模式识别、数据发现与 挖掘、组合学、随机模型、字符串和图形算法以及高性能计算、并行处理等等【3 】。 欧美等发达国家在生物信息方面已有较长时问的积累。从数据库的角度来 讲，早在6 0 年代，美国就建立了手工搜集数据的蛋白质数据库。美国洛斯阿拉 莫斯国家实验室于1 9 7 9 年建立g e n b a n k 数据库，欧洲分子生物学实验室1 9 8 2 年开始提供核酸序列数据库e m b l 的服务，日本也于1 9 8 4 年着手建立国家级的 核酸序列数据库d d b j 并于1 9 8 7 年开始提供服务。从专业机构的角度来讲，美 国于1 9 8 8 年成立了国家生物技术信息中心( n c b i ) ，其目的是进行计算分子生 物学的基础研究，构建和散布分子生物学数据库；欧洲于1 9 9 3 年3 月着手建立 欧洲生物信息学研究所( e b i ) ，日本也于1 9 9 5 年4 月组建了信息生物学中心 ( c i b ) 【2 】。 我国的众多科研机构也纷纷参与了生物信息学的研究领域。1 9 9 6 年，北京 大学加入欧洲分子生物学网络组织( e m b n a ) ，成为该组织的中国国家节点，并 成立生物信息中心，为生物、医学、制药、农业、环境等领域的研究开发提供生 物信息资源服务，并开展二次数据库构建、软件集成、基因组分析等研究。1 9 9 8 年8 月，中科院基因组信息中心暨北京华大基因研究中心成立。2 0 0 0 年3 月， 中科院上海生命科学研究院生物信息中心成立，2 0 0 1 年7 月3 日起正式运作， 与北京大学生物信息中心一起分别维护着国内两个专业水平相对较高的生物信 息学网站。2 0 0 1 年4 月，中国首届生物信息学大会在北京召开，其盛况空前。 与会人员来自各个研究领域，所作报告内容涉及生物信息学的各个方面。 生物信息学的兴起引起了众多公司或组织以及国际计算机巨头的强烈关注， 世界各国纷纷成立相应的研究机构，美国的一些著名大学走在了最前列，像哈佛 大学、普林斯顿大学、斯坦福大学、加州大学伯克利分校都先后成立了生物学、 计算机、数学、物理学等多学科交叉的新中心【4 】。许多大公司例如m o t o r o l a 公司、 h p 计算机公司以及s u nm i e r o s y s t e m 公司等都建立了生命科学部，投资生物信息 公司以谋求一席之地。 生物信息学的当前重要研究课题包括：大规模基因组测序中的信息分析，非 编码区信息结构分析，遗传密码的起源和生物进化，完整基因组的比较研究，大 规模基因功能表达谱的分析，与生物大分子的结构模拟与药物设计等【甜。就目前 的数学和计算机科学的能力而言，对数据容量达到上十亿字节的数据库进行生物 计算仍然是一项很艰巨的任务，因此研究高效算法，发展适用的处理手段，便成 为其中的主要研究热点之一。 硕士学位论文第一章绪论 1 2m o t i f f i n d i n g 问题 生物信息学最重要的基础任务之一是从海量数据中提取新知识，其中包括从 生物序列中识别编码蛋白质的基因以及发现调控基因表达的各种信号位点。这一 过程正是m o t i f f i n d i n g 。这里的m o t i f 是指生物序列中具有特定保守功能的信号 位点( s i t e ) 或模式( p a t t e r n ) 。通过找到不同调控蛋白质内在亲缘关系的调控位点能 更好地理解基因表达控制和调控过程。从生物序列中发现这些信号位点对研究共 表达基因和共调控基因中的绑定位点、基因选择性剪接以及生物体细胞中基因表 达和基因调控等问题具有重要意义，并有助于确定生物序列的功能和阐明生物序 列之问的进化关系以及从生物物理学和病理学上研究基因和蛋白质之间的交互 关系、细胞发育和细胞反应等方面的研烈2 7 1 。 1 2 1 问题定义 m o t i f f i n d i n g 问题用最简单的形式可以表达为以下内容：已知一个序列样本 和一个植入到不同未知位置的m o t i f , 我们能够找到这个未知的m o t i f 吗? 如果一 个长为，的m o t i f ( 包含，个字符) 没有突变的植入到每个序列中，可以通过直接 列举出现在样本中的长为的所有子串来找到m o t i f 但是，生物学中的m o t i f 都是 易受突变影响的，所以通常不能完全一致的出现。一个逼真的模型应该是允许未 知的m o t i f 带一些突变的植入到样本序列中。一个( , t 0 - m o t i f 是指一个长为f 的 m o t i f , 植入到样本的序列中，最多带d 个突变 6 1 。依照p e v z n e r 的( 厶d ) m o t i f 模型【1 9 】随机产生k 个长度均为甩的随机序列，在每个序列中随机挑选一个位置植 入一个( 厶田m o t i f , 该m o t i f 基于一个长为，允许有d 个突变的模式p 产生。m o t i f f m d m g 问题要求在不知道模式p 和植入位置的情况下找出这些植入的m o t i f 基因是遗传的基本的物理和功能单位。一个基因就是位于某条染色体的某个 位置上的核苷酸序列，其中蕴含着某种特定功能产物( 如蛋白质或r n a 分子) 的 编码【2 l 】。基因是编码一条多肽链或功能r n a ( 如r r n a 、t r n a ) 所必需的全部核 苷酸序列，是d n a 分子链上特定区域。基因是一段与多肽链或功能r n a 产生 有关的d n a 片段，包括编码区前的引导序列、编码区后的尾部序列、编码区内 的插入序列和编码区序列【2 j 】。 基因突变是指由于d n a 碱基对的置换、增添或缺失而引起的基因结构的变 化，亦称点突变。基因突变是生物变异的主要原因，是生物进化的主要因素。根 据基因结构的改变方式，基因突变可分为碱基置换突变和移码突变两种类型2 2 1 。 碱基置换突变：由一个错误的碱基对替代一个正确的碱基对的突变叫碱基置 换突变。例如在d n a 分子中的g c 碱基对由c g 或a t 或t a 所代替，a t 碱基 对由t a 或g c 或c g 所代替。碱基替换过程只改变被替换碱基的那个密码子， 3 硕士学位论文第一章绪论 也就是说每一次碱基替换只改变一个密码子，不会涉及到其他的密码子。 移码突变：基因中插入或者缺失一个或几个碱基对，会使d n a 的阅读框架 ( 读码框) 发生改变，导致插入或缺失部位之后的所有密码子都跟着发生变化，结 果产生一种异常的多肽链。 我们的算法中所指的替换操作，就对应于碱基置换突变，插入和删除操作对 应于移码突变。从这里就可以看出替换操作由于不会对d n a 序列长度产生影响 而单独归于一类，插入和删除操作则另外归为一类，而且插入和删除操作是存在 联系的。 若突变个数为d ，则称二者之间的距离为d 。距离的量度有海明距离 ( h a m m i n gd i s t a n c e ) 和编辑距离( e d i td i s t a n c e ) 两种，前者只允许出现替换 突变，而后者允许出现替换、插入以及删除突变。 1 2 2 研究现状 已经证明m o t i ff i n d i n g 问题是n p 难的( 2 3 l ，其中寻找( 1 5 ，4 ) m o t i f 是由 p e v z n e r 和s z e 提出的一个算法挑战，然而对于k = 2 0 ，n = 6 0 0 的序列来说 ( 1 4 ，4 ) ，( 1 6 ，5 ) 和0 8 ，6 ) - m o t i f 问题都是公认为更难的 6 1 。 为解决m o t i ff i n d i n g 问题一些优秀的软件工具已经被设计出来，如基于贪 婪算法的c o n s e n s u s t 2 4 1 ，基于g i b b s 取样的c d b b s d n a 2 5 1 ，基于e m 算法的 m e m e 2 6 】等。但是c o n s e n s u s g i b b s d n a 和m e m e 若缺少好的开始点就不 能检测到相当强的m o t i t t 5 1 。 除了上面提到的算法以外，还有一些基于详尽的列举所有可能的m o t i f 的 m o t i ff i n d i n g 算法，这样就保证了能够找到最优的m o t i f 但是，这种列举算法 的运行时间是随着m o t i f 的长度，的增加呈指数增长的，由于有些挑战问题中， 通常比较大，因而这种算法在这种挑战问题中会变得不可行。其他的m o t i f f i n d i n g 算法已经由f r a e n k e le ta 1 以及r i g o u t s o s 和f l o r a t o s 提出 6 1 。 p c v z n c r 和s z e 介绍了两个新算法：w i n n o w e r 和s p s t a r 例，这两个算 法都能成功的解决寻找( 1 5 。4 ) - m o t i f 挑战问题。概要的说，w i n n o w e r 算法构造 一个图，这个图的顶点对应于k 个输入序列中的长度为，的子序列，如果有两个 顶点对应的子序列至多在2 d 个位置上不同并且不是来自于同一个输入序列，就 用边将这两个顶点连接起来。然后w n n o w e r 在这个图中寻找一个大小为七 的团。第二个算法s p s t a r ，开始时依次为输入的每个单独的长为，的子序列从 其他输入序列里选择一个最接近的匹配，并用一个配对得分和迭代会聚出结果 m o t i t t l 9 】。但是同时p e v z n e r 和s z e 指出这两个新算法虽然比以前提出的算法有 优势，但是也不能解决某些难问题，如：c o n s e n s u s 、g i b b s d n a 和m e m e 在寻找植入到 = 6 0 0 个字符序列中的( 1 5 4 ) - m o t i f 时均失败了，s p s t a r 则在n 4 硕士学位论文第一章绪论 = 1 0 0 0 时失败，而w i n n o w e r 在n 1 3 0 0 时则变得非常耗时甚至不可用【5 1 。 j e r e m y b u l f l e r 和m a r t i n t o m p a 介绍了叫做p r o j e c t i o n 6 】的算法，它基于 使用输入的长为f 子序列的随机映射，这种思想与前面介绍的所有m o t i f f i n d i n g 算法有很大不同。这个算法的关键思想是从，个位置中随机选择k 个，然后用这 k 个位置作哈希函数h ( x ) 。当足够数量的长为，子序列哈希到同一个桶中时，他 们就有可能是要寻找的m o t i l 试验证明p r o j e c t i o n 算法在植入的m o t i f 问题上比其他所有算法都表现 要好。在使用随机产生的输入序列的试验里，p r o j e c t i o n 典型的解决了困难 的植入的( 1 4 ，4 ) ，( 1 6 ，5 ) 一和( 1 8 ，6 ) - m o t i f 问题。甚至当解决这些难题时，成功运 行时间最长的p r o j e c t i o n 仅耗时一个小时，而许多则只用了几分钟。 p r o j e c t l 0 n 还具有w i n n o w e r 和s p s t a r 所没有的优势，这就是 p r o j e c t i o n 是一个统计算法，这意味着如果用户愿意用同一个输入反复运行 多次，则找到植入的m o t i f ( 也包括其他存在的m o t i o l 舸能性将会增加f 6 1 。但是 这个算法的一个致命缺点是，当实例中有插入和删除将破坏用固定的序列位置来 定义映射的概念，这时这个算法将不可用，而不幸的是，插入和删除是生物序列 中的经常出现的现象。 而u r ik e i t h 和p a v e la p e v z n e r 设计一种既扩充了样本驱动方法的查找能 力，又避免了模式驱动方法的计算的复杂性的混合方法：m u l t i p r o f i l e r 算法。 这个算法法利用“多位置剖面”来分散噪声的影响，能在适合的地方获得更多的 解决噪声的能力，因而能够发现p r o j e c t l 0 n 算法发现不了的更为细微的m o t i l 但是这个算法所用的模型是一个不完善的模型，当m o t i f 中的一些位置有多于一 个的优性字符时，会对处于相同位置的其他优性字符产生不必要的影响【5 1 。 一种新的基于样本的穷举搜索算法：判据搜索算法【7 】针对三个序列片段相似 性关系判据作为剪植规则，能够有效的剪裁搜索空间，从而获得较高的执行效率， 但是该算法的判据推导是基于海明距离的，因而无法求解以编辑距离为量度的问 题。 由此可见，已有算法中快速算法往往会产生一些偏差，而精确算法则又耗时 太多，如何即提高精度又加快求解速度是该问题的一个难点。 1 3c l o s e s ts t r i n g 问题 在生物计算中序列选取问题是研究者面临的最重要的问题，因为分子生物学 中的许多问题都涉及到从一组给定的d n a ，r n a 或蛋白质序列中找出一个与所有 序列均相似的公共序列。这些问题在定位绑定位点和在未排序的序列中寻找保守 区域，遗传药物目标辨认，设计遗传探针，通用p c r 启动子设计【1 3 捌和计算生物 硕士学位论文第一章绪论 学之外的编码理论【2 9 j 0 1 中均得到了应用。这些问题均可视为公共子序列的延伸问 题。关于公共区域的量度有多种标准，一个流行的最基本的量度标准是最大海明 距离。这些问题经过抽象可以抽象成两种基本问题，c l o s e s ts t r i n g 问题和c l o s e s t s u b s t r i n g 问题1 3 1 1 ，其中c l o s e s ts t r i n g 问题又是c l o s e s ts u b s t r i n g 问题的基础，我 们将集中阐述c l o s e s ts t r i n g 问题。 1 3 1 问题定义 c l o s e s ts t r i n g 问题( 又称为c o n s e n s u ss t r i n g 或c e n t e r s t r i n g 问题) 描述： 输入：基于字母表长度均为z 的k 个序列s l ，s 2 ，s k 。 闯题：找到一个长为，的序列s 使得d 最小并且d h ( s ，墨) d ，i = 1 ，七? 其中，幽( j ，毋) 代表序列j 和毋间的海明距离。 上述定义是应用较为广泛的被称为广义c l o s e s ts t r i n g 问题，j e n sg r a m m 给 出了固定参数d 的c l o s e s ts t n n g 问题定义： 输入：基于字母表长度均为，的序列s l 沈，龇，和一个非负整数d 。 问题：是否存在一个长为，的序列s 使得d 。( s ，墨) d ，i = 1 ，后? 1 3 2 研究现状 由于其在计算分子生物学及编码理论中的重要应用，c l o s e s ts t r i n g 问题近年 来得到了广泛的研究i s , 9 , 1 0 , 1 1 】，包括对其复杂性的研究 1 2 , 1 3 , 14 】。 在近似算法方面，1 9 9 7 年b e n - d o r 等提出了一个与c l o s e s ts t r i n g 问题类似 的c o n s e n s u s 问题，给出了近似率为2 的近似算法【3 9 1 ，该算法是应用于当d 很大 时的次优近似算法，但是由于直接线性规划松弛技术在d 比较小的时候会引入很 大的错误从而无法工作。1 9 9 9 年，l a n e t o t 等正式提出了c l o s e s ts t r i n g 问题，并 证明了它是n p 难的，同时提出了一个近似率为4 ，3 的近似算法【1 3 】( 【4 0 】也独立 的提出了近似率为4 3 的近似算法，但是只适用于d 很大的情况) ，李明应用多 项式时间近似方案( p o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m e ，简称p t a s 算法) 提出了一个更好的近似算法【8 】，他在2 0 0 2 年又提出一个近似率为1 + e ( 可以 任意小) 的多项式时间近似算法f 阍，算法承袭了作者一贯采用的分治法思想，并 结合了整型线性规划技术，获得了d ( ( n 2 m ) o ( i g 4 ) 的时间复杂度。虽然称为多项式 时间近似算法，其实当比较小时，算法的时间复杂性仍然相当高，不大可能在 现实中得到应用。 在精确算法方面，通过研究其参数复杂性【3 2 邓3 4 1 ，得出它是固定参数可解的 结论【3 5 那3 7 1 ，无论对参数d 还是弘m 。在d n a 序列相关问题中，b c r m a n 等提出 了一个当d 是固定值时的多项式时间精确算法f 3 8 i ，j e n sg r a m m 应用其一个重要 的理论发现设计出了一个能够求精确解的固定参数算法 1 6 , 17 l ，m e n e s e s 提出了 6 硕士学位论文 第一章绪论 能够解决广义c l o s e s ts t r i n g 问题，即最大距离不确定的c l o s e s ts t r i n g 问题，的 整数规划方法【1 8 】，该算法是一个针对比较大d 下的分支界限算法，并给出了计算 c l o s e s ts t r i n g 问题最优上界的一个方法。 以上方法各有其优点，但是也都不同程度的存在应用的局限性，如何弥补这 些不足以及怎样综合运用上述方法的优点更好的解决c l o s e s ts t r i n g 问题是一个 难点也是本论文研究的重点。 1 4m o t i f f i n d i n g 问题与c l o s e s ts t r i n g 问题的关系及研究意义 当应用m o t i ff i n d i n g 算法找到了序列中的可能的m o t i f s 之后，可以如文献 2 8 中应用c l o s e s ts t r i n g 问题的算法判断找到的m o t i f 是否真的是一个m o t i f , 另外若生物工作者得到一组m o t i f 之后想从这些序列得到他们的祖先序列，即从 植入的m o t i f 还原出模式p ，也可以应用c l o s e s ts t r i n g 问题的求解方法来得到。 生物学上可借助l i n k e r - s c a n n i n gm u t a g e n s i s 、d n af o o t p r i n t i n g 和g e l s h i r 分析( e m s a ) 等实验方法来发现序列中的调控信号位点【4 虮。但这些实验预测相当 耗时，且都存在实验误差，对序列中的噪音也不敏感。随着基因组序列、基因表 达微阵列( m i e o r - a r r a y ) 数据和c h i p c h i p 实验技术的研究的迅速发展，人们得到 了大量基因序列和相关的基因信息，因此可借助计算方法搜索m o t i f , 以此弥补 传统生物实验方法的不足【4 9 1 。在可靠的实验数据还无法得到的情况下，虽然通过 计算预测的结果不是非常精确，但生物学家可以根据算法预测的结果指导其生物 实验的展开。 1 5 研究目标与内容 课题的具体研究目标是通过广泛了解m o t i ff i n d i n g 和c l o s e s ts t r i n g 问题的 研究现状，深入分析已有算法的优缺点，结合最新的研究技术，拓展已有算法并 设计新算法，以更好的解决这些问题。 具体内容包括； ( 1 ) m o t i f f i n d i n g 算法分布式研究 通过深入分析c l i q u e 算法，研究并实现一个集合图理论算法的精确与分 布式算法的高效的算法，为m o t i ff i n d i n g 问题的解决提供一个新思路，为通用 分布式平台的设计提供有价值的经验参考； ( 2 ) c l o s e s ts t r i n g 问题上下界的研究 广义c l o s e s ts t r i n g 问题中其上下界的推导是一个很重要且有研究价值的方 向，结合已有算法设计更快速更准确求解最优上界的算法是本文的一个探讨点； 7 硕士学位论文 第一章绪论 ( 3 ) 设计精确求解c l o s e s ts t r i n g 问题的新算法 能够精确求解c l o s e s ts t r i n g 问题的固定参数算法存在一些缺陷，如何设计算 法弥补这个缺陷是本文研究的重点，另外如何改进算法使得算法能够快速准确的 求所有解也是本文的一个探讨重点； ( 4 ) 通用分布式平台的设计 结合生物计算中分布式算法的特点，设计一个提供通用接口适合各种分布式 算法的平台，为生物计算中n p 难问题的解决提供一个有效的途径。 1 6 论文组织结构 本课题针对生物计算中两个基础问题m o t i ff i n d i n g 和c l o s e s ts t r i n g 的提出 背景和相互联系展开讨论，重点分析已有算法的优缺点并研究如何应用新技术拓 展改进现有算法。针对上述研究内容，本文各章内容安排如下： 第一章绪论。简要介绍了生物信息学的概念以及研究内容，在介绍了m o t i f f i n d i n g 问题和c l o s e s ts t r i n g 问题的基本定义之后，介绍了这两个问题的研究现 状，以及两个问题之间的联系，分析了两个问题的难点、已有算法的优缺点及亟 待解决的关键问题。 第二章m o t i ff i n d i n g 问题求解。本章在对已有算法进行了详细分析的基础 上，提出了对已有算法的改进及新算法设计，并对算法实旖了分布式处理，最后 给出了实际测试结果证明了我们的分布式算法的价值。 第三章c l o s e s ts t r i n g n 题求解。本章在深入分析固定参数算法和整数规划算 法的基础上，综合两个算法的优点提出了改进计算最优上界的方法，给出了 c l o s e s ts t r i n g 扣 题d 的下界的推导，并设计优化了下界相关算法。 第四章分布式计算系统设计。本章主要研究如何设计适合生物计算程序特 点的基于i n t e m e t 的分布式计算系统，简要介绍了系统设计方案及系统各模块调 用流程，重点阐述了关键的算法与系统的信息交流，容错机制。系统配置等问题。 第五章r 总结与展望。本章对m o t i f f i n d n g 和c l o s e s ts t r i n g 问题的算法研究 和开发工作进行了总结，并展望将来进一步深入研究的思路。 8 硕士学位论文 第二章m o t i f f i n d i n g 问题求解 第二章m o t i f f i n d i n g 问题求解 由于m o t i ff i n d i n g 问题中距离的量度有海明距离和编辑距离两种，但是大 部分的算法只能解决以海明距离为量度的问题，而对编辑距离束手无策，另外由 于生物数据通常都十分巨大而m o t i f f i n d i n g 问题又是典型的n p 难问题，对于较 难的m o t i ff i n d i n g 问题的求解通常需要花费太多的时间而难以让人忍受，于是 应用分布式系统求解m o t i f f i n d i n g 问题的想法应运而生。 2 1 典型算法 已有算法中有一种应用p e v z n e r 和s z e 的图理论算法将m o t i f f i n d i n g 问题转 换成在k 分图中寻找k - c l i q u e 问题的思路使用较为普遍，该图理论算法描述如下： 在每个序列岛中的第_ ，个位置，建立一个顶点s 口，表示一个从位置a 1 ， 外- 件1 ) 开始的长为f 的子串。如果f 并且8 _ f f ，之间的距离不超过2 d 用一条边 将两个顶点相连。 定义2 1 分图) 设o = ( v , e ) y g - - 个无向图，若v = v ( n ，v ( 协，其中v o 为 第i 个结点部集，使得v ( 1 u uv ( k v ，v ( 1 n nv ( 。l - 西，且g 中的每条边的 两个端点不属于同一个结点部集，则称g 为k 分图，记作g = ( v ( n ，v ( ) ，e ) 。 下面给出了应用该思路的c l i q u e 算法的简述。 2 1 1 序列模型 使用在p e v z n e r 和s z e ( 2 0 0 0 ) 中设想的组合( , d ) - m o t i f 模型：从一组固定长度 的随机序列舾l ，m ) 开始，在每个序列中随机挑选一个位置植入一个随机改变了 d 个位置的长为，的模式p ，通过这样来植入一个( , d ) - m o t i f op 和植入位置都是 未知的，则m o t i ff i n d i n g 问题就是要去发现植入模式的位置。虽然这个形式在 假设一个中心模式p 的存在时被不可避免地过分简单化了，每个序列只有一个 m o t i f 实例，但是这是一个合理的允许被比拟为其它方法的起步模型。 2 1 2 从序列生成k 分图 应用p e v z n e r 和s z e 的图理论算法，一个( 田m o t i f 对应于一个大小为k 的 团，因此将m o t i ff m d m g 问题转化为在图中寻找大型团的问题。虽然图表明了 一个m o t i ff m d m g 问题可能含有很多的顶点，但是有一个重要的发现，那就是 最大团的规模都很小。由于在( , d ) - m o t i f 中，边只存在于不同序列的顶点之间， 9 硕士学位论文 第二章m o t i f f i n d i n g 问题求解 结果图是一个k 分图，某一序列中所有的顶点都在同一个部分。这就将最大团的 大小限制在k 。实际上，在上述( 由m o t i f 模型中，每个序列都只包含一个m o t i f 实例并且最大团的大小为k 。为了简化分析过程，我们假设每个序列的长度都是 一样的，因此，图中每个部分的顶点数目都是一样的了。 我们定义在给定的一个每部分含有n 个顶点的k 分图g 中寻找一个最大团 的问题为c l i q u e k p ，可以证明c l i q u e r r 是一个n p 难问题，当最大团的大小 为k 时，我们称这个问题为k - c l i q u e ”。 2 1 3 在k 分图中寻找k - c l i q u e 定义2 - 2 ( k - c l i q u e k r ) 给定一个每个部分都有疗个顶点的k 分图g ，在图g 中寻找一个k - c l i q u e 。 我们将寻找特征串的问题形式化成为：给定，d ，疗的值和阈值t ，如果在 建立的图中最大团的总数不超过玎每个团代表一个m o t i f ) ，就将它们全部找出； 否则就报告其中没有特征串( f 刃。当一个m o t i f 很弱时，通常是存在着一些带有 相同性质的m o t i f 异变体，所以要使用一个合适大的t 来避免将这些模式遗漏。 尽管如此，这种变异不应该是大范围的以免导致一个非特征串。另一方面，将t 设得过小的话f 如：t = - 1 ) ，即使m o t i f 很强都可能导致模式的丢失，特别是当一个 给定的样本含有一个以上的m o t i f 时。我们将这个问题定义为k - c l i q u e k “0 定义2 3 ( k - c l i q u e k r ( 0 1 给定一个每个部分都含有n 个顶点的k 分图g ，如 果所有的大小为k 的团的总数不超过一个给定阂值t 的话就将它们全部找出。 我们将使用分治方法来解决这个问题。基本思想是这样的，因为每个序列都 包含了一个m o t i f 实例，我们可以将k 分图再细分为k 分图，满足条件后( j 并且 独立解决每个更小的予问题，只要在子问题中大小为七 的团的数量不是太高。即 使只使用了简单方法，每个子问题也都可以在o ( n ) 时间内解决。这些团可以被 用做第二个图的顶点，其中从同一个子问题中来的团驻留在同一个部分，同时如 果相应的团结合在一起可以形成一个更大的团的话那么每两个顶点之间由一条 边连接。为了获得使用怎样的七钧较好评估，我们使用了一个随机k 分图模型。 因为在实际情况中，的值通常很大，植入的模式成为图中很小的一部分，在期望 的时间分析范围内这个图也差不多可以被看成是一个随机图。由于相邻顶点之间 的交互作用和实际生物序列的非随机性存在，所以这难免是粗略的近似。 算法2 1 表示了一个使用递归过程的分治算法。在第一个递归层，k 的值同 上面定义的一样。在后来更深层的递归层中，我们发现即使是对最难的m o t i f f i n d i n g 问题，图变的如此稀疏以至于使七，1 2 都不能产生许多团，并且当与最外 1 0 硕十学位论文 第二章m o t i f f i n d i n g 问题求解 层相比较起来运行时间变得可以忽略。为了在一个给定的含有k 个部分的子图中 找到所有的团，可以使用一个运行时间为o ( n k 3 的简单列举算法，结果最外递归 层运行时间为o ( ( k k 3 n k 3 。一个要点就是七可能不能均分k 。在这种情况下，最 后的子图会加入更多与其他子图相覆盖的部分，需要对算法进行一点修改。 算法2 1 ：f i n d c l i q u e ( g = ( v n ，v ) ，e ) ) 输入