（计算机科学与技术专业论文）以stem为单位的rna结构比对算法研究.pdf

国防科学技术大学研究生院丁学硕士学位论文 摘要 基于比较基因组学预测r n a 二级结构是当前r n a 研究的热点问题，多序列 比对作为其关键过程，比对的准确性直接影响到结构预测的精确度。但传统的多 序列比对算法并未考虑序列中蕴含的结构信息，因此，r n a 结构比对成为人们关 注的焦点。由于现有算法受到存储空间的限制，难以处理超过1 0 0 0 核苷的序列， 且在比对过程中没有考虑伪结情况，导致比对结果可能受到伪结的影响。针对这 些问题，本文提出了一种基于s t e m 的r n a 结构比对算法，主要工作和贡献如下： 1 给出了s t e m 的寻找算法和比对算法。我们采取滑动窗口模式改进了基于序列 的折叠矩阵搜索s t e m 的方法，并综合s t e m 之间的位置相似度和序列相似 度构建了s t e m 比对的打分机制。此外，还针对长序列窗口搜索的高复杂度问 题，提出了相应的并行化策略。 2 以s t e m 比对算法为基础，利用序列拆分技术和递归方法，构建了一种基于 s t e m 的双序列结构比对算法。 3 提出了r n a 多序列结构比对算法。在双序列结构比对的基础之上，利用加权 矩阵和指导树策略构建r n a 多序列结构比对，并提出了并行化策略。数值实 验表明我们的方法能够有效地处理长度不超过2 0 0 0 核苷序列的结构比对问 题，同时保持较高精度。在相似度较高的情况下得到的比对结果优于m a r n a 、 p m m u l t i 算法。 主题词：r n a ，s t e m ，序列比对，结构比对 第i 页 国防科学技术大学研究生院工学硕l = 学位论文 a b s t r a c t t h es e c o n d a r ys t r u c t u r ep r e d i c t i o no fr n a b a s e do nc o m p a r a t i v eg e n o m l c si sa h o tp r o b l e m b e i n go n eo ft h ek e yp r o c e s s e so ft h i sm e t h o d ，m s a ( m u l t i p l es e q u e n c e s a l i g n m e n t la f f e c t s t h ep r e c i s i o no fp r e d i c t i o ng r e a t l y f o rt h el o s so fs t r u c t u r a l i n f o r m a t i o ni nt r a d i t i o n a lm s aa l g o r i t h m s ，t h ep r o b l e mo f s t r u c t u r e a l i g n m e n t a l g o r i t h m sb e c o m e sp r e v a i l i n g ，a n dm a n ya l g o r i g h m sa r ed e v e l o p e d b u tb e c a u s e o ft h e m e m o r yl i m i t a t i o n ，t h es t r u c t u r ea l i g n m e n ta l g o r i t h m si ne x i s t e n c ea r ed i f f i c u l tt od e a l w i t hs e q u e n c e so fm o r et h a n10 0 0b a s e sl e n t h ，a n da n o t h e rp r o b l e mi st h a ts t r u c t u r e a l i g n m e n ta l g o r i t h m sm a y b eo b t a i naf a u l t yr e s u l tc a u s e db yi g n o r i n gp s e u d o k n o t t o s o l v et h e s ep r o b l e m s ，t h i st h e s i sp r e s e n t san e wm e t h o do fs t r u c t u r ea l i g n m e n tb a s e d o n s t e mf r a g m e n t sf o ri 矾as e q u e n c e s 。t h em a i nw o r ka n dc o n t r i b u t i o n so ft h i st h e s i sa r e a sf o l l o w s ： 1 a na l g o r i t h mo ff i n d i n ga n dc o m p a r i n gs t e mf r a g m e n t si sp r e s e n t e d w eu s ea s l i d i n gw i n d o wt oi m p r o v et h em e t h o d o ff i n d i n gs t e mf r a g m e n t sb a s e do nf o l d i n g m a t r i x ，a n du s ep a r a l l e lt e c h n i q u et or e d u c et h et i m ec o m p l e x i t yc a u s e db yt h e s l i d i n gw i n d o w 2 a na l g o r i t h mo fp a i r w i s es t r u c t u r a la l i g n m e n to fl as e q u e n c e si sg i v e nb a s e d o n t h es t e m t h r o u g ht h es e q u e n c es p l i t t i n ga n dr e c u r s i o n ，w em a k et h ep a l r w l s e s t r u c t u r a la l i g n m e n tb yd i v i d i n gl o n gs e q u e n c e si n t os h o r ts e q u e n c e sb a s e do nt h e s t e m s ，a n dg i v e na na l g o r i t h mb a s e do nt h es t e ma l i g n m e n t 3 a na l g o r i t h mo fm s ao f 础n as e q u e n c e sb a s e do nt h es t e mi sd e s i g n e d w eu s e t h e w e i g h tm a t r i xa n d t h ed i r e c t i o n t r e et oc o n s t r u c tt h em u l t i p l es e q u e n c e sa l i g n m e n t b a s e do np a i r w i s es t r u c t u r a la l i g n m e n t s w ea l s oi n t r o d u c eap a r a l l e lt e c h n i q u et o r e d u c et h et i m ec o m p l e x i t y t h en u m e r i c a le x p r e m e n ts h o w st h a to u rm e t h o dl s s u f f i c i e n tt os o l v et h es t r u c t u r a la l i g m e n to fr n as e q u e n c e sw i t hn om o r et h a n 2 0 0 0l e n t hw i t hh i g hp r e c i s i o n o u rm e t h o do b t a i nb e t t e ra l i g n m e n tr e s u l t sf r o m s e q u e n c e sw i t hh i g hs i m i l a r i t y ，c o m p a r e dw i t hp m m u l t ia n dm a i 必a k e yw o r d s ：r n a ，s t e m ，s e q u e n c ea i i g n m e n t ，s t r u c t u r ea l i g n m e n t l 一一- _ - - - _ _ _ - - - _ 一 第i i 页 国防科学技术大学研究生院工学硕士学位论文 表目录 表3 1 加速比和并行效率- 1 7 表4 1s t e m 的比对得分2 7 表5 1 双序列结构比对的c s 和s p s c o r e 得分表：3 6 表6 1s p s c o r e s 得分表1 。4 7 表6 2s p s c o r e s 得分表2 4 8 表6 3 长度不超过1 0 0 0 的结构比对c s 得分表4 8 表6 4 长度超过1 0 0 0 的结构比对c s 得分表。4 9 第1 n 页 国防科学技术大学研究牛院t 学硕l 学位论文 图目录 图1 1r n a 二级结构组成单元示意图2 图3 1 逆补序列的一个例子1 1 图3 2 一条r n a 序列的折叠矩阵1 1 图3 3 序列的一个s t e m 1 2 图3 4 序列s e q 的所有s t e m 一1 3 图3 5 窗口化寻找s t e m 的例子1 5 图3 6 加速比示意图1 8 图3 7 并行效率示意图l8 图4 1 同一序列上的两个s t e m 之间的不相交关系2 l 图4 2 同一序列上的两个s t e m 之间的相交关系2 2 图4 3 两条序列上的s t e m 的位置关系2 3 图4 4 逻辑迭代图2 4 图5 1 序列拆分过程3 0 图6 1 加权矩阵的一个例子3 9 图6 2 指导树的一个例子4 0 图6 3 裁剪的一个例子4 3 图6 4 多序列比对算法的测试比较4 5 图6 5 比对结果中的结构信息4 6 图6 6 二级任务工作池策略5 0 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下透行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：邀墨型羞坚焦鲮曼坠箜蛰出殖篡洼受窒 学位论文作者签名：雄忽 日期：矿g 年f 月，日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题日：哒墨型羞望焦煎塞坠箜擅出挝篡洼珏巍 学位论文作者签名：越日期：7 形年f 月耳 作者指导教师签名：2 薄 日期溯年1 月1 日 国防科学技术大学研究生院学位论文 第一章引言 生物信息学是包含生物信息的获取、处理、储存、分析和解释等在内的一门 交叉学科，它综合运用数学、计算机科学和生物学的各种工具进行研究，目的在 于了解和阐明大量生物学数据所包含的生物学意义。生物信息学的研究内容几乎 涵盖了生命科学的各个领域，它的发展给生命科学研究带来重大的变革。生物信 息学的发展将对生命科学本身的发展产生革命性的影响，其研究成果将大人地促 进生命科学其他研究领域的进步。 序列比对是以核酸和蛋白质序列为依据，来比较两个或两个以上核酸或蛋白 质在碱基( a ，t ，c ，g ) 、氨基酸( 2 0 个氨基酸) 水平上的相似性。序列比对问 题是生物信息学中最基本的问题，也是生物信息学最基本的分析方法，生物信息 学中许多问题都和序列比对问题相关。多序列比对是以两两序列比对为基础，逐 步优化两条或多条序列比对结果的方法，其目的是建立两条以上序列可能存在的 进化关系。它在发现序列模体( m o t i f ) 【3 j 和保守区域、系统发育分析、结构预测等 方面具有重要的作用，是生物信息学当前研究的热点问题之一，多序列比对的应 用方向正变得更加广泛，如对蛋白质家族与进化关系的分析，检测与发现同源性 等，这些都是建立在对序列结构信息的研究基础之上，尤其在r n a 序列的研究 领域中，结构信息相似性的研究显得更加重要。因此，序列结构比对问题在生物 信息学中具有极其重要的意义。 1 1 课题背景 随着人类基因组及多种模式生物测序项目的完成，生物信息学的研究已步入 后基因组时代【4 。人们在获得静态、可作为参照标准的基因组序列信息后，已开 始系统地重点研究基因组的转录及调控，并进一步研究全基因组发挥功能的动态 机带u j t 4 1 。其中，r n a 在生物体内所起的重要作用越来越受到人们的关注，尤其 是非编码r n a ( n o n c o d i n gr n a ，简称n c r n a ) ，它是一类能够转录并执行一 定的功能但不编码蛋白质的r n a 分子拉j ，如t r n a l 6 1 、r r n a t7 1 、m i r n a t 8 】等。近 几年来，随着越来越多n c r n a 基因及其功能被识别和揭示，人们逐渐认识到 n c r n a 和蛋白质分子一样重要甚至是主要的功能性分子【9 】。本文课题正是来源于 国家自然科学基金项目( 6 0 6 7 3 0 1 8 ) “大规模n c r n a 二级结构预测算法及其并 行化研究 。 在对r n a 进行同源性研究、功能分析等深入研究之前，我们就需要对r n a 序列的二级结构进行分析，人们一般通过结构预测算法来预测r n a 的二级结构。 r n a 的二级结构组成单元通常包括茎环( s t e m ) 、发夹环( h a i r p i nl o o p ) 、内部环 第1 页 国防科学技术大学研究生院学位论文 ( i n t e r i o rl o o p ) 、突起环( b u l g e ) 、多分枝环( m u l t i l o o p ) 等等( 如图1 1 1 2 1 ) 。 内部环 发夹环突起环 多分枝环 图1 1r n a 二级结构组成单元示意图 多序列比对作为算法的输入来预测所有r n a 序列的共同二级结构，可以大 大提高结构预测的精度，多序列比对结果中隐含的结构信息比较将直接影响后续 r n a 序列分析结果的可信度。由于r n a 序列所特有的协同变异性，导致同源 r n a 序列可能在序列水平上并不保守。因此，一般的多序列比对算法( 如 c l u s t a l w 1 0 】、t c o f f e e 【1 1 】等) 并不适用于r n a 序列的比对，尤其是在序列相似性 较低时，其比对结果更差，已经不能满足人们的需求。r n a 序列中的结构信息 以及序列间的保守结构信息显得越来越重要，因此如何采取有效的序列结构比对 算法对r n a 序列进行比对成为人们急需解决的问题。 在现有的序列结构比对算法中，主要有两类方法：第一类方法以双序列结构 比对为基础，利用两两比对构建多序列比对。这类方法主要针对长度少于5 0 0 的、 序列，先找出每条序列中的结构信息，如茎环、发央环、内部环等l l 引，结合序列 相似和结构信息相似进行比对，然后根据t c o f f e e j i l l 系统或者进化距离分析，利 用两两比对构建成多序列比对，如m a r n a i l j 、r n a f o r e s t e r 1 3 j 、c b a i l 4 i 等。第 二类方法是首先寻找所有序列的结构信息，经过裁剪处理将结构信息规格化，直 接在多条序列间进行分析，寻找序列问匹配的结构信息，结合序列相似性，构造 多序列比对，如s c a r n a t l 5 】。但这两类方法都有所缺陷，主要存在以下几个问 题： 1 对长度超过1 0 0 0 核苷序列的处理能力不够； 第2 页 日n目 国防科学技术大学研究生院学位论文 2 在进行多序列结构比对的时候可能会丢失一些结构信息； 3 多序列结构比对中可能会受到伪结的影响。 如果无法对长度超过1 0 0 0 核苷的序列进行处理，那么对这些r n a 序列将无 法进行有效分析：如果丢失任何一个结构信息，都有可能导致最后结果有所偏差； 如果受到伪结影响，那么比对结果中将可能含有错误的保守区域，会给二级结构 预测算法带来未知的影响。 1 2 研究思路 由于序列的不同，其中蕴含的结构信息也会不同。而设计结构比对算法的目 的，就是为了在序列相似的前提下将序列中结构信息的相似度呈现出来。我们认 为，结构比对算法的核心，就是在比对过程中对序列中的所有结构信息进行比对 分析，将其中相似的结构信息匹配上，保留在比对结果中。为了找出每条序列中 存在的所有结构信息，并尽可能的在比对过程中找出保守的结构区域，不受到伪 结影响，同时能够有效的处理长序列比对，我们提出了本文的结构比对算法。 本文的主要研究思路是： 1 通过循环比对操作构建序列的折叠矩阵，然后根据折叠矩阵的数字特 征，用一定的判断机制和映射方法找出序列中的s t e m 部分。对于超过 5 0 0 碱基的长序列，我们采取滑动窗口模式来寻找序列的所有s t e m ， 以牺牲时间复杂度来解决由于存储空间引起的限制。 2 详细分析序列间s t e m 的位置关系，综合它们的位置相似度和序列相似 度构建s t e m 比对的打分机制，得到s t e m 之间的比对得分和结果。 3 基于s t e m 比对算法，通过寻找序列间的最佳匹配s t e m 对序列进行划 分，然后采用递归方式对子序列进行同样处理，以此构建双序列比对。 4 计算两两序列比对中的加权值得到加权矩阵，以此生成指导树并指导构 建多序列比对，最后经过裁剪优化处理得到最终比对结果。 本文算法的主要创新点有： 1 构建滑动窗口模式，计算分析最佳窗口大小来寻找长序列中的s t e m ； 2 利用序列拆分和递归方式将长序列的结构比对问题转化为若干子序列 的结构比对问题； 3 对部分算法提出了并行化策略。 1 3 论文结构 本文共分七章，内容组织如下： 第一章为前言，总体介绍r n a 结构比对的研究背景和和研究意义，并指出 了现存的主要问题，介绍了本文算法的主要工作与创新，以及论文结构。 第3 页 国防科学技术大学研究生院学位论文 第二章介绍了序列比对和结构比对的数学定义、研究现状以及现有算法的优 缺点。 第三章讨论了序列中的s t e m 寻找算法，分析窗口化模式寻找s t e m 的优 缺点，并采用并行化策略降低窗口划分带来的时间复杂度。 第四章详细讨论序列上的s t e m 位置关系以及序列间的位置关系，结合序 列比对的特点得出了s t e m 比对得分的打分机制，对序列间的s t e m 进行比对 评估。 第五章是本文的重点章节之一，介绍双序列结构比对算法，详细介绍比对过 程中的各个步骤，最后测试比对结果，分析算法优缺点。 第六章是本文的核心章节，详细讨论了多序列比对过程中的各个环节，尤其 对其中的关键步骤进行重点分析。选取r f a m 1 6 墩据库中家族数据对算法进行 测试，并将结果进行评估，与m a r n a 、p m m u l t i i 2 j 等算法进行比较，讨论算法 优缺点，最后对部分算法进行并行化处理。 第七章结束语，总结了本文的主要工作，分析本文算法的优缺点，并展望了 下一步的工作。 第4 页 国防科学技术大学研究生院学位论文 第二章序列的比对算法介绍 从序列比对的目的来看，序列的比对算法目前可分为两种，一种是序列比对， 寻求最大序列相似度的结果，一种是结构比对，主要寻求最大结构相似度的结果。 从数学角度看，序列比对的核心问题是评估从一条序列转换到另一条序列所需要 的位点上的替换、插入和缺失事件的最少数目，但从生物学角度看序列之间的比 对还应考虑序列的进化形式、分子结构和三联体密码子的翻译阅读框等诸多问 题，因此序列的比对问题不是单纯的数学问题，而是数学方法结合生物学信息， 给出更多更准确地生物学解释的问题，结构比对算法就是其中一例。 2 1 序列比对 序列比对是将同源序列位点上匹配位点( 相同或相似残基) 与不匹配位点( 不 相似的残基) 按照一定的记分规则转化成序列间相似性或差异性数值进行比较， 相似值最大的比对结果具有最多的匹配位点，从数学角度讲，应该是最优的比对 结果【4 引。比对结果反映了数学模型或算法在多大程度上反映序列之间的相似性关 系以及它们的生物学特征。记分规则是由取代矩阵的选择和空位罚分的参数设置 决定，规则的核心是奖励匹配位点，惩罚不匹配位点及具有空位的位点。针对不 同的研究目标和对象应该构建适宜的取代矩阵。空位的引入是为了补偿插入和缺 失对序列相似性的影响，以求得最佳序列比对结果。序列的缺失或插入是相对而 言的，一条序列插入一定长度的序列，另一条序列就相应地缺失同样长度的序列。 任何两条序列在自由引入空位( 没有罚分) 后最终可使所具有的匹配位点都匹 配，但这样的匹配没有任何意义，因此在一定程度上限制空位的数目以产生有生 物学意义的比对结果。因此，对空位的罚分数值应该比较高。由于没有什么合适 的理论模型能很好地描述空位问题，因此空位罚分缺乏理论依据而带有较多的主 观色彩。对于具体的比对问题，采用不同的罚分方法会取得不同的效果。这样， 通过设置空位引入和空位延伸的罚分程度，可以控制比对结果中含有空位的总体 数目：一般来说，罚分程度越高，比对结果中含有空位的总体数目就会越少，真 正的同源区域就可能被破坏；相反，罚分程度越低，比对结果中含有空位的总体 数目就会越多，非同源区域也可能变成同源区域。 2 1 1 多序列比对问题定义 一条长度为l 的生物序列是由l 个字符组成的字符串，字符串中的字符取自 于一个优先的字母表，对于d n a 序列，包含a 、t 、c 、g 四个字母，分别 代表4 种不同的核苷酸。对于r n a 序列，包含a 、u 、c 、g 四个字母，分别 代表4 种不同的核苷酸。a 、t 、c 、g 、u 统称为碱基。对于蛋白质序列，包 第5 页 国防科学技术大学研究生院学位论文 含2 0 个不同的字母，分别代表2 0 种彳、= | 一的氨基酸，将其统称为残基。给定n 条序列组成的序列组s = ( s l ，s 2 ，s n ) ，s i 的长度为l i ，s i j ( 1 匀5 l j ) 表示第i 条序 列的第j 个碱基或残基，那么关于s 的多序列比对可定义为如下的一个矩阵【4 3 】： 卫 s k ( s u ，) ，l s i n ，1 匀冬l ，m a x ( l , ) l 厶。 该矩阵有如下特性： 1 s i i u ，其中“”代表空位； 2 如果删除空位，那么s 的每一行s i 与对应序列s i 相同； 3 s i 不存在只由空位组成的列。 2 1 2 序列比对算法分类 大多数现有的多序列比对方法可以分为4 类：精确比对方法、渐进比对方法、 迭代比对方法、基于图论的对方法【l7 。 精确比对方法完全基于动态规划算法，最为经典的是多维n e e d l m a n w u n s c h 算法【l 引，它是一种全局比对算法，在给定罚分函数和替换矩阵的情况下，总能给 出具有最高得分的比对结果。但其可行的计算维数为3 。 渐进比对算法的基本思想是：基于双序列动态规划算法，采用迭代的方式， 由两条序列的比对开始，逐渐添加新序列，直到所有序列都添加完为止。但是， 不同的添加顺序会产生不同的比对结果，所以，寻找最恰当的比对顺序是渐进比 对方法的一个关键问题。一般的算法都是依据两个序列之间的相似度衡量的，从 最相似的两个序列开始，由近至远逐步完成。基于这种方法的软件很多，主要有 c l u s t a l w 1 0 j 、t - c o f f e e i j 等。其中，c l u s t a l w 是一个使用最广泛的渐进比 对程序，它主要是根据两两比对的分值构建了一个进化树，然后根据进化树进行 渐进比对。t c o 虢e 类似于c l u s t a l w ，利用扩展库取代c l u s t a l w 中的替 代矩阵进行渐进比对，使得每一步渐进比对过程中用到的打分信息都取自于所有 序列之间的关联信息，而不仅仅是当前要比对的序列，这在比对初期，可以明显 地减少比对错误的情况。但是，t _ c o 髓e 运行时间比c l u s t a l w 要慢。其他针 对蛋白质或短d n a 序列的基于渐进比对的多序列比对软件有 m u l t a l i g n ( m u l t i p l ea l i g n m e n o 【1 9 1 m a f f t ( m u l t i p l es e q u e n c ea l i g n m e mb yf a s t f o u r i e r t r a n s f o r m ) 【2 0 1 。 m u s c l e ( m u l t i p l es e q u e n c ec o m p a r i s o nb y l o g e x p e c t a t i o n ) t 2 1 j ，a l i g n m 6 0 2 2 j 和p r o b c o n s ( p r o b a b i l i s t i cc o n s i s t e n c y ) 2 3 】等。 迭代比对方法的策略是：基于一个能产生比对的算法，并通过一系列的迭代 方式改进多序列比对，直到比对结果不再改善为止。基于这种思想的方法有模拟 退火、遗传算法、隐马尔可夫模型【2 4 】【2 5 】等。其中，最有影响的多序列比对软件 包s a g a ( s e q u e n c ea l i g n m e n tb yg e n e t i ca l g o r i t h m ) 1 2 6 基于遗传算法构建，共设计 了2 2 种不同的遗传算子，采用动态调度的策略控制2 2 种遗传算子的使用。 基于图模型的比对是近年来发展起来的方法，其主要代表就是偏序比对 ( p a r t i a lo r d e ra l i g n m e n t ，简称p o a ) 2 7 l 一种以有向无环图( d i r e c t e da c y c l i c g r a p h ，简称d a g ) 的表示方式取代行列表示的多序列比对方法。在行列比对方法 第6 页 国防科学技术大学研究生院学位论文 中，图总是单一的有向路径。然而，p o a 方法扩展了图的结构，使得它是一个 有向无环图。p o a 方法在多序列比对领域打开了一个新的视角。后来，y u z h e ny e 和a d a mg o d z i k 2 8 1 把偏序结构又进一步应用于蛋白质结构比对。2 0 0 4 年，p e v z n e r 等人提出了新的基于图论的多序列比对方法a b a ( a b r u i j na l i g n m e n t ) z 9 1 。与p o a 不同的是，它把序列比对表示成可能含有环的有向图，使得a b a 比p o a 具有更 大的灵活性，尤其是对于含有交错或重复结构域的蛋白质序列比对和包含重复和 倒位的d n a 序列比对非常适用。其他基于图模型的比对方法还可参见文献 3 0 】。 在序列比对算法中，仅仅考虑序列之间的相似度，而没有对序列中隐含的结 构信息进行分析和比对，因此并不适合用于r n a 的比对问题。 2 2 结构比对 多序列比对是比较基因组预测算法的关键过程，将多序列比对作为算法的输 入来预测所有序列的共同二级结构，可以大大提高结构预测的精度。多序列比对 中隐含的结构信息直接影响预测的精度，因此带结构信息的结构比对算法合适。 从图1 1 可知，这些r n a 二级结构的组成单元在形式上表现了序列上的结 构关系，不难看出发夹环、内部环、突起环和多分枝环都与茎环( s t e m ) 相关， 只要确定了序列上的茎环( s t e m ) 结构，我们就可以得到其它组成单元的结构， 所以我们认为s t e m 是序列结构信息的核心。大多数现有的r n a 结构比对算法 都是针对s t e m 结构进行比对分析。 2 2 1 多序列结构比对问题定义 一条长度为l 的r n a 序列是由l 个碱基组成的字符串，字符串中的碱基有 四种，a 、c 、g 、u 。给定n 条r n a 序列，组成的序列组s = ( s 1 ，s 2 ，s n ) ，s i 的 长度为l i ，s i j ( 1 匀5 l i ) 表示第i 条序列的第j 个碱基，l i k 表示第i 条序列第k 个子序列，l i k 表示l 搬的长度，l i k 为非s t e m 区域或者一个s t e m 的一边( 详情 请见3 1 中的定义3 4 ) ，那么关于s 的一个多序列比对可定义为如下的一个矩阵 【4 3 】： 一 s = ( s u ，) ，l i n ，l 匀 l ，m a x ( l j ) 上，厶， 1 = 1 其中弓= 。u ：u u k ， 七 厶= 屯。 l = l 该矩阵有如下特性： 1 s i j u ) ，其中“”代表空位； 2 如果删除空位，那么s ，的每一行s i 与对应序列s i 相同； 3 s i 不存在只由空位组成的列。 2 2 2 结构比对算法分类 在现有的序列结构比对算法中，主要有三类方法： 第7 页 国防科学技术大学研究生院学位论文 第一类方法以双序列结构比对为基础，利用两两比对构建多序列比对。这类 方法主要针对长度少于5 0 0 的序列，先找出每条序列中的结构信息，如s t e m 、 环等，结合序列相似和结构信息相似进行比对，然后根据t c o f f e e 系统或者进化 距离分析，利用两两比对构建成多序列比对，如m a r n a i 、r n a f o r e s t e r 1 3 】、 c b a 4 j 等。 i i a r n a ( m u l t i p l ea l i g n m e n to fr n a s ) 是s v e ns i e b e r t 和r o l fb a c k o f e n 于 2 0 0 5 年7 月在d e p a r t m e n to fb i o i n f o r m a t i c s 上发表的。他们首先利用两条序列之 间的序列信息和二级结构信息构建双序列结构比对，然后用t c o f f e e 系统将这 些双序列结构比对联合成一个多序列结构比对，时间复杂度为o ( e 2 n 2 l 4 ) + o ( n 3 l 2 ) ，其中l 为序列长度，n 为序列个数，e 为s t e m 个数。它的结构比对 精度较高，是种经典方法，在之后的一些结构比对算法都是沿用了它的思想。 m a r n a 最高能对长5 0 0 核苷的序列进行结构比对，队列总长度不能超过1 0 0 0 0 核苷。 r n a f o r e s t e r 的主要思想是将序列树形化，利用树型队列模型构建进行双序 列结构比对，然后根据c l u s t a lw 算法思想构建多序列比对。这种算法能够 处理有错误结构信息的序列比对，即使在有错误结构信息的情况下，也能产生有 意义的结果，但对于非同一家族数据，精度较差。 c b a 是在m a r n a 的基础上作了改进，先进行两两结构比对，然后同时考 虑所有两两结构比对，利用保守区域的一致性从全局上重新排列这些结构比对结 果，构建一个最大相似度的多序列结构比对，主要应用在蛋白质结构比对中。这 类算法无法处理长度超过1 0 0 0 核苷的序列的结构比对问题。 第二类方法是首先寻找所有序列的结构区域，经过裁剪处理将结构信息规格 化，直接在多条序列间进行比较分析，寻找序列间合适的结构信息比对，构造多 序列比对，如s c a r n a 15 1 。 s c r n a 是y a s u ot a b e i ，k o j it s u d a ，t a i s h i nk i n 和k i y o s h ia s a i 于2 0 0 6 年5 月在b i o i n f o r m a t i c s 发表的。它是一种基于固定长度的候选s t e m s 片断的 结构比对方法。它首先找到序列中的s t e m ，然后将那些长的s t e m s 进行切割， 并剔除短的s t e m s ，使得所有的s t e m 都是一样长度，然后基于这些一样长度 的s t e m 进行结构比对分析。这种方法适用于长序列的大规模分析，能对长于 1 0 0 0 核苷的队列进行结构比对，且精度不低。但由于它对结构信息进行了裁剪 工作，所以序列中的保守区域有所减少，丢失了一些有用的结构信息。 第三类方法，一些r n a 二级结构预测算法对输入序列都进行了重新处理， 涉及到结构信息的搜索算法和比对优化问题，如f o l d a l i g n t 圳、d y n a l i g n 3 2 】、 p m c o m p l 3 3 】等，它们都是基于s a n k o f f 算法p 4 j 进行的，即对同源序列同时进行比 对和结构预测，采用递归的方式通过结构信息来预测结构和指导修正比对结果。 还有r n a a l i f o l d 3 5 1 、p f o l d 3 6 1 、i l m t 3 7 】等，他们利用能量计算、协变分值计算、 概率方法等对比对序列进行一致结构信息搜索。 我们综合利用前两类算法的思想，先对序列间的s t e m 进行比对分析，基 于s t e m 比对采用序列拆分和递归方式处理r n a 双序列结构比对问题，避免伪 第8 页 国防科学技术大学研究生院学位论文 结的影响并保留了s t e m 信息的完整性，然后根据第一类算法的思想通过两两 比对构建多序列比对，用我们的裁剪策略优化比对结果。 2 3 小结 在本章中，我们对现有的序列之间的比对算法进行大致的分类，分析了其中 典型的几种算法。此从本章谈到的比对算法中我们可以看出，虽然很多算法并不 适合直接应用到r n a 的结构比对问题中，但其中有很多思想和方法都值得我们学 习和借鉴。 第9 页 国防科学技术大学研究生院学位论文 第三章s t e m 的寻找算法 每条r n a 序列都可能有若干个s t e m ，j 由于在本文算法中我们认为s t e m 是r n a 序列的结梅信息的核心，因此我们将r n a 的结构比对问题定义为s t e m 部分的比对。而我们需要首先找出序列中的所有s t e m 区域，才能对它们进行 比对分析。 在本章算法中j 我们首先会定义序列和逆补序列的概念，通过循环比对操作 构建序列韵折叠矩阵广然后根据折叠矩阵的数字特征，找出连续为1 的区域，辅 以一定的判断机制和映射方法，得到该区域对应于序列中的s t e m 部分。另外， 对于超过5 0 0 碱基的长序列，我们采取窗口模式来寻找序列的所有s t e m ，以牺 牲时间复杂度来解决由于存储空间引起的限制。只要序列长度不超过1 0 0 0 ，我 们就能找出序列中的所有s t e m 部分：保证不丢失其中的结构信息。对于长度 超过1 0 0 0 的序列，：由于我们的窗口大小上限为5 0 0 ，所以搜索过程中会存在 些无法进行搜索的盲区，所以可能会丢失一些结构信息。当然，在长序列的处理 过程中，用窗口化模式来搜索s t e m 会增加算法的时问消耗。为了解决这个问 题，我们提出了基于m a s t e r - s l a v e 的分布并行处理模型，以此来降低时间消耗。 3 1 折叠矩阵 我们在参考文献 4 0 】的研究基础上定义如下的折叠矩阵相关概念。 定义3 1 ：逆补序列 给定一条r n a 序列s e q ，它的逆补序列s e q7 是由s e q 执行以下操作而得到： i 从最后一个字符开始依次扫描s e q ； i i 如果s e q 的字符是a ，那么得到s e q 韵字符u ； i i i 如果s e q 的字符是u ，那么得到s e q 7 的字符a ； i v 如果s e q 的字符是g ，那么得到s e q 的字符c ； v 如果s e q 的字符是c ，那么得到s e q 的字符g 。 图3 1 就是一个求逆补序列的例子。 第1 0 页 国防科学技术大学研究生院学位论文 s e q s e q 7 a c u g a c a g g iliiliiil u g a c u gu c c 图3 1 逆补序列的一个例子 假设s e q 是原序列，s e x l 的最后一个字符是g ， 那么s e q 7 的第一个字符就是c ，依次类推，就得n - j 逆补序列s e q l “c c u g u c a g u ”。 通过这种方式，我们就得到了r n a 序列的逆补序列。然后我们通过原序列 和它的逆补序列的比对操作，就可以得到该序列的折叠矩阵。 定义3 2 ：两个字符的比对操作 假设a 、a r a ，u ，g c ) ，那么a 与a 的比对操作定义如下： i 如果a 与a 相等，那么比对结果就是l ； i i 如果a 与a 不相等，那么比对结果就是0 。 这是两个字符之间的比对操作，然后我们通过定义3 3 得到每条序列的折叠 矩阵。 定义3 3 ：折叠矩阵 假设s e q 是一条r n a 序列，序列长度为l ，那么它的折叠矩阵m s e q 就是一 个l x l 矩阵，且矩阵m s e q 的元素为o 或者1 。矩阵m s e q 是由以下操作构成的： i 由定义3 1 得到序列s e q 的逆补序列s e q ； i i 对于矩阵m s e q 的第i 行( 0 主i l 1 ) ，s e q 循环向右移i 位，然后依次 将s e q 的第j 个字符( o 耋j 耋l 一1 ) 与s c q7 的第j 个字符通过定义3 2 进行 比对，得到元素o 或者1 。 我们就得到了折叠矩阵m s e q ，图3 2 就是一个折叠矩阵的例子。 s e e l ：a c u g a c a g g s e a ：c c u g u c a g u m s e q = 图3 2 一条r n a 序列的折叠矩阵 第1 1 页 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 厂 一 国防科学技术大学研究生院学位论文 给定一条r n a 序列s e q ，根据定义3 1 得到它的逆补序列s e q ，然后根据定 义3 3 一行行的比对，得到折叠矩阵m s e q 。如果s e q 的长度是l ，那么折叠矩阵 就是一个l l 矩阵。 定义4 ：s t e m 序列的s t e m 是对应与序列上两两相互匹配的连续碱基对。s t e m 是由两部 分组成，这两部分的碱基两两匹配。我们定义s t e m 的碱基对数为s t e m 的长 度。如图3 3 所示，”u c c g u ”和”a c g g a ”就是一个s t e m ，且长度为5 。”u c c g u ” 对应于序列位置的3 到7 ( 序列的第一个碱基位置是o ) ，我们用( 3 ，7 ) _ ( 1 0 ，1 4 ) 的方式来表示这个s t e m 。 g u a u c c g u c u a c g g a g g c 图3 3 序列的一个s t e m 序列中的s t e m 为( 3 ，7 ) 一( 1 0 ，1 4 ) 。 3 2s t e m 的寻找 序列信息中隐含着结构信息，这些结构信息对二级结构预测、三级结构预测 和蛋白质功能分析都有着重要的作用，要对序列中的结构信息来进行比对分析， 就要先找出序列上的所有结构信息，而s t e m 结构是结构信息中的骨干。下面 介绍本文算法如何寻找出