序列比对优化算法研究

《序列比对优化算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、西安电子科技大学硕士学位论文序列比对优化算法研究姓名：杨丽申请学位级别：硕士专业：软件工程指导教师：霍红卫;刘忠武20060401摘要序列比对是整个生物信息学中重要的组成部分，是从生物分子序列中进行信息分析与挖掘的基础。通过序列比对人们可以从DNA序列中推断出蛋白质分子的结构；通过序列比对人们可以从基因数据库中搜索查找新的序列：通过序列比对人们可以分析生物进化以及推断生物分子的结构与功能信息。本文首先介绍了分子生物学背景知识，对生物序列比对技术的各个方面进行了介绍，包括序列比对的基本原理、全局比对、局部比对、双

2、序列比对和多序列比对。其中研究了几种用于序列比对的软件系统。FASTA搜索和BLAST搜索用于双序列比对，能够在数据库中找出与新序列相关的己知序列。ClustalW程序用于多序列比对，它是目前比较好的一种多序列比对软件。在对多序列比对的研究中，主要是基于渐进算法的全局多序列比对算法的分析和实现。阐述了渐进比对算法的原理，算法用到了许多基本算法，主要是动态规划算法和Needleman．Wunsch算法，讨论了系统发生树的构建以及邻近归并算法。分析了空位罚分和打分矩阵对比对的影响。在此基础上，用面向对象的方法设计了

3、渐进算法的全局多序列比对软件系统，文章给出了设计思想和UML活动图、UML类图。在JBuilderX开发平台上实现了软件系统，并给出了JBuilderX根据代码自动生成的UML类图。对于测试结果按组进行分析。在渐进算法的基础上，本文提出可以使用迭代算法对全局多序列比对软件系统进行改进，文章给出了改进的方法和具体设计。最后，使用BAIiBASE数据库中142个文件进行测试，给出了测试用例。并且把改进前后的比对结果进行比较分析，分析表明迭代方法有效地改进了渐进算法的比对系统。本文研究内容是渐进算法的全局多序列比对系

4、统，通过使用迭代算法对系统进行了改进，经过具体的实验测试和分析，其比对效果有较高的改善。关键词：全局比对多序列比对渐进算法迭代算法软件系统活动图类图AbstractSequencealignmentisanimportantpartofbioinformatics，whichisthefoundationtoanalyseandminethedatafromthebiomoleculesequences．Usingsequencealignment，wecanconcludethestructureofapro

5、teidsequenceaccordingtotheDNAsequences．Wecanalsosearchanewsequencewithinthebasedatabase．Throughsequencealignment，wecangettheevolutionofbiologyandgetthestructureandthefunctionofbiomolecules．Firstly,wedescribetheconceptsaboutthemolecularbiology．Wedescribethete

6、chnologyofsequencealignmentintheround，includingthebasicprincipleofsequencealignment，globalalignment，localalignment，pair-wisesequencealignment，multiplesequencealignment．Thereareseveralsoftwaresystemstoalignsequences·FASTAandBLASTsystemscanaligntwosequencesino

7、rdertosearchthedatabase．ClustalWcanalignmultiplesequences，whichisamuchbettersoftwaresystemofsequencealignmentatpresent．Inthestudyofmultiplesequencealignment，wefocusourmindsontheprogressivealgorithmforglobalmultiplesequencealignment．Weexpoundthetheoryofthepro

8、gressivealgorithm，whichcontainsomeotheralgorithmssuchasdynamicprogramming,Needleman-Wunschalgorithm．Wediscusstheconstructionofaphylogenetictreewithneighbor-joiningmethod．Thefunctionsofgappenalty