一种dna序列比对中的打分方法

一种dna序列比对中的打分方法
【技术领域】
[0001] 本发明属于生物信息领域，具体设及一种DNA序列比对中的打分方法。
【背景技术】
[0002] DNA是由A，T，C，G四种碱基链接而成的长链聚合物，人的DNA序列总共包含30 亿对碱基（3Gbp)。由于高通量测序平台的误差及个体和参考序列间存在差异，测量得到 的短序列与参考序列之间将会出现完全匹配（perfectmatch),错配（mismatch),插入 (insedion，read序列比参考序列多出部分碱基）和缺失（deletion,read序列中缺少部 分碱基）等各种情况。read序列比对是给定一段参考序列，read短序列跟参考序列进行比 较，观察参考序列上哪个片段跟read序列差异最小，给出该片段的位置（参见附图1中的 示例）。
[0003] 序列比对在生物信息领域一直扮演着重要的角色，并且随着新一代测序技术的深 入发展，在生物信息领域起到越来越关键的作用：
[0004] 1、在生物学方面，序列比对常常用于同源分析，就是将新序列跟与之同源但不同 物种的序列进行比较，得到该序列与其他序列间同源性大小，从而确定新序列的生物属性。
[0005] 2、在同一个物种中，序列比对可W用来将被测基因组read数据比对到参考基因 组上，从而找到基因组间个体上的差异，如单核巧酸多态性（SNP)、拷贝数变异（CNV)等与 疾病相关的基因位点。
[0006] 在序列比对中，为了找到最优比对结果通常需要借助于得分矩阵，根据得分矩阵 计算得到得分最高的比对结果被认为是最优结果。但是目前得分矩阵的设计通常比较简 单，往往只根据一个维度来设计，失去了对很多有用信息的利用，使得最后的拟合结果与真 实最优结果相去甚远，或者在找到局部最优结果时陷入"早熟"的僵局，使得与全局结果失 之交臂。因此，研究一套采用更多维度信息，使得结果更趋近于真实值的打分规则具有很大 的意义。

【发明内容】

[0007] 为了解决现有技术中的问题，本发明提供了一种DNA序列比对中的打分方法，引 入参考序列中碱基排列概率的统计，构建权重矩阵，利用权重矩阵和传统得分矩阵共同设 计得分规则，利用全局合理性来调控避免"早熟"现象。
[0008] 本发明具体通过如下技术方案实现：
[000引一种DNA序列比对中的打分方法，其包括W下步骤：
[0010] S101;引入参考序列中碱基排列概率的统计，构建权重矩阵N'；
[0011] S102 ;构建比对碱基得分矩阵M;
[001引 S103 ;设置打分规则：设S=SA. . .Sm和T=t山...tn是两个待比对的序列，通 过在S和T中合适的位置插入空位得到s'和r，使得Is'I=IT'I，令位置i上字符比对 得分为0 (S' [i]，T' [i])，其中R为正数，表示空位，
[0013]
[0014] 其中，m仪[i]r[i])为矩阵M的元素，P'（r[i-l]T' [i])为矩阵N'的元素，则序 列全局得分为：
[0015]
[0016] 进一步地，所述方法还包括步骤S104;采用动态规划算法进行序列比对得到最优 比对。
[0017] 进一步地，所述步骤S102需要考虑两个原则，一是匹配得分比失配得分高，二是 转换得分比颠换得分高。
[0018] 本发明的有益效果是；本发明提供的DNA序列比对中的打分方法，引入参考序列 中碱基排列概率的统计，构建权重矩阵，利用权重矩阵和传统得分矩阵共同设计得分规则， 根据打分规则计算序列全局得分，得到最优比对。本发明的方法能够利用全局合理性来调 控避免"早熟"现象。
【附图说明】
[0019] 图1是read序列比对示意图；
[0020] 图2是本发明的DNA序列比对中的打分方法流程图；
[0021] 图3是矩阵元素B[i，j]来源示意图；
[0022] 图4是采用回溯方法来构造最优比对的算法程序示意图； 图5是构造S和T的得分矩阵示意图。
【具体实施方式】
[0023] 如附图2所示，本发明的针对生物碱基图像的降噪方法具体实现的过程如下：
[0024]S101;构建权重矩阵N'。
[0025] 基因上碱基排列服从一定的规律，故引入参考序列中碱基排列概率的统计对于序 列比对具有一定的指导意义。表1为W2个碱基为例，对需要比对的参考序列统计的碱基 概率矩阵N，也可W根据需要自行定义需要统计的碱基排列的长度。
[0026] 表1;双碱基排列概率矩阵N
[0027]
[0028] 当碱基排列的概率越高时，可W认为该样的排列更具合理性，因此产生满足高概 率碱基排列的替换对应的扣分权重应该越小。为何扣分；在比对过程中，鼓励匹配，不鼓励 失配，一般的失配是需要进行扣分的，因此对于失配的得分设为负数。
[0029] 基于W上两点，权重矩阵N'与概率矩阵N元素排序相反，其中排序相反举例如 下：
[0030] 表2权重矩阵N'与概率矩阵N元素值对照表 [00311
[00础表3;权重矩阵N'
[0033]
[0034] S102 ;构建比对碱基得分矩阵M
[00巧]在构建比对碱基得分矩阵时要考虑两大原则：
[0036] 1、匹配得分比失配得分高
[0037] 在比对过程中，会遇到的无非两个情况；1)匹配，2)失配。在鼓励匹配的前提下， 在设置匹配得分时自然要比失配得分高。一般的，匹配得分设为正数，失配需要扣分，得分 设为负数。
[003引 2、转换得分比颠换得分高
[0039] 在考量失配得分时，根据对生物序列进化过程的研究，可W发现某些替换比其它 替换的发生概率更高，如在DNA序列中转换发生的概率要比颠换发生的概率高，因此在设 置得分的时候转换的得分应该比颠换的得分高。
[0040] 转换：同类型碱基之间发生的变换，如喀晚类内变换；C(胞喀晚）一T(胸腺喀 晚），和嚷岭类内变换A(腺嚷岭）一G(鸟嚷岭）。
[0041] 颠换；和转换相反，指的是不同类型间碱基发生的变换，如嚷岭变换为喀晚；A(腺 嚷岭）一C(胞喀晚），喀晚变换为嚷岭；T(胸腺喀晚）一G(鸟嚷岭）。
[0042] 根据W上两大原则构建比对碱基得分矩阵M，表示如下：
[0043] 表4;比对碱基得分矩阵M
[0044]
[0045]其中m(TA) =m(AT)，其他组合同理。
[0046] S103 ;设置打分规则
[0047] 基于权重矩阵N'和比对碱基得分矩阵M，比对碱基得分矩阵M保证在序列比对过 程中找到局部最优比对，权重矩阵N'在考虑了全局合理性之下，在一定程度上避免了序列 比对过程中的"早熟"现象，使最终的比对结果更接近真实比对结果，设置如下打分规则： [004引设S=SA. . .Sm和T=tit2. . .t。是两个待比对的序列，通过在S和T中合适的位 置插入空位得到s'和T'，使得Is'I=It'I，令位置i上字符比对得分为0(s' [i]，T' [i])， 其中R为正数，'-'表示空位（W下同理）。
[0052] 本具体实施例将采用动态规划算法进行序列比对，在过程中运用本发明所制定的 打分方法，来对本发明的使用方式做一个简单的阐述。
[0053] 假设有一参考序列R= {AACGTGTCGATGCGTAGCGATGCGATCGG}
[0054] 则双碱基概率矩阵N如下（为了计算方便，该里直接用频数代替概率）：
[00巧]
[0056] 相应的权重矩阵N'设为：
[0057]
[0058] 根据构建比对碱基得分矩阵时要考虑的两大原则，设置比对碱基得分矩阵M如 下：
[0059]
[0060] 因此根据公式（1)，令R=| 6,则有打分规则如下：I
[0061]
[006引假设有两个带比对序列S=SA. . .Sm和T=t山...t。，其中ISI=m，ITI=n;S[l. . .i]和T[l. . .j] (1《i《m，1《j《n)分别表示S和T的由前i个和前j个碱基组 成的前缀子序列。
[006引构建（m+1)X(n+1)大小的得分矩阵，矩阵中的元素B[i，j] (0《i《m，0《j《n) 记录了前缀子序列S[l...i]和T[l...j]的最优比对得分。根据递归关系，B虹，n]是S= SA. . .Sm和T=t山...t。的最优比对得分。设定计算得分矩阵元素的初始条件：
[0064] B[0, 0] = 0
[0067] 非空子序列S[l...i]和T[l...j]的最优比对得分B[i，j]有S种来源；l)S[i] 与一个空位的比对得分加上子序列和T[l...j]的最优比对得分B[i-1，j]; 2)T[j]与一个空位的比对得分加上子序列S[l...i]和T[l...j-1]的最优比对得分 B[i，j-1] ;3)S山和T[j]的比对得分加上子序列和T[l...j-1]的最优比对 得分j-1]。
[0068] 得到如下递归式：
[0069]
[0070] 比如给定S= "GATG"来自于参考序列R，T= "GAG",则根据权重矩阵N'、碱基比 对得分矩阵MW及公式（3) (4)巧），构造S和T的得分矩阵如附图5所示（实线箭头代表 B[i，j]的产生方向）。
[0071] 采用回溯方法来构造最优比对，方法如附图4所示。可W得到上表中虚线箭头所 代表的的最优比对路径，序列S= "GATG"和T= "GAG"最优比对为：
[0072]
[0073] S:GATG
[0074] T:GA-G
[00巧]W上内容是结合具体的优选实施方式对本发明所作的进一步详细说明，不能认定 本发明的具体实施只局限于该些说明。对于本发明所属技术领域的普通技术人员来说，在 不脱离本发明构思的前提下，还可W做出若干简单推演或替换，都应当视为属于本发明的 保护范围。
【主权项】
1. 一种DNA序列比对中的打分方法，其特征在于：所述打分方法包括以下步骤： 5101 :引入参考序列中碱基排列概率的统计，构造权重矩阵Ν' ； 5102 :构造比对碱基得分矩阵M ; 5103 :设置打分规则：设S = S1S2. . . sj T = t山...tn是两个待比对的序列，通过在 s和τ中合适的位置插入空位得到s'和τ'，使得|s' I = |τ' I，令位置i上字符比对得分为 σ (S' [i]，T' [i])，其中R为正数，表示空位，其中，m(S' [i]T' [i])为矩阵M的元素，Ρ'（Τ' [i-l]T' [i])为矩阵Ν'的元素，则序列全 局得分为：2. 根据权利要求1所述的打分方法，其特征在于：所述方法还包括步骤S104 :采用动 态规划算法进行序列比对得到最优比对。3. 根据权利要求1所述的打分方法，其特征在于：所述步骤S102中构造比对碱基得分 矩阵M需要考虑两个原则，一是匹配得分比失配得分高，二是转换得分比颠换得分高。4. 根据权利要求3所述的打分方法，其特征在于：匹配得分一般设为正数，失配得分一 般设为负数。
【专利摘要】本发明提供了一种DNA序列比对中的打分方法，引入参考序列中碱基排列概率的统计，构建权重矩阵，利用权重矩阵和传统得分矩阵共同设计得分规则，根据打分规则计算序列全局得分，采用动态规划算法进行序列比对得到最优比对。本发明的方法能够利用全局合理性来调控避免“早熟”现象。
【IPC分类】G06F19/22
【公开号】CN104881592
【申请号】CN201510072511
【发明人】汪晓丹, 徐勇
【申请人】哈尔滨工业大学深圳研究生院
【公开日】2015年9月2日
【申请日】2015年2月11日