XAT软件系统设计与实现

论文摘要

本文的主要工作是通过研究序列比对算法,实现一个cDNA/mRNA序列与DNA序列的跨物种比对软件XAT（cross-Alignment Tool）。本文主要借鉴了blastz软件的跨物种方法和sim4软件的intron与exon的边界确定方法。本文实现的方法允许多条cDNA/mRNA序列与整个基因组的比对,同时给出结果的统计值,另外,XAT软件通过设定配置文件,增加了用户的使用方便性和灵活性,XAT软件用C语言编写,容易移植。 本文首先介绍了序列比对的概念、数学模型和一些通用的算法,主要阐述了一些已有的序列比对的算法和相应的软件。 针对本文实现的XAT软件,介绍了它的意义,详细介绍了它的实现算法,并用C语言实现了XAT软件,并介绍了XAT软件的界面、配置文件和它的输出结果的一些格式。 本文的重点是如何实现cDNA/mRNA序列与整个基因组序列的比对,如何提高它的速度,如何实现它的跨物种特性和如何判定intron与exon的边界,如何对于它的结果进行统计上的描述。在本文中都对它们进行了详细的描述。 最后,采用一种类似genefinding程序中采用的方法来对XAT软件的结果进行了分析,并且将XAT软件和一些其他的序列比对软件的结果进行了比较。

论文目录

• 第一章 绪论
• 1.1 课题的目的和意义
• 1.1.1 序列比对的意义
• 1.1.2 序列比对的数学模型
• 1.1.3 序列比对的算法
• 1.1.3.1 替代矩阵
• 1.1.3.2 空位罚分
• 1.1.4 序列比对的边界问题
• 1.1.5 课题的目的和意义
• 1.2 国内外研究现状
• 1.2.1 fasta软件算法
• 1.2.2 blast软件算法
• 1.2.2.1 MSP
• 1.2.2.2 统计方法
• 1.2.2.3 序列压缩
• 1.2.2.4 重复序列
• 1.2.2.5 算法
• 1.2.3 sim4软件算法
• 1.2.4 blat软件算法
• 1.2.5 blastz软件算法
• 1.2.5.1 替代矩阵
• 1.2.5.2 种子模板
• 1.3 论文的主要内容
• 第二章 XAT软件算法
• 2.1 读入序列和参数，确定种子模板和替代矩阵
• 2.2 去除cDNA序列头尾的高A区域和高T区域
• 2.3 基因组序列窗口化
• 2.4 选择一组cDNA序列
• 2.5 对cDNA序列建立哈希表
• 2.6 搜索基因组
• 2.7 基因组序列延伸
• 2.8 获取 #MSP
• 2.9 MSP转换成 EXON
• 2.10 确定 EXON边界
• 2.10.1 EXON位于开始
• 2.10.2 EXON位于结尾
• 2.10.3 EXON位于中间
• 2.10.3.1 EXON之间存在间隔
• 2.10.3.2 EXON之间连续
• 2.10.3.3 EXON之间重叠
• 2.11 取得 EXON的联配信息
• 2.12 获取 EXON的统计值
• 2.13 序列坐标的调整
• 2.14 输出结果
• 小结
• 第三章 XAT软件实现
• 3.1 XAT软件的安装
• 3.2 XAT软件的输入
• 3.3 XAT软件的参数
• 3.4 XAT软件的配置文件
• 3.5 XAT软件的输出结果
• 第四章 XAT软件结果分析
• 4.1 评价方法
• 4.2 测试数据集的选择
• 4.3 跨物种的比对结果比较
• 4.4 基因组范围内的跨物种的比对结果比较
• 小结
• 第五章 总结
• 参考文献
• 致谢