（计算机科学与技术专业论文）基于树模型的rna序列结构比对算法研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 r n a 序列结构比对是生物信息学的基础研究内容之一。通过对r n a 序列和 结构进行相似度比较，人们可以发现r n a 序列中蕴含的功能和进化信息，对r n a 序列分类、二级结构预测、发现序列保守区域都具有极其重要的研究意义。 本文首先介绍了r n a 序列结构的基本知识，给出了r n a 序列结构比对问题 的详细描述，分析了已有的r n a 序列结构比对算法，对现有算法进行了分析和比 较，并指出了当前比对算法存在的主要问题。接着详细阐述了树模型的构造和操 作，给出了r n a 序列结构与树模型的对应关系。 针对目前低相似度r n a 序列比对结果准确度不高的问题，本文基于r n a 树 形结构模型，提出了一种基于动态规划思想的r n a 双序列结构比对算法，对算法 进行了设计和实现。通过比较与其他比对算法在同一数据集上的运行结果，本文 算法在低相似度r n a 序列比对上表现出较高的准确度。在r n a 双序列结构比对 的基础上，本文结合t c o f f e e 算法思想，设计并实现了r n a 多序列结构比对算法， 通过数值实验讨论了r n a 多序列比对结果与序列数目及序列平均相似度的关系， 同时验证了本文算法的有效性。 主题词：r n a 序列结构比对，树模型，动态规划，t c o f f e e 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t i 矾as e q u e n c e s t r u c t u r ea l i g n m e n ti so n eo ft h eb a s i cr e s e a r c hc o n t e n t si n b i o i n f o r m a t i c s t h r o u g ht h es i m i l a r i t yc o m p a r i s o no fr n as e q u e n c e sa n ds t r u c t u r e s ， p e o p l ea r ea b l et of i n dt h ef u n c t i o n a la n de v o l u t i o n a li n f o r m a t i o nh i d i n gi nr n a s e q u e n c e s 砸sh a sv i t a lr e s e a r c h i n gs i g n i f i c a n c ei n t l l ec l a s s i f i c a t i o no fr n a s e q u e n c e s ，t h ep r e d i c t i o no fi 矾as e c o n d a r ys t r u c t u r e sa n df m d i n gc o n s e r v e dr e g i o n si n s e q u e n c e s n l ep a p e rf i r s ti n t r o d u c e st h eb a s i ck n o w l e d g eo ft h er n a s e q u e n c ea n ds 觚c t t t r e ， g i v e st h ed e t a i l e dd e s c r i p t i o no f 量m as e q u e n c e s t r u c n l r ea l i g n m e n tp r o b l e m s ，a n a l y s i s t h e e x i s t i n g r n as e q u e n c e s 觚l c t u r e a l g o r i t h m s ， a n dt h e n g i v e sa n a l y s i s a n d c o m p a r i s o no fp r e s e n ta l g o r i t h m sa n dp o i n t so u tt h em a i np r o b l e m so ft h ep r e s e n t a l g o r i t h m s ，d e s c r i b e st h ec o n s t r u c t i n ga n do p e r a t i n go nt h et r e em o d e li nd e t a i l ，g i v et h e r e l a t i o nb e t w e e nr n a s e q u e n c e - s t r u c t u r ea n dt r e em o d e l c o n s i d e r i n g t h eu n s a t i s f i e da c c u r a c yo fc u 玎e n ts e q u e n c e - s 仃u c t u r e a l i g n m e n t a l g o r i t h m so nl o ws i m i l a rr n as e q u e n c e s ，t h i sp a p e rp r e s e n t sap a i r w i s e 砌、i a s e q u e n c e s t r u c t u r ea l i g n m e n ta l g o r i t h mb a s e do nd y n a m i cp r o g r a m m i n gu s i n gt h et r e e m o d e l ，d e s i g na n di m p l e m e n tt h ea l g o r i t h m 1 1 1 ec o m p a r i s o n 谢mo t h e ra l g o r i t h m so n t h es a m ed a t as e t ss h o w st h a tt h ea l g o r i t h mo ft h i sp a p e rc a ng i v eah i g h e ra c c u r a c yo n t h el o ws i m i l a rr n as e q u e n c e s f u r t h e r m o r e ，b a s e do nt h e i d e a so ft - c o f f e e ，t h e p a i r - w i s er n as e q u e n c e - s t r u c t u r e a l g o r i t h mo ft h i sp a p e ri se x t e n d e dt oam u l t i p l e r n a s e q u e n c e - s t r u c t u r ea l i g n m e n ta l g o r i t h m t h e n ，t h er e l a t i o nb e t w e e nt h er e s u l t so f t h em u l t i p l ei 斟as e q u e n c e s t r u c t u r ea l i g n m e n ta n dt h en u m b e ro fs e q u e n c e s ，a v e r a g e s e q u e n c es i m i l a r i t yi sd i s c u s s e da n dt h ev a l i d i t yo fo u ra l g o r i t h mi sv e r i f i e d k e yw o r d s ：r n as e q u e n c e - s t r u c t u r ea l i g n m e n t ，t r e em o d e l ，d y n a m i c p r o g r a m m i n g ，t - c o f f e e 第i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表3 1r n a 双序列比对算法复杂度2 5 表4 1r n a 多序列比对算法复杂度3 6 表4 2 三序列比对c o m p a l i g n 打分和s c i 打分。4 0 表4 3 五序列比对c o m p a l i g n 打分和s c i 打分一4 2 表4 4 七序列比对c o m p a l i g n 打分和s c i 打分4 6 第1 i i 页 国防科学技术大学研究生院硕士学位论文 图1 1 图1 2 图1 3 图1 4 图2 1 图2 2 图2 - 3 图2 4 图2 5 图2 6 图2 7 图2 8 图3 1 图3 1 图3 2 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 图4 图4 图4 图4 1 4 图4 1 5 图目录 图模型的构建3 树模型的构建。4 弧注释序列模型的构建5 概率模型的构建6 典型r n a 二级结构1 0 序列比对和序列结构比对比较1 2 砌叮a 双序列结构比对13 单个碱基替换打分矩阵l5 碱基对替换打分矩阵l6 r n a 序列结构和对应树模型1 7 树编辑示例17 树编辑与树编辑映射关系1 8 r n a 双序列结构比对实验流程图2 6 低相似度双序列比对c o m p a l i g n 打分2 8 低相似度双序列比对s c i 打分2 9 t c o f f e e 算法流程3 2 多序列结构比对算法设计3 3 多序列比对实验流程3 7 三序列比对参考比对结果的一致结构3 9 三序列比对本文算法结果的一致结构3 9 三序列比对m a f f t 结果的一致结构3 9 三序列比对c l u s t a l w 结果的一致结构3 9 五序列比对参考比对结果的一致结构4 1 五序列比对本文算法结果的一致结构4 2 五序列比对m a f f t 结果的一致结构4 2 五序列比对c l u s t a l w 结果的一致结构4 2 七序列比对参考比对结果的一致结构4 5 七序列比对本文算法结果的一致结构4 5 七序列比对m a f f t 结果的一致结构4 5 七序列比对c l u s t a l w 结果的一致结构4 5 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目 学位论文作者 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存，汇编学位论文 ( 保密学位论 学位论文题目 学位论文作者 作者指导教师 国防科学技术大学研究生院硕士学位论文 第一章绪论 存储、利用和传递信息是生物最显著的特征。二十世纪九十年代，随着人类 基因组计划的顺利实施，核酸和蛋白质等生物信息出现了爆炸性的增长，迫切需 要对海量数据进行处理。 揭示序列数据所代表的生物学意义，是一门深奥的科学，难度之大，不亚于 破译一部“天书 。如同我们所熟悉的自然语言一样，这部“天书是由一个个 句子，一个个的单词直至一个个字母组成的，准确地破译这部“天书，是生物 信息学面临的艰巨任务【1 1 。 1 1 1 课题背景 1 1 课题背景和研究意义 伴随着基因组计划的实施，涌现出海量的生物数据。这些生物数据具有丰富的 内涵，其背后隐藏着人类目前尚不知道的生物学知识。生物信息学的中心任务， 就是从浩如烟海的数据中提取理性知识，得到人类有用的信息。生物信息学是一 个新兴的交叉学科，由生物学家，数学家和计算机科学家共同研究生物分子信息 的获取、管理、分析和利用，力图找出具有重要生物学意义的信息，并破译这些 信息是如何精确地控制生物体内的生化环境【2 】。 生物信息学对揭示人类及重要动植物的基因信息，开展对生物序列大分子的 结构和功能的研究，进行药物设计和理解生物的起源、遗传、变异等进化活动的 本质具有十分重要的意义，同时为人类疾病的诊治开辟了全新的研究途径。生物 信息学不仅有重要的科学意义，而且有着巨大的经济效益。随着基因组学的发展， 设计与制造很多重要的生物分子，这些分子可以用于制药、农业、食品、能源等 诸多领域。据报道，生物信息学产业的市场在1 9 9 6 年已经达到1 0 亿美元，而在 2 0 0 2 年已经增长到2 0 0 0 亿美元以上1 3 j 。 1 1 2 研究意义 生物信息学的基本任务是对各种生物分子序列进行分析，从大量的序列和结 构信息中获取生物序列的功能和进化等知识，通过研究序列在序列信息及结构信 息方面的相似度，来分析序列间的进化关系。生物学的事实表明：序列和结构不 同的多条r n a 序列可能起源于同一祖先序列，由祖先序列中碱基的取代，插入和 删除等变异过程演化而来。生物信息学研究某一未知序列时，通过将该序列与已 第1 页 国防科学技术大学研究生院硕士学位论文 知序列进行序列和结构的相似度比较，可以得出该序列与己知序列的关系，推断 未知序列的结构和功能。生物信息学早期研究主要集中于两种生物序列，一种是 d n a 序列，另一种是蛋白质序列。科学研究表明，自然界的绝大多数生物是以d n a 作为遗传物质，但是有些病毒不含有d n a 而只含有r n a ，这时r n a 就充当了遗 传物质的作用。伴随着r n a 本身的功能作用不断被发现，针对r n a 的研究正越 来越受到人们的重视。 比对又称为联配( a l i g n m e n t ) ，基本含义是通过将研究对象进行比较来寻找对象 间的共性，是生物信息学中进行序列分析的一种常用手段，序列比对也是生物信 息学中一个最基本的研究问题。比对的基本过程是将所有的序列并列排在一起， 将不同序列中的相同碱基尽量可以排在同一列上，以确定序列间的相似区域。r n a 序列比对主要是基于序列信息的比对，在比对过程中不考虑r n a 序列所蕴含的结 构信息，本文主要研究考虑结构信息的r n a 序列结构比对。考虑结构信息的主要 原因有：首先r n a 的结构比序列更加保守，在进化过程中更不容易发生变化，其 次两条序列信息差异较大的r n a 序列，可能结构相同，最后r n a 功能与二级结 构和三级结构之间有着密不可分的联系，功能与结构密切相关是贯穿所有生物体 系的一条基本法则。当参加比对的序列的序列相似度较低且数目较多时，单纯序 列信息比对不能取得准确的比对结果，此时需要考虑序列的结构信息，提高比对 结果的准确度。 r n a 序列结构比对可用于很多用途：将r n a 的二级结构与一些特定r n a 家 族的保守性结构特征进行比较，可以对r n a 进行分类；对于功能未知的r n a 序 列，通过将序列与结构已知并且带有功能注释的r n a 序列进行比较，可以推断该 条r n a 序列的功能；在非编码r n a ( n o n c o d i n gg n a ) 家族里，发现家族内的共有 结构；构建系统发育树，研究序列间进化关系。综上所述，r n a 序列结构比对具 有重大的研究意义。 1 2 国内外研究现状 本节采用文献【4 】中对r n a 序列结构比对算法进行分类的方法，详细描述基于 四种模型的比对算法：基于图模型比对算法、基于树模型比对算法、基于注释序 列模型比对算法和基于概率模型比对算法，最后介绍其他序列结构比对算法。 1 2 1 目前国内外主要算法 ( 1 ) 基于图模型的r n a 序列结构比对算法 r n a 图模型表示是将r n a 序列中每个碱基对应于线性图的一个结点，根据 碱基间关系在图中添加边。如图1 1 所示1 4 ，左侧为图模型，右侧为输入r n a 序 第2 页 国防科学技术大学研究生院硕士学位论文 列及其结构。 图1 1 图模型的构建 基于图模型比对算法主要分为两类：基于整数线性规划( i l p ) 模型比对算法和 基于最大公共结构模式( m c s p ) 模型比对算法。 b a u e r 4 】提出的算法通过对边赋予权值，对不同边集合添加权重系数得到目标 函数，然后引入拉格朗日松弛算子将约束条件作为罚分函数放入目标函数中，从 而对迭代过程进行优化，结合渐进比对算法思想将双序列比对推广到多序列比对， 利用文献【5 】中提出的多序列比对处理空位方法，可以处理伪结和空位的序列结构 比对问题。 当r n a 序列不含伪结时，d a v y d o v 【6 】将最大公共结构模式模型转化成求解最 大内嵌线性图( m a x - n l s ) i 口- 题，算法思想是：输入一组r n a 序列结构对应的线性 图，通过比对在这些图中寻找特定公共结构模式，表示出序列结构中的保守部分。 f e r t i n 等人【7 】在d a v y d o v 工作基础上提出了基于最大公共结构模式模型的近似算 法，进一步考虑了不同类型的公共结构模式。文献【8 对最大内嵌线性图问题做了 进一步研究，提出了解决在单幅图中求解最大内嵌线性图问题的动态规划算法， 算法时间和空间复杂度分别为o ( n 2 + n _ n 1 ) $ - f lo ( n 2 ) ，其中n 表示图的顶点数，l r l 表示 图的边数。并证明了即使在图最大内嵌深度至多是2 时，求解最大内嵌线性图已 经是n p 完全问题。 ( 2 ) 基于树模型的r n a 序列结构比对算法 r n a 结构树模型表示是将序列中碱基对对应树内部结点，将单个碱基对应树 叶子结点，将靠近序列两端的碱基作为树的根结点。如图1 2 所示呻1 ，左侧为r n a 结构，右侧为对应的树结构。 第3 页 同燃幽 。盼 姆 国防科学技术大学研究生院硕士学位论文 图1 2 树模型的构建 基于树模型比对算法主要分为两类：基于树编辑( t r e ee d i t ) 模型比对算法和基 于树比对( a l i g n m e n to f t r e e ) 模型比对算法。在讨论算法之前，先给出有序树和无序 树的定义：当树中双亲后代结点以及兄弟结点间顺序确定时，此时称树为有序树， 否则称为无序树。 基于树编辑模型比对算法由z h a n g s h a s h a 1 0 】首先提出，其基本思想是：首先 定义替换、插入和删除三类基本操作并对操作定义一定开销值，然后将两条r n a 序列分别转换成相应树模型，经过一定操作序列将一棵树转换成另一棵树，最后 计算操作序列所对应操作开销和，开销和最小的操作序列对应于双序列最优比对。 算法【1 0 】得到的基于有序树编辑比对算法时间复杂度是o ( i t i i i t 2 i m i n d e p ( t 1 ) ，l e a ( t 1 ) m i n d e p ( t 2 ) ，l e a ( t 2 ) ) ，其中| t i l 表示树t i 中结点数，d e p ( t i ) 表示树t i 最大深度， l e a ( t i ) 表示树t i 叶子结点数。k l e i n 1 l 】提出的算法将树的每条边看作两条有向边， 用一对括号进行表示，采用深度优先( d e e p f i r s o 策略对树进行遍历，将遍历所得括 号串记为欧拉事( e u l e rs t r i n g ) ，然后对欧拉串进行比较，从而得到树比对结果。将 算法【1 0 1 时间复杂度在最坏情形降低至o ( i r l l 2 l t 2 i l o g l t 2 i ) 。基于无序树编辑比对问题 是m a x s n p 难问剐1 2 】，算法【1 3 】考虑了近似树匹配问题，通过引入受限结构比对 将基于无序树编辑比对算法时间复杂度降至 o ( 1 t l i i t 2 i ( d e g ( t 1 ) + d e g ( t 2 ) l o ( d e g ( t 1 ) + d e g ( t 2 ) ) ) ，其中i t “表示树t i 中结点数，d e g ( t i ) 表示树t i 结点度数的最大值。 j i a n gt 等人【1 4 】首先给出树比对模型：在将r n a 序列转换成相应树结构后， 通过添加空格的方法将两棵树变成同构树，再将两棵树相应位置进行重合得到一 棵新树，新树中每个结点是原来两棵树中相应位置标记构成的二元组，接着对树 中所有结点打分后进行求和，和值最小的比对对应于两序列间最优比对。该算法 可以解决基于有序树比对模型和无序树比对模型的比对问题。基于有序树比对模 型算法时间复杂度是o ( i t l i i t 2 1 ( d e g ( t 1 ) + d e g ( t 2 ) ) 2 ) 。基于无序树模型比对算法在对 树结点度数进行限定时，运行需要多项式时间，如果对树中结点度数未加限定， 问题转换成m a x s n p 难问题。h o c h s m a r m 等人【l5 】对树比对模型进行推广，算法 第4 页 国防科学技术大学研究生院硕士学位论文 时间复杂度是o ( i f d l f 2 1 d e g ( f 0 d e g ( f 2 ) ( d e g ( f 1 ) + d e g ( f 2 ) ) ，其q b l f i l 表示森林f i 中结点 数目，d e g ( f i ) 表示森林f i 中结点度数最大值。 ( 3 ) 基于弧注释序列模型的r n a 序列结构比对算法 r n a 结构弧注释序列模型中包含了r n a 序列信息和结构信息，可形成氢键 作用的碱基在模型中用弧进行连接，并按照从序列5 到3 端的顺序对碱基进行 排列。如图1 3 所示【1 6 】，左侧为r n a 结构图，右侧为对应的弧注释序列模型。 c c g u a g u a c c a c a g u g u g g 图1 3 弧注释序列模型的构建 基于弧注释序列模型比对算法主要分为两类：基于编辑( e d i t ) 模型比对算法和 基于最长弧注释公共子序歹q j ( l a p c s ) 模型比对算法。 l i n 1 7 】提出基于编辑模型的弧注释序列比对算法，算法基本思想是：对弧和碱 基分别定义替换和删除的基本操作，对以上这些基本操作赋予一定开销值，通过 编辑序列将一条弧注释序列转换成另一条弧注释序列，操作开销值最小的编辑序 列对应于最优比对。j i a n gt t i s 进一步讨论了弧操作开销间的关系，并证明了基于 编辑模型的弧注释序列比对是m a x s n p 难问题。m a r n a 1 9 】在算法【1 8 】基础上主 要做了三点改进：一是细化对碱基对的操作；二是每条序列用结构预测算法产生 多种结构构象( c o n f o r m a t i o n ) ，在构象之间进行双序列比对；三是结合渐进比对算 法思想推广到多序列结构比对。进行双序列结构比对时，算法所需时间是 o ( l 2 1 l 2 2 ) ，l l 和l 2 代表两条碱基序列长度。 基于最长弧注释公共子序列模型比对算法思想是：对给定的两条r n a 序列首 先用弧注释序列模型表示出r n a 序列和结构信息，然后寻找两个弧注释序列的公 共子序列，得到的公共子序列就反映了两序列共有保守结构。e v a n s t 2 0 】给出最长弧 注释公共子序列问题的定义，并指出如果对弧注释序列结构类型不加限制，基于 最长弧注释公共子序列模型比对问题是n p 完全问题。文献f 2 1 】对基于最长弧注释 公共子序列模型比对算法做了进一步研究，在最长公共序y u ( l c s ) 模型基础上提出 解决r n a 序列结构比对问题的近似算法，证明得到基于最长弧注释公共子序列模 型的含伪结r n a 序列结构比对是m a x s n p 难问题。 ( 4 ) 基于概率模型的序列结构比对算法 构建r n a 概率模型表示的基本思想是用概率模型的状态转换机制来表示 第5 页 国防科学技术大学研究生院硕士学位论文 r n a 结构信息。如图1 4 所示2 2 1 ，左侧为r n a 结构，右侧为对应的概率模型。 5 3 图1 4 概率模型的构建 文献 2 3 c o 指出，h m m 模型不足之处是仅仅可以对r n a 序列进行建模，对 r n a 二级结构建模结果不够准确。s a k a k i b a r a 2 4 】将树比对模型【1 4 】和自动机理论模 型( a u t o m a t a t h e o r e t i c ) 相结合，提出树结构双隐马尔可夫模型( p h m m t s ) ，基于树 结构双隐马尔可夫模型是对隐马尔可夫模型( h m m ) 的扩展，可以处理已知结构和 未知结构序列之间的比对。算法的时间复杂度是o ( k m l 3 ) ，其中k 代表模型中状 态个数，m 代表树结点数目，l 代表序列长度。 h o l i i l e s 【2 5 】在双随机上下文无关文 法( p a i r s c f g ) 模型上基于动态规划进行双序 列结构比对，算法提出基于预先计算好结构的折叠信封( f o l de n v e l o p e ) 方法，可以 有效得对递归过程中碱基对集合进行限制。在s t e m 或l o o p 很长的特殊情形下， 算法时间复杂度可以降低到o ( l l l 2 ) ，其中l l 和l 2 分别代表两条序列长度。e d d y 口6 】 提出基于协方差模型的序列结构比对算法。协方差模型是一种剖面随机上下文无 关文法( p r o f i l e s c f o ) ，可用于计算多条r n a 序列的中心序列。基于协方差模型的 比对算法首先将结构比对转换为指导树，后利用指导树( g u i d et r e e ) 构建协方差模 型，模型状态分别表示结构的s t e m 和l o o p 区域。算法采用分而治之 ( d i v i d e a n d c o n q u e r ) 策略，将所需的空间复杂度降至o ( l 2 1 0 9 l ) ，其中l 表示序列 长度。 ( 5 ) 其他序列结构比对算法 s a n k o f t f 2 7 】基于动态规划思想提出并发序列比对和结构预测算法，算法的时间 和空间复杂度分别是o ( l 3 k ) 和o ( l 2 k ) ，其中l 表示比对序列长度，k 表示序列数 目。过高的算法复杂度使得该算法不具有实用性，下列算法在s a n k o f f 算法基础上 做了改进： d y n a l i g n 算法【2 8 】考虑r n a 序列碱基具有协同变异特性，比对时不再依赖于序 列相似性，通过对双序列中的比对碱基在各自序列中的位置差异距离进行约束， 将算法时间复杂度降至o ( l 3 m i i i 入3 ) ，空间复杂度降至o ( l 2 r a i n 入2 ) ，其中l m i n 表示 第6 页 国防科学技术大学研究生院硕士学位论文 两条序列长度的较小值，入表示比对碱基在各自序列中位置差异的最大值。 f o l d a l i g n 算法【2 9 】基于能量信息和序列相似度进行打分，可进行全局比对和局部比 对，通过对予序列最大长度、两条子序列长度最大差异值、子结构类型进行约束， 采用剪除策略将算法的时空复杂度降至o ( l 3 m i n 入3 ) 和o ( l 2 m i n 入2 ) 。p m c o m p 3 0 】通过 直接比对碱基配对概率矩阵的方式，并对子序列长度差异值进行约束，将算法时 间和空间复杂度分别降至o ( l 4 ) 和o ( l 3 ) ，其中l 表示比对序列长度。在p m c o m p 基础上，p m m u l t i 3 0 l 和f o l d a l i g n m 0 1 】根据比对碱基配对概率矩阵得到的相似度打分 构建指导树，采用渐进比对( p r o g r e s s i v ea l i g n m e n t ) 方法将双序列比对推广到多序列 比对。上述两个算法的不同点是参加比对的碱基配对概率矩阵可以不同。 1 - 2 2 主要算法比较 基于图模型的比对算法的缺点是当序列长度较长时模型变得过于复杂，使算 法效率降低；基于树模型比对的算法只能处理结构已知r n a 序列之间比对，且无 法处理含伪结的r n a 序列结构比对；基于弧注释序列模型比对算法优点是表示 r n a 序列和结构信息方式十分直观，可以处理含伪结的序列结构比对；基于概率 模型算法缺点是具有很大的局限性，同时算法时间复杂度较高。基于s a n k o f f 思想 的改进算法降低了s a n k o f f 算法在特定情形下的时间和空间复杂度，优点是可以并 发进行序列比对和结构预测，不足是有时会出现无解或者与最优解相差较远的情 况，无法保证解的最优性。 1 2 3 算法存在的主要问题 ( 1 ) 由于r n a 序列结构比对在比对过程中加入了结构信息，相比于单纯序列信息 比对，时间复杂度普遍较高：基于弧注释序列模型含伪结r n a 序列结构比对是 m a x s n p 难问题【2 1 】；基于无序树模型r n a 序列结构比对是m a x s n p 难问题【1 2 】； 解决基于弧注释序列模型不含伪结r n a 序列结构比对问题效率较高的是文献 9 中算法，时间复杂度是0 ( l 4 ) ，其中l 表示序列长度，但当r n a 序列较长时算法 仍不适用。 ( 2 ) 伪结是r n a 序列体现功能的重要部分。目前含伪结的r n a 序列结构比对仍然 是一个难点，文献【1 1 ，1 9 ，2 4 d p 的算法无法处理含伪结的r n a 序列比对，文献 3 2 】 只能处理伪结类型特定的r n a 序列结构比对问题。 ( 3 ) 参加比对的序列相似度较低时，比对结果的准确度较差。 以上问题导致现有r n a 序列结构比对算法准确度不高和时间复杂度较高，影 响了算法在大规模r n a 序列数据库中的应用。为此，如何降低算法时间复杂度以 及提高比对结果准确度是当前r n a 序列结构比对的研究热点。 第7 页 国防科学技术大学研究生院硕士学位论文 1 3 文章的主要工作和创新点 本文在对现有r n a 序列结构比对算法深入分析的基础上，针对目前算法中存 在的主要问题，提出了基于树模型的r n a 序列结构比对算法，主要的工作和创新 点包括： ( 1 ) 介绍了r n a 序列结构比对的基础知识，分析了当前比对算法的主要模型及 主要思想，并对算法进行了比较和分析，指出了现有算法中存在的问题。描述了 树模型的构建和操作与r n a 序列结构比对的联系。 ( 2 ) 提出了基于树模型的r n a 双序列结构比对算法，对算法进行了设计和实 现，与已有比对算法进行了比较。测试结果表明当序列相似度较低时，本文算法 的比对结果具有较高的准确度。 ( 3 ) 在r n a 双序列结构比对算法的基础上，结合t c o f f e e 算法基本思想，本文 设计并实现了r n a 多序列结构比对算法，与其它算法进行了复杂度比较。数值实 验结果表明，在序列相似度较低且参加比对序列数目较少时，本文算法具有较优 的比对结果。 1 4 文章结构 r n a 序列结构比对是生物信息学中一个重要的基础课题，根据功能主要由结 构决定的基本规律，在比对过程中考虑r n a 序列本身的结构信息进行比对。本文 在对国内外已有算法进行深入分析的基础上，提出了基于动态规划算法思想的 r n a 双序列结构比对算法，并结合t c o f f e e 算法思想推广到了多序列结构比对。 按照研究内容的先后顺序以及求解问题所需的基础理论知识进行论文撰写，各章 节的内容安排如下： 第一章：绪论。介绍了生物信息学的研究背景和r n a 序列结构比对算法的研 究意义。介绍了当前国内外的主要算法，对主要算法进行了比较并指出当前算法 存在的主要问题。 第二章：基础知识介绍。首先介绍了r n a 序列结构的基本概念，接着对r n a 序列结构比对问题进行了详细描述，给出了打分方法设计。最后给出了树模型的 构建方式以及对树模型的操作。 第三章：提出了一种基于树模型的r n a 双序列结构比对算法。利用动态规划 的基本思想，将基于树模型的r n a 序列结构比对分割成相关的子问题，通过对子 问题的求解得到原问题的解。本章首先介绍了动态规划算法的基本思想和应用， 接着对r n a 双序列结构比对算法进行了详细分析和设计，并进行了实现。通过与 现有算法进行比较，实验结果表明本文算法具有较高的比对准确度。 第8 页 国防科学技术大学研究生院硕士学位论文 第四章：提出了一种结合t c o f f e e 算法思想r n a 多序列结构比对算法，将双 序列结构比对推广到多序列结构比对。首先介绍了基于渐进比对思想的多序列比 对算法，并重点对t c o f f e e 算法的基本原理进行了分析和描述。接着，结合t c o f f e e 算法思想将双序列结构比对推广到多序列结构比对，对算法进行了实现。通过数 值实验研究多序列比对结果与参加比对的序列数目以及序列的平均相似度间的关 系。实验结果表明当序列相似性较低且比对数目较少时，本文算法结果是较优的。 第五章：结束语。对本文的研究方法、主要工作和创新之处进行了总结，并 给出了可能的进一步研究方向。 第9 页 国防科学挂术大学研究生院硕士学位论文 第二章基于树模型的r n a 序列结构比对基础知识 随着r n a 结构和功能的研究越来越受到人们的重视，k n a 序列结构比对作 为一种重要的技术手段，己逐渐成为研究单条序列功能以及序列间相似度的重要 途径。树模型具有表现方式直观，易于操作等特点适合描述和建模r n a 序列结 构比对。本章介绍了k n a 序列结构相关概念和序列结构比对问题的基础理论，并 结合比对问题介绍了树模型的构建和操作。 2 1r n a 序列结构相关知识 r n a 分子中存在四种不同的碱基：a 一腺嘌呤，g 鸟嘌岭，c 胞嘧啶，u 屎 嘧啶。序列由a 、u 、g 、c 四个碱基组成，每种碱基与磷酸集团和核糖结合形成 核苷酸，而核苷酸是p , n a 分子的基本组成单位。核苷酸的线性排列形成心a 序 列，r n a 序列有时又被称为r n a 初级结构( p r 岫- ys t r u c t u r e ) 。r n a 初级结构类 似于平时所说的字符串，r n a 序列包括5 1 端和3 。端，5 端称为上游端( u p s u e a me n d ) ， 3 端称为下游端( d o w n s t r e a me n d ) 。在r n a 分子内，碱基间可以通过氢键作用而形 成配对：a 与u 、g 与c 可以形成稳定配对在某些情形下，g 与u 可形成不稳 定配对。序列中未形成配对的碱基称为自由碱基( f r e eb a s e ) ，形成配对的碱基称为 碱基对( p a i rb a s e s ) ，将形成配对两个碱基根据与5 。端的远近分为5 1 端碱基和3 端碱 基。 r n a 中的互补碱基通过氢键作用形成二级结构，在单链r n a 中，由于碱基 配对出现在单个r n a 分子中，因此会形成连续碱基配对的区域，称为茎区( s t e m r c g i o n ) ，由于能量的堆积此时称为栈( s t a c k ) 。在r n a 链中，为了形成碱基配对有 时需要反转链的方向，此时形成发夹环( 1 - 1 a i r p i ni o o p ) 。如果r n a 链上存在少量的 碱基没有对应的互补碱基，此时会形成一个小的突起部分( b u l g e ) 和内部环( i n t e r i o r l o o p ) 。当多个连续的未配对碱基与若干个茎区相连时，此时形成多分支环( m u l t i p l e l o o p ) 吲。下图是一个典型r n a 二级结构1 3 3 1 ： 霞墨硬：嫱, h a i r p i n l o o p p ；彩i 爱襄爹9 第1 0 页 国防科学技术大学研究生院硕士学位论文 在自然界演化过程中，r n a 核苷酸序列的每一位都有可能发生变化，而序列 发生变化过程与生物本身的进化过程是密切相关的。r n a 中碱基发生变异主要包 括替换( s u b s t i t u t i o n ) ，插入和删除( i n s e r t i o n d e l e t i o n ，缩写为i n d e l ) 。替换是指在进 化过程中序列中的某个碱基发生了变化，由新的碱基替换原有碱基，此时产生新 的r n a 序列。插入和删除是指在r n a 序列中添加或删除一个或多个碱基。插入 和删除是一个相对的过程，在序列层次上，仅仅包含对碱基的插入和删除，在第 一个序列中插入一个碱基等价于在第二个序列在相同位置删除该碱基。在结构层 次上，插入和删除既包括对碱基的插入和删除，同时又包含碱基对的插入和删除， 在碱基对插入和删除时，将构成碱基对的两个碱基作为一个基本单位，同时插入 和删除。由于在自然界的进化过程中存在着碱基协同变异( c o m p e n s a t o r yb a s e c h a n g e ，记为c b c ) ，所以当序列层面上发生变化时，可能从结构层次上并不会随 之发生变化。在自然界中，插入和删除的概率要比替换小很多。在序列结构比对 的过程中，常常通过加入空位( g a p ) 的方式来反映插入和删除的过程。 r n a 序列结构可以用二元组( p ) 来表示。其中r 表示定义在集合上由序列 碱基构成的集合，集合元素按照从5 喘到3 喘的顺序依次排列，p 表示碱基对构成 的的集合。从序列的5 端开始计数，定义第i 个碱基用r i 】表示，我们定义 = a ，u ，g ，c ) ，r i 】。若序列的第i 个碱基和第j 个碱基间形成氢键作用，若r i 】 和r d 表示配对碱基，可以缩写成( i j ) ，( i j ) 是集合中p 的元素当且仅当( r i 】，r d 】) b p ，b p - ( a ，a ) ，( g ，c ) ，( c ，g ) ，( g ，u ) ，g ) ) 。定义r i j 表示r n a 序列中从碱 基r i 】到碱基r d 】的一段子序列，则r 嘶 和r k ，l 】分别表示两个连续的r n a 子序列， 且i j k l ，r 【i 】与r 1 ，r i + 1 】与r 1 1 】r 【j 】与r k 】之间都存在氢键作用，我们把r i j 】 和r k ，l 】称为茎区。 定义( i j ) ，( 瑚) 表示集合p 中的两个元素，i r l l ，i r 2 1 分别表示两条r n a 序列的 长度，则1 i j i r , i ，l i - j l r 2 l ，其中i 勺表示在序列中，r i 在r d 】的左侧，即 r 【i 】更接近5 端。定义( i j ) ，( 巧) 具有如下基本性质： ( 1 ) i = i 当且仅当产i ( 2 ) r i 和r 团表示形成配对的两碱基，则| j - i | 4 。 性质( 1 ) 表明r n a 序列的碱基至多只能与一个碱基形成氢键作用。性质( 2 ) 表 明在序列内可以形成配对的碱基在序列的位置上存在要求，靠得太近的碱基往往 不能形成氢键作用。在i i t 且j i 的前提下，r n a 具有三种基本结构类型：( 1 ) 前 序( p r e c e d e d ) ：i j q ；( 2 ) 内嵌( n e s t e d ) ：i ：a 归 ，l i ，膏i i 在s i 计算的基础上，比对a 的s p s 分值可以计算为： m s p s = 嵩 y 笥 其中m ，表示参考比对的长度，s 一表示参考比对中第i 列的分值。 c o f f e e 目标函数定义如下式： ii - 1 w f j s c o r z ( a “) t = 2j = l ( 2 - 2 ) ( 2 3 ) 女, -