基于TF-IDF的基因序列特征提取算法研究开题报告

全文总字数：3580字

1. 研究目的与意义

随着人类基因组计划(hgp)的完成，基因组序列迅猛的增长，吸引了越来越多的研究人员对全基因组的系统发生树的注意。目前越来越多的研究倾向于使用全基因组进行系统发育分析，因为这考虑了所有的生物特征并可作为所有生物的共同指标。从生物的基因组角度研究物种间的进化关系，才能获得更加全面的关于进化的信息。

全基因组dna序列测定是生物信息学研究的基础，在普遍使用的shotgun方法中，其中一个重要的步骤就是根据片段信息来重构原始序列。片段拼接是一个费时的复杂过程，其中包含了一些实际困难，重复子序列对片段间正确重叠的干扰就是其中一个。关于基因组的研究中还没有出现象在其他科学问题(如力学、核物理等)中出现的表征了某些运动或演化规律的方程式，没有建立起有效的数学物理模型，对问题的处理属数据密集，这时就要对重复序列进行基因序列特征提取来去除重复的序列。

基因序列特征提取问题虽然有理论上的组合数学模型，但不能得到有效的处理，因此就需要转化为其它问题并作一定的简化。要处理的数据的成份中实质上的非数值运算远多于数值运算，而在非数值并行计算领域的对此有益研究成果并不多见。测序所得原始数据的出现是随机的且总体上的相关性比较大，重复片段(repeats)对拼接结果的影响较大，如何在理论上分析这些特征从而在实际中避免和消除相关，正确匹配重复片段，是一个国际公认的难题。

2. 国内外研究现状分析

对于tfidf算法的研究情况，目前国际上主要将该算法应用于以下几大方面：

1.特征选择：tfidf算法最初为了计算权重而提出的，但其在特征选择时也颇受青睐。一种简单的方法，即把词条的tfidf权值高于一定值的词条选作特征项(词)。另一类方法是变换idf函数，包括：1)改进idf函数；2)用特征选择函数(例如：互信息、期望交叉熵等)来替代idf函数；3)引入新的因子来改进tf]df算法以适应特征选择。

2.领域词典构造领域词典可以方便读者查询领域知识，但其编撰非常耗时，并需要领域专家的参与。领域词典的更新维护也比较困难。一个单词在前景语料(我们需要的类别的文档)中出现的次数越多，在背景语料(其他类别的文档)出现的次数越少，则说明该词很好地体现了该类别。因此，领域特征词语的获取实际上是利用tfidf算法来计算词语在不同领域文档中的权重值，将权值大的特征词作为该领域的领域词汇。

3. 研究的基本内容与计划

研究内容：

全基因组dna序列测定是生物信息学研究的基础，在普遍使用的shotgun方法中，其中一个重要的步骤就是根据片段信息来重构原始序列。片段拼接是一个费时的复杂过程，其中包含了一些实际困难，重复子序列对片段间正确重叠的干扰就是其中一个。本论文主要研究在基因测序过程中遇到的有关片段拼接内容的算法，从而降低片段拼接的难度。

1.利用tfidf算法特征提取：

4. 研究创新点

tf/idf的概念被公认为信息检索中最重要的发明。tfidf算法最初为了计算权重而提出的，但其在特征选择时也颇受青睐。而我们在这里提出将tfidf算法作为一种基因序列特征提取，不管是从大量的文本中提取关键字，还是从重复的基因序列中提取特征值，从本质上也都是对数据的深层挖掘，相信这一算法能够很好的实现基因序列特征提取这一功能。

而传统的拼接过程算法实际上将问题转化为图论中寻找图的hamilton路径的问题，造成了重复片段(repeat)错误匹配，时间效率较低，结果精度不易控制等后果，片段拼接方法的计算局部性较差，并行难度大。

同时，在研究过程中我们采用对每一个reads进行16个字符截取字符串，并将截取下来的字符串作为字典库，该字典库及对应tfidf的总词数和文档数。通过该方法计算每个公共字符串的特征值。通过这样的序列截取，能够是我们的算法更加准确。