K-前缀树全文搜索方法及其应用

摘要

在科学技术高速发展和信息爆炸式膨胀的时代，如何快速和有效的从海量信息中获取有用信息是信息检索技术主要的研究课题。当前应用广泛的后缀树和后缀数组全文搜索方法在搜索速度和计算空间方面各有特点和局限，本文正是针对此问题提出了K-前缀树全文搜索方法。 K-前缀树全文搜索方法是一种基于前缀树且能够对内容长度不大于K的字串进行搜索的文本全文搜索方法，其主要特点是使用K子串来构建前缀树，使得最大空间复杂度为O(Zk+1)，并具有折中后缀数和后缀数组在计算空间和搜索速度上的优点。通过与广泛应用的后缀树和后缀数组两种全文搜索方法的计算比较，说明了K-前缀树全文搜索方法在计算空间和搜索速度上具有良好的综合性能。 载体识别是生物信息学中一项基础而重要的任务，对去除EST序列中的污染和提取cDNA inset具有重要作用。本文针对植物EST序列的载体识别问题，基于EST序列期望结构给出了EST序列的载体结构描述，由此结合K-前缀树全文搜索方法提出了基于K-前缀树的EST序列载体识别方法，其主要特点是基于EST序列载体结构来构建K-前缀树，并以K-前缀树进行K子串的匹配、扩展和合并。通过对172229条松树EST序列的载体识别，说明了基于K-前缀树的EST载体识别方法的可行性和有效性。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景

1.2研究现状

1.3本文的主要工作

1.4本文的组织结构

第二章基于前缀树的搜索方法

2.1基本概念

2.2前缀树与后缀树

2.3前缀树与后缀树的比较

2.3.1前缀树与后缀树的共同点

2.3.2前缀树与后缀树的差异

2.4前缀树与后缀树的应用与研究

第三章K-前缀树全文搜索方法

3.1 K-前缀树

3.2创建

3.2.1简单的创建方法

3.2.2优化的创建方法

3.3搜索

3.4方法特点

第四章与后缀树和后缀数组全文搜索方法的比较

4.1全文搜索

4.2后缀数组全文搜索方法

4.2.1后缀数组

4.2.2后缀数组与后缀树比较

4.2.3后缀数组的研究与应用

4.3比较实验

4.3.1 K-前缀树全文搜索方法程序设计

4.3.2实验结果

4.3.3结果分析

第五章K-前缀树在载体识别中的应用

5.1载体识别背景

5.1.1生物信息学

5.1.2序列比对

5.1.3载体识别

5.2 EST序列的期望结构与载体结构

5.2.1生物学基础知识

5.2.2 EST序列的载体结构

5.3基于K-前缀树的EST序列载体识别方法

5.2.1建立载体K-前缀树

5.2.2使用K-前缀树载体识别

5.4 K-前缀树载体识别实验

5.4.1基于K-前缀树载体识别方法程序设计

5.4.2实验结果及分析

第六章总结与展望

6.1总结

6.2展望

参考文献

致谢