序列拼接,是指将测序生成的读段拼接在一起,恢复出测序前的序列。序列拼接问题是非常基础又极具挑战的生命科学问题之一,其结果的好坏直接影响后续功能分析等一系列研究的成败。高通量测序技术的迅猛发展为序列拼接工作带来无限机遇的同时,也令其在计算上遇到前所未有的挑战。高通量测序技术每次可以产生海量的读段,这些读段的长度通常远远短于原始序列。如何利用这些海量的读段恢复出原始的序列是序列拼接问题的研究核心。多外显子的基因在转录时大多存在可变剪接现象,而异常可变剪接是导致癌症等疾病的重要因素。组装和分析转录组是研究疾病和转录组学的重要手段。转录组是转录后的所有mRNA的总称。RNA高通量测序技术能够对这些mRNA序列进行测序,产生大量的读段,少则百万,多则数以亿计。理论上,通过这些读段可以拼接出所有的被测转录本,并准确地估计出它们的表达量。然而受测序错误、可变剪接事件、同源基因事件以及转录本的差异表达等因素的影响,现有的转录组组装算法的准确度远远无法满足实际需求,即使在相对简单的模拟数据上,其表现也不尽人意。因此,研究基于高通量测序数据的转录组拼接问题并设计出行之有效的算法,一直是计算生物学和生物信息学研究领域的难点与热点。研究表明,很多病毒如埃博拉病毒、塞卡病毒、艾滋病病毒、新冠病毒等存在多种菌株。这些菌株通常具有不同的毒性、耐药性以及发病机理等。这说明具体到菌株水平的病毒研究至关重要。其中,病毒菌株拼接是一个具有重要生物学意义并且极具挑战的问题。所谓病毒菌株拼接问题,是指在已知某种病毒的某些菌株的测序数据的情况下,拼接出该数据中所包含的所有菌株的具体序列。对于转录组拼接问题,本文设计了 IsoTree以及DTA-SiST等从头组装算法,提出了一套通用的转录本序列提取策略MultiTrans,并给出了一种用于转录本表达水平估计的方法PSOISO。对于病毒菌株拼接问题,本文提出了一种全新的从头拼接策略LG-Strain。本文的主要内容和创新点如下:1.现有的转录组从头组装算法通常由两个主要步骤组成,一是利用读段构图,二是在图中提取能够表示转录本的路径。在利用读段进行构图的过程中,大多数算法将读段分割为多个长度为k的短序列（k-mer）,然后利用这些短序列间的重叠信息进行构图。本文称上述构图法为k-mer构图法。k-mer构图法只能保证k-1长度的重叠信息,忽略了读段间更长的重叠信息。本文认为两个读段重叠的越长,它们来自同一种转录本的可能性越大。为充分利用读段间的重叠信息,本文提出了基于读段的剪接图构造法。该方法首先选择一个未使用过的最厚的读段为种子序列,然后不断地选择一个与当前种子序列重叠最长的读段对其进行扩展与延伸,最终形成一个连通分支。本文称该连通分支为剪接图。随后,本文根据可变剪接事件类型,对剪接图进行修正与完善。为提取剪接图中的转录本路径,本文提出了同源异构树（Isoform Tree）模型。根据剪接图中的顶点与边的厚度等信息,本文将每个剪接图转化为一棵同源异构树。在同源异构树中,每条由根节点出发到叶子节点的路径代表一条候选转录本,叶子节点的权重表示该候选转录本的表达值。本文称上述转录组从头组装算法为IsoTree。实验结果表明,IsoTree在模拟数据和真实数据上都有较好的表现。不足的是,IsoTree在构造剪接图的过程中,所花费的时间较长。2.为解决IsoTree构图耗时长的问题,本文提出了一套基于后缀树的转录组从头组装策略DTA-SiST。该策略改进了 IsoTree的剪接图构造方法,提出了基于后缀树的序列扩展方法。该方法能够在线性时间O（L）内找到与当前序列末端（或首端）重叠最长的读段,其中L表示读段的长度。该方法构造的后缀树所占用的空间为O（N’（L-l））,其中N’≤N,N为读段数量,l为最小重叠长度。在转录本路径提取方面,考虑到越厚的长路径越有可能是转录本路径,本文提出了一个时间复杂度为O（（V+E）E）的基于动态规划的最厚最长路径提取算法。其中,V与E分别表示剪接图中的顶点个数与边的条数。此外,为了涵盖尽量多的转录本路径,本文提出了一个时间复杂度为O（V+E）P)的基于深度优先的s～t路径穷举算法。其中,P表示剪接图中初始顶点为s的路径条数。实验结果表明,这两个路径提取策略各有优势。3.本文提出了一套通用的基于混合整数线性规划的转录本序列提取算法,并将该算法应用到目前最流行的图模型（剪接图与装配图）。根据已有的经验,本文综合考虑图的结构、双末端读段、测序深度以及路径条数等信息,将转录本提取问题建模为如下路径提取问题:求取一个能够覆盖图中所有的顶点与边的路径集合,要求属于同一条双末端读段的顶点至少同时被一条路径覆盖。此外,通过每个顶点的路径流量总和需要与该顶点的厚度尽量一致。本文要求在满足上述条件下所选取的路径集合尽量小。针对这个优化问题,本文设计了一套基于混合整数线性规划的路径提取策略MultiTrans。由于综合考虑了图的结构、双末端读段以及测序深度等信息,MultiTrans能够充分提取出剪接图（或装配图）中的转录本序列。另外,在路径尽量少的目标的作用下,MultiTrans具有较高的精度。本文分别在模拟数据以及人类、老鼠、大米的真实数据上对MultiTrans进行了测试。实验结果与预期一致,MultiTrans能够以较高的精度重构出较多的转录本序列。4.现有的病毒菌株从头拼接算法大多沿用了转录组从头拼接的思想,以致最后得到的候选序列的长度差异较大。这与同一病毒的不同菌株序列具有相似长度这一特点不符。基于此,本文综合考虑病毒菌株之间的差异特点,设计了一个专门针对病毒菌株拼接的图模型,称为Level图。本文首先利用读段构造一条主干作为参考,然后将读段回贴到主干,并计算单位点突变（Single Nucleotide Variant,SNV）。随后,本文从主干的最左端开始,不断地移动一个动态大小的窗口,并计算该窗口内能够被读段支持的SNV组合类型。本文将窗口内每种SNV组合视为一个顶点,并将属于同一个窗口的顶点添加到Level图的同一层中。此时,每条病毒菌株序列都可以表示为Level图上的一条长度为LG的路径,其中LG表示Level图的层数。为降低Level图的复杂度,本文利用双末端测序信息对Level图进行局部分解,并将Level图的局部分解问题建模为一个优化问题,并利用混合整数线性规划对其进行求解。然后,本文从顶点数量最多的一层出发,不断地合并相邻层的顶点,直至只剩下一层顶点。本文认为,最后一层中的每个顶点对应一条候选菌株序列。最后,本文把读段再次比对到这些候选序列上,并根据比对结果对候选序列进行更新。本文称上述病毒菌株从头拼接策略为LG-Strain。本文分别在塞卡病毒、艾滋病毒、脊髓灰质炎病毒以及丙肝病毒的数据上对LG-Strain进行了测试。结果表明,LG-Strain构造的主干是高度可信的,它所构造的主干有时甚至就是一条完整的菌株序列。在重构菌株序列方面,LG-Strain也有不错的表现,它拼接出的候选序列的长度的分布更接近真实菌株序列的长度分布。5.虽然很多转录组组装算法在重构转录本序列的过程中,会计算每条转录本的表达值,但是其准确性往往不是很高。学者们通常将转录本的表达水平估计作为一个单独的问题展开研究。针对转录本表达水平估计问题,本文提出了PSOISO。其主要思想是:首先对读段来自于某个外显子独立区域的概率进行分析与计算,随后为每条转录本的表达值赋一个初始值,并不断地对其进行优化,使由该表达值估计出的比对到每个外显子独立区域的读段数量与真实数量尽量一致。本文分别尝试将转录本的表达值初始化为随机值以及组装算法计算得到的表达值。结果表明,在随机化初始值的情况下,PSOISO的准确度要高于一些组装算法。在以Cufflinks、StringTie、Tigar2与rSeq等组装算法计算得到的表达值为初始值时,PSOISO能够有效地提高这些算法在计算转录本的表达值方面的准确性。