DNA序列比对数目的算法研究

维普资讯 http://www.cqvip.com 第２４卷第１期　２００８年２月　大　学　数　学　Ｃ（）Ｉ　Ｉ　ＥＧＥ　ＭＡＴＨＥＭＡＴＩＣＳ　Ｖｏ１．２４，№．１　Ｆｅｂ．２００８　ＤＮＡ序列比对数目的算法研究　徐琛梅　，　刘晓杰　（１．河南大学数学与信息科学学院，开封４７５００１；２．南开大学组合数学中心，天津３０００７１）　［摘　要］生物序列比对是生物信息学中非常重要的内容．文［１］中作者用差分方程理论给出了求两　ＤＮＡ序列间比对数目的一个计算公式，然而解法较为繁琐．本文将借助于组合数学中母函数这一计数＿Ｔ具给　出另一简单、优美的算法，并在此基础上剔除非生物比对，得到进一步的计算公式，这一结果缩小了需要考查　的比对范围．　［关键词］ＤＮＡ序列；序列比对；母函数；非生物比对　［中图分类号］ＴＰ３０１　［文献标识码］Ａ　［文章编号］１６７２—１４５４（２００８）０１—０１００—０４　１　序列比对　生物信息学是由生物学、数学和计算机科学交叉形成的一个新兴学科．面对人类基因组计划产生的　庞大的分子生物学信息，生物信息学的重要性将越来越突出．由于数学和计算机科学的强大功能的合理　应用，这一学科的发展将为生命科学的研究带来革命性变革．ＤＮＡ、ＲＮＡ以及蛋白质序列比对　（Ａｌｉｇｎｍｅｎｔ）是生物信息学的重要研究内容之一．例如，可以通过对比不同物种序列的相似性判断它们　之间的同源性（Ｈｏｍｏｌｏｇｏｕｓ），同源性较高的序列可能具有相似的三维结构和生物学功能，因此序列比　对的结果具有重要的生物学意义．　目前关于两ＤＮＡ序列比对算法，较流行的有动态规划比对算法和数据库搜索算法．文［１］中作者　用差分方程方法给出了求两ＤＮＡ序列比对数目的一个计算公式，然而算法较为繁琐．本文借助于组合　数学中的母函数方法，给出了一个简洁算法．并在此基础上，剔除非生物比对，得到了更简洁的计算公　式．这一结果缩小了需要考查的比对范围．　一个ＤＮＡ序列的元素由Ａ，Ｃ，Ｇ，Ｔ四种核苷酸组成．假定：　Ｘ一（ｘｌ，ｚ２，…，　），ｌ，一（Ｙｌ，Ｙｚ，‘・‘，　）　分别表示长度为　和ｍ的两个ＤＮＡ序列，其中　，　，（ｉ一１，２，…，　；Ｊ一１，２，…，ｍ）均取四个核苷酸　Ａ，Ｃ，Ｇ，Ｔ中的一个．　现在，我们要对比这两个序列的相似性，并确定它们残基间的对应．为了比较两序列对应位置上的　核苷酸，需要首先安排这些对应，任何一个保持序列中残基顺序的对应的安排就是一个序列比对，这种　安排允许　’（ｇａｐ）出现，但不允许一个序列中的‘。’直接与另一个序列中的　’对应，这一规定保证了可　能出现的比对数目是有限的．例如：给定两个ＤＮＡ序列ｚ—ＴＣＧＴＡＣＧ和Ｙ—ＴＣＡＣＴＧＣ，则下表是序　列ｚ，　间的一个比对．　表１　序列ｚ＝ＴＣＧＴＡＣＧ和　＝ＴＣＡＣＴＧＣ的一个比对　Ｉ　Ｔ　Ｃ　Ｇ　Ｔ　Ａ　Ｃ　Ｇ　ｌ　Ｔ　Ｃ　Ａ　Ｃ　Ｔ　Ｇ　Ｃ　表中ｌ－’表示插入和删除．　［收稿日期］２００６—０２—０７　［基金项目］新世纪高等教育教学改革工程本科教育教学改革立项项目（编号１２８３Ｂ０１０７１）　维普资讯 http://www.cqvip.com

第１期　徐琛梅，等：ＤＮＡ序列比对数目的算法研究　１Ｏ１　两ＤＮＡ序列Ｘ和ｙ间可能出现的比对数目ｆ（”，　）满足如下的递推关系式［２］：　厂（”，　）一厂（”一１，　）＋厂（”，ｍ一１）＋厂（”一１，　一１）　（１）　及初始条件：　－厂（０，　）一厂（”，０）一１”，　∈｛０，１，２，…｝．　一∑一　厂　（２）　上述递推方程有唯一确定的解，文献［１］应用差分方程理论给出了它的精确表达式：ｍ　　一　２　（　），　ｌ　ｌ㈦　然而，其求解过程较为繁琐，且不易推广．那么我们自然要问：是否有更简便的算法？这种算法能推广到　∑一　一般情况吗？　厂　一　２母函数解法　ｍ　下面我们借助于母函数这一重要计数工具给出方程（１）和（２）的另一解法．　＋　定义　设（ｎ。，ａ　，ｎ　，…，ａ，，…）是一序列事件的符号表示或者是一个数列，称函数　一∑一　Ｆ（　）一ａ０　ｏ（　）＋ａｌ　ｌ（　）＋ａ２　２（　）＋…＋Ⅱ　，（ｚ）＋…　厂　为序列（ｎ。，ａ　，ａ　，…，ａ，，…）的普母函数，简称母函数ｌ３］．　其中　。（　），　（　），…，　，（ｚ），…是一序列　的函数，称为指标函数．指标函数的选择应保证任意两　ｍ　　—个不同的序列所生成的母函数亦不同，这里不妨取　的幂为指标函数（即：，ｕｒ（　）一　）．由于　只是一个　卅　形式变量，故毋须考虑级数的收敛性．　＋　对每一”≥０，设序列（厂（”，０），厂（”，１），厂（”，２），…，厂（”，　），・・・）的普母函数为　Ｆ　（　）一厂（”，０）＋厂（”，１）　＋厂（”，２）　＋…＋厂（”，　）　＋…，　∑一厂　　（４）　由方程（１）中的递推关系式，有　聍　一　ｍ　Ｈ口　—　Ｆ　（　）一＿，’（”，０）一Ｆ　一】（　）一ｆ（”一１，０）＋ｘＦ，　（　）＋ｘＦ　一ｌ（　）．　ｚ　又由方程（２）中初始条件知：ｆ（ｎ，０）一厂（”～１，０）一１，从而上式可化为　Ｆ　（　）一　Ｆ　（　）．　（５）　由此可得　（　）一（　）”　１．　显然，ｆ（ｎ，　）就是Ｆ　（　）幂级数表达式中ｚ　项的系数．由　胁　一、　ｌ　＋ｘＩ　１　”ｃ　…ｌ一奎ｌ＝０　ｋ　＝０（　）　知　一　（　．㈣　这样就得到了ｆ（ｎ，　）的另一精确表达式．　显然，与文［１］方法相比较，上述解法是简单和优美的，并且对于更一般的带双指标的常系数线性递　推关系式（如：ｆ（ｎ，　）一ａｆ（ｎ一１，　）＋ｂｆ（ｎ，　一１）＋ｃｆ（ｎ一１，　一１）＋　其中Ⅱ，ｂ，ｆ，ｄ为常数）的求　解也是适用的．　３进一步研究　由于递推方程（１）和（２）有唯一确定的解，因此首先说明ｆ（ｎ，　）的表达式（６）和（３）是等价的．对　维普资讯 http://www.cqvip.com １０２　大　学　数　学　第２４卷　Ｆ，　（　）进行重新考查，由于　一（　ｌ＋ｘ）”　１一（　＋　）　１一［ｋ奎＝Ｏ　２　（　）（　）　］［　『］　一［　＋薹塞２　（ｎ是，［、ｋ＋志一ｒ－　）　］［妻ｌ＝０　］，　从而　…　ｉ＝ｌ『－　ｋ＝ｌ（　二　）］＝ｍｉ　２　（　）．　这样就得到了ｆ（ｎ，ｍ）的精确表达式（３），也就是说，表达式（６）和（３）同是Ｆ　（　）幂级数表达式中　项　的系数，因此两者等价，并且还可以看出：ｆ（ｎ，ｍ）一ｆ（ｍ，　）．　其次，上面的讨论中包含了序列问没有任何两个残基对准的比对，这样的比对是不具有生物意义　的，应当将其从比对数目中剔除，以便进一步缩小需要考查的比对数目的范围．以下将这类比对称之为　非牛物比对．　例如：给定两个ＤＮＡ序列　—ＣＧＴ和　—ＧＡＣＴ，则下表就是这两个序列间的一个非生物比对．　表２　ｚ—ＣＧＴ和　—ＧＡＣＴ的一个非生物比对　　Ｉ—　Ｃ　Ｇ　Ｔ　　『Ｇ　Ａ　Ｃ　Ｔ　易见，两ＤＮＡ序列Ｘ和ｙ间的非生物比对数目ｇ（　，ｍ）满足如下递推关系式　ｇ（ｎ，ｍ）一ｇ（ｎ。ｍ一１）＋ｇ（ｎ一１。ｍ）　（７）　及初始条件　ｇ（Ｏ，ｍ）一ｇ（ｎ，０）一１，　，ｍ∈｛０，１，２，…｝，　（８）　同样应用上述母函数解法可得　Ｉ　＋ｍ、　ｇ（ｎ，ｍ）一ｌ　１．　（９）　显然，ｇ（ｎ，ｍ）一ｇ（ｍ，　）．值得指出的是，这一结果亦可由排列组合方法获得．　最后，将非生物比对剔除，可以得到比对数目的进一步计算公式：　…　－－ｇ　一　’（　ｋ）．　（１０）　４　结　论　在本文中，我们用母函数方法重新求解方程（１）和（２），得到了与文Ｉ－１－１不同的表达结果，并在此基础　上排除了非生物比对，缩小了需要考查的比对范围，得到了ＤＮＡ序列比对数目计算公式，更精确地描　述了随着序列长度　和ｍ的增加，可能出现的比对数目厂（　，ｍ）的增长情况．　我们希望还可以进一步减小要考查的比对数目，例如，根据生物信息学的研究实际，增加对序列比　对的限制性条件，进而得到更加有效的比对范围，从而为设计序列比对算法和进行相应的算法复杂性分　析提供可靠的依据．这种算法可以和搜索算法结合，以缩短搜索过程．　［参　考　文　献］　Ｅｌｉ　Ｔｏｒｒｅｓ　Ａ，Ｃａｂａｄａ　Ａ，Ｎｉｅｔｏ　Ｊ　Ｊ．Ａｎ　ｅｘａｃｔ　ｆｏｒｍｕｌａ　ｆｏｒ　ｔｈｅ　ｎｕｍｂｅｒ　ｏｆ　ａｌｉｇｎｍｅｎｔｓ　ｂｅｔｗｅｅｎ　ｔＷＯ　ＤＮＡ　ｓｅｑｕｅｎｃｅｓ［Ｊ］　ＤＮＡ　Ｓｅｑｕｅｎｃｅ，２００３，１４（６）：４２７—４３０．　［２］Ｌａｎｇｅ　Ｋ．Ｍａｔｈｅｍａｔｉｃａｌ　ａｎｄ　Ｓｔａｔｉｓｔｉｃａｌ　Ｍｅｔｈｏｄｓ　ｆｏｒ　Ｇｅｎｅｔｉｃ　Ａｎａｌｙｓｉｓ［Ｍ］．Ｎｅｗ　Ｙｏｒｋ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２００２．　［３］Ｌｉｕ　Ｃ　Ｉ　．Ｉｎｔｒｏｄｕｃｔｉｏｎ　ｔＯ　Ｃｏｍｂｉｎａｔｏｒｉａｌ　Ｍａｔｈｅｍａｔｉｃｓ［Ｍ］．魏万迪译．成都：四川大学出版社，１９８７．　维普资讯 http://www.cqvip.com 第１期　徐琛梅，等：ＤＮＡ序列比对数目的算法研究　１Ｏ３　Ｆｕｒｔｈｅｒ　Ｓｔｕｄｙ　ａｂｏｕｔ　ｔｈｅ　Ｅｘａｃｔ　Ｆｏｒｍｕｌａ　ｆｏｒ　ｔｈｅ　Ｎｕｍｂｅｒ　ｏｆ　Ａｌｉｇｎｍｅｎｔｓ　ｂｅｔｗｅｅｎ　Ｔｗｏ　ＤＮＡ　Ｓｅｑｕｅｎｃｅｓ　ＸＵ　Ｃｈｅｎ—ｍｅｉ　，　Ｌ　Ｕ　Ｘｉａｏ－ｊｉｅ。　（１．Ｍａｔｈ，Ｄｅｐ，Ｈｅｎａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｋａｉｆｅｎｇ　４７５００１，Ｃｈｉｎａ；　２．Ｃｅｎｔｅｒ　ｆｏｒ　Ｃｏｍｂｉｎａｔｏｒｉｃｓ　ａｎｄ　ＬＰＭＣ，Ｎａｎｋａｉ　Ｕｎｉｖｅｒｓｉｔｙ，Ｔｉａｎｊｉｎ　３０００７　１，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ａｌｉｇｎｍｅｎｔ　ｉｓ　ａｎ　ｉｍｐｒｏｔａｎｔ　ｐａｒｔ　ｏｆ　Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ．Ｉｎ　ｔｈｅ　ｐａｐｅｒ［１］，ｔｈｅ　ａｕｔｈｏｒｓ　ｇｉｖｅ　ａｎ　ｅｘａｃｔ　ｆｏｒｍｕ１ａ　ｆｏｒ　ｔｈｅ　ｎｕｍｂｅｒ　ｏｆ　ｐｏｓｓｉｂｌｅ　ａｌｉｇｎｍｅｎｔｓ　ｕｓｉｎｇ　ｔｈｅ　ｔｈｅｏｒｙ　ｏｆ　ｄｉｆｆｅｒｅｎｃｅ　ｅｑｕａｔｉｏｎｓ，Ｈｏｗｅｖｅｒ，ｉｔｓ　ｓｏｌｕｔｉｏｎ　ｉｓ　ｃｏｍｐｌｉｃａｔｅｄ．Ｉｎ　ｔｈｉｓ　ｓｈｏｒｔ　ｃｏｍｍｕｎｉｃａｔｉｏｎ，ｗｅ　ｇｉｖｅ　ａｎｏｔｈｅｒ　ｓｉｍｐｌｅ　ａｎｄ　ｇｒａｃｅｆｕｌ　ｄｅｄｕｃｅｄ　ｍｅａｎｓ　ｕｓｉｎｇ　ａ　ｃｏｕｎｔｉｎｇ　ｔｏｏｌ　ｃａｌｌｅｄ　ｇｅｎｅｒａｔｉｎｇ　ｆｕｎｃｔｉｏｎ　ｉｎ　ｃｏｍｂｉｎａｔｏｒｉａｌ　ｍａｔｈｅｍａｔｉｃｓ，　ａｎｄ　ａｔｔａｉｎ　ａ　ｆａｒｔｈｅｒ　ｅｘａｃｔ　ｆｏｒｍｕｌａ　ｆｏｒ　ｔｈｅ　ｎｕｍｂｅｒ　ｏｆ　ａｌｉｇｎｍｅｎｔｓ　ｂｙ　ｗｅｅｄｉｎｇ　ｏｕｔ　ｔｈｅ　ｎｏ—ｂｉｏｌｏｇｉｃａｌ　ｏｎｅｓ　ＳＯ　ａｓ　ｔｏ　ｓｈｏｒｔｅｎ　ｔｈｅ　ｎｕｍｂｅｒ，　Ｋｅｙ　ｗｏｒｄｓ：ＤＮＡ　ｓｅｑｕｅｎｃｅ；Ａｌｉｇｎｍｅｎｔ；Ｇｅｎｅｒａｔｉｎｇ　ｆｕｎｃｔｉｏｎ；Ｎｏ－ｂｉｏｌｏｇｉｃａｌ　ａｌｉｇｎｍｅｎｔ