（计算机应用技术专业论文）基因组序列拼接算法及ncrna新基因的发现.pdf

摘要 摘要 随着基因组研究的不断深入，生物信息学这一领域得到了迅速的发展 本论文就是在生物信息学中的大规模基因组测序中的信息分析和基因组中非编码区 信息结构分析两个重要方面开展的一些研究工作 具体来说是： i 新的d n a 序列拼接算法的研究； 2 r e p e a ts e p a r a t i o n 相关理论问题的研究； 3 基于e s t 序列寻找n e r n a 新基因的方法的研究； 4 基于s a r s 蛋白的d r n a 设计 主要成果有： 针对基因组序列拼接问题提出了新的算法其实质是将拼接问题抽象成为求解最短 公共超串问题，并将局部搜索( l o c a l s e a r c h ) 方法用于求解最短公共起串中这一新的策 略为克服传统的基于贪心算法的拼接软件所导致的拼接错误开辟了途径本文还进一步提 出了。邻域剪枝”( n e i g h b o r h o o d p r u n i n g ) 和“互补校验”( c o m p l e m e n t a r y - v a l i d a t i o n ) 两种优化策略，从提速和提高拼接质量两方面显著地改进了算法性能 本文将基因组序列拼接中重复序列的处理问题形式化为k 一最近子串问题( k - c l o s e s t s u b s t r i n gp r o b l e m ) 和k 一最小海明距离和子串问题( k - c o n s e n s u s p a t t e r np r o b l e m ) 我们借鉴并发展了。随机维选取策略”( r a n d o ms a m p l i n gs t r a t e g y ) ，取得以下研究成 果： 1 给出0 ( 1 ) 一最近子串问题的一个p t a s 2 给出0 0 ) 最小海明距离和子串问题的一个p t a s 3 给出了耳一最近串问题( h a m m j n g t a d u sk c l u s t e r i n g p r o b l e m ，k 最近子串 问题当l = m 时的一个特侧) 的( 2 一e ) 不可近似性的一个新颖直接的证明 以上研究结果可望为设计解决r e p e a t 相关问题的实用算法有所启发 关于基因组中非编码区信息结构分析的研究当中本文主要包括以下两方面的工作： 建立了基于e s t 数据库发现新的n e r n a 基因的系统方法，并完成了相应的软件 在利用这些软件寻找n c r n a 基因的工作中我们发现了9 条序列与已知的n c r n a 基因 高度同源，他们有s c r n a 、s n r n a 、趿o r n a 和s r pr n a ；另有一条可能是人的新 n c r n a 候选序列由此，表明e s t 数据库中确实包含n e r n a 基因的信息这一结果也 证实了我们的方法是正确的、有效的 针对s a r s 冠状病毒( s a n sc o r o n a v i r u s , s a i l s - c o 中编码5 个主要蛋白质的基 因，用生物信息学的方法设计了3 4 8 条候选s i r n a 靶位。理论上，相应的s i r n a 双链 体可能会特异性地抑制s a p o s - c o v 靶基因的表达，同时不会影响细胞正常基因这也为 下一步进行实验研究提供了理论基础 关键词：d n a 序列拼接；算法优化；n c r n a 基因发现；k - c l o s e s ts u b s t r i n g ； s i r n a 设计 英文摘要 a b s t r a c t d n a s e q u e n c ea s s e m b l ya l g o r i t h ma n d n e wn c r n ag e n e f i n d i n g x u3 i n 酸l ( c o m p u t e ra p p l i e dt e c h n o l o g y ) d i r e c t e db yl ig u o j i e w i 抽t h eg r e a ta d v a n c ei nt h eg e n o m i c s , b i o i n f o r m a t i c sm a k e sar a p i dp r o g r e s s s y n c h r o n o u s l y t h i s 曲e s i s f o c u s e s0 1 1t h et w o i m p o r t a n t b r a n c h e si nb j o i n f o r m a t i c s ，w h i c j l a r e “d n as e q u e n c ea s s e m b l y ”a n d 。n o n c o d i n gg e n ea n a l y s i s ”s p e c i f i c a l l y , w ed e v e l o pan o v e la s s e m b l ya l g o r i t h m r e s e a r c ho i lt h et h e o r e t i c a lp r o b l 咖sr e l a t e dt o r e p e a ts e p a r a t i o n ，d e v e l o p an o v e lp o t e n t i a l n c r n a - g e n e - f i n d i n gm e t h o da n dd e s i g nt h e s i r n a os a r s p r o t e i n s t h em a i na c h i e v e m e n t sa r el i s t e da sf o l l o w s an e wd n as e q u e n c ea s s e m b l ya i g o r i t h mi sd e v e l o p e d ，t h ek e yi d e ai st h a tw e e m b e dt h es e q u e n c ea s s e m b l yp r o b l e mi n t ot h e “s h o r t e s tc o m m o ns u b s t r i n g ”( s o s ) f r a m e w o r ka n dt h e “l o c a ls e a r c h ”a l g o r i t h mi sa p p f i e dt of i n dt h es u b o p t i m a ls o l u t i o n o fs c s i ti sat o t a l l yn e wa p p r o a c h ，w h i c hc a nb ee x p e c t e dt oi m p r o v et h em i s a s s e m b l y r e s u l t sg e n e r a t e db yt r a d i t i o n a la s s e m b l e r s ，i na d d i t i o n ，t w oe f f e c t i v eo p t i m i z i n gs t r a f e - g i e s “n e i g h b o r h o o dp r u n i n g ” a n d 。c o m p l e m e n t a r y - v a l i d a t i o n ”， a r ea d o p t e dt o s i g n i f i c a n t l yi m p r o v et h ep e r f o r m a n c e o f o r i g i n a la l g o r i t h m ，b o t hi nt h es p e e da n d i nt h e r e s u l tq u a i l t y w ec o n s i d e rt h e “弘c l o s e s ts u b s t r i n gp m b l e m ”a n d 。k 二c o n s e n s u sp a t t e r n p r o b l e m ”w h i c ba r et w od i f f e r e n tf o r m u l a t i o n so ft h er e p e a ts e p a r a t i o np r o b l e m i n t b j sa r t i c l e ，w ea d o p ta n de x t e n dt h e “r a n d o m s a m p l i n g s t r a t e g y ”a s a r e s u l t ，w e 昏i r e a p t a sf o rt h e “0 0 ) c l o s e s ts u b s t r i n gp r o b l e m ”a n df o rt h e “0 0 ) 一c o n s e n s u s p a t t e r n p r o b l e m ”s e p a r a t e l y i na d d i t i o n ，u d n g an o v e l c o n s t r u c t i o n ，w e 百y e ad i r e c t a n dn e a r e rp r o o f o ft h en p - h a r d n e s so f “( 2 一e ) 一a p p r o x i m a t i o no f t h eh a m m i n gr a d i u s k - c l u s t e r i n gp r o b l e m ”as p e c i a l 溅v e r s i o no f t h e “k - c l o s e s ts u b s t r i n gp r o b l e m ” r e s t r i c t e dt ol = m t h ea b o v et h e o r e t i c a lr e s u l t sa r eo r i g i n a la n dc a nb ee x p e c t e dt op r o v i d es o m ei n s i g h t sg u i d i n gt h ed e s i g no f t h ep r a c t i c a la l g o r i t h mt os o l v et h er e a lr e p e a tr e l a t e dp r o b l e m si na s s e m b l y an o v e lp o t e n t i a i n c r n a 一骨e n e - 矗d i n gm e t h o di sd e v e l o p e db a s e do nt h ee s t d a t a b a s e a s8r e s u l t w ef i n dn i n es e q u e n c e sa r ec o n f i r m e dn c r n a g e n e 。o n es e q u e n c e m a yb ean o v e lh u m a nn c 眦g e n e t h e o b t a i n e dp o s i t i v er e s u l t sc o n f i r mt h a tt h e r e a r en c r n a g e n e si nt h ee s t d a t a b a s e a l s o ，j tv e r i f i e st h ev a l i d i 妒o f o u tn c r n a - g e n e - f i n d i n gm e t h o d f o c u s i n g o nt h e f i v e g e n e s , w h i c h c o d e f i v e c r u c i a l p r o t e i n s o f s a r s c 0 v r e s p e c t i v e l y , w eo b t a i n3 4 8s i r ac a n d i d a t et a r g e t sf o l l o w i n gb i o i u f o r m a t i cm e t h o d s p o t e n ts i r n a d u p l e x e ss p e c i f i c a l l ys u p p r e s se x p r e s s i o n o fi t sc o r r e s p o n d i n gs a r s g 0 yt a r g e tg e n e w h i l eh a v e1 3 0i n f l u e n c e0 1 1t h en o r m o e x p r e s s i o no f h u m a ng e n e i tw o u l dl a y af o u n d a t i o n f o rt h ef u r t h e re x p e r i m e n t a lr e s e a r c h e so nt h es i r n a j j k ed r u gd e s i g nf o rt h es a r s - c o v k e y w o r d s ：d n as e q u e n c ea s s e m b l y ；a l g o r i t h mo p t i m i z a t i o n ；n c r n ag e n ef i n d i n g ； k - c l o s e s ts u b s t r i n g ；s i r n ad e s i g n 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。就我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 作者签名：徐獬，眩 日期：移咖季- 。 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件， 允许论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采 用影印、缩印或其它复制手段保存该论文。 储繇糊帕导师虢枷艺嗍渺“弓驴 第一章引言 1 1 生物信息学 第一章引言 生物信息学( b i o i n f o r m a t i c s ) 是一门新兴的交叉学科它所研究的材料是生物学的 数据，而它进行研究所采用的方法，则是从各种计算技术衍生出来的【1 1 2 0 世纪5 0 年代，d n a 双螺旋结构的阐明开创了分子生物学的时代以生物学和 医学为主要研究内容的生命科学研究从此进入了前所未有的高速发展的阶段生物学相 关信息量的革命性的爆炸，产生了对海量生物信息进行处理的需求；而计算机技术的革 命性发展，形成了处理海量生物信息的能力于是，生物信息学便在综合计算生物学研 究和生物学信息的计算机处理的基础上迅速而成功她发展起来了生物信息学是计算机 和网络大发展、各种生物数据库迅猛增长形势下如何组织数据、并从数据中提取生物学 新知识的学问 广义地说，生物信息学从事对生物信息的获取、加工、储存、分配、分析和释读；并 综合运用数学、计算机科学和生物学工具，以达到理解数据中的生物学意义的目标它 需要发达的、复杂的、可相互交流的数据库系统；强有力的创新算法和软件；自动化的 大规模高通量的生物学研究方法与平台技术 具体地说，生物信息学是把基因组d n a 序列信息分析作为源头，找到基因组序列 中代表蛋白质和r n a 基因的编码区，阐明非编码区的信息实质，破译隐藏在d n a 序列 中的遗传文法规律；同时，归纳、整理与基因组遗传文法信息释放及其调控相关的转录 谱和蛋白质谱的数据，从而认识代谢、发育、分化、进化的规律生物信息学综合基因信 息和大规模蛋白质空间结构测定及蛋自质相互作用检测的数据，进行蛋白质空间结构的 模拟和蛋白质功能的预测( 包括认识蛋白质与蛋白质相互作用以及蛋白质与配体的相互 作用规律) ，进而将此类信息与生物体和生命过程的生理生化信息相结合，阐明其分子机 理，最终进行分子设计、药物设计和个体化的医疗保健设计 在基因组研究时代，生物信息学至少应包含三个层次上的重要内容；基因组信息学、 蛋白质的结构计算与模拟以及药物设计其中基因组信息学包括大规模基因组测序中的 信息分析，新基因和新s n p s 的发现与鉴定，非编码区信息结构分析，遗传密码起源和生 物进化的研究以及完整基因组的比较研究基因组信息学是生物信息学的源头和基础； 蛋白质的结构计算与模拟是基因组信息学发展的必然结果；分子与药物设计是利用蛋白 质结构与功能信息造福人类健康和农业的有力工具。这三者紧密地围绕着遗传信息传递 的中心法则，因而必然有机地连接在一起 本论文就是在大规模基因组测序中的信息分析和非编码区信息结构分析两个方面开 展了一些研究工作具体来说，主要包括以下四项内容： 1 提出并优化一种新的d n a 序列拼接算法； 2 r e p e a ts e p a r a t i o n 相关理论问题的研究； 中国科学院硕士学位论文一基因组序列拼接算法及n c r n a 新基因的发现 3 发展了基于e s t 序列寻找新的n c r n a 基因的方法； 4 基于s a r s 蛋白的s i r n a 设计 1 2 基因组序列的获取及拼接 1 2 1 鸟枪测序法 基因组研究的核心目标是获得生物体的整套遗传密码其实现的技术途径是大规模 d n a 测序，最主要的测序方法是鸟枪测序法( s h o t g u ns e q u e n c i n g ) ，其主要包括两个 步骤： 第一步，d n a 长链基于酶切或者物理方法被打碎成数量在百兆级的随机片断，对这 些小片段进行扩增形成许多c l o n e ，然后对每个c l o n e 进行测序由于测序仪的工艺限 制，一般每次测得高质量序列片断只有5 0 0 - 7 0 0 个碱基左右( 一次测量称为一个r e a d ) 第二步。拼接与组装，就是用各种计算机软件识别出具有首尾间重叠关系的r e a d s ， 并依此重建出原始的序列 就像一个巨大的拼图游戏一般，鸟枪法测序过程中产生的d n ar e a d s 必须组装出对 应基因组的全景图这个看似简单的过程由于测序的误差，不完全覆盖性以及d n a 序列 中重复序列的存在等问题，实际上是对现有技术的重大挑战也正因为上述问题的存在， 实际的测序过程中，还需要引入额外的第三步，即涉及到大量的人工干预的“f i n i s h i n g ” 阶段由于f i n i s h i n g 要求专业的实验技术以及经专门训练的人员，所以其成本极高这 就要求拼接软件能够考虑到f i n i s h i n g 阶段获得的额外信息，以实现动态的降低成本的目 的 1 2 2 大规模基因组测序流程 实际上，目前获得大规模基因组主要两大类测序流程是： “t h ec l o n e - b y c l o n ea p - p r o a c h ”和“t h ew h o l e - g e n o m es h o t g u na p p r o a c h ”现分别简要介绍如下 1 “t h ec l o n e b y c l o n ea p p r o a c h 。 该方法由两个层次构成，如图1 1 所示具体的，首先将基因组序列随机地打碎成 长度为5 0 k b p 到3 0 0 k b p 的片断，并将其插入到b a c s ( b a c t e r i a l a r t i f i c i a l c h r o m o s o m e ) 中。其中，b a c s 是专门设计为能够容纳大的d n a 片断的载体机制，而插入到b a c s 中的d n a 片断被称为i n s e r t 然后，收集b a ci n s e r t s 并保存在文库中( 1 i b r a r y ) ，这 样研究人员可以在后续的实验中选取特定的b a ci n s e r t s 用于扩增。第一个层次包括覆 盖整个基因组的这些大的i n s e r t s 的一个拼接和定位，或称为物理图谱( p h y s i c a lm a p ) 的 构建对于已给定的物理图谱，研究者从中寻找能够覆盖整个基因组的具有最小重叠关 系的i n s e r t s 集合( t h em i n i m u mt i l i n gs e t ，图1 1 中用绿色表示) 。 2 第一章引言 图1 1 ：“t h ec l o n e - b y c l o n ea p p r o a c h4 的两层方法 而在第二个层次上，对上述选取的i n s e r t s 集合中的每个i n s e r t 进行鸟枪法测序 这里的p h y s i c a lm a p 指的是对于i n s e r t s 堆接后每一个i n s e r t 在基因组序列上的一 个物理定位与鸟枪测序法中的序列拼接使用i n s e r t 的完整序列确定重叠关系不同的是 b a ci n s e r t s 之间的重叠关系是基于每一个i n s e r t 的。印迹”( f i n g e r p r i n t ) 数据确定的 目前研究所使用的“印迹”数据有限制性长度酶切( r e s t r i c t i o nl e n g t hd i g e s t s ) 2 、限 制性图谱( r e s t r i c t i o nm a p ) 【3 】、微量探针杂交( o l i g op r o b eh y b r i d i z a t i o n ) 4 以及 s t s 探针( s e q u e n c et a g g e ds i t ep r o b e ) 【5 】等其中，由于在成本、自动化程度、可靠 性以及便于使用等方面的优点，s t s 探针目前被广泛使用，但其结果还是存在约2 的 假阳性和1 0 到2 0 的假阴性 该方法的优点在于；其一，对b a c s 的鸟抢测序方法已经是常规技术，相关的可靠 软件容易获得而且各中心有快速测序b a c s 并进一步加速的能力；其二，虽然物理图 谱难于构建，但是已有很多人的染色体备有相应的物理图谱，其覆盖了相当大部分的染 色体。尽管如此，h g p 仍然在成本、效率以及完全覆盖性上存在缺陷在此就不详细叙 述了。 2 “t h ew h o l e g e n o m es h o t g u na p p r o a c h ” 该方法又称“全基因组鸟枪测序法”是通过对整个基因组序列进行鸟枪法测序，并 直接用测序获得的最初始的f r a g m e n t s r e a d s ) 来构建整个基因组序列，最终获取完整 基因组序列的途径【6 与。t h ec l o n e - b y - c l o n ea p p r o a c h ”不同的是她引入了新的测序 方法。d o u b l eb a r r e l ”鸟枪测序法该方法可提供丰富信息，使得在构建基因组序列 的整个过程中无需任何物理图谱 。d o u b l eb a r r e l “鸟枪测序法是基于原始的鸟枪测序法的一个改进所有i n s e r t s 都 经过长度大小的选择，使其平均长度至少为测序仪可以测得的r e a d 序列长度的二倍；然 后，对于每一个i n s e r t 的两端经由测序仪进行测序该方法产生的具有对应关系的r e a d s 3 垦壁堂堕塑主堂垡迨塞基因组序列拼接算法及n c b n a 新基因的发现 s c 膏酬d = c , o f l t k j l c d 咖g2 洲蛔3 ) 图1 2 ：。t h ew h o l e - g e n o m es h o t g u na p p r o a c h ”中的m a t e s ，c o n t i g s ，g a p s 和s c a n f f v l d 对，称为m a t e s ，他们具有方向相反，间距约为个i n s e r t 长度等特性( 通常被称为d b c o n s t r a i n t 引入到拼接过程中) 。这类m a t e 的成对信息可以以一种整合的方式应用于序 列拼接软件中，也可以作为对于拼接结果的确认信息同时他们还能为c o n t i g s 间的定序 和定位提供重要的信息。 ( c o n t i g 是重建的f r a g m e n t s 的一种排列形式，它覆盖基因组 上段连续区域。) 也就是说，如果有成对关系的两个r e a d s 分别位于不同的c o n t i g 上， 那么我们将知道这两个c o n t i g s 的方向，并对它们之间的距离有所了解由于般情况下 在两个c o n t i g 之闻都会有多对m a t e 8 ，所以据此我们可以获得可靠的e o n t i g 之间的序关 系，进而形成s c a n f f o l d ( s c a n f f o l d 是最大的确定顺序和连接关系的c o n t i g s 集合) 。 总的来说，全基因组鸟枪测序的途径就是：首先，对d n a 序列进行。d o u b l eb a r r e l 一 鸟枪测序；接着，使用拼接软件直接对测序过程中获得的f r a g m e n t s 进行拼接与组装生成 组c o n t i g s ；然后，根据m a t e s 关系确定c o n t i g s 之间的序关系，最终获得s c a n f f o l d 最后，使用p c b 方法，补充测序c o n t i g 之间的g a p 区域( 如图1 2 所示) 。 图1 2 中顶端显示了一个蓝色的v e c t o r 上的一个绿色的i n s e r t ，测序反应从其两端 开始读取序列浅绿色的虚线表示r e a d s 之间的联系，其间距应用于拼接过程中三个 着以不同颜色的c o n t i g s 的相对序关系由m a t ep a i r i n g 关系所确定最终，将通过p c r 反应对c o n t i g s 间的g a p s 重新测序并填充，获得s e a n f f o l d 该方法的优点在于：其一，大大缩短测序周期并降低了测序成本由于不用构建物 理图谱，节省了大量的时间，以及人工实验所需要花费的大量成本；其二，双端测信息， 可以有效的排除r e p e a t 区域的对整个拼接过程的影响，这样就缩短f i n i s h i n g 阶段大量人 力财力的投入。而缺点在于：拼接过程中计算量明显加大，对软硬件性能要求较高；双端 4 第一章引言 测信息的引入，需要引入新的算法，并改进现有的软件 1 2 3 序列拼接 序列拼接任务即将这些测序生成的r e a d s 短片段拼接起来，恢复出原始的序列该 问题是序列分析的最基本任务，是基因组研究成功与失败的关键，拼接结果直接影响到 序列标注，基因预测、基因组比较等后续任务因此，基因组序列的拼接也是基因组研 究必须解决的首要难题其困难不仅来自它的海量数据( 以人类基因组序列为例，从数 量为l o 兆级的片断恢复出长度为亿级的原始序列) ，而且源于它含有高度重复的序列 图1 3 给出了一个典型大规模测序的流程图图中清楚地显示从测序仪的光密度采样与 分析、碱基读出、载体标识与去除、拼接、填补序列间隙、到重复序列标识、读框预测 和基因标注的每一步都是紧密依赖基因组信息学的软件和数据库的拼接则是其中的核 心 目前，最著名的基因组序列拼接系统有p h r e d - p h r a p 软件包和g i g a s s e m b l e r 软件 包。 p h r e d p h r a p 软件包由美啻华盛顿大学的p h i lg r e e n 和b r e n te w i n g 所研发，是目 前d n a 测序和序歹! 拼装工作中使用最为广泛的免费的软件包 7 j 8 】实际上，它由两部 分组成：b a s ec a l l i n g 软件p h r e d 和序列拼装软件p h r a p p h r e d 是一个采用快速傅利 叶变换分析技术以及动态规划算法从d n a 测序所得到的图形数据中提取d n a 序列排 列顺序信息( b a s ec a l l i n g ) 进而得到d n a 序列的软件p h r e d 对序列中的每一个数据 产生一个被广泛接受的带有质量控制标准( q u a l i t ys c o r e s ) 的”b a s ec a l l ”而p h r a p 是一个用于将鸟枪法测序的原始r e a d 8 序列拼接成c o n t i g 的软件【9 】p h r a p 结合相应 的质量控制标准值对p h r e db a s ec a l l i n g 所得到的d n a 序列依贪心法进行拼接在拼 接过程中p h r a p 可以自动地在p h r e d 质量指标的基础上计算拼接后得到的c o n t i g 序列 中的每个位置上碱基的误差的概率，并给出其质量控制标准值( q u a l i t ys c o r e s ) g i g a s s e m b l e r 的软件包是加州大学s a n t ac r u z 分校的w j a m e sk e n t 和d a v i d h a n s s l e r 在g r e e d y 算法的基础上发展的【1 0 1 2 其特色是它在建立s c a f f o l d 时利用了 各种不同的信息，包括测序片段、图谱、m r n a 、e s t 和b a c 末端序列数据来装配基 因组序列以决定克隆的排序和定向并用b e l l m a n f o r d 算法检测每个s c a f f o l d 的距离限 制( d i s t a n c ec o n s t r a i n ) 【m l n g i g a s s e m b l e r 在非常大规模的数据上工作，它能在 g i g a b a s e ( 1 0 9 ) 的测序r e a d 片段、1g i g a b a s e 的e s t 序列、2g i g a b a s e s 的成对质粒末 端序列以及0 5g i g a b a s e 的b a c 末端序歹的输入基础上，拼接大约4 0 亿碱基的序列 此外，还有许多种算法用于拼接b a c 、p a c 、c o s m i d 和其他克隆的亚克隆序列 或者拼接一些较小的无很强的重复序列的全基因组鸟枪法测序的序列c e l e r a 公司发展 了一个从成对的全基因组鸟枪法测序结果直接拼接较大基因组的方法【1 3 】，并将它成功 地运用于果蝇 1 4 】以致人类基因组的拼装 无论何种拼接软件，其核心算法都是在g r e e d y 算法基础上建立的首先寻找片段 5 中国科学院硕士学位论文一基因组序列拼接算法及n c r n a 新基因的发现 图1 3 ：典型大规模测序及信息处理流程图 6 第一章引言 之间的重叠部分( o v e r l a p ) ，然后，以最佳重叠为标准建立序列c o n t i g 所有这些方 法都采用一定的启发式方法以减少重复序列的混淆现有的拼接系统的核心算法在准确 度和运算速度上难以满足实际应用越来越高的要求钎对这种现状，我们提出一种新的 d n a 序列拼接算法，跳出传统的基于图论的框架，采用新的理论模式，即以最短公共超 串模型为理论依据，采用局部搜索( l o c a ls e a r c h ) 方法优化计算已实现的初步系统 显示了此算法的有效性关于我们算法的将在后面的第二章和第三章论述 1 3 编码蛋白质基因的理论预测方法 通过拼接得到人或其他生物的完整基因组序列后发现新基因就成了国际上基因组和 生物信息领域的热点，特剔是与人类缝康擅关的癌基因、高血压和冠心病相关基因以及 植物中的优质、高产、抗逆基因等使用基因组信息学的方法是发现新基因的重要手段 靠理论方法预测新基因对于细菌之类的小基因组是直截了当的对于较少有内含子的真 核生物，理论预测也是比较可行的；如啤酒酵母完整基因组( 约1 3 m b ) 所包含的6 千多 个基因，大约6 0 是通过信息分析得到的但是，人类基因组的情况就十分不同人类 基因一般含有较小的外显子( 平均5 0 个密码子，邵约1 5 0 b p ) ，较长的内含子( 有些超 过1 0 k b ) 因此。用理论方法预报人类基因组中编码蛋白质的基因在使用完整基因组序 列数据的同时还大量依据来自c d n a 和e s t 的序列数据以及比较基因组的分析结果 本节将综述编码蛋白基因预测领域的研究进展 用理论方法预报基因组中编码蛋白质的基因主要使用两类实验数据，即：完整基因 组序列数据和e s t 序列数据由于数据来源不同所以使用的数学方法和原理也不同下 面分别加以介绍 1 3 1 利用e s t 数据库发现新基因和新s n p s e s t 序列( e x p r e s s e ds e q u e n c e1 蛔s ) 是基因表达的短c d n a 序列，它们携带着 完整基因的某些片段的信息到2 0 0 0 年初g e n b a n k 的e s t 数据库( d b e s t ) 中人类 e s t 序列已超过1 6 0 万条，现在它已超过4 0 0 万条，大约覆盖了人类基因的9 0 以上 因此，如何利用这些信息发现新基因成了近几年的重要研究课题【1 5 1 1 1 6 】 应用这一技术路线，该组已经找出了几千条未与多种巳知数据库匹配的序列，并不 断地通过电脑克隆和组装寻找它们的全长序列用e s t 数据发现新的编码蛋白质的基因 虽然技术上是可行的，但程序设计是复杂的，计算量是巨大的重要之处是排除各种非 编码区信息，如引物、3 及5 端的非编码区序列等；排除错误信息。如非人类e s t 序列 等；构建各种专门数据库，如种子序列数据库等 单核苷酸多态( s n p ) 反映了不同物种间、不同个体间基因组序列上的差异，因而 被认为是基因组研究走向应用的关键1 9 9 8 年，国际上开展了以e s t 为主发现新s n p s 的研究其原理就是对同一基因从e s t 数据拼接得到了不同的转录本，它们就可能是一 7 中国科学院硕士学位论文一基因组序列拼接算法及n c r n a 新基因的发现 组s n p 此后，国际s n p 图谱工作组( t h e i n t e r n a t i o n a ls n p m a pw o r k i n gg r o u p ) 又 利用大规模基因组测序的数据，结合国际公用的多种族检测p a n e l ( 2 4 个种族差异的个 体) 和大片段重叠d n a 序列比较的方法，鉴定了一百四十多万个s n p ( 即每1 9 k b 一 个s n p ) ，并对其进行了初步的分析 1 3 2 从完整基因组d n a 序列中预测新o r f 从基因组d n a 预测新基因，现阶段主要是三种方法的综合： 1 从转录子m r n a 和e s t 得到的直接证据； 2 从与已知基因和蛋白的序列同源性得到的间接证据； 3 综合关于剪接位点( s p l i c es i t e s ) 、密码子使用偏爱的概率，以及外显子( e x o n ) 和内含子( i n t r o n ) 长度等统计数据的基于隐马尔可夫模型( h i d d e nm a r k o vm o d e l s ， h m m s ) 的从头预测方法等理论预测方法 第一种方法基于实验数据，但也受到污染e s t 、污染基因组d n a 等问题的干扰 第二种方法一般会得到基因相关序列，但有时会得到假基因( p s e u d o g e n e ) 这个方法显 然不可能得刭完全新的基因，即，与已知基因不存在序列同源性的新基因在理论上， 如果对于细胞识别基因的规律有了完整的认识，第三种方法应该能够精确地从基因组上 鉴定基因；但是，我们实际对于这些规律的认识是远远不够的因此，这些方法的灵敏 度和专一性受到信噪比的严重影响一般来说。这些预测对于果蝇和线虫的应用比对于 人类的应用较为成功具体地说，第三种方法还分为两类，一类是基于编码区所具有的 独特信号。比如起始密码子终止密码子等。另一类是基于编码区的碱基组成由于蛋 白质中2 0 种氨基酸出现的概率不同，每种氨基酸的密码子兼并度不同，同一种氨基酸的 兼并密码子使用频率不同等原因使得编码区中6 4 个三联码的分布远离它的随机分布概 率1 6 4 ，因此有别于非编码区 近十几年来，国际上又发展了许多有效算法和软件用于识别缩码区。比较著名的有t 基于人工神经网络【17 1 和模式识别的算法和软件，它们是g r a i l 【1 8 1 1 1 9 1 ，g e n e p a r s e r f 2 0 ，g e n e i d 【2 1 1 ，基于语言学方法的g e n l a n g1 2 2 1 ，基于隐含马尔可夫模型的g e n i e 【2 3 ， h m m g e n e 【2 4 】，还有基于非线性的分维方法【2 5 1 ，基于数学的复杂度方法【2 6 】等将 密码学方法用于识别编码区，也取得了较好的结果【2 7 1 这些方法的本质是识别基因组 d n a 中的外显子、内含子和剪接位点理论方法在预测编码区时存在的缺点是部分软件 处理多基因序列存在组合爆炸问题【2 8 】，对过长、过短外显子、内含子的预测准确性不 高 g e n s c a n 是较为常用的基因预测软件它是由斯坦福大学数学系c h r i sb u r g e 和s a m u e lk a r l i n 所研发基于隐马尔科夫过程模型( h m m ) 的基因预测软件( h t t p ：g e n e s m i t e d u g f j i s c a n h t m l ) g e n s c a n 主要用于完整基因的预测，包 括基因组序列中的外显子、内含子( 起始端内含子、内部内含子以及末端内含子) 、启动 子、多腺苷酸信号位点、供体与受体剪切位点的预测g e n s c a n 对预测中出现的所有 8 第一章引言 上述信息进行综合评估，以获取实际的完整的基因结构信息不同于其他一些主要基因 预测软件，g e n s c a n 允许对多基因基因组d n a 序列或其互补链上的部分的、完整的 甚至多重的基因进行预测g e n s c a n 被广泛的用于基因组序列的基因结构预测，也是 许多生物信息学数据处理软件包，如e b i 的e n s e m b l 基因注释专家系统的主要功能模 块g e n s c a n 适用于脊椎动物、线虫类、玉米、拟南芥等不同物种的基因预测此外， 适用于脊椎动物的版本在被用于果蝇d n a 序列的基因预测也取得很好的结果 1 4 基因组中非编码序列信息结构分析和n c r n a 基因预测 随着基因组研究的深入，科学家们通过分析海量数据很快就发现了一些重要事实： d n a 上编码蛋白质的区域，也就是基因，只占人类基因组的一小部分，不会超过整个基 因组的3 ，其余9 7 左右的d n a 序列仍不清楚功能，国际上科学家们习惯地把这部 分d n a 统称为“非编码d n a ”或4j u n k ”d n a 通过对完整基因组的比较发现， 低等的生物，象病毒、细菌等只有少量的“j u n k ”d n a ，而高等的动、植物则含有大 量“j u n k ”d n a ，它们甚至占据着基因组的大部分这就是说，伴随着生物从简单到 复杂、从低级蓟高级、从信息少到信息多，非编码d n a 不断增加它意味着4j u n k ” d n a 可能蕴涵着生物体复杂性的信息为此，“s c i e n c e ”周刊2 0 0 1 、2 0 0 2 、2 0 0 3 连续 三年将“小r n a ( s m a l lr n a ) ”评选为该年度全球科学十大进展，而2 0 0 2 年更将其作 为进展的第一位本论文的另一研究工作就是试图在基因组的非编码序列中发现n c r n a 基因于此相关，本论文还进行了基于s a r s 蛋白的s i r n a 设计，以期为s a r s 的治疗 提供信息 长期以来人们一直认为r n a 分子的主要作用是与蛋白质合成有关，无论是t r n a ， r r n a 还是m r n a ，它们一起构成一套精密的机构将d n a 中的基因信息传递到蛋白 质但自上世纪九十年代以来对小片段r n a 研究的一系列新发现，使人们不得不重新认 识r n a 在生命活动中的重要作用近年来大量的新实验结果表明非编码d n a 是可以表 达的，其表达产物是许多对生命过程富有活力的信息载体小r n a ( s m a l lr n a ) 的研究 就是最突出的例子上世纪九十年代美国d a r t m o u t h 医学院v i c t o ra m b r o s 小组以线虫 为对象用基因打靶技术研究某些基因对其发育的影响他们找到了一个对发育有明显干 扰的基因通常线虫要通过四个幼虫阶段才能成熟，这个基因的突变使其只停留在第一 阶段令人们惊奇的是这个基因并不编码任何蛋白质，而是编码一