摘要：生物信息学发展至今已经积累了大量的生物数据，现在的工作重心也已经转移到了数据的分析上，序列的分析是生物信息学最基本的一项工作，不同的参数，不同的比对方式，会得到不同的比对结果。在学习主要的生物学知识和序列比对的算法，以及了解了目前的一些序列比对的软件的基础上，利用Java语言对现有的blast算法对序列的比对进行实现，主要包括对序列进行全局比对算法、局部比对算法、求出最长子串和blast搜索等操作。在实现比对之前对fasta文件进行处理，得到相应的序列信息，实现过程中则根据设定的打分规则和空位罚分指定相应的打分函数对序列进行打分。然后拓展延伸序列得到最高计分值片段。最终实现blastn、blastx、blastp、tblastx和tblastn五个子程序的功能，并且比对结果与现有的blast软件基本一致。
目录
摘要 1
关键词 1
Abstract 1
Key words 1
1．选题背景 2
1.1 问题的提出 2
1.2 国内外研究状况 2
1.2.1 国外研究状况 2
1.2.2 国内研究状况 2
1.3 研究的目的和内容 3
1.3.1 研究目的 3
1.3.2 研究内容 3
2 序列比对算法简介 3
2.1 点阵法 3
2.2 全局比对算法简介 4
2.3 局部比对算法简介 4
2.4 blast算法简介 5
3 序列比对核心算法 5
3.1 打分函数的设定 6
3.1.1 匹配计分 6
3.1.2 结构与性质的计分 6
3.1.3 可观测变换计分 7
3.2 全局比对算法 7
3.2.1 计分矩阵的生成 7
3.2.2 动态规划法 8
3.2.3 回溯算法 9
3.3 局部比对算法 9
3.3.1 计分矩阵的生成 9
3.3.2 回溯算法 10
3.4 最长子串算法 11
3.
 *51今日免费论文网|www.jxszl.com +Q: ^3^5^1^9^1^6^0^7^2^* 
5 BLAST算法 11
3.5.1 对fasta文件的处理 11
3.5.2 生成序列单词 12
3.5.3 生成字母匹配组合 13
3.5.4 得到匹配的组合 13
3.5.5 种子序列的生成 14
3.5.6 拓展延伸 14
3.5.7 核酸与蛋白质之间的转换 14
4 核心数据结构和函数的介绍 15
4.1 文件的处理 15
4.1.1 文件的读取 16
4.1.2 对文件内容进行处理 16
4.2 计分矩阵的生成 16
4.3 回溯算法 17
4.4 最长子串算法 18
4.5 blast算法 19
4.5.1 生成序列单词 20
4.5.2 生成匹配单词组合 21
4.5.3 生成序列种子 21
4.5.4 拓展延伸 23
5 调试结果以及结果的分析 24
5.1 读取序列结果展示 24
5.2 全局比对算法结果展示 25
5.3 局部比对算法结果展示 25
5.4 最长子串算法结果展示 26
5.5 blast算法结果展示 27
6 运行结果与BLAST软件结果的比较 30
6.1 blastn运行结果的比较 30
6.2 blastx运行结果的比较 31
6.3 blastp运行结果的比较 33
6.4 tblastn运行结果的比较 34
6.5 tblastx运行结果的比较 36
7 展望与不足 37
致谢 37
参考文献 38
基于BLAST算法实现生物序列比对
引言
在研究生物学的过程中，通过对生物序列的同源性进行分析来确定新测得的序列的一些生物属性[1]。序列比对是根据要比对的序列之间的排列顺序，提前设定好相应的打分函数和空位罚分的规则，对于序列进行打分，算出每一段序列之间的得分值，比较得分值，找出最大的的得分片段[1]。如果两个序列之间具有的相似性比较大，就推测这两条序列可能是有相同的进化祖先[2]。序列存在相似性虽然不代表二者一定有共同进化的祖先，但是序列的相似性越高，其具有相同祖先的可能性就越大。序列比对是生物信息学研究的一个主要工具，它在序列拼接、蛋白质结构的预测等问题研究中被普遍使用[3]。
通过序列比对可以从DNA序列中推测出蛋白质分子的结构，可以从基因的数据库中搜索查找新的序列，分析生物进化以及推断生物分子的结构和功能信息[4]。从序列的片段测定，拼接，基因的表达分析，到RNA和蛋白质的结构功能的预测[5]，从大量的序列信息中获取基因的结构、功能和进化等知识，物种亲缘树[6]的构建都需要进行生物分子序列的相似性比较。
1．选题背景
1.1 问题的提出
随着人类基因组计划的完成[7]，生物信息学的发展越来越蓬勃，在生物信息学中越来越需要各种其他学科的融入。序列的比对也是生物信息学中重要的一项工作。序列比对是将未知的生物序列和已知的生物序列进行相似性比较的一种手段[7]。但是由于采用不同的参数以及不同的序列比对方式会产生不同的比对结果，在生物序列比对中有全局比对、局部比对、双序列比对以及多序列比对，寻找一个高效快捷的比对方式是目前所亟需的。
国内外研究状况
1.2.1 国外研究状况
当前，大部分的序列比对方法使用的算法都是基于 Needleman 和 Wunsch 在 1970年提出的动态规划算法的思想[8]，但是不同程度的改进了该思想。在1981 年，Smith 和 Waterman 提出了SmithWaterman 算法[9]，它是由 NeedlemanWunsch 算法演变而来的。后由Pearson和Lipman在1985年提出了FASTA算法，并且他们在1988年对该算法进行了改进。在1990年由Altschul等人提出了BLAST算法[9]，该算法是利用短片段匹配算法和统计模型来分析找出目的序列和数据库之间的最佳局部比对效果。
1.2.2 国内研究状况
自2000年以来，随着越来越多的研究人员开始进入到序列比对的研究中，西安电子科技大学使用了遗传算法[10]、模拟退火算法等优化了SP值，并且对部分方法进行了对比。因为生物序列数据具有特殊性，所以在序列上创建索引方式的研究也是研究的热点[11]，在数据库、生物信息学以及信息检索等领域也都有涉及对后缀树索引技术的研究[12]。
1.3 研究的目的和内容
1.3.1 研究目的

原文链接：http://www.jxszl.com/jsj/wljs/46043.html