生物序列近似频繁模式挖掘研究

摘要

随着生物信息学的快速发展，人类基因、蛋白质测序的实施和完成，积累了大量的生物数据。从生物数据中挖掘频繁模式有助于发现生物序列中潜在的信息、生物基因和蛋白质同源性的检测等。生物序列中频繁模式的挖掘已经成为生物信息领域研究的重要任务。本文深入研究了生物序列中带可变长度间隔约束的近似频繁模式挖掘问题，序列之间相似性的度量使用了编辑距离和生物字符间的评分。此外，本文定义了插入、替换和删除字符三种近似操作，克服了已有的近似频繁模式挖掘算法仅仅包含替换字符一种近似操作的不足。本文的主要工作如下:
　　(1)给出了包含插入、替换和删除字符的三种近似操作的定义，及近似模式匹配与挖掘的相关定义。为了使用模式的出现频率判断该模式是否是频繁模式，本文给出了近似模式匹配中补偿序列数（Nl,editmax）的推导。由于带可变长度的近似频繁模式挖掘具有较大的候选解空间，本文设计了Apriori-like剪枝策略用于降低候选解空间的维度。
　　(2)本文基于编辑距离度量序列间的相似性，设计了编辑距离矩阵(A-EDM)和其构造函数，编辑距离矩阵记录了模式子字符串与序列子字符串之间的最小编辑距离（误差）。在A-EDM的基础上，本文设计了候选模式解集合的矩阵结构(MST)和近似模式匹配算法(APM)计算模式在序列中的近似出现次数和出现位置。然后本文给出了近似频繁模式挖掘算法(MAPA)，当编辑距离阈值editmax=0时，MAPA算法转变为精确频繁模式挖掘算法。
　　(3)为了对生物序列频繁模式的挖掘更具有针对性，本文在编辑距离约束的基础上结合了生物字符的评分矩阵，设计了模式与序列之间的匹配得分矩阵(MSM)，MSM中记录了模式子字符串与序列子字符串之间的最大匹配得分。基于MSM，本文设计了针对生物序列的近似模式匹配方法(S-APM)，S-APM采用回溯MSM的方式计算模式在序列中的近似出现次数。随后本文给出了针对生物序列的近似频繁模式挖掘算法(MAPS)和多序列共同频繁模式挖掘算法（co-fp-miner）。co-fp-miner算法中对Apriori-like剪枝规则进行了改进，设计了Pruning剪枝策略，Pruning剪枝策略具有较好的剪枝效果。实验验证本文提出的算法较经典的精确频繁模式挖掘算法MPP和近似频繁模式挖掘算法ArpGap具有较好的性能和解的优势。

目录

声明

致谢

摘要

第一章 绪论

1．1 引言

1．2 课题来源及本文主要研究内容

1．3 本文组织结构

1．4 本章小结

第二章 相关工作概述

2．1 模式匹配问题的研究现状

2．1．1 精确模式匹配问题

2．1．2 近似模式匹配问题

2．1．3 带通配符和间隔约束的模式匹配问题

2．2 模式挖掘问题的研究现状

2．2．1 精确模式挖掘问题

2．2．2 近似模式挖掘问题

2．3 本章小结

第三章 基于编辑距离的近似频繁模式挖掘的研究

3．1 问题的定义

3．2 构造近似编辑距离矩阵

3．3 近似Apriori剪枝原理

3．3．1 补偿序列数码Nl，editmax的计算

3．3．2 确定性剪枝原理(Apriori—like性质)

3．4 算法设计

3．4．2 APM方法获取模式的支持度

3．4．3 MAPA算法挖掘近似频繁模式

3．5 实验结果分析

3．5．1 带通配符间隔约束的精确频繁模式挖掘

3．5．2 带通配符间隔约束的近似频繁模式挖掘

3．5 本章小结

第四章 基于匹配得分矩阵的生物序列频繁模式挖掘

4．1 问题定义

4．2 近似匹配得分矩阵MSM

4．3 S—APM算法计算模式的近似支持度

4．4 单序列频繁模式挖掘算法MAPS

4．5 多序列共同频繁模式挖掘算法co—fp—miner

4．5．1 Pruning剪枝规则

4．5．2 共同频繁模式挖掘算法co-fp-miner

4．6 实验结果与分析

4．6．1 MAPS与ArpGap在DNA上近似挖掘的比较

4．6．2 MAPS与ArpGap在蛋白质近似挖掘上的比较

4．6．3 MAPS关于序列长度的时间和空间趋势实验

4．6．4 co-fps-miner算法在多序列模式挖掘的效果展示

4．6．5 co-fps-miner算法Pruning剪枝的有效性验证

4．6．6 co-fps-miner与MPP和ArpGap在多序列模式挖掘上的比较

4．7 本章小结

第五章 总结与展望

5．1 工作总结

5．2 工作展望

参考文献

攻读硕士学位期间的学术活动及成果情况