生物信息学是一门新兴的交叉学科,它利用数学、信息学、统计学和计算机科学的方法来研究和解决生物学的问题。当前生物信息学所研究的问题主要集中在分子生物学领域,其中一个非常重要而又极具挑战性的问题就是转录组的从头拼接,即利用转录组的测序片段来拼接出整个转录组中的所有表达的转录体。本文主要研究如何利用经典的组合优化模型来解决复杂真核生物转录组的从头拼接问题,这对于研究包括癌症在内的许多与可变剪接相关的人类疾病,具有十分重要的意义。随着第二代测序技术的发展,特别是RNA测序(RNA-seq)的出现,给转录组的拼接在计算上提出了前所未有的挑战。目前的转录组的拼接算法主要分为两大类,一类是基于参考基因组的拼接方法,一类是从头拼接方法。尽管基于参考基因组的方法比从头拼接方法表现要好,但是它的一个致命的缺点是必须要有一个高质量的参考基因组。而事实上,绝大多数生物根本不存在一个已知的基因组可供参考,在这种情况下,从头拼接算法就显得尤为重要。转录组的从头拼接比基于参考基因组的拼接在计算上更具有挑战性,尽管目前已经有了一些算法,但是效果并不理想。本文在分析当前拼接算法的基础上,提出了一个全新的转录组从头拼接算法(命名为Bridger),巧妙地利用基于参考基因组算法的一些技巧来弥补目前从头拼接算法的不足。在狗、人和老鼠的RNA测序数据上的测试结果一致表明,Bridger比当前所有的从头拼接算法都要好。Bridger拼接出了更多的全长的转录体,而给出的候选转录体的数目却很少,暗示着Bridger不仅提高了从头拼接算法的敏感性,也大大降低了预测结果中的假阳性。另外,在时间和内存的使用方面,Bridger也比绝大多数从头拼接算法要少很多。更有意思的是,Bridger在敏感性和准确性上甚至可以跟当前最好的基于参考基因组的算法Cufflinks相媲美。本文的新算法Bridger主要有以下几个创新点：(1)放弃了通常使用的deBruijn图,由RNA的测序片段来直接构建一个能更好地反映出每一个基因可变剪接结构的图——剪接图。(2)构造图的过程中利用双端测序的信息,不仅使得到的剪接图更加准确、完整,而且有效地控制了图的规模,从而降低了在图中寻找对应转录体的路的难度。(3)通过引进一个辅助图——兼容图,成功地将一个经典的组合优化模型——最小路覆盖模型——应用到转录组的从头拼接中,相比于以前的穷举方法,可以大大降低结果的假阳性。(4)通过给模型加权,巧妙地将测序的深度信息整合到模型中,大大提高了拼接的准确性,据我们所知,这是测序的深度信息第一次被成功地用在从头拼接算法中。尽管Bridger算法有很多优点,但是也存在不足。第一,当前的Bridger的代码实现还有待进一步优化,在构造剪接图的过程中实现并行化计算是我们的一个努力方向。第二,算法中的最小路覆盖模型,并不是对于任何情况都非常有效,有些比较特殊例子,该模型也表现不太理想,这时可以通过一些技巧来克服算法的不足。本文通过两个例子展示了Bridger在实际应用中重要价值。一个例子是利用Bridger对肺癌病人的RNA测序数据进行分析,发现了与致癌基因相关的可变剪接转录体以及它们在不同样本中的表达差异。另一个例子是利用Bridger分析狗的RNA测序数据,发现了很多当前基因组中尚未注释的新的转录体。最后,本文还介绍了转录组拼接下游的一些研究工作以及我们今后的几个研究方向。Bridger已经用C++语言实现成一个开源的软件,可以通过以下网址下载：https://sourceforge.net/projects/rnaseqassembly/files/?source=navbar