%0 Journal Article
%T 一种基于彩色编码技术的基序发现算法
%A 王建新？
%A 黄元南？
%A 陈建二？
%J 软件学报
%P 1298-1307
%D 2007
%X 从dna序列中发现基序是生物计算中的一个重要问题,序列条数k=20包含基序用例的序列条数k=16的(l,d)-(k-k)问题(记作(l,d)-(20-16)问题)是目前生物学家十分关注的基序发现问题.针对该问题提出了一种基于彩色编码技术的sda(sample-drivenalgorithm)搜索算法--彩色编码基序搜索算法(colorcodingmotiffindingalgorithm,简称ccmf算法).它利用彩色编码技术将该问题转化为(l,d)-(16-16)问题,再采用分治算法和分支定界法来求解.在解决将(l,d)-(20-16)问题转化为(l,d)-(16-16)问题时,ccmf算法利用彩色编码技术将4845个组合降低到403个着色,这将极大地提高算法的整体运行效率.使用模拟数据和生物数据进行测试的结果表明,ccmf算法能够快速发现所有(l,d)-(20-16)问题的基序模型和基序用例,具有优于其他算法的综合性能评价,能够用于真实的基序发现问题.同时,通过修改着色方案,ccmf算法可以用于求解一般的(l,d)-(k-k)问题,其中,k＜k.
%K 彩色编码技术
%K 基序发现
%K 着色
%K (l
%K d)-(k-k)问题
%K 算法优化
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=20070605&flag=1