论文部分内容阅读
从生物序列中发现基序是生物信息学中一个的热点研究问题,也是生物学中理解基因调控的最重要的基础计算问题之一。随着生物技术的迅速发展,人们不断地对最初的基序发现问题的计算模型进行改进,并针对不同的计算模型提出了许多求解基序发现问题的算法。
本文首先对已有的各类基序发现问题算法进行综述,详细介绍基序发现问题算法中基序模型表示方式、计分模型和评价指标等相关内容,分析三类经典基序发现问题算法的基本思想和特点。本文选取九个经典的求解植入基序问题(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)的基序模型,具有优于其他算法的综合性能评价,能够用于真实的基序发现问题。
本文最后对基序发现问题算法研究工作进行了总结,并阐述了将来对生物计算中相关问题进一步研究的一些工作。