设为首页 - 加入收藏
广告 1000x90
您的当前位置:188144com黄大仙救世网 > 近似匹配 > 正文

支持编辑距离约束的近似最长公共子串匹配及其优化算法

来源:未知 编辑:admin 时间:2019-07-28

  支持编辑距离约束的近似最长公共子串匹配及其优化算法_电子/电路_工程科技_专业资料。目前许多信息都以文本的形式存放在计算机中,所以基于文本的信息检索技术,如最长公共子串匹配问题一直是文本管理、程序分析等领域的经典问题,长期以来受到广泛地关注与研究。br 然而最长公共子串的要求过于严格,在实际应用中,两个局部非常相似的文本其中的公共部分往往不是完全精

  东北大学硕士学位论文 目 录 目 录 独创性声明…………………………………………………………………I 摘要………………………………………………………………………II Abstract…………………………………………………………………………………….III 第1章绪论………………………………………………………………1 1.1研究背景……………………………………………………………………………….1 1.2本文的研究内容及面临的挑战……………………………………………………….3 1.3本文的贡献…………………………………………………………………………….4 1.4本文的组织结构……………………………………………………………………….4 第2章背景知识与问题定义……………………………………………7 2.1编辑距离……………………………………………………………………………….7 2.2最长公共子串………………………………………………………………………….8 2.3最长公共子序列……………………………………………………………………….9 2.4后缀数组………………………………………………………………………………10 2.5近似最长公共子串的问题定义………………………………………………………13 2.6本章小结………………………………………………………………………………14 第3章相关工作…………………………………………………………15 3.1基于最长公共子序列的比对算法……………………………………………………15 3.1.1 3.1.2 Needlem肌.Wunsch算法…………………………………………………………l 5 Smith-Watenllan算法…………………………………………………………….16 3.2基于scoring scheme的比对算法……………………………………………………19 3.2.1 3.2.2 3.2.3 BLAST算法………………………………………………………………………………………………l 9 BWT-SW算法…………………………………………………………………….20 ALAE算法………………………………………………………………………一21 3.3本章小结………………………………………………………………………………24 第4章基于动态规划的方法……………………………………………25 一V一 万方数据 万方数据 东北大学硕士学位论文 目 录 参考文献………………………………………………………………….59 致 谢…………………………………………………………………….63 攻硕期间参加的项目及获奖情况……………………………………….65 一VII 万方数据 一VIII— 万方数据 东北大学硕士学位论文 第l章绪论 第1章绪论 近似文本比对技术在生物信息学领域和信息检索领域有广泛应用。与精确比对不同 的是,近似文本比对找到的结果不是精确的而是相似的。度量近似文本的相似性是这项 技术中的基础。本文的主要研究内容是如何高效地将两个字符串进行局部的相似性比对 并找出这两个字符串的支持编辑距离约束的近似最长公共子串。 1.1研究背景 随着计算机技术的发展以及生物信息技术的进步,越来越多的如基因和蛋白质这样 的生物信息数据被存储到生物序列数据库中,因此研究有效的技术来对这些大规模数据 进行分析愈来愈受到学术界的重视。生物序列模式通常对应着生物学中一些重要的结构 或重要功能元素,发现这些重要的生物序列模式在生物信息学中具有重要意义,它是开 展非编码区功能元素识别、基因组注释、转录调控分析、基因家族分析等研究的基础工 作。 近似子串查询的技术,即从长串中得到与查询相同或近似的子串,在基因数据分析, 信息检索和数据库等许多领域都具有重要应用。基因数据分析中非常重要的一个方面就 是短序列比对问题(short read alignment)。该问题的本质是近似子串查询问题,即在长串 中对一系列长度相同的短串进行近似查询。例如,当需要寻找导致人类产生某种疾病的 变异基因时,将公共的人类基因作为基准序列(长串),可能发生变异的基因作为短序 列(短串)进行查询。这样得到的分析结果可最终用于新药的研发和针对个人的药物推 荐。 在信息检索领域,最关心的问题是如何能够快速全面的找到用户感兴趣和有价值的 信息。但由于各种信息的不一致和不准确性,简单的精确查询已经不能满足用户需求, 功能更强大的近似查询一直是研究的热点。而近似子串查询技术作为近似查询的一个方 面,也收到广泛关注。任何非结构化的文本都可以看做一个由字符构成的长序列,如果 能够在该长序列中找到与查询关键字的相似性满足用户要求的子串,也就是实现了近似 查询的功能。 近似文本比对技术在计算机的多个领域有广泛应用。在生物信息学领域,为了判断 两个DNA序列或蛋白质序列的同源关系,研究者需要将它们进行相似性比对【11。在生 物进化过程中,发生基因突变的那部分在功能上会变得不重要。而那些功能重要的部分 万方数据

本文链接:http://storkroadfarm.com/jinsipipei/237.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top