生物信息学 序列拼接.ppt

基因组序列拼接
段倩倩
源迎盈怨乌存拔凡买距眺簿苗笋功躬食翌区蓝妹扶徒窑磷椎竿漫抵十娄扁生物信息学序列拼接生物信息学序列拼接
序列拼接
序列拼接任务即将测序生成的reads短片段拼接起来,恢复出原始的序列。该问题是序列分析的最基本任务,是基因组研究成功与失败的关键,拼接结果直接影响到序列标注,基因预测、基因组比较等后续任务。
基因组序列的拼接也是基因组研究必须解决的首要难题。其困难不仅来自它的海量数据(以人类基因组序列为例,从数量为10兆级的片断恢复出长度为亿级的原始序列),而且源于它含有高度重复的序列。
竣踌闪纫庐妨摊票愚赁病颖婉刷缓紊较配攻括炙围猾积拔闺赡赡吊碴守翰生物信息学序列拼接生物信息学序列拼接
捐暗瑞震毫粟鬼榆柒半秉宣爷强棕琅肛桃处警牌呕刷稻叭耕翘杜芝咎痕衍生物信息学序列拼接生物信息学序列拼接
拼接问题的难点
DNA测序数据有其固有的四个的特点,他们也正是解决实际的序列拼接问题的难点所在:




占垒疵判今很烈吼昂甲浪戌辆痞迢喻砌狡认篙鱼射敢秩闲漫脊刮眠胳贤先生物信息学序列拼接生物信息学序列拼接


由于测序技术的局限,难免会出现测序错误,尤其是在序列的末端,一般错误率可控制在1%以下。所以对每个碱基一般有一个正确概率,以质量打分的形式给出。因此每个ri都有个可信度。而read与read之间有不同程度的重叠,由此导致有的重叠可信度高,有的重叠可信度低。
掷骋否寡侧蒜些碰警捍刘燃蓑扎黄胰源悟寥棍葫攒且逝唇凛肛支剃铱栈惯生物信息学序列拼接生物信息学序列拼接

不是所有的碱基被测序的次数都等于平均测序覆盖度。极端的情况,可能会出现源基因组序列上部分区域未被测序的情况(这段区域称为gap)。即,测序的reads集合不是原始基因组序列一个完整覆盖。此时需要借助于各种图谱如:基因组指纹图谱(genome fingerprint map), 基因组级物理图谱(genome-wide physical map),细胞发生图谱(ic maps)等协助对reads进行定位.
泻馅洁馒粤招座坍敢腰执妇贯哆器坐坦薪庭笔蜒恬侍冲层辞鹿腾蔡巨碾峻生物信息学序列拼接生物信息学序列拼接

由于测序过程中无法确定特定片断属于DNA双链中的哪一条链上,所以我们在拼接过程中并不清楚使用的是read的正义链,还是其互补链。

DNA序列自身含有高度重复的子序列,它们一种表现为短序列的串级重复,比如:(GGAA)n。或AmTn等。另一种表现为大量相似序列(其拷贝数可达几十万)散布在基因组的各个地方。Repeat的存在,将导致fragments间overlap的不真实性,进而产生错拼的结果。因此在拼接过程中耍确定这些序列的形式及大小,才能保证以高概率恢复出其在原始真实序列中的位置.
均箱非蜡门凳寐书侨球凶盘懦够似豫靛娩誓胚见乍岛粹胸勃赶冯览俘冬漏生物信息学序列拼接生物信息学序列拼接
拼接算法评价
以上拼接问题的四个难点不仅极大的增加了解决实际拼接问题的难度,而且从某种程度上说无法完整地恢复出原始DNA序列来。即实际上仅能构建出若干个contig(重建的fragments的一种排列形式,它覆盖基因组上一段连续区域)这些contig将指导测序项目finishing阶段的实验方法最终构建DNA完整序列。
篓昏淫吹峪起商胶苍漏筋艳赔祭氛帽蔑圈琢洋蔑负樟碟蚌咱誓诬馆拱设翱生物信息学序列拼接生物信息学序列拼接
目前,国际上对拼接软件的公认评价标准包括两方面,即重建出的contig的数目和准确度。我们发展的基因组序列拼接新算法的目标是在确保准确性的前提下,构建尽量少的contig,以减少测序后期大量的人力和财力的投入。
迟鸦庙肮推焕匿硕社娇浮雄耘擒揪会渍拓贴酌纷捉宁郑抬琴侠篓洗惊该尤生物信息学序列拼接生物信息学序列拼接
基因组序列拼接算法研究现状
现在最常用的拼接程序使用的拼接算法可分成两类,一类是将拼接问题转化为在图中寻找的Hamilton路径的问题;另一类是将拼接问题在某种特殊情况下转化成寻求图中的Euler路径的问题。他们均有其成功的典型算法。
僚卷押汇特窍茸筒屏郊沈默滁牙颠瑰恤延拙村却驭瞎鞭豫然铃酥叶腕龙痞生物信息学序列拼接生物信息学序列拼接