一种基于彩色编码技术的基序发现算法

从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.