大规模基因组中重复体识别算法的研究

论文摘要

重复体识别问题是现代生物信息学中基因组分析的一个基本研究课题。通过识别重复体可以发现基因组的进化规则和许多疾病的遗传规律。许多转位子重复体序列作为可编码区域重复出现在基因组序列中,识别这些重复体对基因组解码起到了非常重要的作用。虽然现在已经存在多种算法解决重复体识别问题,但是这些算法在很多方面还不够完善。针对当前存在的问题,本文提出了一种基于种子序列的方法来求解重复体识别问题。本文提出了两个重复体识别算法RepeatSearcher和GSRSearcher,这两个算法的共同点在于都是基于对种子序列扩展的识别算法。RepeatSearcher算法的核心是对包含种子的序列通过双序列局部比对构建多序列局部比对,结合限定范围的空位罚分策略,通过比对得分值扩展调和序列,同时扩展每一个重复体序列。这种方法的优点在于在扩展调和序列的同时可以确定每一个重复体序列的精确边界。构建多序列局部比对在很大程度上防止了基于高分相似对算法的边界不精确性。GSRSearcher算法继承了算法RepeatSearcher基于种子序列扩展的特点,结合Gibbs采样统计方法,综合考虑了基因组中背景碱基对结果的影响,使识别出来的重复体家族序列更加精确。通过概率统计策略的GSRSearcher算法收敛速度明显比通过比对的算法RepeatSearcher更合理,而且可以判断出重复体序列的精确边界。本文最后使用这两个算法测试了12种哺乳动物的部分基因组序列,将实验结果和重复体数据库RepBase以及当前流行的算法RECON的结果进行了比较,结果表明:本文提出的算法在大部分情况下均优于RECON算法的结果,是一种高效的重复体识别算法。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 重复体识别问题的发展和现状
• 1.3 本文的研究工作
• 1.4 本文各章节安排
• 第二章 生物信息学重复体识别
• 2.1 重复体识别概述
• 2.1.1 重复体识别问题
• 2.1.2 局部序列比对及其相关问题
• 2.1.3 调和序列
• 2.1.4 重复体识别结果的评判标准
• 2.2 重复体识别算法
• 2.2.1 基于已知重复体数据库的重复体识别算法
• 2.2.2 基于序列比对的重复体识别算法
• 2.2.3 其它重复体识别算法
• 2.3 本章小结
• 第三章 基于BLAST的重复体识别算法
• 3.1 BLAST算法简介
• 3.1.1 BLAST算法过程
• 3.2 基于BLAST的RepeatSearcher重复体识别算法
• 3.2.1 算法的引入
• 3.2.2 算法的描述
• 3.2.2.1 目标函数的定义
• 3.2.2.2 比对得分函数计算
• 3.2.2.3 比对过程及其优化
• 3.2.2.4 算法实现
• 3.2.3 算法分析
• 3.2.4 实验结果及性能分析
• 3.2.4.1 实验结果
• 3.2.4.2 结果分析
• 3.3 本章小结
• 第四章 基于概率统计的重复体识别算法
• 4.1 Gibbs 采样算法
• 4.1.1 Gibbs采样算法数学背景
• 4.1.2 多序列比对中的Gibbs采样算法
• 4.2 GSRSearcher算法的引入
• 4.3 GSRSearcher算法描述
• 4.3.1 目标函数的定义
• 4.3.2 种子序列的扩展过程
• 4.3.3 算法实现
• 4.4 算法分析
• 4.5 实验结果及性能分析
• 4.5.1 实验结果
• 4.5.2 结果分析
• 4.6 本章小结
• 第五章 结论与展望
• 致谢
• 参考文献
• 研究成果