多重序列比对的数学模型与算法

多重序列比对的数学模型与算法

自美国提出组织的人类基因组计划（Human Genome Proreet）简称为HGP以来，美国每年拔出相当大的经费支持，日本、法国、英国、德国等纷纷响应，它们的工作使新的交叉学科生物信息论得以诞生和发展，生物信息论是用数理和信息科学的观点、理论和方法去研究生命现象，组织和分析呈指数增长的生物学数据。生物信息学是一门综合学科，是计算机科学、数学、物理、生物学的结合。生物信息学的基础是各种数据库的建立和分析工具的发展。目前，生物学数据库已达500个以上，共有四大类：基因组数据库，核酸和蛋白质一级结构数据库、生物大分子三维空间结构数据库及其以她们为基础构建的二级数据库。生物信息学主要研究基因组测序及其信息分析、生物大分子的结构与功能预测及其模拟和药物设计、大规模基因表达数据的分析与基因芯片设计，以及基因与蛋白质相互作用网络等四方面的问题。

多重序列比对是计算分子生物学中最重要的运算。多重序列比对的基本问题就是找出适当安排删减与插入尽量少的空格，使得两个序列达到最大程度的一致的方案。比如给出下列三个序列：

AC_G AGTCC (1) ACT

我们适当安排删减与插入空格得到： ACG___ A_GTCC (2) AC_T__

（2）就是多重序列的一个比对。

局部分段比对是其中更为常见的运算。上世纪80年代，Smith-Waterman提出了两个序列的局部比对的明确的模型。1998—1999年，相继出现利用k-tuple的快速容错分段比对搜索法。2002年开始出现对完整基因组及其异常基因的比

较研究以及多重序列比对问题的研究，2003年刘军Mayetri Gupta和刘军得到Motif的搜索算法。

人类基因组计划后，目前已经进入后基因时代，主要就是对人类基因组计划实施得到的基本数据库进行信息分析、加工和利用，提取有用信息，用来研究生命现象中的重大问题。多重序列比对问题是生物信息学的基本问题，多重序列比对技术也是生物信息学的基本工具，有着十分广泛的应用，比如基因是否为同一个家族，癌症患者的基因与正常时的基因比对分析等等。因此，请您们就基因的多重序列比对，设计合理的衡量比对好坏的定量描述模型，建立多重序列比对的基本问题的数学模型，并设计一种求解的算法。最后就附录一中的12个序列，请您们利用你们得到的模型与算法，给出使序列有最大相似程度的比对。

附录一：

CATTTCTTTTTAGGGATTTTAAAAGTTGTCTTTTCTT CATTTCTTTTTAAGGTTTTAAAAATTGTCTTTTTT CATTTCTTTTTAAGGGTTTTAAAAATTGTCTTTTCTT CATTTTTTCTTAAGTGTTTTGGTATTTATCTTTTTCTT CATTTTTGCTTATGTATTTATAGTGGGTTGTCTTTTTGACTT CATTTCTTTTGAAGTGATTTGAGATTTATCTTTTTCTT CATTTCTTTTTAAGGGTTTTAAAAATTGTCTTTTCTT CATTTCTTTTTATGTTGAGATATTTGTCTGTTTTCTT CATTTTTACTATGTGTTGATTGTGGATTGTCTTTTCTT

CATTTCTTTTATTGAGTGAAGAAGAGATTTTGTCTTGTTTTGAT CATTTTTCTTAGTGTTTTGGTATTTATCTTTTTCTT CATTTCTTTTAAGGGTTTTAAAAATTGTCTTTTCTT

本文来源：https://www.bwwdw.com/article/sa4g.html