生物信息学中的基序发现问题算法研究

摘要

从生物序列中发现基序是生物信息学中一个的热点研究问题，也是生物学中理解基因调控的最重要的基础计算问题之一。随着生物技术的迅速发展，人们不断地对最初的基序发现问题的计算模型进行改进，并针对不同的计算模型提出了许多求解基序发现问题的算法。 本文首先对已有的各类基序发现问题算法进行综述，详细介绍基序发现问题算法中基序模型表示方式、计分模型和评价指标等相关内容，分析三类经典基序发现问题算法的基本思想和特点。本文选取九个经典的求解植入基序问题(PMP)的(l,e)问题的算法进行标准测试，并分析测试结果的综合性能。 在研究中发现，扩展的基序问题(EMP)中的(l,e)-(20-16)问题是目前生物学家十分关注的基序发现问题。针对这个具体的问题，本文提出了一种基于彩色编码技术的样本驱动(SD)搜索算法——彩色编码基序发现算法(Color Coding Motif Finding Algorithm，CCMF算法)。它利用彩色编码技术将(l,e)-(20-16)问题转化为序列条数t=16的(l,e)问题(记作(l,e)-(16-16)问题)，再采用分治算法和分支定界法来求解(l,e)-(16-16)问题。在解决将(l,e)-(20-16)问题转化为(l,e)-(16-16)问题时，CCMF算法利用彩色编码技术将4845个组合降低到403个着色，将能极大减少用分治算法和分支定界法求解(l,e)-(16-16)问题的次数，从而明显提高整个算法的运行效率。测试结果表明，CCMF算法能快速发现所有(l,e)-(20-16)的基序模型，具有优于其他算法的综合性能评价，能够用于真实的基序发现问题。 本文最后对基序发现问题算法研究工作进行了总结，并阐述了将来对生物计算中相关问题进一步研究的一些工作。

目录

文摘

英文文摘

原创性声明及关于学位论文使用授权说明

第一章绪论

第二章基序发现问题算法综述

第三章一种基于彩色编码技术的基序发现问题的算法

第四章结束语

参考文献

致谢

攻读硕士期间主要的研究成果