当今的生物技术快速发展,生物学大数据每天以爆炸式的速度增长,这无疑给生物学研究和发展带来前所未有的机遇,然而传统的生物学分析方法已经无法处理如此庞大的数据。生物信息学,作为一门新兴的交叉学科应运而生,它将数学,计算机科学,统计学等结合起来研究和解决大数据下的生物学问题。其中一个非常基础,重要而又极具挑战性的问题就是序列拼接问题,转录组拼接就是其典型代表。转录组拼接就是利用RNA-seq等测序技术产生的海量测序片段拼接出实验组织中所有的表达转录本,并估计出其表达量。本文的研究主要集中在如何利用组合优化方法来解决转录组拼接问题,这对于新物种研究,以及与异常转录相关的人类复杂疾病研究等相关问题意义重大。第二代RNA-seq测序技术的快发展和广泛应用给转录组拼接工作带来无限机遇的同时,也伴随着在计算上前所未有的挑战。目前的拼接算法根据计算策略可大致分为两类:1)基于参考基因组的转录组拼接算法;2)从头转录组拼接算法。当有高质量的参考基因组存在时,可先将测序片段回贴到参考基因组上,之后,根据回贴的结果对每个基因分别进行转录组拼接。在参考基因组不存在,不完整,严重片段化或是在癌组织中大量突变等,从头转录组拼接就成为了非常重要的且是唯一的选择。从头拼接策略不需要依赖任何参考信息,直接从测序片段本身出发,重构出最终的表达转录体序列。无论是转录组拼接的何种策略,目前的算法在计算精度和计算效率上都存在明显的缺陷和严重的不足,导致其实际应用效果非常差。因此,两种策略都亟待开发出全新的,高质量的拼接算法,以准确重构出真核生物组织中的全长转录组。基于上述的考虑,本文设计全新的基于参考基因组的转录组拼接算法TransComb,这个算法给转录组拼接提出了全新的设计思路,极大的弥补了当前算法存在的严重缺陷。经过在模拟数据和多组真实数据上的测试,结果充分地表明,无论在模拟数据还是真实数据上,本文开发的拼接算法与其他主流拼接算法比较都展示出明显的优势:不仅具有更高的灵敏度,而且具有更高的准确度,对其他算法普遍存在的假阳性高的难题得到了极大程度的解决。而且,在计算资源消耗方面,TransComb使用的CPU时间明显更短且运行内存更低。经过综合的测试表明,TransComb无论是在计算精度上还是在计算效率上都显著超过其他拼接算法。本文的新算法TransComb具有以下几个明显的的创新点:1)新的技术构造出更加准确的剪接图。本文设计出使用双端测序信息来修复片段化的外显子的技术,以及为修复错误连接的外显子而设计出的窗口滑动技术。2)梳图模型和双端测序信息解决转录组拼接的核心难题。转录组拼接的核心难题就是外显子两侧进出边连接的不确定性,这也是目前几乎所有的拼接软件共存的一大漏洞。本文开发的梳图模型将测序覆盖度信息和双端测序信息合理的整合在一起,巧妙的解决了拼接的核心难题。3)全新的图模型:加权节点图。打破基于RNA-seq的转录组拼接算法依赖传统重叠图和剪接图的现状,我们的算法是在加权节点图的基础上完成拼接,节点图中包含了更多有效信息,因而克服了现有算法的若干缺陷。4)基于节点图设计的新的路的延伸策略。该策略在延伸过程中每一步都有节点图上边的权重作为依据,使得每一条延伸出的路都以很大概率代表一个表达的转录体,无论该转录体是高表达还是低表达。尽管TransComb在拼接方面表现出了明显的优势,但是其仍然存在不足之处。比如:1)TransComb在设计过程中没有实现并行化,因此,在程序设计方面还有待进一步提升。2)表达量估计算法设计没有将测序偏好等信息考虑进去,因此,在某些数据上的表达量估计中TransComb与其他主流算法效果接近,没有表现出明显的优势,这个过程还有待于进一步提高。最后,本文还将简要介绍我们开发的另一个转录组拼接算法BinPacker,该算法是不依赖参考信息的从头拼接算法。BinPacker把转录组拼接问题重新模型化为追踪一系列物品的轨迹模型,每个物品代表一种转录体,物品的尺寸表示该转录体的覆盖度。这个方法能够巧妙地将覆盖度信息合理的利用在拼接过程中,另外,BinPacker具备如下两个独有的特征:1)只有剪接图中的可变剪接事件作为拼接过程的考虑对象;2)拼接大量杂乱无章的测序片段的过程被形象的模型化为梳理剪接图中的边的过程。最后,我们同时在模拟数据和真实数据上测试BinPacker,测试结果显示,BinPacker在各种数据类型下均明显超过几乎所有现存的从头拼接软件,包括最主流的软件Trinity,在某些数据下,BinPacker的表现甚至超过了基于参考基因组的拼接算法,如StringTie。而且,相比于其他的拼接软件,BinPacker消耗更少的运行时间和更低的内存。TransComb和BinPacker已经用C++语言实现成一个开源的软件,两个软件可以通过以下网址下载:http://sourceforge.net/projects/transcriptomeassembly/files/