基于分步查找的高效复合模式查找算法

摘要

复合模式查找是生物信息学中模式发现问题的一个新的研究领域，而寻求效率更高，精度更高的复合模式查找算法将是复合模式研究领域的长期热点与目标。本文对此进行了深入的研究和探讨。
　　 本文深入研究了当今国际上的各种复合模式查找算法，系统地阐述了最具代表性的MITRA-Dyad算法和RISO算法。同时，由于本文实现的算法需要用到单分体模式查找算法，故对当今流行的单分体模式查找算法进行了简要的介绍，分析了各算法的优缺点，并对本文使用到的MITRA-Count单分体模式查找算法进行了系统阐述。
　　 ECOMP算法是一种使用错配树数据结构的复合模式分步查找算法。本文针对复合模式的一种简单形式-二分体模式的特点进行研究，通过对：ECOMP算法的理论分析和实验测试，证明ECOMP算法可以应用于实际的复合模式查找问题。同时，由于ECOMP算法的第一部分MITRA-Count算法的设计机制，导致其运行速度和空间占用方面都存在低效性的特点，本文将对错配树的递归遍历方式改进为基于栈式节点存储的非递归遍历方式，从而提高了MITRA-Count的运行速度，减少了空间占用。另一方面，本文还对ECOMP算法的第二部分，即将单分体模式组合为复合模式的部分进行了空间优化，减少了算法实现时的内存开销，并通过模拟数据和真实数据的测试证明了本文对ECOMP算法改进的有效性。

目录

文摘

英文文摘

第一章 绪论

1.1 引言

1.2 模式查找问题概述

1.3 复合模式查找问题概述

1.4 本文所做的工作

第二章 复合模式查找基础

2.1 单分体模式问题描述

2.1.1 单分体模式问题定义

2.1.2 单分体模式查找问题研究现状

2.2 复合模式问题定义

2.3 复合模式查找问题研究现状

2.3.1 MITRA-Dyad算法

2.3.2 RISO算法

2.4 本章小结

第三章 ECOMP算法研究

3.1 MITRA-Count算法

3.1.1 错配树

3.1.2 MITRA-Count算法概述

3.1.3 MITRA-Count实现

3.2 ECOMP算法

3.2.1 ECOMP算法概述

3.2.2 ECOMP实现

3.3 复杂度分析

3.4 本章小结

第四章 改进的ECOMP算法

4.1 MITRA-Count实现改进

4.2 ECOMP实现改进

4.3 本章小结

第五章 实验结果与分析

5.1 模拟数据实验结果

5.2 真实数据实验结果

5.3 实验结果分析

5.4 本章小结

第六章 结束语

致谢

参考文献