随着生命科学和相关测序技术的蓬勃发展,生物数据呈指数增长之势。生物学的进步也越来越依赖于相关数据的收集、储存、检索、分析与挖掘。一个新兴的交叉学科--生物信息学应运而生,并迅速成为当今自然科学的前沿与核心领域之一。生物信息学从数据入手,以数学、计算机科学、统计学和控制学等为手段,深度挖掘生物数据中所蕴含的各类信息,以揭示生命的奥秘。转录组学属于生物信息学的关键分支,是在RNA水平上探究细胞中基因转录情况的学科,旨在了解信使RNA剪接程度以及非编码RNA和增强子RNA对基因表达的调控作用等一系列科学问题。转录组组装算法是转录组学开展后续分析的前提,为转录组调控规律、基因差异分析、共表达分析、富集分析等下游研究提供支持,起到了基础性的铺垫作用。目前主要的转录组组装算法通常可分为两种策略:从头组装（de novo）和基于参考基因组序列的组装（genome guide）。近几年,研究人员开发出大量的组装算法,极大地促进了转录组学的发展。但我们通过测试发现,目前的算法仍有很大的局限性,主流算法的召回率与准确率仍然较低。随着测序技术的进步,各种序列比对以及组装算法的不断开发,我们可利用的数据信息也越来越多。充分融合已知信息并开发准确高效的转录组组装算法依然是十分有意义且充满挑战的研究课题,这也是本论文的主要研究工作。目前,转录组组装时面临的具体问题主要有:1)如何更充分地利用已知的信息构造更加精确的可以代表基因表达的剪接图;2)如何更准确地解决外显子两端可变剪接事件连接的不确定性这一核心问题。此外,几乎所有转录组学研究都涉及多个样本的RNA测序。为了下游的量化以及差异表达分析,往往需要对于多样本的RNA测序数据创建一个一致的转录本集合,即基于多样本RNA-seq数据的转录本重构问题。对于多样本的转录组组装,如何将多个样本的信息融合到同一个剪接图中同时又能体现出每个独立样本的特有信息,也是一个迫切需要解决的问题。针对以上问题,本论文充分研究了现有算法的缺陷,并深入剖析了目前可以利用的有效信息,利用图论、组合优化等相关知识,从1)融合不同序列比对工具的回帖结果并引入标签剪接图模型,2)整合多个不同样本信息并引入向量加权剪接图模型,这两个不同角度分别设计了转录组重构的组装算法Tiglon和TransMeta。这两个算法均提出了全新的图模型,并分别设计了不同的组装算法,能有效地解决重构全长转录本的难题,一定程度上克服了现有算法的不足与缺陷。相关研究基于第二代测序技术（高通量测序技术）开展,成果主要包括:1.Tiglon算法:基于参考基因组的组装策略,其第一步就是RNA-Seq测序数据的回帖,而回帖需要借助序列比对工具,单一序列比对工具由于其不同的设计方法有着很强的数据偏好性。我们研究发现,基于单一的序列回帖工具往往无法捕捉到一个基因里所有的可变剪接事件,这直接影响到后续的拼接结果。针对上述问题,为了充分利用不同的序列回帖工具产生的回帖信息,我们开发了基于序列比对工具融合的Tiglon算法,主要创新之处在于:1)首次提出融合多个序列比对工具的结果作为输入,这样可以减弱单个工具的数据偏好性,使得输入信息更为准确。2)首次提出了一个新的图模型,称为标签剪接图（Labeled Splicing Graph）。标签剪接图在每条边的权重上都加入一个标签,通过这些标签可以明确知道支持该边的读段具体可以被几个序列比对工具识别,有效区分信息来源,以便捕获到更多正确的剪接位点。3)设计了基于标签的动态路径搜索算法,利用标签剪接图所特有的标签权重进行分析,根据读段被多少个序列比对工具所识别等信息计算可信度,并以此为依据有选择地在图上进行延伸,寻找代表转录本的路径。本文在一组模拟数据集和50组真实数据集上,从正确重构的转录本数量、准确率、F-Score等多个维度评估了 Tiglon与其他常用工具的性能（其中包括StringTie2和Scallop在内的目前世界上最先进的转录组组装算法）。结果表明,Tiglon提出的针对不同序列比对工具的融合策略在性能上比其他组装工具均有着很大的提高。尤其是,Tiglon在重构低表达转录本方面有着显著的提升（这是转录组组装中比较困难的问题,也是考察算法是否优秀的重要指标之一）。2.TransMeta算法:针对多样本转录组组装问题,本文开发了基于多样本数据融合的TransMeta算法,其主要创新之处包括:1)首次提出了矢量加权剪接图（Vector Weighted Splicing Graph,简称VWSG）的概念,这与之前算法常用的赋权方法大有不同。VWSG使用矢量对剪接中的边和节点加权,矢量第k位的元素是在样本k中对应的权重。这样可以将每个样本的测序信息完整保留,同时避免了信息缺失,达到求同存异的效果。2)首次利用余弦相似度去梳理加权边或节点间的关系,利用相临边矢量权的夹角而非范数大小去计算相似度以解决外显子两端的可变剪接事件连接不确定性这一核心问题。即只关注同一读段在不同样本中信息的相似性,这样做更符合多样本数据的特性,有利于更准确得进行路径延伸。3)利用新设计的依据标签的路径搜索算法来重构转录组。TransMeta会通过一个转录本选择算法来生成全样本转录组,并基于此修正单个样本的数据错误,针对每个样本输出特定的转录本集合。本文分别选取了包含了 25个样本的模拟数据,包含不同样本数量的5组人类大样本RNA-Seq数据集（其中包括189个样本数据）以及两组小样本数据集（其中包括9个样本数据集）,从召回率、准确率、准确率--召回率曲线、F-Score等多个评价标准对TransMeta进行了大量的测试,并与目前最出色的工具作了对比。在多样本组装水平上,TransMeta在多个覆盖度阈值下实现了最佳的准确率-召回率曲线,超过了包括PsiCLASS在内的目前最好的多样本组装算法。同时,TransMeta在单个样本组装水平上也一致地取得了最优的结果。Tiglon与TransMeta均通过C++语言实现且为开源软件,下载地址分别为:Tiglon:https://github.com/yutingsdu/Tiglon-v.1.1.gitTransMeta:https://sourceforee.net/proiects/transassembly/files/TransMeta/