生物序列数据库相似性搜索算法研究

《生物序列数据库相似性搜索算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、生物序列数据库相似性搜索算法研究(申请扬州大学工学硕士学位论文)培养单位：堵乔旱1互：专业名称：研究方向：研究生：指导教师：扬州大学管理科学与工程知识与信息管理丁茂华徐永安副教授2013．5扬州ResearchonAlgorithmforSimilaritySearch．ofBiologicalSequenceDatabase(ApplyingfortheDegreeofMaster)DingMaohuaUndertheguidanceandsupervisionofAssociateProfessorXuYong’an砀甜／sSubmittedtoYangzhouUniversityI

2、lllllllllllllllllIlllllllDlllllllllUltllllJIY2419228YangzhouUniversity,Yangzhou，ER．China，May,2013摘要随着国际人类基因组计划的启动，生物序列数据库的数据呈爆炸性增长，生物序列数据库中的数据蕴含着大量的信息和知识，如何挖掘和利用这些信息和知识是值得研究的问题。生物序列数据库相似性搜索是生物信息处理中最基本的一个问题，通过比较待查询的序列和数据库的目标序列的相似程度进而推断其同源性，以便满足生物学研究人员的研究和应用需求。虽然目前生物序列数据库提供了基因序列数据进行存储管理和相似性搜索等功能，但是

3、生物数据库的序列数据增长达到了惊人的速度，平均每十四个月就要翻一番，这对生物序列数据库相似搜索算法的速度提出了挑战。目前，大部分生物序列数据库相似搜索算法的速度是通过牺牲一定的灵敏度而获得的，如何研究和设计同时满足高灵敏度和快速的生物序列数据库相似搜索的算法是值得思考的问题。因此，本文的具体工作如下：1、总结了点阵图法和基于动态规划算法的双相似性序列比对算法，它们是最基本的生物序列相似性比对算法，也是生物数据库相似搜索的理论基础和灵敏度参照的标准；详细介绍了生物序列数据库相似性搜索算法的原理和经典的生物序列数据库相似性搜索算法，即BLAST算法、FASTA算法和PattenffIunte

4、r算法。2、研究了生物序列数据库相似性搜索算法的重要参数．种子。种子是调节生物序列数据库相似性搜索的速度和灵敏度阀门，目前使用的连续种子和空位种子相对灵敏度较低，如何设计高效率的种子是关键问题。因此，本文提出了一种新的匹配模式的种子．模糊匹配种子，理论和实验证明模糊匹配种子在同样的搜索长度下比连续种子和空位种子具有更高的灵敏度，使用模糊匹配种子可以提高生物数据库相似性搜索的性能。3、给出了模糊匹配种子的最优化计算方法。传统的生物序列数据库相似性搜索的种子长度都是取得一个经验值，在搜索的时候并不满足最优灵敏度且自适应性较差。本文设计了一种模糊匹配种子的最优灵敏度的数学规划模型，并根据其数学

5、模型的特点设计了一种简单的求解方法。4、本文还研究了局部相似性区域种子连接的问题。由于基因序列的基本操作还包括插入和删除，而插入和删除种子的算法是属于NP-hard问题，其计算复杂度非常大。局部相似性区域种子连接可以快速、有效的识别潜在的属于同一相似性区域的种子，这对提高生物序列数据库相似性搜索的速度和灵敏度都有显著性的效果。5、本文设计了一个高效率的FSSA算法用于生物序列数据库相似性搜索。介绍了FSSA算法的特点及算法过程，实验证明FSSA算法是一种高灵敏度的且快速的生物序列数据库相似性搜索算法。关键词：生物序列数据库；相似性搜索；种子优化；模糊匹配种子：局部相似性区域种子连接Abs

6、tractWiⅡlthestartoftheinternationalHumanGenomeProject,thedataofsequencedatabase，whichcontainalotofinformationandknowledge，haveincreasedexplosively．Howtotapandusetheinformationandknowledgeofthesequencedatabaseisaproblemworthyofstudy．Similaritysearchesofbiologicalsequencedatabasesisabasicproblemofb

7、iologicalinformationprocessingwhichcancomparethesimilaritybetweenaquerysequenceandthetargetsequenceofthedatabaseandtheninfertheirhomologytomeetthenoodsoftheresearchandapplicationofbiologicalresearchers．Althoughthebiolo