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

摘要：

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

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

CLC Number: 

• TP311