基因组最长带恢复问题的核心化算法研究

发布时间：2022-11-05 15:12

　　计算基因组学中许多问题都是NP难问题,人们可以利用近似算法、启发式算法、随机算法来解决这些问题。但是,计算基因组学归根究底的研究目的是为生物学、药理学、病理学做贡献,这些领域关乎生命,所以问题的解必然是越精确越好。因此,参数化算法在解决计算基因组学问题时不失为一种好方法。对遗传信息进行数据分析之前,需要保证基因图谱中没有冗余数据和干扰数据。最长带恢复问题（Maximal Strip Recovery,简称为MSR）就是对基因图谱中的数据进行处理,使之没有错误和模糊的干扰数据。其补问题（Complementary Maximal Strip Recovery,简称为CMSR）与其等价。本文主要针对CMSR问题进行具体的核心化算法研究,提出了改进的核心化算法,具体的研究内容包括:首先,对于参数计算与复杂性理论的发展背景进行了简单的介绍,同时对于我们所研究的CMSR问题介绍了相关理论和技术,比如参数算法和核心化技术的相关理论。其次,本文根据当前关于CMSR问题最好结果的核心化思想,进一步分析了 CMSR问题的结构特性,提出了新的更有助于分析的辅助图,我们在每一个同源块之间生成边而不是每个超级... 

【文章页数】：59 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第一章 绪论
    1.1 研究背景
    1.2 研究内容
    1.3 研究意义
    1.4 组织结构
第二章 参数计算及核心化技术介绍
    2.1 参数计算及复杂性理论概述
    2.2 核心化技术介绍
        2.2.1 基于最大匹配的核心化技术
        2.2.2 线性规划技术
        2.2.3 皇冠分解技术
        2.2.4 极值归纳技术
        2.2.5 随机方法
    2.3 本章小结
第三章 最长带恢复问题的42K核心化算法
    3.1 问题介绍
    3.2 核心化算法
        3.2.1 相关术语
        3.2.2 简化规则
        3.2.3 核大小分析
    3.3 本章小结
第四章 最长带恢复问题的26K核心化算法
    4.1 己有规则和相关术语
    4.2 新规则
    4.3 优化的核
    4.4 本章小结
第五章 总结与展望
    5.1 主要贡献和创新点
    5.2 展望
参考文献
致谢
附录A 攻读硕士学位期间所发表的学术论文及成果
附录B 攻读硕士学位期间参加的项目


【参考文献】：
期刊论文
[1]参数计算中核心化技术及其应用[J]. 李绍华,王建新,冯启龙,陈建二.  软件学报. 2009(09)
[2]P2-Packing问题参数算法的改进[J]. 王建新,宁丹,冯启龙,陈建二.  软件学报. 2008(11)



本文编号：3702836