毕业设计（论文）-基于RNA测序技术的转录组从头拼接算法研究

基于RNA测序技术的转录组从头拼接算法研究学院：专业：班级：学生姓名：学号：指导老师:完成日期：摘要：生物信息学主要研究分子生物学领域,而对于分子生物学领域，转录组的从头拼接又是其核心内容,即利用转录组的测序片段拼接出整个转录组中的所有表达的转录体。而RNA测序的出现，在计算上给转录组的拼接提供了一定的挑战。在目前，转录组的拼接算法主要是基于参考基因组的拼接方法与从头拼接方法。虽然基于参考基因组的方法比从头拼接方法更有突破性，不过基于参考基因组的拼接方法，仍然存在着一定的致命缺点，即为要有一个高质量的参考基因组。而从实际情况分析,绝大多数的生物根本不存在一个可供参考的已知基因组,相比之下，头拼接算法的重要性就突显而出。基于该现象，本文主要在分析当前拼接算法的基础上,提出了一个全新的转录组从头拼接算法(Bridger),巧妙地利用基于参考基因组算法的一些技巧来弥补目前从头拼接算法的不足。借助人、狗与老鼠的RNA测序数据上的测试结果,来表明Bridger比当前所有的从头拼接算法突出。除此之外，还将通过例子展示了Bridger在实际应用中重要价值。最后,提出总结，进一步介绍了转录组拼接下游的一些研究工作与研究方向。关键词：生物信息；参考基因组；拼接算法；测序数据Abstract: The main field of bioinformatics research in molecular biology, and for the field of molecular biology, scratch spliced transcripts group is the core content, namely the use of transcriptase sequencing fragments of mosaic in the entire transcriptase expression of all transcripts. The emergence of RNA sequencing, spliced transcripts in the calculation to provide a certain set of challenges. At the moment, stitching algorithm transcriptase mainly splicing method reference genome from scratch stitching method. Although the reference genome-based approach is more than de novo mosaic method breakthrough, but based on the reference genome splicing method, there are still some fatal flaw, that is to have a high-quality reference genome. From the analysis of the actual situation, the vast majority of organisms does not exist an alternative known reference genome, by contrast, the importance of the first stitching algorithm to highlight out. Based on this phenomenon, this paper based on the analysis of the current stitching algorithm, proposed a new de novo transcriptase stitching algorithm (Bridger), clever use of some techniques based on the reference genome de novo algorithm to supplement the current stitching algorithm. With people, test results RNA sequencing data on dogs and rats, to show all current Bridger prominent than stitching algorithm from scratch. In addition, by way of example will demonstrate the important value of Bridger in practical applications. Finally, summarize, and further describes some research work and research transcriptase downstream splicing.Keywords: bioinformatics; reference genome; stitching algorithm; sequencing data目 录摘要.ii第一章 绪论第一章 分子生物学的背景知识1.1生物学基础31.2测序技术.31.2.1测序技术的发展31.2.2单端测序和双端测序41.2.3 RNA 测序.51.3 测序片段的拼接6第二章 拼接算法的研究现状分析 2.1基因组的拼接算法 142.1.1贪婪方法 .162.1.2重叠-排列-共有序列的方法172.1.3 De Bruijn 图方法.182.2基于参考基因组的转录组拼接算法.202.3基因组从头拼接算法222.4转录组从头拼接算法的改进25第三章Bridger:新的转录组从头拼接算法3.1拼接前的考虑303.1.1测序数据的特点30 3.1.2测序错误的预处理313.2算法的创新点323.2.1舍弃deBruijn图而去构造剪接图323.2.3引进兼容图和最小路覆盖模型373.2.4通过加权巧妙地利用测序深度信息383.3Bridger算法393.3.1利用RNA测序片段构造剪接图403.3.2构造兼容图413.3.3寻找最优的转录体集合43第四章Bridger的测评4.1测试数据和评价标准444.1.1测试的数据454.1.2参数设置454.2评价方法和标准474.3 Bridger的优缺点494.4 Bridger的下游分析.51第五章 总结 参考文献 .55致谢词 6769第一章 绪论随着科技的增强，生物信息学的范畴也逐步增长，生物信息学是改革开放以来，出现的一门新颖的交叉学科，它主要的研究意义是利用数学、统计学以及信息学的相关知识，再结合计算机科学的相关研究知识去探讨并解决生物学上出现的问题。又随着生物学上的基因组测序技术的突破、而分子结构的测定技术在互联网的普及下又迈入了另一层面。据此，生物数据在科技的冲击下，沿直线上增，数以百计的生物学数据库如同雨后春算般迅速成长，这些数据给生物学的研宄提供了一定的屏障。对于复杂多变的生物数据，生物学家们需要借助一定的数学算法和计算工具去研究并处理分析这些数据。然后在从生物数据中获取更多的有用信息，周而复始，逐步沉淀，从而形成生物信息学。在当下，对于生物信息学的研究，则主要是集中在分子生物学这一领域上。而所谓的分子生物学，它主要是研究细胞内的核酸、脂肪、蛋白质等大分子的组成、形态、结构特征等等，根据这些特征的研究数据，人类可以真正地从分子平面上了解生物的特征与生活习性，进一步了解一些微生物的结构组成，在研究细胞内大分子的结构特征时，主要是研宄细胞内的DNA重组、遗传物质的表达、以及一些大分子的结构与功能等等。经过几十年的研究，生物信息学的发展与突破就如同催化剂般在逻辑层次上极大限度地推动了分子生物学的进步与发展。与此同时，生物信息学在其他领域范畴内也产生了共鸣。在数学领域上、计算机科学领域内都留下了诸多具有挑战意味的学术问题。例如对于遗传物质的剪接研究，也有一定的冲击效果，本文也主要研究遗传物质的剪接问题。众所周知，在遗传物质的剪接过程中，mRNA(信使RNA)的产生并不单一，有着两种或者多种以上的mRNA，故此，通过翻译过程皆能产生两种或者多种以上的蛋白质，该现象在分子生物学上人们称其为可变剪接。对于可变剪接，在生物学中，若真核生物经过一定的手段处理，基因中的内含子就会被处理掉，而所有的外显子就会相连。而基因中的外显子之间就获得不同的组合方式，从而形成不种种类的信使RNA。就目前而言，在信息生物学上，可变剪接的方法常常用于对真核生物的处理，且越来越普遍，对于人类而言，基因中都具有多个外显子，这也是说，在人类的细胞内大约有95%以上的基因都存在着可变剪接。可变剪接的出现极大程度地增加编码的种类，这也是体现蛋白质多样性的主要因素。在对细胞结构的研究中，我们已然知晓，细胞内所有的染色体物质皆构成一个庞大的基因组。而相对于真核生物的基因而言，原核生物的基因结构较于简普，简言之，原核生物的基因就是一段具有编码蛋白质的碱基序列，它并存在外显子与内含子，所以结构较为简单。真核生物的基因结构比原核生物的基因结构复杂得多，它不仅包括具有编码蛋白质功能的外显子(exon)，还含有不具有编码蛋白质能力内含子（intron)，外显子与内含子的存在也是分辨原核生物与真核生物的一大因素。基因传递遗传信息是以蛋白质的形式表达，在表达过程中，蛋白质的形成包括两个阶段，其一为转录（transcription)，其二则为翻译（translation）。转录是机体的遗传信息由DNA转向RNA的过程，即以双链DNA中的一条单链为模板，以四种核苷酸为原料，在RNA聚合酶的催化作用下生成RNA的过程，其中，四种核苷酸分别为腺嘌呤（A)、鸟漂呤（G)、胞啼唼(C)、尿喷唆(U)。在转录过程中，对于每一个RNA分子，我们都称之为转录体（transcript)，而一个细胞又包含着成千上万的转录体，转录体的总和即为一个转录组。转录完成之后，才完成蛋白质合成的前一部分工作，转录体还需要进入下一环节，才能合成具有生物功能的蛋白质，此环节则为翻译，所谓翻译，也就是利用RNA合成蛋白质的过程。在本文中，研究的主要问题主要针对于转录阶段，对于翻译阶段，且不坐谈。故此，我们主要着重于介绍蛋白质合成中的转录过程，翻译过程在此且不着分析。对于基因的转录过程，一般分为预启动、启动、核糖核酸聚合酶与启动子脱离、转录延续与转录终止这五个阶段。在转录过程中，其主要是由DNA的一条链着手，借助于RNA聚合酶与其它转录蛋白的帮助，从而合成一条对应的核糖核酸序列。该序列的作用，就是将遗传基因中的存储信息完整地复制出来。在DNA转录成RNA时，我们通过等价关系，可以将DNA中的T转换成了RNA中的U，这样便简化分析。以上言论，只对于真核生物，原核生物的转录阶段相对于真核生物，较为简单，其转录后的产物皆可以直接用于翻译蛋白质（个别噬菌体除外）。而真核生物的基因由编码蛋白质的外显子和不编码蛋白质的内含子组成，转录过程中，首先会形成mRNA前体，然后经过加工，再翻译成蛋白质。转录组是合成蛋白质的核心部件，基于其重要性，本文则以当前一些转录组拼接算法为基础,去研究并提出了一个全新的转录组从头拼接算法(Bridger),巧妙地利用基于参考基因组算法的一些技巧来弥补目前从头拼接算法的不足。第一章 分子生物学的背景知识1.1生物学基础众所周知，对于生物而言，其遗传密码是以DNA的形式存在于基因组中。而DNA分子是一个依照碱基互补配对原则，由两条核苷酸链构成的双螺旋结构的分子化合物。在RNA的剪接过程中，由于RNA的剪接变化，转录体就会发生多种异常情况，而转录体的异常剪接，正是疾病产生的导火索。就中国科学院近几年的研宄表明，生物所有的致病变异，就有三分之二的疾病变异产生于可变剪接阶段。在对癌症的研究中，异常的可变剪接时常发生在癌细胞中，这也是导致癌细胞增值的主要原因，是产生癌症的因素之一。因此，在对遗传物质的研究时，研究可变剪接过程，对于治疗许多人类疾病（包括癌症）都有着不可磨灭的意义。1.2测序技术测序技术的发展对于可变剪接的研究给予了一定的便利条件。为此，在研究可变剪接时，我们有必要了解第二代测序技术与RNA测序。掌握这些知识，在分子生物学中，对于分析测序数据与设计转录组拼接算法都异常常重要。1.2.1测序技术的发展20世纪50年代初，测序技术在生物界中横空出世，在测序技术出现的早期，人们就懂得利用化学降解的方法去研究并测定了DNA中的多聚核糖核苷酸序列。在后来，学者Sanger与Gilbert在此基础上又分别探寻出两种不同的DNA测序方法，这些测序方法的产生，有着及其重要的意义，它标志着第一代测序技术的诞生。而Sanger的双脱氧核苗酸末端终止测序法最终占据了第一代测序的主流地位。又历经十余年，经过六个国家的不懈努力，在2001年，完成了人类基因组计划（Human Genome Project, HGP)。时光不老，科学家们经过十年的艰辛，终于在解读基因密码上取得了一定的突破，继而推出第二代测序技术。人类基因组计划的顺利完成，使我国生物学跨上了另一层面，也充分地证明了我国具有研究遗传信息的能力。第二次测序技术的出现，是以Roche公司的454技术与Solexa技术和ABI公司推出的SOLiD技术为代表，对于第二代测序技术而言，它不仅饱含第一代测序技术的高准确性，还极大限度地提高了遗传信息的测序通量，测序通量的提高，标志着测序时间与测序成本得以降低。例如，在研究人类基因组计划时，科学家们就使用第一代测序技术作为研究手段，在此期间，花费了近 30亿美金的研究经费，历时十三余年；相比之下，如果利用第二代的SOLiD测序技术去研究一个人的全基因组测序，只需花费几千美金与一周的时间就可以完成这一项目。虽然说第二代测序技术具有很多优点，不过针对于第二代测序的测序数据分析，却给科学家们带来了一些问题与挑战，其原因在于第二代测序技术的测序片段较短、数据量大、不利于研究与分析。在第二代测序技术的基础上，Helicos公司又推出单分子测序技术；Pacific Biosciences公司推出单分子实时测序技术；Oxford Nanopore Technologies公司的单分子测序技术，这些技术又统称为第三代测序技术，不过，由于诸多因素的影响，就目前而言，第三代测序技术并不成熟，错误率较高，很少使用于实际应用之中。由此，第二代测序技术仍然占据测序的主流地位。1.2.2单端测序和双端测序第二代测序技术Roche 454，Illumina和ABI SOLID有单端测序（singleend)和双端测序（pairedend)两种方式。在目前，这三种技术是诸多测序方式的三大主流技术。其中，对于Roche454测序技术来说，它主要是单端测序，它的测序片段长度可以达到400bp800bp，在单端测序中，我们经常利用到基因组骨架的组装；而Solexa测序技术与ABISOLID测序技术的测序长度相对较短，其用途主要是用于对遗传信息基因组骨架的进一步组装与填补。不过Solexa技术与ABISOLID技术不仅可以单端测序，还可以双端测序。因此，只要合理运用双端测序的信息，就可以有效地克服测序片段短的缺点。在本节中，我们主要以Illumina为例去介绍单端测序与双端测序。对于单端测序，其测序步骤大体总结如下：首先利用一定的方法，将DNA样本进行片段化处理，使其被打碎，从而形成200-500bp长度的测序片段。此步骤完成之后，又将引物序列连接到DNA片段的另一端，然后在引物序列的末端加上一个接头，最终固定片段，这样便能从测序序列的一端读取DNA中的碱基信息。而双端测序，就是在构建待测序的DNA库时，在测序序列的两端接头上都加上测序引物结合位点，继而进行两轮测序，这样便能依靠测序序列的两端来获得DNA中的碱基信息。在实际应用中，在设计不同数据的拼接算法时，首先我们一定要充分考虑到是否利用双端测序技术。如果利用，就应该注意以下两个方面，其一，对于DNA测序片段的本身序列信息分析一定要合理；其二，双端测序的配对信息应有效利用。这样，才能给拼接过程提供更为权威的指导与参考。1.2.3 RNA 测序在设计拼接算法时，我们有必要介绍一下RNA测序，对于RNA测序的定义，我们可以将其解释为将高通量的测序技术应用到mRNA（信使RNA）上，然后逆转录生成的cDNA，在此过程中，就会产生了RNA测序，对于产生的RNA测序，通常被称为RNA-seq。对于RNA测序的用途，据总结，主要有如下几个方面，第一，可以利用RNA测序去研究不同基因的mRNA种类与各自基因的表达量；第二，可以借助RNA测序去分析探讨基因不同样本间的表达差异，继而为转录组的研究开拓一个有效的研究手段。在RNA测序未出现之前，对于转录组问题的研宄，研究人员主要是利用基于杂交的基因芯片技术为主要研究工具，不过由于技术上的缺陷，基于杂交的基因芯片技术无法准确地检测到新的mRNA，除此之外，此技术的灵敏度有限，对于表达水平的微小变化，也不能检测出来。在转录组的研究中，其技术主要有传统的基因芯片技术与EST技术，不过对于这两种技术而言，RNA测序具有诸多优点。例如，RNA测序可以达到单核苷酸的分辨率，能够确定出表达量很低的转录体，还可以研究可变剪接等等，这些成果，以上两种技术只能望尘莫及。基于RNA测序的优越性，一些专家学者便以此预测，在今后的几年或者几十年内，RNA测序技术有可能会取代传统的基因芯片技术，成为转录组研究的主要工具。而在应用方面，随着时间的推移，RNA测序技术也被广泛地使用于转录组的研究。RNA测序对于转录组的研究具有不可磨灭的划时代意义，不过凡事都具有两面性质，在生物信息学中，RNA测序技术产生的海量数据虽然给转录组的研究带来一定的机遇，不过在带来机遇的同时，也赋予了一定的挑战。因此，有效地对RNA测序数据进行合理的分析与探讨，是RNA测序技术是否在科学探索中获得一席之位的关键。关于RNA测序的主要目的，可以理解为它是研宄转录体的表达情况与比较多个不同信息样本间的转录组差异。其主要研究的问题包括了如何准确地确定DNA转录组中表达的转录体序列，在转录体序列得到表达之后，又如何估计基因中的转录体序列的表达量，继而依照转录体序列去探讨不同样本之间的差异性表达等等。在本章中，我们所谈论只是RNA测序研究的一个热点问题，即为从测序片段着手，去分析并拼接出基因中所含有的转录体序列，确定此序列，也是转录组研究的一大重要基石，在转录组的研究中必不可少，因此，合理掌握RNA测序，是研究生物信息学的基本要求之一。1.3 测序片段的拼接在生物学中，测序片段的拼接一直以来，都是生物界中最为棘手的问题之一，虽然诸多学者专家研究测序片段已经有了几十年的历程，不过至目前而言，这一领域的相关问题并未得到真正的解决。所谓测序拼接，其意义就是将基因测序所获得的短序列通过一些方法手段，从而还原成一个较为完整的序列，该过程则称之为测序拼接。对于遗传物质DNA中的测序片段，在针对拼接此过程时，最后得到的是一个完整的基因组序列。然而拼接RNA测序片段，由于可变剪接的存在，在拼接中，往往会得到一些彼此之间不连通的图，且每一个图的含义都是代表着一个基因位置上的转录情况。在拼接过程中得到的每一个图，我们都可以利用一定的方法去寻找与之对应的全长的转录体路。也就是说，在对转录组的拼接时，最终所获得的产物并不是一个长的测序序列，而是不计其数的转录体序列，在生物学上，我们将全体转录体统称为一个转录组。在研究转录组时，我们可以将其合理地比喻成以下这种情况，从理论上来说，如果我们将一本书复制多份，然后利用剪刀将这些书分别剪碎，形成千千万万个细小的碎片，在剪接的过程中，我们剪书的方式都不相同，最终在这些碎片之中，我们总会找到某一个碎片与其他碎片具有相同之处，也就是说，某一个碎片与其他碎片具有一定的重叠几率。而我们依靠碎片中，这些重叠的部分，最终是完全有可能将这本书的碎片重新组合，继而拼接成未剪接时的样子，依靠碎片重叠，将整个碎片组装成一本完整的书籍，这就是生物学中的序列拼接问题的最好举例。话虽如此，不过在解决实际情况时，我们所研究的问题，远远不止这些，也没有这么简单，因为事物具有一定的偶然性。就上述问题来说，假如在剪碎片时，由于自身的原因，我们将一千万个小碎片中的一部分碎片丢失了，而另外一部分碎片又不巧被一些东西污染，使其的外表发生了改变，那么这些碎片上的字迹就会被污染物遮挡，在研究中，就会大大地增加寻找碎片重叠的难度。在这种情况之下，我们是很难将这些碎片从新拼接出来的，我们在生活中遇见的拼接问题事实上与上述问题相似，情况变幻莫测，所以，对于某件事物，我们都应该从多层次的角度去探析这一问题。在最初研究序列拼接的算法时，其性质也只是为了开发一些具有启发式的算法，然后通过寻找，最终获得与当前序列的一段具有最大的重叠区域的测序片段来不断地延长基因中的当前序列。频繁使用，最终这种方法逐渐演变成一种基于图的算法，该算法主要包括以下两种，第一种被人们称为：“重叠一一排列一一共有序列”的方法,而另外一种方法则是基于 de Bruijn 图的方法。对于这两种方法的使用，它们都各自拥有着自己的优缺点，在第二代测序数据未出现之前，主要为第一代测序数据，在第一代测序数据的拼接之中，第一种方法“重叠一一排列一一共有序列”获得了成功的应用。由此可见，第一种方法的主流意义是先计算出基因中的测序片段的两两之间的重叠区域，然后再将这些测序片段重新，继而使其排列成一个新的图。每一个测序片段都来自于基因组中，而基因组序列应该穿过每一个测序片段，所以在研究时，我们应该从图中获得一个测序片段的路，利用这个测序片段的路最终求取最后的基因组序的所有转录体的序列，在求取中，也要对转录组进行一定的拼接。在测序研究的初期，人们对于转录拼接的研究并未引起重视，他们只是简单地按照基因组的一些传统方法去拼接RNA测序的数据，不过却未得到理想的成果。追溯其原因，我们可以将其总结为：转录组的测序与拼接的本质都异于基因组。虽然DNA测序的深度，在整个基因组上我们都可以将其看为相同，不过对RNA测序而言，它测序的深度并不相同，虽然RNA测序在不同的转录体之间或者在同一个转录体的不同位置都具有非常大的差异，在某些时候，其深度甚至相差了几个数量级。我们知道，基因组的拼接实质在于拼接出一个具有线性关系的基因组序列，不过基于转录组的拼接，又与基因组的拼接有着一定的差异。在转录组的拼接中，因为转录组中存在着可变剪接，所以每一个基因中，都有可能存在着很多个转录体，故而在转录组的拼接中就会形成数以万计的图，而这些图都能有效地刻画出一个基因的不同种剪接情况，此为两者不同的原因之一。又因为转录组的测序与基因组的测序有所差异，所以转录组的测序具有一定的链特异性。在拼接转录组时，我们就可以利用DNA中链的信息，从而拼接出具有重叠区域的转录体或者是具有重叠区域的反义转录体，而对于基因组拼接的算法，我们可以不用考虑其链中的特异性，也就没有几率获得转录体与反义转录体。由以上阐述，我们可以明确到转录组的拼接为基因组拼接拉开了挑战的序幕。在逝去的几年时光内，对于这方面的知识，人们己经取得了不少的成果，且发明了许多转录组拼接算法。针对于这些转录组算法，我们可以根据它们是否需要一个参考基因组，将这些拼接算法分为如下两大类（如图1.1所示）：图1.1.基于参考基因组的转录组拼接和转录组从头拼接。第一：基于参考基因组的拼接算法；第二：从头拼接算法。首先，我们先来谈谈第一种算法，所谓的基于参考基因组的拼接算法，其步骤在于，先将需要测序的基因片段映射到基因组之上，这样不同的基因测序片段就会全部映射到基因组的不同位置，继而形成一个接着一个的测序片段簇,最终再通过一定的手段对这些测序片段簇进行拼接，这就是基于参考基因的拼接算法的大体步骤。而从头拼接算法的意义，从字面上我们已然知晓，从头拼接算法并不需要参考基因组，它是直接借助于RNA测序片段去拼接出最终我们所需的转录体，相对于参考基因的拼接算法，从头拼接算法的难度要大的多。总体而言，基于参考基因组的拼接算法要比从头拼接算法简便，不过在简便的同时，基于参考基因组拼接却有一个较为明显的缺点，此缺点就是该算法必须依赖于一个参考基因组，而且对于参考基因组的质量要求也十分苛刻，换言之，基于参考基因拼接算法需要一个十分准确的参考基因组才能真正地获得最终转录体，不过在现实生活中，不是所有的物种都具有准确的参考基因，只有极少数物种的基因组达到这种要求，而绝大多数物种的基因组都是一个未知之谜，这给基于参考基因拼接算法带来了致命的打击。除此之外，有些物种就算存在高质量的参考基因组，这些参考基因组也不见得能使用于参考基因拼接算法中。第二章 拼接算法的研究现状分析 在上节中，我们已经知道转录组的拼接与基因组的拼接有所差异，不过从算法上去研究该问题，两者之间又有着十分密切的关系。在本章节中，首先，我们先回顾基因组拼接中的常用算法。其次，再依次探究基于参考基因组的拼接算法与转录组从头拼接算法。最后，在前者的基础上，去总结并分析出当代生物学中关于转录组拼接研宄的现状与待解决的问题。 2.1基因组的拼接算法 对于基因组的拼接的概念，我们可以如此描述，从测序中所获取的短DNA序列片段出发，拼接出一个完整的基因组序列的过程就称之为基因组的拼接。在基因组拼接的问题刚刚萌芽之期，人们常常将其模型化处理，使其成为一个最短字符超串问题。而最短字符超串问题，其实质就是设定一个字符串集合为S，在集合S中找出一个最为短捷的字符串，使得集合中的字符串都是此字符串的子字符串，这便是最短字符超串问题。 以下，我们便举例说明该问题，下面是一个三个字符串和它对应的超串，如果将三个字符串中的每一个字符串都看成一个点，那么有重叠区域的两个字符串之间就会连成一条边，这样由点就可以构造出一个图。图构造出来之后，那么对于此问题，就可以将其演变成在一个图中寻找哈密尔顿路，所谓寻找哈密尔顿路，其实质是遍历图中的所有点，而且图中的每个点都只能遍历一次。在生物学上，哈密尔顿路的问题是一个及其富有挑战意味的问题，也没有一个相对而言的解法。不过，在后来人们受到物种杂交测序的影响，寻找出了一个稍微简单的解决方法，此方法就是在对物种的基因组拼接时，基因上的每一个测序片段被会被拆分成相互之间只有k-1个重叠核苷酸长度为k个的短序列，而且每一个长度为k的短序列都称为一个k-mer；下面是一个序列及其对应的一系列k-mer的例子：ATCGTCAGGATCGTCGTCGTCGTCA CAGG 依靠以上例子，我们可以将这些K-mer建立成一个deBruijn图，每一个k-mer是图中的一个点，如果两个k-mer中有k-1个核苦酸的重叠区域,就给这两个点之间连一条边。依照以上方法，我们就可以将基因组拼接问题模型化处理，就可以将哈密尔顿问题转换为在deBruijn图中寻找的欧拉路问题。而欧拉路问题，就是一条访问图中每一条边一次并且仅访问一次的路。由于哈密尔顿问题与欧拉路的建模方法有所差异，所以对于基因的拼接问题就从一个寻找哈密尔顿路问题转化为寻找欧拉路问题，这样，求解难度就在原有的基础上下降了不少。 在过去的几十年内，对于基因组拼接算法我们已经开发出诸多算法，通过总结，我们可以将这些算法分为如下三种类型：第一，贪婪方法；第二，“重叠排列共有序列”方法；第三，则为图方法，针对这三种方法，我们将在下节一一介绍。 2.1.1贪婪方法 在研究基因组拼接的初期，对于基因组拼接，学者们的处理方法都是借助贪婪方法来进行基因组拼接的，且许多拼接工具都是利用这一理论思想。 在基因组拼接中，贪婪拼接方法的基本思路主要是：在测序时，将具有重叠区域的测序序列进行一定的延长，且每一次延长，我们都要选择与当前序列的一端较长的重叠区域并且此重叠区域的相似度尽可能高的一条序列，然后再通过合并这两个重叠区域相似度极高的序列去延长当前序列，从而达到基因组拼接的效果。 以上我们简单地介绍了贪婪方法的基本思路，接下来，我们将重点介绍贪婪方法的步骤，对于贪婪方法的步骤，具体总结如下： 第一.计算出基因中测序片段的所有两两联配(alignment); 第二.在测序片段中，获得两个具有最大的重叠区域的序列； 第三.合并这两个重叠区域最大序列，使之成为一个新的序列； 第四.重复步骤二和三，直到剩下的所有序列小于某一个数值或者没有重叠区域。从步骤上看，我们已然知晓，序列的两两联配是贪婪算法的重要支持点，也是生物信息学研究的基本问题之一。2.1.2重叠-排列-共有序列的方法在测序中，重叠排列共有序列的方法是第一代测序数据的拼接中最为常用的方法，同时也是最成功的算法之一。在测序中，很多拼接工具都利用重叠排列共有序列方法，由此可见，重叠排列共有序列方法在测序中具有较高的实用性，因此，我们有必要对此方法进行一定的介绍，据总结，重叠排序共有序列方法的步骤如下：第一.计算重叠区域。在测序拼接中，首先要计算出所有测序片段两两之间的重叠区域，计算重叠区域的意义是为了构造出一个重叠图，而重叠图中的每一个点都代表着一个测序片段，当两个测序片段之间具有重叠区域时，则给他们之间连一条边。第二.图排列阶段。重叠图构造成功后，我们便在重叠图中寻找一些能够代表原始DNA序列的路。在理想情况下，在重叠图中，我们都希望获得一条相对完整的基因组序列，这样我们便可以从重叠图寻找到一个哈密尔顿路。第三.确定共有序列。所谓确定共有序列，其实质就是确定一个序列，使该确定序列包含步骤二中的每一条序列，也就是说，该共有序列是步骤二中所有序列的子序列。从效果上分析，贪婪方法的效果要次于重叠排列共有序列的方法，这也是重叠排序共有序列方法为什么能在第一代测序片段拼接中受欢迎的原因之一。虽然重叠排序共有序列具有高效性，不过与贪婪方法一样，重叠排序共有序列方法要计算测序片段两两之间的联配，而测序片段之间的联配的计算量十分浩大，故此，在第二代测序的拼接中，此方法的应用相对于第一代测序拼接要少得多。2.1.3 De Bruijn 图方法在二十一世纪初期，Pavel与Pevzner等人通过相关的研究探讨，最终提出了一个新的基因组拼接方法，这个拼接方法与贪婪方法和重叠排序共有序列方法并不相同，因为此方法并不直接利用测序序列，而只是通过一定的手段，将基因中的测序片段打碎，使之成为具有重叠区域的一系列长短序列，而打碎的短序列都具有相同的长度，且长度都为A个核苷酸，在此，我们都称之为tmer。且每一个测序片段都依次被人为打碎，从而成为相互之间都具有k-l个核苦酸的重叠A:mer。因此，我们可以利用测序数据中所包含的的A:mer,然后去构造出一个deBruijn图，在此图中，对于每一个tmer，我们都可以将其看成是一个点，而两个tmer之间如果正巧有h个核苷酸重叠区域，那么这两个tmer之间就可以连一条边。正因为两个tmer之间如果有h个核苷酸重复区域可以连一条边，那么在测序过程中，就可以避免一些测序错误，构造出来的图与直接用测序片段构造的图有异曲同工之妙。在deBrujin图中，基因组所对应的一条能通过所有边的路，在生物学上，我们都称其为欧拉路。这样，就可以将基因组的拼接问题摇身一变，使其转化为在deBrujin图上寻找到一个欧拉路的问题，而在图中寻找欧拉路，我们可以利用多项式的解法去处理该问题。在基因拼接过程中，基于图方法的设计，并不是针对于第二代测序的拼接，从实际意义上研究，deBrujin方法出现的时间要早于第二代测序，在其出现之前，此方法就己经存在了。不过，由于该算法中deBruijn图的规模与基因测序数据的规模没有一点联系，这两者之间仅仅只跟基因组的大小有关联，故此，该方法特别适用于像第二代测序技术的高通量数据拼接中，这也是为什么该方法在第二代测序的拼接中得到了广泛应用的最佳解释。重叠排序共有序列方法之所以在第一代测序中取得不菲的成绩，其主要因素在于它所构造的图的规模跟测序片段的数量多少有一定的关联性，而拥有高通量数据的第二代测序技术，也正因为其数据量相对较大，导致图的规模较，最终出现无法求解的尴尬现象。然而正因为份图这一优点，导致基因拼接过程比重叠排共有序列方法高效，所以在后来的研究中，基于第二代测序的基因组拼接算法，人们都差不多采用deBrujin这一方法。以上阐述的观点基本上适用于理想状态，而在实际的拼接过程中，我们最终所获得基因组序列并不是一条十分完整的基因组序列，受到其他因素的影响，在基因拼接中，我们所获得的序列是几条或者几十条、以至于更多条且序列与序列之间没有重叠区域的一些DNA序列。故此，要想获得完整的基因组序列，还需要借助一些方法或者手段对这些序列进行进一步加工处理，这样才能充分利用基因双端的测序信息，求解出序列的方向与序列与序列间的对应位置。除此之外，我们还可以通过一些实验去填补基因组中的缺陷，最终解决问题获得一条较为完整的基因组序列。2.2基于参考基因组的转录组拼接算法在对绝缘拼接的过程中，基于参考基因组的拼接，主要涉及如下三个步骤：第一步，RNA-seq的数据被映射到参考基因组上。在此过程中，我们利用的映射工具主要有以下几大类：其中包括TopHat , SpIiceMap，MapSplice以及GSNAP等，这些映射工具对剪接具有一定的敏感。所谓对剪接敏感，其意义主要是指能够处理含有剪接连接处的测序片段。基因中的转录体是由不同的外显子连接而成的，在拼接中，转录体中间的内含子会被剪掉，若将内含子的测序片段直接映射在基因组上，那么测序片段的前后两部分就会被映射两个不同的位置，当然普通的映射工具无法完成这一工作。将数据映射到参考基因上时，我们可以针对不同的位置，可以建立不同的图。对于每一个图，只要遍历图中的路，我们就可以获取基因中的所有转录体。参考基因组的算法的步骤一为：进行序列映射；序列映射是将测序所获的序列重新定位在基因组上。把测序片段定位在基因组上后，来自不同基因的测序片段就会被映射到基因组的不同位置，形成一个个测序片段簇。转录组的拼接问题就转化为单独的转录体拼接问题。对于每一个图，只要遍历图中的路，就可以找到最终的转录体。比较有代表性的参考基因组的拼接算法是Cufflinks和Scripture。Cufflinks算法对映射到每一个基因位置的测序片段上定义了兼容关系。利用这种兼容关系，我们可以建立一个重叠图（over lap graph)，在重叠图上，每一个测序片段可以看作图中的点，如果两个测序片段兼容，我们就给他们连一条边。重叠图中的路表示基因的各个转录体。在Cufflinks算法中，人们应用了一个最小路模型在图中寻找对应转录体的路。Scripture算法的主要思路为：构造一个有向图连通性图（connectivity graph)，构图思路是将基因组中的每一个碱基看成一个点，在两个碱基之间加一条边，继而构成图。从构造的图中，寻找到所有超过某一个阈值的测序深度的路，作为最后的转录体集合。据总结，参考基因组的方法主要有以下几个优点：一，通过映射，可以将一个大的拼接问题分解成多个小的拼接问题。每一个小的拼接问题之间相互独立，从而提高了计算效率。二，对于表达量比较低的转录体，具有一定的敏感性，对于检测较低的未翻译区，基于参考基因组的拼接算法具有十分重要的意义。三，由于基因组是已知的，转录体间的小的空白区域可以依靠基因组序列填充。这样，转录体中，没有被测序片段也有可能被正确拼接。以上是基于参考基因组的拼接算法的优点，对于其缺点总结如下：第一，要依靠参考基因组。且拼接成果取决于的参考基因组的质量。因为生物界中，大部分生物基因组都不是很完善，寻找已知基因组十分困难。第二，拼接成果与序列片段映射过程息息相关，在映射过程中，许多映射不到的基因组序列会被丢弃，从而造成信息丢失，这样拼接成果会大打折扣。由以上言论中，我们已经简便地知道基于参考基因组的拼接算法的优点与缺点，故此，在实际情况中，一定要结合实际，才能使结果更加趋于完善。2.3基因组从头拼接算法不利用参考基因组，仅仅从测序所得的片段出发，通过一定的方法最终将转录组的全部的转录体序列拼接出来的方法，称之为基因组从头拼接算法。基于基因组的拼接算法，对于低等的真核生物的转录体拼接而言，异常简便，不过对于真核生物的转录组拼接，效果却不太如意。因此，在对转录组拼接时，我们结合实际，分析转录组的特点，这样才能得到最佳的成果。在诸多基因组从头拼接算法中，Trinit算法是第一个专门针对转录组设计的拼接算法，同时也是老鼠们公认的最好的转录组从头拼接算法。其算法思想是依靠测序片段构造出一个长序列，然后在根据构造出的长序列构造出连通分支，针对长序列构造的连通分支，都能构造出一个图，然后利用穷举的方法寻找到路。Trinit算法的具体步骤是：第一步.利用贪婪策略拼接出长序列。在该步骤中，首先要构建出一个哈希表，然后在表中记录下所有的测序数据以及出现hmer出现的次数。第二步，依靠第一步的相关数据，从而建立出deBruijn转录体图。在第一步中，长序列并并不能直接反映出转录组的复杂性，不过他保持着一个完整图的全部信息。因此，我们可以通过一些方法，去建造出一些图，构图思路为，将所有的长序列聚类成不同种类的连通分支，使连通分支内的长序列之间至少存在一个核昔酸的重叠区域；其次，为每一个连通分支建立图；最终，将测序片段全部映射图中。第三步，从构造的图中，寻找到相关的转录体的路。对于寻找转录体的路，我们可以按照如下方法：合并deBruijn图中连续且不分叉的ytmer，使其形成一个更长的序列。除去由测序错误导致的小分叉边，使图得到简化。图得到简化之后，我们可以通过一些动态规划过程与遍历图中路的方法去确定被测序片段支持的转录体。然后再运用测序片段自身的一些信息与双端测序的相关信息，将图中路的组合数降低，继而一一列举。就目前而言，所有的从头拼接算法都是基于deBruijn图，因此ytmer的长度十分重要。一般来讲，对于ytmer的长度，大的A值在高表达的数据或者序列长度较长的数据上表现较好。而小的A值与其相反，它只是在低表达的数据或者序列长度较短的数据上表现较好。基于这一特点，老鼠们经常使用许多不同的值对转录体进行拼接，最后再将这些不同的拼接结果逐一合并，这样才能得到更加完美的拼接效果。用这种方法拼接转录组的软件大致包括Rnnotator、Multiple-A：、TransABySS与Oases_M。虽然这种策略能得到较高的敏感性，不过却引进更多的假阳性转录体，故此，该策略并不是一个较为理想的策略。在Trinity的算法中，我们可以根据不同的转录组数据与基因组数据，在拼接过程中，老鼠们地使用很多具有转录组数据的拼接技巧，这样，才能使拼接效果有了突破性的进展。虽然Trinity算法的拼接效果十分明显，不过它仍然存在着很多缺点与不足之处，这需要我们在今后的学习中，逐步总结。2.4转录组从头拼接算法的改进在本节中，针对于不同的RNA测序数据，我们选用了目前效果最佳的两个算法，Trinity算法与Oases算法，然后利用模拟数据的方法对其进行系统化分析。从分析的结果中，我们不难发现，对于简单转录组的拼接，这些算法的表现还可以，不过对于相对来说，较为复杂的转录组的拼接，该算法的效果却不是十分明显以至于很差。对于Trinity算法与Oases算法，我们可以通过老鼠与乳酸菌的数据表现去探究。从结果上看，老鼠的数据是依靠工具BEERS生成，它含有40,000,00个双端测序的测序片段，而每一个测序片段的长度为75bp，而插入长度为200bp。在获得老鼠的相关数据之后，我们又利用Perl程序使之生成乳酸菌的RNA测序数据。在测试中，要保持乳酸菌的数据的可比性，数据量以及测序片段长度和插入长度与老鼠的数据量、测序片段长度一致。如果一个拼接出来的转录体能够完全覆盖一个参考转录体，并且插入删除不超过序列长度的1%，我们就认为这个参考转录体被完整拼接了出来。如果拼接出来的转录体的50%以上的序列不能映射到任何参考转录体上，就将其确定为一个错误的拼接，或者将其定位为一个假阳性的转录体。然而，对于拼接的质量，在生物学上，并没有一个固定的标准，因此我们可以采取以下两个度量去衡量拼接的质量，这两个词为敏感性与假阳性。Trinity和Oases在老鼠和乳酸菌上的拼接的结果如图2.1所示。从图中可以看出，虽然Trinity和Oases的表现有差异，但是结果一致表明，当前的拼接算法对于乳酸菌的拼接，敏感性很高，假阳性很低，效果比较好，对于老鼠的转录组的拼接，表现却差了好多，不仅敏感性低，而且假阳性也比较高。图2.1. Trinity和Oases在老鼠和乳酸菌上的拼接的结果Trinity和Oases在五份数据的拼接结果如图2.2所示，随着转录组的复杂性的增加，拼接的敏感性迅速下降（图2.2a)，假阳性也不断上升（图2.2b)，进一步表明当前的拼接算法在处理复杂的转录组时表现很差。因此，非常有必要去进一步提高转录组的从头拼接算法。图2.2：测序数据的拼接结果当转录组中的基因的剪接情况比较复杂时，拼接出来的图就相应的比较复杂，从这个图中去找对应转录体的路就变得很困难，所以，拼接的效果就变得往往很差了。因此，要想提高拼接的效果，必须在从图中寻找对应转录体的路这一步下功夫，建立一个更好的模型，充分利用各种信息，从而找到一个更好的路的集合。我们应该提出的算法Bridget，我们舍弃了Trinity中利用的穷举算法，引入了一个经典的组合优化模型一一最小路覆盖模型，来找一个尽可能小的路的集合，来解释当前观察到的所有测序片段。仅仅这样还不能保证解的唯一性，我们又通过加权，通过优化来得到一组更好的解，加权后的模型在实际中几乎可以保证得到唯一解。目前，老鼠们普遍将提高转录组从头拼接的质量寄希望于测序片段长度的增加。Mark Chaisson等人在研宄测序片段长度对于基因组的拼接的影响时，曾经给出过一个惊老鼠的结论：对于双端测序来说，测序片段的长度较短时，增加片段长度对拼接是很有用的，但是测序片段一旦超过某个阈值，增加测序片段的长度对拼接的结果影响不大。这个结论并不能不假思索地推广到转录组的拼接，毕竟转录组的拼接跟基因组的拼接有很大不同，那么对于转录组的拼接，是不是也有类似的结论呢？为了弄清楚这个问题，我们通过模拟数据进行了深入研宄。首先，我们模拟了三个不同物种的RNA测序数据，老鼠，老鼠和乳酸菌。对于每一个物种，我们又分别生成了多份不同长度的数据。对于老鼠和老鼠，我们用一个模拟器BEERS分别生成了六份长度不同的RNA双端测序数据，序列长度分别为50bp, 75bp，lOObp, 150bp,175bp和200bp。每一份数据的中间插入的长度都为200bp，测序片段的数据量都是五千万左右，以保证有足够的测序深度。对于乳酸菌，我们利用一个Perl脚本生成了测序长度为35bp, 50bp, 75bp, lOObp和150bp的五份双端测序数据。对于每一份测序数据，中间插入的长度都是200bp，测序片段的数据量也都是五千万左右。图2.3：老鼠RNA数据上的拼接结果比较我们选用两个当前比较流行的拼接算法Trinity和Oases进行拼接，以防止因为某一个拼接算法自身的特点而导致错误的结论。对于拼接的结果，我们分别从敏感性和假阳性两个角度进行评价。虽然Trinity比Oases的拼接效果要好，但是随着测序长度的变化，二者的拼接效果的变化趋势是一致的。在老鼠的RNA测序数据上（图2.3)，当测序片段长度从50bp增加到150bp时，两个算法的敏感性上升很快，敏感性也迅速下降，表明拼接的结果不断提高，但是当测序片段的长度超过150bp时，测序片段长度的继续增加对两个算法的拼接结果的影响微乎其微，具体表现为：敏感性的提高不到1%，假阳性几乎不再下降。在老鼠的测序数据上，也观察到了几乎一模一样的结果（图2.4)。图2.4：乳酸菌RNA数据上的拼接结果比较在乳酸菌的数据上，拼接的结果也是随着测序片段长度的增加表现出先有所提高后几乎没有什么变化的规律。不过有意思的是，在乳酸菌的数据上，测序片段的长度增加到75bp时，拼接的效果就基本达到了最优值，之后测序片段长度继续增加，对拼接几乎不再有任何影响。可见，对于转录组双端测序的片段长度，也存在一个阈值（这个阈值对不同的物种是不同的），在这个阈值之下，测序片段的长度的增加对提高从头拼接的结果有一定的影响，但是，一旦超过了这个阈值，测序片段长度的增加对拼接结果就不