| 摘要: |
| 从DNA序列中发现基序是生物计算中的一个重要问题,序列条数K=20包含基序用例的序列条数k=16的(l,d)-(K-k)问题(记作(l,d)-(20-16)问题)是目前生物学家十分关注的基序发现问题.针对该问题提出了一种基于彩色编码技术的SDA(sample-driven algorithm)搜索算法--彩色编码基序搜索算法(color coding motif finding algorithm,简称CCMF算法).它利用彩色编码技术将该问题转化为(l,d)-(16-16)问题,再采用分治算法和分支定界法来求解.在解决将(l,d)-(20-16)问题转化为(l,d)-(16-16)问题时,CCMF算法利用彩色编码技术将4 845个组合降低到403个着色,这将极大地提高算法的整体运行效率.使用模拟数据和生物数据进行测试的结果表明,CCMF算法能够快速发现所有(l,d)-(20-16)问题的基序模型和基序用例,具有优于其他算法的综合性能评价,能够用于真实的基序发现问题.同时,通过修改着色方案,CCMF算法可以用于求解一般的(l,d)-(K-k)问题,其中,k＜K. |
| 关键词: 彩色编码技术 基序发现 着色 (l,d)-(K-k)问题 算法优化 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.30370418, 90209008, 60302016, 60532050, 30500131 (国家自然科学基金); the Project for National Science Fund for Distinguished Young Scholars of China under Grant No.60225008 (国家杰出青年科学基金); the Joint Research Fund for Overseas Chinese Young Scholars under Grant No.30528027 (海外杰出青年研究基金); the Beijing Natural Science Foundation under Grant Nos.4051002, 4042024 (北京市自然科学基金) |
|
| A Motif Finding Algorithm Based on Color Coding Technology |
|
WANG Jian-Xin,HUANG Yuan-Nan,CHEN Jian-Er
|
| Abstract: |
| 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. |
| Key words: color coding technique motif finding coloring (l,d)-(K-k) problem algorithm optimization |
