资源描述：
《生物序列比对算法的研究现状_文凤春》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第8卷第1期生物信息学Vol.8No.12010年3月ChinaJournalofBioinformaticsMar.,2010生物序列比对算法的研究现状111文凤春,王邦菊,肖枝洪(华中农业大学理学院,湖北武汉430073)摘要:序列比对是生物信息学研究的一个重要工具,它在序列拼接、蛋白质结构预测、蛋白质结构功能分析、系统进化分析、数据库检索以及引物设计等问题的研究中被广泛使用。本文详细介绍了在生物信息学中常用的一些序列比对算法,比较了这些算法所需的计算复杂度,优缺点,讨论了各自的使用范围,并指出今后序列比对研究的发展方向。关键词:生物信息学;序列比对;算法;PC
2、GR点中图分类号:TP301文献标识码:A文章编号:1672-5565(2010)-01-064-04StudyonbiologicalsequencealignmentalgorithmsWENFeng-chun,WANGBang-ju,XIAOZhi-hong(SchoolofscienceHuazhongAgriculturalUniversity,Wuhan430073,China)Abstract:Sequencealignmentisanimportantmethodinbioinformatics.Itiswidelyusedinsequencespl
3、icing,proteinstructurepre-diction,proteinstructurefunctionanalysis,phylogeneticanalysis,databaseretrievalandprimerdesign.Thispaperintroducescom-monlysequencealignmentalgorithmsatpresent,comparethecomputationalcomplexityofthesealgorithms,advantage,disadvantageandapplicablefields.Finally
4、wepointedoutproblemsofsequencealignmentandstudydirection.KeyWords:Bioinformatics;SequenceAlignment;Algorithm;PCGRPoint1引言2序列比对生物信息学是在生命科学的研究中以数学和计序列比对问题可以定义为一个五元数组MSA'算机科学为手段对生物信息进行存储、检索和分析=(∑,S,A,F),其中:'的科学,是当今生命科学与自然科学的重大前沿领(1)∑=∑∪{-}为序列比对的符号集。“-域之一,也是21世纪自然科学的核心领域之一。在”表示缺失的核苷酸或氨基酸,∑
5、表示四个核苷酸生物信息学中得到生物序列仅仅是第一步,如何处或20个氨基酸字符集。理、存储和分析这些数据,从中获得生物结构、功能(2)S={S1,S2,…,SN}为序列集,其中Si=Si1,Si2…SiL,Sij∈∑,Li为第i个序列的长度,i=1,的相关信息乃是基因组研究取得成果的决定性步i骤[1-2]。序列分析是生物信息学研究的一项重要的2…,N,j=1,2,…,Li。(3)矩阵A=(aij)N×M表示比对的结果,其中手段,是了解基因组结构和功能的基本途径。在序N'列分析中,比对是最常用和最经典的研究手段。最aij∈∑,max{Li}≤M≤∑Li。iii=1常见的
6、比对是蛋白质序列之间或核酸序列之间的两矩阵A满足:行数等于序列的数目;如果移去两比对,通过比较两个序列之间的相似区域和保守每一行中的“-”字符,将得到原来序列;每列中不性位点,寻求同源结构,揭示生物进化、遗传和变异允许同时为“-”。等问题。序列比对也是数据库搜索算法的基础,将(4)F是比对A的记分函数,用来评估比对A查询序列与整个数据库的所有序列进行比对,迅速的优劣。地获得有关查询序列的大量有价值的参考信息,对(5)序列比对问题MSA就是通过适当的空位[3]于进一步分析其结构和功能都会有很大的帮助。插入,构建一个使F(A)达到最大的比对A。在序列比对中,需要将序列间
7、残基的相似转换收稿日期:2008-11-05;修回日期:2009-03-10.资助项目:华中农业大学学科研究交叉基金(2008XKJC008)。作者简介:文凤春,女,湖北武汉人,副教授,硕士。研究方向:生物信息学;Email:wfc@mail.hzau.edu.cn.第1期文凤春,等:生物序列比对算法的研究现状65成数值后进行比较,为了评价一个比对质量的优劣,3.1Smith-Waterman算法需要给定一个记分系统。常见的记分系统有氨基酸Smith-Waterman算法主要寻找生物进化过程中置换矩阵PAM和区块氨基酸置换矩阵BLOSUM。的局部保守区域,比全局
