寡核苷酸芯片的逐步探针选取算法

doi:10.3969/j.issn.1000-3428.2010.22.011

计算机工程 ›› 2010, Vol. 36 ›› Issue (22): 32-33.doi: 10.3969/j.issn.1000-3428.2010.22.011

寡核苷酸芯片的逐步探针选取算法

彭胜蓝1，周一鸣2

(1. 景德镇陶瓷学院信息工程学院，江西景德镇 333403；2. 清华大学生物科学与技术系，北京 100084)

出版日期:2010-11-20 发布日期:2010-11-20
作者简介:彭胜蓝(1975－)，男，博士，主研方向：生物信息学；周一鸣，博士
基金项目:
国家自然科学基金资助项目(60961003)

Stepwise Probe Selection Algorithm for Oligonucleotide Array

PENG Sheng-lan1, ZHOU Yi-ming2

(1. School of Information Engineering, Jingdezhen Ceramic Institute, Jingdezhen 333403, China;2. Department of Biological Sciences & Biotechnology, Tsinghua University, Beijing 100084, China)

Online:2010-11-20 Published:2010-11-20

摘要/Abstract

摘要：

探针集的挑选是寡核苷酸芯片设计过程中最重要的部分。基于合成探针成本的考虑，探针的个数成为评价探针集优劣的一个最重要的指标。一个好的探针挑选算法应该挑选出尽可能少的探针。为此，对探针选取的贪心算法作了改进，提出一个类似于逐步向前回归算法的探针选取算法。该算法在每次向探针集加入边际效用最大的探针的同时，把边际效用没有或者很小的探针从探针集中剔除出去。对HLA等位基因数据的实验结果表明，逐步选取算法得到的探针集优于贪心算法挑选出的探针集。

关键词: 基因分型, 寡核苷酸芯片, 探针选取问题, 贪心算法, 逐步算法

Abstract:

Probe selection plays an essential role in the procedure of designing oligonucleotide array. Considering the cost of synthesizing probes, the size of probe set becomes the most important criterion to evaluate the probe set. A good probe selection algorithm should produce a small number of probes as possible. This paper makes an improvement for the greedy algorithm of Herwig’s which is based on Shannon entropy as a quality criterion. The new algorithm is similar to the forward stepwise regression search algorithm. While adding the probes with maximal marginal effect, those probes with little marginal effect are dropped from the optimization set. Experimental results making on the data sets of HLA alleles show that the probe set produced by the algorithm is superior to the probe set selected by greedy algorithm.

Key words: genotyping, oligonucleotide array, probe selection problem, greedy algorithm, stepwise algorithm

中图分类号:

TP311

彭胜蓝, 周一鸣. 寡核苷酸芯片的逐步探针选取算法[J]. 计算机工程, 2010, 36(22): 32-33.

BANG Qing-La, ZHOU Yi-Ming. Stepwise Probe Selection Algorithm for Oligonucleotide Array[J]. Computer Engineering, 2010, 36(22): 32-33.

参考文献

[1]	Drmanac S, Stavropoulos N, Labat I, et al. Gene-representation cDNA Clusters Defined by Hybridization of 57419 Clones from Infant Brain Libraries with Short Oligonucleotide Probes[J].Genomics.1996, 37(5):29-40
[2]	Cuticchia A, Arnold J, Timberlake W. PCAP: Probe Choice and Analysis Package——A Set of Programs to Aid in Choosing Synthetic Oligomers for Contig Mapping[J]. Comput. Appl. Biosci., 1993, 9(2): 201-203.
[3]	Fu Y, Timberlake W, Arnold J. On the Design of Genome Mapping Experiments Using Short Synthetic Oligonucleotides[J].Biometrics.1992, 48(2):337-359
[4]	Li F, Stormo G. Selection of Optimal DNA Oligos for Gene Expression Arrays[J].Bioinformatics.2001, 17(11):98-99
[5]	Herwig R, Schmitt A, Steinfath M, et al. Information Theoretical Probe Selection for Hybridization Experiments[J].Bioinformatics.2000, 16(10):890-898
[6]	Borneman J, Chrobak M, Della V, et al. Probe Selection Algorithms with Applications in the Analysis of Microbial Communities[J]. Bioinformatics, 2001, 17(1): 39-48.
[7]	Zhou Y, Peng S, Gao H, et al. Probe Selection Algorithm for Oligonucleotide Array-based Medium-resolution Genotyping[J].Medical & Biological Engineering & Computing.2004, 42(6):812-816
[8]	Hochbaum D. Approximation Algorithms for NP-hard Problems[M]. Boston, USA: PWS Publishing, 1997,
[9]	韦小丽, 孙涌, 张书奎, 等. 基于最大熵模型的本体概念获取方法[J].计算机工程.2009, 35(24):114-116 浏览

[1]	杨奔, 王炜晔, 赵婉婷, 谢瑾奎. 基于DQN的动态深度多分支搜索自动配载算法[J]. 计算机工程, 2020, 46(8): 313-320.
[2]	郑金金,罗志年. LTE-A系统载波聚合下基于贪心算法的资源管理[J]. 计算机工程, 2017, 43(11): 50-54.
[3]	吕天航,刘勤让,赵博. 基于贪心算法的3D-Mesh片上网络层间互联结构[J]. 计算机工程, 2016, 42(9): 52-57.
[4]	魏浩,陈华锋,陈军. 基于路径覆盖的城市监控摄像网络优化部署方法[J]. 计算机工程, 2016, 42(5): 269-274.
[5]	张翔,朱明,孙吟龙,方雪峰. 网络电视直播中的虚拟频道生成算法[J]. 计算机工程, 2015, 41(12): 236-240.
[6]	凌权,李枚毅. 无线Mesh网络中骨干节点部署算法研究[J]. 计算机工程, 2015, 41(11): 147-152.
[7]	程权, 廖名学, 胡晓惠, 何晓新. 超短波无线网络规划方法研究[J]. 计算机工程, 2013, 39(2): 61-66.
[8]	张佩云，宫秀文. 基于概率转移矩阵的社会网络影响最大化算法[J]. 计算机工程, 2013, 39(11): 41-45,51.
[9]	徐云峰, Rudolf Fleischer. 求解区间图K-连接最短路径问题的在线算法[J]. 计算机工程, 2012, 38(11): 51-52,55.
[10]	陈光平. 传感器网络节点选择的分布式在线算法[J]. 计算机工程, 2012, 38(10): 95-98.
[11]	翁鸣, 王吴静. 基于报童模型和贪心算法的订货管理系统[J]. 计算机工程, 2012, 38(01): 261-263,267.
[12]	孙泽宇, 邢萧飞, 魏巍. 无线传感器网络中的目标关联覆盖算法[J]. 计算机工程, 2011, 37(9): 138-140,143.
[13]	张志远, 徐涛, 冯霞. 航班信息抽取规则的自动生成技术[J]. 计算机工程, 2011, 37(6): 65-67.
[14]	刘高峰, 牟廉明, 张涛. 基于改进区分矩阵的决策表增量式属性约简[J]. 计算机工程, 2010, 36(20): 46-48.
[15]	陆王红;曹永忠;张剑峰. 基于Web的新城疫病毒基因分型系统[J]. 计算机工程, 2009, 35(4): 255-257.

寡核苷酸芯片的逐步探针选取算法

Stepwise Probe Selection Algorithm for Oligonucleotide Array

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10