• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
    • / 17
    • 下载费用:30 金币  

    重庆时时彩小助手: 碱基序列比对系统及方法.pdf

    摘要
    申请专利号:

    重庆时时彩单双窍门 www.4mum.com.cn CN201310064514.9

    申请日:

    2013.02.28

    公开号:

    CN103793625A

    公开日:

    2014.05.14

    当前法律状态:

    撤回

    有效性:

    无权

    法律详情: 发明专利申请公布后的视为撤回IPC(主分类):G06F 19/22申请公布日:20140514|||实质审查的生效IPC(主分类):G06F 19/22申请日:20130228|||公开
    IPC分类号: G06F19/22(2011.01)I 主分类号: G06F19/22
    申请人: 三星SDS株式会社; 延世大学校产学协力团
    发明人: 朴旻胥; 朴商贤; 吕润九
    地址: 韩国首尔市
    优先权: 2012.10.29 KR 10-2012-0120649
    专利代理机构: 北京铭硕知识产权代理有限公司 11286 代理人: 韩明星;李云霞
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201310064514.9

    授权公告号:

    ||||||

    法律状态公告日:

    2017.03.29|||2014.06.11|||2014.05.14

    法律状态类型:

    发明专利申请公布后的视为撤回|||实质审查的生效|||公开

    摘要

    本发明公开一种碱基序列比对系统及方法。本发明一实施例提供的碱基序列比对系统包括:片段序列生成单元,从短片段序列生成多个片段序列;过滤单元,从所生成的多个片段序列构成候补片段序列集合;片段序列扩张单元,计算各个候补片段序列的在对象序列的映射位置的数量,选择所计算的映射位置的数量超过设定的值的片段序列,并对所选择的片段序列的大小进行扩张,直至在对象序列的映射位置的数量变成设定的值以下为止;映射长度计算单元,将对象序列分割为多个区间,并按照各区间分别计算候补片段序列的总映射长度;比对单元,选择所计算的总映射长度为基准值以上的区间,并对所选择的区间执行针对短片段序列的全局比对。

    权利要求书

    权利要求书
    1.  一种碱基序列比对系统,其中,包括:
    片段序列生成单元,从短片段序列生成多个片段序列;
    过滤单元,从所生成的所述多个片段序列构成候补片段序列集合;
    片段序列扩张单元,计算各个所述候补片段序列的在所述对象序列的映射位置的数量,选择所计算的所述映射位置的数量超过设定的值的片段序列,并对所选择的片段序列的大小进行扩张,直至在所述对象序列的映射位置的数量变成所述设定的值以下为止;
    映射长度计算单元,将所述对象序列分割为多个区间,并按照所述各区间分别计算所述候补片段序列的总映射长度;
    比对单元,选择所计算的所述总映射长度为基准值以上的区间,并对所选择的区间执行针对所述短片段序列的全局比对。

    2.  根据权利要求1所述的碱基序列比对系统,其中,所述片段序列生成单元从所述短片段序列的第一个碱基以设定的间隔移动的同时以设定的大小读取所述短片段序列的值,由此生成所述片段序列。

    3.  根据权利要求1所述的碱基序列比对系统,其中,所述过滤单元将与所述对象序列的精确匹配的结果为不匹配的碱基的数量达到设定的数量以下的片段序列包含到所述候补片段序列集合。

    4.  根据权利要求1所述的碱基序列比对系统,其中,所述片段序列扩张单元在所选择的所述片段序列的第一个或最后一个部分增加对应于该位置的所述短片段序列中的碱基。

    5.  根据权利要求1所述的碱基序列比对系统,其中,所述比对单元在所述候补片段序列中选择映射于所选择的所述区间的候补片段序列,并在所选择的各个候补片段序列的在所述对象序列内的映射位置执行针对所述短片段序列的全局比对。

    6.  根据权利要求5所述的碱基序列比对系统,其中,所述比对单元将所选择的所述区间分割为多个小区间,并判断在将要执行全局比对的所述对象序列内的位置所属的小区间是否已经执行了全局比对,且仅在所述判断的结果为没有执行过全局比对时才执行所述全局比对。

    7.  根据权利要求1所述的碱基序列比对系统,其中,所述基准值为从以 下数学式H=L-f*e-2s或者H=f+s中计算出的值中的最大值,
    此时,H为基准值,L为短片段序列的长度,f为片段序列的长度,e为短片段序列的最大误差数量,s为各片段序列的移动间隔。

    8.  根据权利要求7所述的碱基序列比对系统,其中,所述基准值满足以下数学式:f+s≤H≤L-(f+s)。

    9.  根据权利要求1所述的碱基序列比对系统,其中,所述基准值为16以上59以下。

    10.  一种碱基序列比对方法,用于将短片段序列比对于对象序列,其中包括如下步骤:
    由片段序列生成单元从短片段序列生成多个片段序列;
    由过滤单元从所生成的所述多个片段序列构成候补片段序列集合;
    由片段序列扩张单元计算所生成的各个所述候补片段序列的在所述对象序列的映射位置的数量;
    由所述片段序列扩张单元选择所计算的所述映射位置的数量超过设定的值的片段序列;
    由所述片段序列扩张单元对所选择的片段序列的大小进行扩张,直至在所述对象序列的映射位置的数量变成所述设定的值以下为止;
    由映射长度计算单元将所述对象序列分割为多个区间,并按照所述各区间分别计算所述候补片段序列的总映射长度;
    由比对单元选择所计算的所述总映射长度为基准值以上的区间,并对所选择的区间执行针对所述短片段序列的全局比对。

    11.  根据权利要求10所述的碱基序列比对方法,其中,生成所述片段序列的步骤为,从所述短片段序列的第一个碱基以设定的间隔移动的同时以设定的大小读取所述短片段序列的值,由此生成所述片段序列。

    12.  根据权利要求10所述的碱基序列比对方法,其中,构成所述候补片段序列集合的步骤为,将与所述对象序列的精确匹配的结果为不匹配的碱基的数量达到设定的数量以下的片段序列包含到所述候补片段序列集合。

    13.  根据权利要求10所述的碱基序列比对方法,其中,扩张所选择的所述片段序列的大小的步骤构成为,在所选择的所述片段序列的第一个或最后一个部分增加对应于该位置的所述短片段序列中的碱基。

    14.  根据权利要求10所述的碱基序列比对方法,其中执行所述全局比对 的步骤为,在所述候补片段序列中选择映射于所选择的所述区间的候补片段序列,并在所选择的各个候补片段序列的在所述对象序列内的映射位置执行针对所述短片段序列的全局比对。

    15.  根据权利要求14所述的碱基序列比对方法,其中,执行所述全局比对的步骤包括如下步骤:将所选择的所述区间分割为多个小区间;判断在将要执行全局比对的所述对象序列内的位置所属的小区间是否已经执行了全局比对,
    而且仅在所述判断的结果为没有执行过全局比对时才执行所述全局比对。

    16.  根据权利要求10所述的碱基序列比对方法,其中,所述基准值为从以下数学式H=L-f*e-2s或者H=f+s中计算出的值中的最大值,
    此时,H为基准值,L为短片段序列的长度,f为片段序列的长度,e为短片段序列的最大误差数量,s为各片段序列的移动间隔。

    17.  根据权利要求16所述的碱基序列比对方法,其中,所述基准值满足以下数学式:f+s≤H≤L-(f+s)。

    18.  根据权利要求10所述的碱基序列比对方法,其中,所述基准值为16以上59以下。

    19.  一种碱基序列比对系统,其中,包括:
    片段序列生成单元,从短片段序列生成多个片段序列;
    过滤单元,从所生成的所述多个片段序列构成候补片段序列集合;
    映射长度计算单元,将所述对象序列分割为多个区间,并按照所述各区间计算所述候补片段序列的总映射长度;
    比对单元,选择所计算的所述总映射长度为基准值以上的区间,并对所选择的区间执行针对所述短片段序列的全局比对。

    说明书

    说明书碱基序列比对系统及方法
    技术领域
    本发明的实施例涉及用于分析基因组的碱基序列的技术
    背景技术
    由于低廉的费用和快速的数据生产,生产大容量的短序列的下一代测序(next-generation sequencing;NGS)正在快速地代替传统的桑格(sanger)测序方式。而且,多种NGS序列再组合程序是将焦点聚焦到准确度的情形下被开发出来的。但是,最近随着下一代测序技术的发展,制造片段序列的费用变为以前的一半以下,随此能够使用的数据的量变多,因此需要能够在较快的时间内准确地处理大容量的短序列的技术。
    序列再组合的第一个步骤为通过碱基序列比对(alignment)算法将短片段(read)映射(mapping)到参考序列的准确位置。在此存在的问题是,即使是相同种的个体也会因为各种遗传变异而有可能在基因组序列上存在差异。而且,由于测序过程中的误差,碱基序列也可能会产生差异。因此,碱基序列比对算法不得不有效地考虑这种差异和变异,以提高映射准确度。
    得到的结论是,为了进行基因组信息的分析,需要尽可能多的数量的准确的整个基因组信息数据。而且,为此,需要先行开发出具有无比出色的准确度和大处理量的碱基序列比对算法。但是,以往的方法在满足这种要求条件上存在限制。
    发明内容
    本发明的实施例的目的在于提供一种在确保映射准确度的同时,改善映射时的复杂度,由此能够提高处理速度的碱基序列比对手段。
    用于解决上述问题的本发明的一实施例提供的碱基序列比对系统为用于将短片段(read)序列比对到对象序列的系统,包括:片段序列生成单元,从所述短片段序列生成多个片段序列(fragment);过滤单元,从所生成的所述多个片段序列构成候补片段序列集合;片段序列扩张单元,计算各个所述 候补片段序列的在所述对象序列的映射位置的数量,选择所计算的所述映射位置的数量超过设定的值的片段序列,并对所选择的片段序列的大小进行扩张,直至在所述对象序列的映射位置的数量变成所述设定的值以下为止;映射长度计算单元,将所述对象序列分割为多个区间,并按照所述各区间分别计算所述候补片段序列的总映射长度;比对单元,选择所计算的所述总映射长度为基准值以上的区间,并对所选择的区间执行针对所述短片段序列的全局比对(global alignment)。
    用于解决上述问题的本发明的一实施例提供的用于将短片段序列比对到对象序列的方法包括如下步骤:由片段序列生成单元从短片段序列生成多个片段序列;由过滤单元从所生成的所述多个片段序列构成候补片段序列集合;由片段序列扩张单元计算所生成的各个所述候补片段序列的在所述对象序列的映射位置的数量;由所述片段序列扩张单元选择所计算的所述映射位置的数量超过设定的值的片段序列;由所述片段序列扩张单元对所选择的片段序列的大小进行扩张,直至在所述对象序列的映射位置的数量变成所述设定的值以下为止;由映射长度计算单元将所述对象序列分割为多个区间,并按照所述各区间分别计算所述候补片段序列的总映射长度;由比对单元选择所计算的所述总映射长度为基准值以上的区间,并对所选择的区间执行针对所述短片段序列的全局比对。
    另外,用于解决上述问题的本发明的另一实施例提供的碱基序列比对系统为用于将短片段(read)序列比对到对象序列的系统,包括:片段序列生成单元,从短片段序列生成多个片段序列;过滤单元,从所生成的所述多个片段序列构成候补片段序列集合;映射长度计算单元,将所述对象序列分割为多个区间,并按照所述各区间计算所述候补片段序列的总映射长度;比对单元,选择所计算的所述总映射长度为基准值以上的区间,并对所选择的区间执行针对所述短片段序列的全局比对。
    根据本发明的实施例,在对短片段序列进行比对时,并不是仅考虑短片段序列的特定区域,而是考虑整个短片段,由此选在种子片段(片段序列),因此相比于仅考虑短片段的一部分的算法,可提高准确度。
    另外,按照短片段序列分别对在对象碱基序列内的重复数进行限制,对于超过此的种子片段确定种子片段的长度,由此提高映射的准确度,同时还具有能够提高映射的速度的效果。
    而且,利用映射柱状图选择短片段映射到对象碱基序列内的可能性高的特定区域,并仅在该区域内执行全局比对,由此可大幅度地减少全局比对时间。
    进而,对构成组合的可能性高的片段序列直接执行全局比对,以代替对从短片段导出的片段序列的映射位置和组合进行查找的复杂过程,由此可进一步提高全局比对速度,而且构成为记住全局比对位置之后,不在该位置周边重复执行全局比对,因此具有能够减少不必要的全局比对次数的优点。
    附图说明
    图1为用于说明本发明一实施例提供的碱基序列比对方法100的图。
    图2为用于例示出本发明一实施例提供的碱基序列比对方法100的108步骤中的mEB计算过程的图。
    图3为用于说明本发明一实施例提供的碱基序列比对方法100的112步骤中的片段序列生成过程的图。
    图4为例示出利用本发明一实施例提供的映射柱状图的映射对象区间选择过程的图。
    图5为用于说明本发明的一实施例提供的在进行全局比对时用于减少不必要的全局比对次数的方法的示例图。
    图6为示出本发明的一实施例提供的碱基序列比对系统600的方块图。
    符号说明
    600:碱基序列比对系统
    602:片段序列生成单元
    604:过滤单元
    606:映射长度计算单元
    608:比对单元
    610:片段序列扩张单元
    具体实施方式
    以下,参照附图说明本发明的具体的实施方式。但是,这只不过是示例,本发明并不局限于此。
    在说明本发明时,当判断为对于与本发明相关的公知技术的具体说明有 可能混淆本发明的要旨时,省略对其的详细说明。而且,后述的术语是考虑到在本发明中的功能而进行定义的,其根据用户、应用者的意图或惯例等而可能不同。因此,其定义应当以整个本说明中的内容来定义。
    本发明的技术思想由权利要求书来确定,以下的实施例只不过是用于向本发明所属技术领域的具有通常的知识的技术人员有效率地说明本发明的技术思想的一种手段。
    在详细说明本发明的实施例之前,首先对在本发明中所使用的术语进行说明为如下。
    首先,所谓“短片段(read)序列”(或者简称为“短片段”)是从基因组测序仪输出的长度短的碱基序列数据。短片段序列的长度根据基因组测序仪的种类而通常以35~500bp(碱基对,base pair)左右构成为多种,通常,DNA碱基用A、C、G、T的字母文字表示。
    所谓“对象碱基序列”是指从所述短片段序列生成整个碱基序列时作为参考的碱基序列(reference sequence)。即,在碱基序列分析中,对于从基因组测序仪输出的大量的短片段,参考对象碱基序列进行映射,由此完成整个碱基序列。在本发明中,所述对象碱基序列可以是在碱基序列分析时预先设定的序列(例如,人类的整个碱基序列等),或者也可以将从基因组测序仪制造的碱基序列作为对象碱基序列而使用。
    “碱基(base)”是构成对象碱基序列以及短片段的最小单位。如前所述,DNA碱基可由A、C、G以及T四个种类的字母文字构成,这些分别表示为碱基。即,DNA碱基由四个碱基表示,这对于短片段也相同。
    “片段(fragment)序列”(或者种子片段(seed))是为了短片段序列的映射而比较短片段序列和对象碱基序列时作为单位的序列。从理论上来讲,为了将短片段映射到对象碱基序列,需要将整个短片段从对象碱基序列的最前面的部分依次进行比较的同时计算短片段的映射位置。但是,在这样的方法中,映射一个短片段需要非常长的时间和计算功率,因此实际上首先将由短片段的一部分构成的片(即,片段序列)映射到对象间隙序列中,由此找出整个短片段序列的映射候补位置,并在该候补位置映射(Global Alignment)整个短片段序列。
    图1为用于说明本发明一实施例提供的碱基序列比对方法100的图。在本发明的实施例中,所谓碱基序列比对方法100是指将从基因组测序仪输出 的短片段序列与对象碱基序列进行比较,以确定短片段序列的在所述对象序列中的映射(或比对)位置的一系列过程。
    首先,当从基因组测序仪输入短片段序列时102,尝试整个短片段序列与所述对象碱基序列的精确匹配(exact matching)104。如果所述尝试结果为针对整个短片段的精确匹配获得成功,则不进行之后的比对步骤,判断为比对成功106。
    将人类的碱基序列作为对象进行试验的结果表示,当将从基因组测序仪输出的100万个短片段序列精确匹配到人类的碱基序列时,在总共200万次的比对中(正方向序列100万次,逆向互补(选反向互补序列,Reverse Complement)方向序列100万次)发生231,564次的精确匹配。因此,执行所述104步骤的结果,能够减少约11.6%的比对需要量。
    但是,与此不同,在所述106步骤中判断为该短片段序列没有精确匹配时,计算在将该短片段序列比对到所述对象序列时可能出现的误差的最小数量(mEB,最小误差界(minimum Error Bound))108。
    图2为用于例示出所述108步骤中的mEB计算过程的图。首先,如图2的(a)所示,最初将mEB设定为0,并从短片段序列的最前面第一个碱基开始一个碱基一个碱基地向右侧移动的同时尝试精确匹配。此时,如图(b)所示,假设从短片段序列的特定碱基(图中由第二个T标记的部分)开始不能再精确匹配。此时,表示在从短片段序列的匹配开始位置至当前位置之间的区间的某一处发生了误差,因此,此时将mEB值增加1(mEB=1),并在下一个位置重新开始精确匹配(图中由(c)标记)。之后,再次判断为不能精确匹配时,表示在从重新开始精确匹配的位置至当前位置之间的区间的某一处再次发生了误差,因此将mEB值再次增加1(mEB=2),并在下一个位置重新开始精确匹配(图中由(d)标记)。经过这样的过程,到达至短片段的最末位时的mEB值成为该短片段的mEB。
    当经过上述的过程计算出短片序列的mEB值时,判断所计算出的mEB值是否超过预设的最大误差容许值(maxError)110,若超过,则判断为针对该短片段序列的比对失败,从而结束比对。
    在前述的将人类的碱基序列作为对象进行的试验中,在将最大误差容许值(maxError)设为3的情况下计算剩余的短片段的mEB的结果表示,相当于总供844,891次的短片段超过所述最大误差容许值。即,执行所述108步 骤的结果,能够减少42.2%的比对需要量。
    但是,与此不同,在所述110步骤中的判断结果为计算出的mEB值为所述最大误差容许值以下时,经过如下的过程执行针对该短片段序列的比对。
    首先,从所述短片序列生成多个片段(fragment)序列112,并构成仅包含所生成的多个片段序列中的与所述对象序列映射的片段序列的候补片段序列集合114。之后,将所述对象序列分割为多个区间,并按照所述各个区间分别计算所述候补片段序列的总映射长度,由此生成映射柱状图116,在所生成的映射柱状图中选择所述总映射长度为基准值(柱状图切值(Histogram cut))以上的区间,对于被选择的区间将执行针对所述短片段序列的全局比对(global alignment)118。此时,当所述全局比对的结果为短片段的误差数量超过预设的最大误差容许值时,判断为比对失败,反之,则判断为比对成功120。
    以下,详细说明所述112步骤至118步骤的具体过程。
    从短片段序列生成多个片段序列112
    本步骤是为了正式地进行短片段序列的比对,从短片段序列生成多个小片(即,片段序列)的步骤。在本步骤中,从所述短片段序列的第一个碱基至最后一个碱基为止,以设定的间隔移动(移动大小,shift size)的同时,以设定的大小(片段大小(fragment size))读取短片段序列的值,由此生成所述片段序列。
    图3为用于说明所述112步骤中的片段序列生成过程的图。图示的实施例示出的是,短片段序列的长度为75bp(碱基对,base pair),短片段的最大误差容许值为3bp,片段序列的大小(fragment size)为15bp,移动间隔(shiftsize)为4bp的实施例。即,从短片段序列的第一个碱基开始,以4bp为单位向右侧移动的同时生成片段序列。然而,图示的实施例仅为示例性的,对于例如所述移动间隔、片段序列的大小等,可考虑短片段序列的长度、短片段的最大误差容许值等值来适当地设定。也就是说,需要注意的是,本发明的权利范围并不局限于特定的片段序列的大小以及移动间隔。
    生成的片段序列的过滤以及扩张114
    经过如上的过程生成了片段序列时,接着经过在所生成的片段序列中去除不与对象序列映射的片段序列的过滤过程,由此构成候补片段序列集合(sub-candidate)。即,尝试所生成的片段序列与所述对象序列之间的精确匹配(exact matching),且由其结果为不匹配的碱基的数量为预设的容许值以下的片段序列(候补片段序列)构成所述候补判断序列集合。此时,所述容许值为0时,所述候补片段序列集合仅包含与所述对象序列精确匹配的片段序列。
    例如,在图3所示的实施例中,假设所述种子片段的第15个、第31个以及第47个位置上发生了误差(图中用虚线表示)。此时,包含所述误差的片段序列(图中用灰色表示)不会与对象序列精确匹配,而只有没有受到误差影响的49~63、53~67、57~71、61~75的四个片段序列才与对象序列精确匹配。因此,此时,在所述候补片段序列集合中仅包含上述的四个片段序列。
    另外,通常来说,对象碱基序列(例如,人类的基因组)包含多个重复序列(repeat sequence)。这种重复序列分布于对象序列的多个位置,且重复地包含相同的碱基序列,因此在进行部分片段序列与对象序列之间的映射时,将会在非常多的位置中发生精确匹配。但是,由于这样的重复序列,在部分片段序列中生成非常多的数量的映射时,对于整个比对算法的复杂度以及准确度产生坏影响,因此,此时需要利用适宜地方法来减小被映射的位置的重复数。
    为此,本步骤还可包括当候补片段序列中在所述对象序列中的映射位置超过预设的值(例如,50个)时,直至所述映射位置的数量变成所述设定的值以下为止,扩张该片段序列的大小的步骤。
    具体来讲,在本步骤中,计算出所生成的所述候补片段序列中的每一个的在所述对象序列中的映射位置的数量,并选择出所计算出的所述映射位置的数量超过设定的值的片段序列之后,直至在所述对象序列中的映射位置的数量变为所述设定值以下为止,扩张所选择的片段序列的大小。此时,所述选择的片段序列的大小的扩张可通过在所述选择的片段序列的第一个或最后一个部分增加对应于该位置的所述短片段序列中的碱基来执行。
    对此举例说明如下。例如,假设如下地从短片段序列生成了片段序列。
    短片段序列:ATTGCCTCAGT
    片段序列:TTGC(在短片段序列中画下划线的部分)
    如果对于所述片段序列的映射的结果,在对象序列中的映射位置的数量为超过作为基准值的50个的65个,则如下所示地将每次以1bp为单位扩张所述片段序列的长度,直至所述映射位置的数量降低到基准值以下。
    TTGC(65个映射位置)
    TTGCC(54个映射位置)
    TTGCCT(27个映射位置)
    在上面的示例中,参考短片段序列增加了两个碱基时,映射位置的数量降低至预定值以下,因此最终片段序列变为相比最初生成的值扩张2bp的TTGCCT。另外,需要注意的是,与前述的其他示例相同地,所述设定值是可根据对象序列、短片段序列以及片段序列的特性等而适宜地设定的值,本发明的权利范围并不局限于特定的设定值。
    在将人类的碱基序列作为对象进行的实验中表现出了如下状况:在100万个短片段中以片段序列的长度为15np、移动间隔为4bp生成片段序列之后,将所生成的片段序列映射到对象序列时,当将基准值设为50时,在总共15,547,856个片段序列中有约77%的片段序列具有50个以下的映射。即,实验结果表示,当基准值设为50时,77%的片段序列能够直接使用,而剩余的23%的片段序列需要进行基于前述方法的片段序列的扩张。
    映射柱状图的生成116
    通过上述的过程构成了候补片段序列集合(sub-candidate)时,原则上来说,可利用这些候补片段序列集合的在所述对象序列内的映射位置将短片段序列映射到对象序列。但是此时,需要考虑候补片段序列的各个映射位置的所有组合,因此用于短片段序列的映射的计算的复杂度变得非常高。例如,当候补片段序列集合中所包含的候补片段序列为4个,且各个候补片段序列 的在对象序列的映射位置的数量分别为3、6、24、49个时,需要对21,168(=3*6*24*49)个组合全都检索。本发明为了降低如此的计算复杂度而使用映射柱状图。
    在本发明中,映射柱状图为具有预定大小的排列(integer array),排列的值对应于将对象序列分割为具有相同大小的多个区间时的各个区间。例如,当将对象序以65536(=216)bp大小的区间进行分割时,对象序列的0~65535bp为止的区间对应于映射柱状图h的第一个值(即,h[0]),65536~131071bp为止的区间对应于映射柱状图h的第二个值(即,h[1])??衫谜庋姆绞浇韵笮蛄械姆指畹母鞲銮涠杂τ谟成渲赐?。
    而且,映射柱状图的各个值h[i]中存储有在所对应的对象序列区间的所述候补片段序列的总映射长度A,进一步地,可存储有映射于该对象序列区间的候补片段序列在短片段序列的位置中的最大的值B。
    例如,图3所示的实施例中,当53~67的片段序列映射于h[0]区间时,h[0]的柱状图值为变为(15,67)(此时,15为映射于h[0]区间的候补片段序列的总映射长度,67为被映射的候补片段序列在短片段序列的最后位置)。以相同的方式,当49~63的片段序列映射于h[1]区间时,h[1]的柱状图值变为(15,63)。之后,61~75的片段序列映射于h[0]区间时,h[0]的柱状图值更新为(23,75),其理由如下。
    第一个值23:考虑了最初被映射的53~67和之后被映射的61~75的交叠(overlap)的区间的总映射长度。
    第二个值75:相当于被映射的片段序列的最后位置,即61~75的最后位置。
    映射对象区间选择以及全局比对(Global Assignment)118
    经过如上的过程生成映射柱状图时,将映射柱状图的柱状图值(在该区间的候补片段序列的总映射长度)为预设的基准值(柱状图切值(Histogram cut))以上的区间选择为映射对象区间。
    图4为例示出利用本发明一实施例提供的映射柱状图的映射对象区间选择过程的图。如图所示,假设对象序列被分割为h[0]至h[3]这4个区间,各个区间的柱状图值被计算为如下。
    h[0]=15,h[1]=0,h[2]=23,h[3]=15
    此时,所述柱状图切值被设定为22时,大于柱状图切值的区间变为相当于h[2]的区间,在本步骤中,将相当于h[2]的区间选择为映射对象区间。此时,如果柱状图值大于柱状图切值的区间为多个,则相关的所有区间变为映射对象区间,并在包含于映射对象区间的多个区间上均执行全局比对。此时,为了提高比对速度,可将包含于映射对象区间的各个区间的柱状图值相互比较,并从柱状图值高的区间开始顺序地执行全局比对。柱状图值高表示被映射的片段序列的总长度更长,因此在该区间上,短片段序列被映射的可能性高。而且,此时,若各个区间的柱状图值相同,则可计算映射到各个区间的候补片段序列的数量,并从片段序列的数量较多的区间开始执行全局比对。
    如此,映射对象区间被选择时,接着将候补片段序列(sub-candidate)中映射于该映射对象区间的候补片段序列选定为最终候补片段序列(candidate),并在所选定的最终候补片段序列的各自的映射位置上执行针对短片段序列的全局比对,由此完成针对短片段序列的比对。
    例如,在所述图4的实施例中,假设映射于h[2]区间的候补片段序列为49~63、53~67、61~75这三个,则所述三个候补片段序列成为最后候补,并将在这些的该区间内的映射位置上执行短片段序列的全局比对。
    另外,在执行针对所述最终候补片段序列的全局比对时,为了减少全局比对所需的时间,记住已经执行过一次全局比对的对象序列中的位置,从而不在靠近其的位置上重复多次执行全局比对。具体来讲,本步骤构成为,将所述映射对象区间分割为多个小区间之后,如果是执行了全局比对的小区间,则将此记录下来。然后,在执行针对该小区间的全局比对时,利用所述记录的信息判断在该小区间上是否已执行过全局比对,并仅在所述判断结果为没有进行过全局比对的情形下才执行全局比对。
    对此举例说明的话如图5所示。如图所示,映射对象区间分为5个小区间,且假设所述三个最终候补中49~63、53~67映射于第二个小区间,61~75映射于第四个小区间。此时,如果对于49~63的片段序列在第二个小区间上执行全局比对时,与其结果无关地,对于所属于相同的小区间的53~67不会执行全局比对,这对于其相反的情形也相同。因此,对于图示的实施例 的情形而言,全局比对将仅对49~63/61~75或者53~67/61~75的组合实施。如本发明一样,即使不是在整个对象序列执行全局比对,而是仅在映射对象区间内执行全局比对,为全局比对所消耗的时间也比较多,因此通过如上的过程可减少全局比对所需的时间。
    柱状图切值(Histogram Cut)计算
    在上述实施例,柱状图切值可通过如下的方式计算。
    首先,f表示片段序列的大小,s表示用于生成片段序列的短片段序列内的移动间隔,L表示短片段序列的长度,e表示在短片段序列中容许的最大误差的数量,H表示柱状图切值时,在短片段序列中不受误差的影响的区域的长度T可通过如下数学式算出。
    T=L-f*e-s
    此时,L和e为执行本发明时已经确定的值,因此T由f、s值确定。即,算法的性能根据如何改变f和s值而变化。
    首先,在确定H值时,考虑下面两个条件。其中必要条件必须要充分满足的,而追加条件在可能的情形下予以考虑。
    -必要条件:由于映射的基本单位为片段序列,因此柱状图切值无论多小也必须是至少为能够包含处于交叠(overlap)的两个以上的片段序列的大小。如果如图2一样,f=15、s=4时,交叠的两个片段序列的最小长度变为15+4=19,因此至少H值应当为19以上。而且,所述H值需要设定成至少包含两个片段序列,因此最小也应当要大于或等于f+s。如将在后面说明的一样,f值应最小为15以上,因此将s值假设为其最小值1时,H变成最小为16(=15+1)以上的值。
    -追加条件:当假设为理想的状况时,若设定为H=T并找出映射有T以上的序列的柱状图时,可找到对于给出的误差的所有的映射。但是,如前所述,当对象序列本身具有较多的重复时,根据状况可能发生需要扩张片段序列的长度的情形。因此,考虑此情形而设定H值时,使用稍小于T的T-s在映射率方面比较有利。如果假设为H=T,则变为H=L-f*e-s,其中将e假 设为最小值1时(若e为0则属于与对象序列精确匹配的情形,因此在前述的104步骤中,映射将结束),变为H=L-f-s。该值变为柱状图值的最大值。如果假设L=75bp、f=15bp、s=1,则H的最大值变为75-15-1=59。
    若进行整理,则所述H值需要满足如下的范围。
    f+s≤H≤L-(f+s)
    接着,f值在满足下面两个条件的值中选择较大的值。必要条件依然是必须要充分满足的,而追加条件在可能的情形下予以考虑。
    -必要条件:f应当为15以上,其理由在于,当片段序列的长度为14以下时,在对象序列内的映射位置的数量将急剧增加。
    下面的表1表示的是基于片段序列长度的在人类基因组内的片段序列的平均出现频数。
    表1
    片段序列的长度平均出现频数102,726.191911681.973112170.91851342.70991410.6470152.6617160.6654170.1664
    从上述表可以知道,当片段序列的长度为14以下时,基于片段序列的频数为10以上,但是当片段序列的长度为15时,基于片段序列的频数减少为3以下。即,片段序列的长度构成为15以上时,相比于构成为14以下的情形能够大幅度地减少片段序列的重复。
    -追加条件:应当满足f≤L/(e+2),这是为了使T的长度确保为片段序列2个的大小以上。
    例如,L=100、e=4时,f应当具有16以下的值。
    通过整理上面的条件,对确定f和s、H的方法进行整理为如下。
    -s固定为4之后,确定f和H。
    -在15≤f≤L/(e+2)范围内将最大的值确定为f。(其中,必须为f≥15)
    -H利用下面的数学式来确定。
    从H=L-f*e-2s或者H=f+s中计算出的值中的最大值。
    (此时,H为基准值,L为短片段序列的长度,f为片段序列的长度,e为短片段序列的最大误差数量,s为各片段序列的移动间隔)
    例1)当L=75,e=3时,
    f=15~15,因此为15,
    s=4,
    H=75-3*15-2*4=22
    例2)当L=100,e=4时,
    f=15~16,因此为16,
    s=4,
    H=100-4*16-2*4=36-8=28
    例3)当L=75,e=4时,
    f=15~12,但是应当为15以上,因此为15,
    s=4,
    虽然H=75-4*15-2*4=15-8=7,但是f+s=19,因此其结果为H=19。
    图6为示出本发明的一实施例提供的碱基序列比对系统600的方块图。本发明的一实施例提供的碱基序列比对系统600为用于执行前述的碱基序列 比对方法的装置,包括片段序列生成单元602、过滤单元604、映射长度计算单元606、比对单元608以及片段序列扩张单元610。
    片段序列生成单元602从来自基因组测序仪的短片段序列生成多个片段(fragment)序列。如前所述,片段序列生成单元602从所述短片段序列的第一个碱基以设定的间隔移动的同时以设定的大小读取短片段序列的值,由此生成所述片段序列。
    过滤单元604构成在所生成的多个片段序列中仅包含与所述对象序列映射的片段序列的候补片段序列集合。此时,与所述对象序列映射的片段序列是指进行与所述对象序列的进行精确匹配的结果为不匹配的碱基的数量达到设定的数量以下的片段序列。
    映射长度计算单元606将所述对象序列分割为多个区间,并按照所述各区间分别计算所述候补片段序列的映射位置以及各区间的所述候补片段序列的总映射长度。
    比对单元608从被映射长度计算单元606分割的区间中选择所计算的所述总映射长度为基准值以上的区间,并对所选择的区间执行针对所述短片段序列的全局比对。具体来讲,比对单元608基于所述候补片段序列中映射于所述选择的区间的候补片段序列在所述对象序列内的映射位置,执行针对所述短片段序列的全局比对。
    而且,比对单元608将所述选择的区间(映射对象区间)分割为多个小区间,并判断在将要执行全局比对的所述对象序列内的位置所属的小区间是否已经执行了全局比对,且仅在所述判断的结果为没有执行过全局比对时才执行所述全局比对,由此能够构成为减少不必要的全局比对的次数。
    片段序列扩张单元610计算在所述过滤单元604中生成的各个所述候补片段序列的在所述对象序列的映射位置的数量,并选择所计算的所述映射位置的数量超过设定的值的片段序列,对所选择的片段序列的大小进行扩张,直至在所述对象序列的映射位置的数量变成所述设定的值以下为止。此时,片段序列扩张单元610通过在所述所选择的片段序列的第一个或最后一个部分增加对应于该位置的所述短片段序列中的碱基来执行所述扩张。
    另外,本发明的实施例可包括计算机可读记录介质,该计算机可读记录介质包括用于在计算机上执行本说明书中记载的方法的程序。所述计算机可读记录介质可单独地包括程序命令、本地数据文件、本地数据结构等或者将 这些组合而包括。所述介质可以是为了本发明而特别设计并构成的介质,也可以是在计算机软件领域中对于具有通常的知识的技术人员来说属于公知而能够使用的介质。计算机可读记录介质的示例包括诸如如硬盘、软盘以及磁盘一样的磁介质、如CD-ROM、DVD一样的光记录介质、如软盘一样的磁光介质、以及只读存储器(ROM)、随机存取存储器(RAM)、闪速存储器等的专门构成为储存命令并执行命令的硬件装置。程序命令的示例可包括如通过编译器翻译而成的机器语言代码,还可包括通过使用解释器而能够被计算机执行的高级语言代码。
    以上,通过代表性的实施例对本发明进行了详细的说明,但是对于本发明所属技术领域的具有通常的知识的技术人员来说应当理解,上述的实施例在不脱离本发明的范畴的情况下可具有多种变形。
    因此,本发明所请求的权利范围并不局限于所说明的实施例,应当由权利要求书所请求的范围和与该权利要求书所请求的范围等同的范围来确定。

    关 键 词:
    碱基 序列 系统 方法
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    关于本文
    本文标题:碱基序列比对系统及方法.pdf
    链接地址://www.4mum.com.cn/p-6156908.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03