序列比对算法CLUSTAL解析及优化

论文摘要

多序列比对是现代生物信息学研究领域非常重要的核心问题。为了能够比对多种相近物种之间的多条序列，我们迫切需要一种多序列比对工具。当前序列比对的研究主要集中于基因组双序列比对，而有效的多序列比对算法只有少数几个，而其中被公认为经典的软件要属CLUSTAL。本文对CLUSTAL程序中的算法做了详尽的研究。CLUSTAL算法主要分为三个步骤：两两比对，构建向导树和渐进比对，本文主要对其算法中的第一步与第二步提出了一种有效的优化算法。在计算得分矩阵的时候使用Ukk-FA算法来完成双序列比对过程，在构建向导树时使用快速NJ法构建向导树算法，而在第三步进行渐进比对的过程使用原有的CLUSTAL程序中算法，进行多序列比对。在多组真实DNA序列上的多序列集上进行的序列比对实验表明，本文提出算法和原始CLUSTAL程序相比具有精度好，效率高的特点。而在构建向导树的这一步中，实验表明随着序列条数的增加，构建向导树的时间性明显提高。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 生物信息学中的多序列比对问题概述
• 1.2.1 生物序列比对背景
• 1.2.2 多序列比对问题研究及现状
• 1.3 论文研究的方法和内容
• 第二章 双序列比对问题及算法研究
• 2.1 序列数据库
• 2.2 序列相似性与同源性
• 2.3 最长公共子序列
• 2.4 全局比对与局部比对
• 2.5 权重矩阵与空位罚分
• 2.6 双序列比对问题算法研究
• 2.7 本章小结
• 第三章 CLUSTAL 算法解析
• 3.1 CLUSTAL 背景及介绍
• 3.2 CLUSTAL 算法描述
• 3.2.1 两两比对
• 3.2.2 构建向导树
• 3.2.3 渐进比对
• 3.3 CLUSTALW 对 CLUSTAL 的优化
• 3.4 本章小结
• 第四章 CLUSTAL 算法优化
• 4.1 E.UKK-FA 优化算法
• 4.2 快速 NJ 法构建向导树
• 4.3 本章小结
• 第五章 实验结果及分析
• 第六章 总结与展望
• 致谢
• 参考文献