英语原文共 19 页，剩余内容已隐藏，支付完成后下载完整资料
基于移码扩展惩罚的蛋白质编码序列比对
弗朗索瓦·贝兰格和阿达·旺拉瓦
研究所
{弗朗索瓦·贝兰盖3,阿依达·瓦昂拉瓦}@加利福尼亚州奥斯布鲁克
摘要:我们介绍了一种基于移码的蛋白质编码序列比对算法。与以前发表的蛋白质编码序列比对方法相比，该算法的主要特点是引入了移帧扩展的惩罚代价。以前的算法只使用常量移帧惩罚，这类似于在经典序列比对算法中使用仿射间隙惩罚的评分方案。然而，在比对中移位部分的整体惩罚不能表示为仿射函数，因为它还应该包含不同的密码子可替换分数。该算法的第二个特点是在经典的DNA序列比对定义下，其搜索空间是两个编码序列之间所有可能比对的集合。以前的算法在路线长度上引入了约束，并为对齐码的表示引入了额外的记号。该算法具有与经典Needleman-Wunsch算法相同的渐近时空复杂度。
关键词：蛋白质编码序列，成对比对，移码，动态规划
1简介和动机
随着越来越多的基因在几个物种中具有多种不同的编码序列，比较基因组学目前面临着巨大的挑战[4,10]。同一基因或同源基因的不同编码序列的差异不仅在于核苷酸序列的突变，还在于外显子的选择性起始密码子和选择性剪接。所有这些机制都会导致翻译移码，从而导致同一部分基因在不同编码序列中的不同翻译[8]。这种对基因结构进化复杂性的新启示，需要一种新的编码序列比较算法来解释编码序列之间翻译移码的存在。
对齐两个编码序列的问题是一个优化问题，它包括在两个序列之间的一组对齐中找到一个最优的分数对齐。编码序列是由一系列长度为3的单词组成的DNA序列，称为密码子。两个DNA序列A和B之间的比对是核苷酸字母表上长度L相同的一对序列A0和B0加上间隙符号amp;apos;-amp;apos;，使得A0和B0在同一位置不包含间隙符号amp;apos;-amp;apos;，并且可以通过移除所有间隙符号从A0和B0导出A和B。A0和B0的长度L称为对齐长度。两个编码序列之间的比对中的翻译移码是由i）一个密码子的一个或两个核苷酸的缺失（例如，与A--对齐的密码子ACC）或ii）一个密码子的两个核苷酸之间的核苷酸插入（例如，与AGACC对齐的密码子A--CC）引起的。两个编码序列之间最佳比对的计算应考虑编码序列到蛋白质序列的翻译，以及两个编码序列之间翻译移码的存在。
比较两个编码序列的经典方法是三步法，首先将编码序列翻译成蛋白质序列，然后对下一个蛋白质序列进行比对，最后将蛋白质比对反译成编码序列比对。这种方法在大多数工具中用于编码序列的多重对齐[1,14,3,6]。然而，它不能解释编码序列之间是否存在帧移。
Hein等人首先解决了在同时考虑相应蛋白质序列和存在移码的情况下对齐长度为n和m的两个编码序列的问题[5,9]。他们提出了一个DNA/蛋白质模型，使得两个编码序列之间的比对得分是其在DNA水平上的得分和其在蛋白质水平上的得分的组合。在这个模型下，提出了一个O（n2.m2）算法[5]和一个O（n.m）算法[9]来计算最优的分数对齐。算法的搜索空间是一组排列，每个排列可以唯一地分解为十一（11）种类型的连续子排列。定义了11种类型的子路线，使得每种子路线的长度都是3的倍数。因此，搜索空间中任何对齐的总长度总是3的倍数，并且对齐的分数是其子对齐的分数之和。
Arvestad[2]提出了另一种基于广义替换概念的O（n.m）蛋白质编码比对算法。在该算法中，两个编码序列A和B之间的对齐是核苷酸字母表上的一对序列，加上间隙符号“-”和移码符号“！”。该算法的搜索空间是一组比对，每个比对由一系列长度为3的子比对组成，每个子比对是a和B两个密码子片段之间的比对。编码序列S的密码子片段定义为S中长度为0到5的单词。如果密码子片段的长度为4（分别为。5） ，然后将密码子片段中的一个或两个核苷酸去除，以适合长度为3的亚序列。在定义长度为3的亚序列的分数时，这种核苷酸的下降被忽略了。如果密码子片段的长度为1或2，则两个或一个移码开始符号“！”在密码子中加上，以适应长度为3的亚序列。然后将路线的得分定义为其长度为3个子路线的得分之和。
最近，Ranwez等人[11]提出了Arvestad[2]模型的简化，其中编码序列S的密码子片段被定义为S中长度为0到3的单词。因此，不需要补充组合学来考虑从长度为4或5的密码子片段中除去一个或两个核苷酸的所有可能性。该算法的复杂度为O（n.m）。该方法在多蛋白质编码序列比对的背景下得到了扩展[11]。
上述三种方法[2,9,11]比较两个编码序列，同时考虑两个序列之间存在翻译移帧开口。对齐中的移帧通过添加恒定移帧成本来惩罚，该成本仅惩罚移帧的启动，而不考虑对齐中此移帧的扩展。
例如，我们考虑以下三个编码序列：Seq1、Seq2和Seq3。Seq1的长度是45。序列2（分别。Seq3）的长度为60，通过删除第30位的核苷酸“C”（第15位的核苷酸“G”）并在末端添加16个核苷酸从Seq1获得。
序号1：
ATGACCGAATCCAAGCAGCCCTGGCATAAGTGGGGGAACGATTGA
M T E S K Q P W H K W G N D *
序号2：ATGACCGAATCCAAGCAGCCCTGGCATAATGGGGGAACGATTGAAGTAGGAACGATTTAA
M T E S K Q P W H N G G T I E V G T I *
序号3：ATGACCGAATCCAACAGCCCTGGCATAAGTGGGGGAACGATTGAAGTAGGAACGATTTAA
M T E S N S P G I S G G T I E V G T I *
当查看Seq1和Seq2的翻译时，很容易发现Seq2与Seq1更相似，而Seq3与Seq1更相似。然而，考虑到移帧的成对对齐算法[2,9,11]将为Seq1和Seq2以及Seq1和Seq3的两个最佳对齐返回相同的分数，在这两种情况下仅惩罚移帧的开始（对齐中的红色位置）。
Seq1和Seq2之间的最佳对齐：
Seq1和Seq3之间的最佳对齐：
我们描述了一个成对对齐算法，该算法使用一个计分方案来惩罚移帧的起始和扩展（对齐中的蓝色位置）。在第2节中，给出了路线的一些初步定义和问题的描述。在第三节中，描述了计算最优分数对齐的新算法。
2初步研究：蛋白质编码序列的比对
在这一节中，我们正式描述了编码序列和在第3节中解决的成对对齐问题。
定义1（编码序列）:编码序列是核苷酸sum;N字母表上的DNA序列={a，c，g，t}，其长度n是3的倍数。一个编码序列是由一系列密码子组成的，这些密码子是序列中长度为3的单词，以位置结尾。编码序列的翻译是氨基酸字母表sum;A上长度的蛋白质序列，使得编码序列的每个密码子被翻译成蛋白质序列中的一个氨基酸
在这项工作中，两个编码序列之间比对的定义与Needleman-Wunsch算法用于两个序列比较的两个DNA序列之间比对的经典定义完全相同[7]。
定义2（DNA序列之间的比对）。两个DNA序列A和B之间的比对是一对（A0，B0）式中，A0和B0是通过在A和B中插入间隙符号0minus;0导出的长度相同的两个序列，使得forall;i, 1 le; i le; L, A0[i] =0 minus;0 or B0[i] =0 minus;. 路线中的每个位置i，1le;ile;L称为路线的一列。
给定字母表上长度为L的序列Ssum;={a，c，g，t，-}，S[k..l] ，1le;kle;lle;l，表示S从位置k到位置l的子序列。| S[k..l] |表示S[k]中的字母数。。l] 与间隙符号0-0不同。例如，| AC--G |=3。
给定两个编码序列A和B之间的比对(A0 , B0 )，如果A或B的密码子的三个核苷酸出现在比对的三个连续列中，则在比对中分组。例如，在比对中显示为ACC的密码子ACC被分组，而显示为A-CC的密码子ACC则不被分组。
在下文中，我们给出了两个编码序列A和B之间比对得分的定义。它基于将A和B的密码子划分为四个集合（类型）：
匹配密码子集（M）包含在比对中分组的密码子，并且与另一序列的密码子精确比对。
这组不匹配密码子（U）包含在比对中分组的密码子，并且与不形成密码子的其他序列的三个连续核苷酸比对。
删除/插入的密码子集合（InDel）包含在比对中分组的密码子，并且与连续的3个间隙比对。
所有其他密码子都是移码密码子。根据文献[11]中关于移码的定义和符号，移码密码子可以分为两组。由缺失引起的移码密码子集（FS）包含在比对中分组的密码子，并且仅与另一序列中的一个或两个核苷酸和一些间隙符号对齐。由插入（FS）引起的移帧密码子集包含在对齐中未分组的所有密码子。minus;
移码密码子（MFS）中的一组匹配核苷酸包含所有属于移码密码子的核苷酸，并与另一序列的核苷酸对齐。
使用氨基酸评分函数saa对匹配密码子（M）和不匹配密码子（U）的替换进行评分，并为每个不匹配密码子（U）添加一个固定的移码扩展代价，用fs扩展代价表示。密码子的插入/删除（Indel）是通过为每个插入/删除的密码子（Indel）添加一个固定的缺口成本来评分的。移码密码子核苷酸（MFS）的比对使用核苷酸评分函数san进行独立评分。移码密码子中核苷酸的插入或缺失是移码起始的原因。然后，通过为每个移码密码子添加固定的移码打开成本（用fs open cost表示）来对它们进行评分。
在下面的比对得分定义中，A和B的匹配（M）、不匹配（U）和删除/插入（InDel）密码子仅通过其在比对中最后一个核苷酸的位置（列）来识别。移码密码子（MFS）中的匹配核苷酸也通过它们在比对中的位置来识别。
定义3（对齐的分数）。让(A0 , B0) 是两个编码序列A和B之间长度L的对齐。
对齐的分数（A0，B0）定义如下：
分数(Arsquo; , Brsquo; ) = 分数(Arsquo; ) 分数(Brsquo;)
例如，考虑以下两个序列，A包含13个密码子，B包含14个密码子，它们之间的长度为48。
A和B之间长度为48的对齐（Arsquo;，Brsquo;）：
比对得分（A0，B0）定义中使用的不同密码子和核苷酸组的组成为：M={3,9,12,15,26,48}；A→B级
U={20,41}；Indel={6}；MFS={21,28,29,30,34,35,42,43,45}；A→B级A→B级A→B级
M={3,9,12,15,26,48}；U={21,30,42}；Indel={33}；MFS={18,34,35,39,43,45}。B类→AB类→AB类→AB类→A
3算法
在本节中，我们描述了一种O（n.m）时间和空间复杂度算法，该算法解决了在长度为n和m的两个编码序列a和B之间找到最大分数对齐的问题。与其他序列比较方法[7,13]类似，我们使用大小为n 1times;m 1的动态规划表，这些表由两个序列的前缀对索引两个编码序列。表D存储了A和B前缀之间对齐的最大得分。表DF用于说明随后计数的移帧扩展的潜在情况。
定义4（动态规划表）。给定两个编码序列A和B作为输入，该算法使用大小为n的两个动态规划表D和DF 1times;m 1。单元格D（i，j）包含前缀A[1。。i] 和B[1。。j] 是的。表DF仅针对i和j的值进行填充，使得i（mod 3）=0或j（mod 3）=0。如果i（mod 3）6=0（分别。j（mod 3）6=0时，单元格DF（i，j）包含前缀A[1]之间对齐的分数..i alpha;]和B[1..j alpha;]式中alpha;=（3minus;i）（mod 3）（分别为。alpha;=（3minus;j）（mod 3））。DF表填写如下：
引理1（填充表D）。
- 假设 i(mod 3) = 0 and j(mod 3) = 0
2. 假设 i（mod 3）=0和j（mod 3）!= 0
3. 假设i（mod 3）6=0，j（mod 3）=0，方程与前一种情况对称。
4.
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[405810]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
