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

A Motif Finding Algorithm Based on Color Coding Technology

作　　者：王建新[1] 黄元南[1] 陈建二[1] 

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410083

出　　处：《软件学报》2007年第6期1298-1307,共10页Journal of Software

基　　金：国家自然科学基金Nos.30370418;90209008;60302016;60532050;30500131;国家杰出青年科学基金No.60225008;海外杰出青年研究基金No.30528027;北京市自然科学基金Nos.4051002;4042024~~

摘　　要：从DNA序列中发现基序是生物计算中的一个重要问题,序列条数K=20包含基序用例的序列条数k=16的(l,d)-(K-k)问题(记作(l,d)-(20-16)问题)是目前生物学家十分关注的基序发现问题.针对该问题提出了一种基于彩色编码技术的SDA(sample-driven algorithm)搜索算法——彩色编码基序搜索算法(color codingmotif finding algorithm,简称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.Finding common pattern, motifs or signals, in a set of DNA sequences is an important problem in computational biology. Recently, some biologists extremely focus on the （l,d）-（K-k） motif finding problem when the number of sequences K is 20 and the number of sequences with instances k is 16, （l,d）-（20-16） problem for short. For solving this problem, this paper introduces a novel sample-driven algorithm （SDA）, called color coding motif finding algorithm, CCMF for short. It uses color coding technology to converse a （l,d）-（20-16） problem to some （l,d）-（16-16） problems, then uses divide-and-conquer and branch-and-bound approaches to solve this （l,d）-（16-16） problem. Using the conversion process can reduce 4 845 combinations to 403 colorings, while increasing the running rate enormously. The experimental results on synthetic and real datasets show that the CCMF algorithm can accurately and efficiently find all （l,d）-（20-16） patterns and instances. Its comprehensive performances in finding motifs are superior to those of other existing algorithms. It is applicable for real biological purpose. The color coding technology can also be used to improve the performances of other similar （l,d）-（K-k） problems when k is less than K.

关 键 词：彩色编码技术 基序发现 着色 (l d)-(K-k)问题 算法优化 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]