【正文】 mation Engineering, Hunan University, Changsha Hunan, 410082, China) Abstract: The tumor diagnosis method based on gene expression profiles will be developed into the fast and effective method in clinical domain in the near future. Although DNA microarray experiments provide us with huge amount of gene expression data, only a few of genes are related to tumor in gene expression profiles. Moreover, it is difficult to select informative genes related to tumor from gene expression profiles because of its characteristics such as high dimensionality, small sample set and many noises in gene expression profiles. According to its characteristic, a novel heuristic breadthfirst search algorithm based on support vector machines is proposed, which can simultaneously find as many informative gene subsets as possible in which the number of informative genes is almost least but its classification performance is almost highest in spite of its timeconsuming characteristic. Three tumor sample sets are examined by the novel approach and experiments show that the novel approach is feasible and effective in tumor classification. Experiment results show that 100% of 4fold crossvalidation accuracy has been achieved by only two, four and four genes for leukemia, colon tumor and SRBCT (Small Round Blue Cells Tumor) datasets, respectively, which is superior to the results of other tumor classification methods. To avoid the affect of different partition of sample set, the fullfold crossvalidated method that can more objectively evaluate the classification performance of informative gene subset is proposed. Keywords: gene expression profiles。 與其它 優(yōu)秀的 腫瘤分類(lèi) 方法相比，實(shí)驗(yàn)結(jié)果 在 信息基因數(shù)量及其 分類(lèi)性能方面 具有明顯的優(yōu)越性 。 根據(jù)腫瘤基因表達(dá) 譜 樣本集 的特點(diǎn)，提出一種 以 支持向量機(jī)分類(lèi)性能 為評(píng)估準(zhǔn)則的 尋找信息基因的啟發(fā)式寬度優(yōu)先 搜索算法，其 優(yōu)點(diǎn)是能夠 同時(shí) 搜索 到 基因 數(shù)量盡可能少而分類(lèi)能力 盡可能強(qiáng)的多個(gè)信息基因 子 集。 陳火旺（ 1936），男， 福建安溪，教授，博士生導(dǎo)師，中國(guó)工程院院士，主要研究領(lǐng)域?yàn)椋很浖碚?、人工智能和軟件工??；痦?xiàng)目：湖南省 自然科學(xué) 杰出青年基金 項(xiàng)目（ 06JJ1010） 作者簡(jiǎn)介：王樹(shù)林（ 1966） 男，四川達(dá)縣，博士生，主要研究方向 ：生物信息學(xué)、軟件工程和復(fù)雜系統(tǒng)。王戟（ 1969），男，博士，教授，博士生導(dǎo)師， CCF 高級(jí)會(huì)員，研究方向：軟件理論、高可信軟件、 Agent 軟件方法學(xué)和生物信息 學(xué) 。 腫瘤 信息基因 啟發(fā)式 寬度優(yōu)先 搜索 算法研究 王樹(shù)林 1,2 王戟 1 陳火旺 1 李樹(shù)濤 3 張波云 1 (1 國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院 , 湖南長(zhǎng)沙 , 410073) （ 2 湖南大學(xué)計(jì)算機(jī)與通信學(xué)院 , 湖南長(zhǎng)沙 , 410082） (3 湖南大學(xué)電氣與工程學(xué)院 , 湖南長(zhǎng)沙 , 410082) 摘要 : 基于基因表達(dá)譜的腫瘤檢測(cè) 方法有望 成為 臨床醫(yī)學(xué)上一種快速而有效的腫瘤 分子 診斷方法，但由于基因表達(dá)譜數(shù)據(jù)存在維數(shù)過(guò)高、樣本量很小以及噪音 很大 等特點(diǎn)，使得 腫瘤 信息基因 選擇 成為一件 有 挑戰(zhàn)性的工作。 實(shí)驗(yàn)采用 了 三種腫瘤 樣本 集 以 驗(yàn)證 新 算法 的 可行性和 有效性 ， 對(duì)于急性白血病 、難以分類(lèi)的結(jié)腸癌和多腫瘤亞型的小圓藍(lán)細(xì)胞瘤樣本集 ， 分別 只需 4 和 4 個(gè) 信息 基因就能獲得 100％的4折 交叉驗(yàn)證識(shí)別準(zhǔn)確率 。 為避免樣本集的不同劃分對(duì)分類(lèi)性能的影響，提出一種能夠更加客觀(guān)地反映信息基因子集分類(lèi) 性能 的全 折交叉驗(yàn)證評(píng)估方法 。 tumor classification。 support vector machines。王戟（ 1969），男，博士，教授，博士生導(dǎo)師， CCF 高級(jí)會(huì)員，研究方向：軟件理論、高可信軟件、 Agent 軟件方法學(xué)和生物信息 學(xué) 。 fullfold crossvalidated method 1 引言 繼人類(lèi)基因組計(jì)劃的順利完成， 一個(gè)規(guī)模更宏大的腫瘤基因組 國(guó)際合作 項(xiàng)目 開(kāi)始付諸實(shí)施，該 項(xiàng)目 預(yù)計(jì) 在未來(lái) 10 到 15 年內(nèi)完成， 我國(guó)科學(xué)家也積極投身 到這一國(guó)際合作項(xiàng)目中來(lái) 。 1999 年， Golub 等 [1]發(fā) 表了一篇采用 基因表達(dá)譜分類(lèi) 急性白血病亞型的文章， 開(kāi)創(chuàng) 了 基于基因表達(dá)譜的腫瘤分類(lèi) 問(wèn)題研究的先河 ， 此后 科學(xué)家們 已 陸續(xù)提出很多 腫瘤分類(lèi)方 法 [2]， 使 這一領(lǐng)域很快成為生物信息學(xué)的一個(gè)研究熱點(diǎn) 。 由于目前發(fā)布的腫瘤樣本集存在樣本類(lèi)別不均衡現(xiàn)象，這也會(huì)影響分類(lèi)器的性能， 李建 中等 [4]針對(duì) 樣本集中樣本類(lèi)別的不平衡性 提出 一種與數(shù)據(jù)分布模型無(wú)關(guān)的基因選擇方法，并在兩種腫瘤數(shù)據(jù)集上驗(yàn)證了這種方法的有效性和穩(wěn)健性。 模式 分類(lèi)方法主要分為 無(wú)監(jiān)督 的聚類(lèi) 方法 和有 監(jiān)督 的學(xué)習(xí) 方法 兩 大 類(lèi)。 有監(jiān)督分類(lèi)方法主要有： k近鄰 (kNearest Neighbor， kNN)[8]、 分類(lèi)樹(shù) [9]、支持向量機(jī) (Support Vector Machines, SVM)[10， 11]、粗糙集 (Rough Set theory, RS)[12]、人工神經(jīng)網(wǎng)絡(luò) (Artificial Neural Networks， ANN)[13]和多層感 知機(jī) (Multilayer Perceptron, MLP) [14]等 經(jīng)典通用的分類(lèi)方法，其優(yōu)點(diǎn)是 能夠根據(jù) 已知 的樣本 類(lèi)別信息 進(jìn)行學(xué)習(xí)，提取樣本分類(lèi)知識(shí) ， 這些方法都已成功 地 應(yīng)用于腫瘤分類(lèi)領(lǐng)域。 雖然近幾年已提出許多解決信息基因選擇問(wèn)題的 新方 法 [2]， 但對(duì)這個(gè)問(wèn)題的研究還不夠 理想。 事實(shí)上，僅采用一種基因選擇方法很難選出 滿(mǎn)足這一條件的 信息基因子集。 本文在獲得了腫瘤樣本集的基本結(jié)構(gòu)的先驗(yàn)知識(shí)的 基礎(chǔ)上提出一種基于 SVM 的 FilterWrapper 混合 方法 來(lái)搜索腫瘤信息基因，其 本質(zhì)是一種 以腫瘤樣本集的分類(lèi)性能作為 啟發(fā) 式 反饋信息 的寬度優(yōu)先搜索算法， 最 后 采用 了三 種腫瘤樣本集進(jìn)行實(shí)驗(yàn)以驗(yàn)證 所設(shè)計(jì)的 啟發(fā)式 算法的 可行性和有效性 。設(shè) },{ 1 mssS ?? 表示由基因表達(dá)譜 樣本所構(gòu)成的樣本集合，其中 mS? 表示樣本 數(shù)量，每一個(gè)樣本 )1( misi ?? 表示在特定 條件下 由 所有基因的表達(dá)值 構(gòu)成的向量 ， 則 ni Rs? )1( mi?? 是一個(gè) n 維空間向量。矩陣 M 的一行表示同一條件下所有基因的基因表達(dá)譜，構(gòu)成 n 維空間的一個(gè) 點(diǎn)，而矩陣 M 的一列表示一個(gè)基因在不同條件下的表達(dá)情況 。 實(shí)際上 由于腫瘤 樣本集合 S 中的每一個(gè)樣本的所屬類(lèi)別是已知的，可用 LS? 表示類(lèi)別樣本空間，則一個(gè)具體的已知類(lèi)別樣本集合就是 {( , ) , , 1 , 2 , }ni i i is l l Cla ss s R i m? ? ?。到目前為止，科學(xué)家們并不 完全 清楚哪些基因 是與特 定腫瘤相關(guān)的以及與腫瘤相關(guān)的 基因 數(shù)量是多少，因此，可以 假設(shè) 對(duì)于特定的腫瘤樣本集 其分類(lèi)能力 最 強(qiáng)的基因子集 T 是與腫瘤相關(guān)的基因，從生物醫(yī)學(xué)角度考慮，這一假設(shè) 也有一定的合理性 。 )()( GAccTAcc ? ，其中 TP? (1) arg ( )minTP T? (2) arg ( ( ))m axTP A cc T? (3) 這三個(gè)條件被稱(chēng)之為 基因子集 T 所應(yīng)滿(mǎn)足的 最佳 條件 ，滿(mǎn)足最佳條件的信息基因子集稱(chēng)之為最佳信息基因子集 *T 。 由于基因總數(shù) n 通常很大，所以 在 n2 的 基因空間 內(nèi)使用窮舉 搜索方法發(fā)現(xiàn) *A 是一個(gè)不現(xiàn)實(shí)的方法 ，因此 ，需要設(shè)計(jì) 壓縮搜索空間的啟發(fā)式 搜索 算法 來(lái)漸進(jìn)達(dá)到這一目標(biāo) ?；虮磉_(dá)譜數(shù)據(jù)的獲取是一個(gè)復(fù)雜的生物過(guò)程，是通過(guò)測(cè)量雙 色熒光強(qiáng)度再經(jīng)適當(dāng)數(shù)據(jù)處理獲得的，獲得的數(shù)據(jù)往往存在大量噪聲以及 數(shù)據(jù)不在同一 量綱范圍，甚至存在基因表達(dá)數(shù) 據(jù)缺失現(xiàn)象，因此對(duì)基因表達(dá)譜數(shù)據(jù)進(jìn)行預(yù)處理是一個(gè)非常重要的環(huán)節(jié)；預(yù)處理工作主要包括缺失基因表達(dá)數(shù)據(jù)補(bǔ)齊和數(shù)據(jù)規(guī)格化處理等； 特征抽取或 信息基因的選擇在腫瘤分類(lèi)模型中起著至關(guān)重要的作用 ，抽取或選擇的特征與腫瘤愈相關(guān)意味著分類(lèi)性能愈高 。 通常，分類(lèi)算法按其子過(guò)程有無(wú)反饋可分為 Filter 方法和 Wrapper 方法 [15]，但由于 腫瘤分類(lèi) 過(guò)程 模型的復(fù)雜性 以及分類(lèi)方法的不斷進(jìn)步 ， 其過(guò)程模型也越來(lái)越復(fù)雜，所以， 沿用軟件工程學(xué)中軟件 開(kāi)發(fā)過(guò)程模型 的分類(lèi)準(zhǔn)則對(duì)腫瘤分類(lèi)過(guò)程模型進(jìn)行分類(lèi)，可 分為 兩種：瀑布模型和迭代模型。 雖然迭代模型存在計(jì) 算量大的缺點(diǎn)，但 其優(yōu)點(diǎn)是能夠選出數(shù)量盡可能少的候選信息基因 并使得其分類(lèi)能力盡可能強(qiáng) ，根據(jù)目前對(duì)腫瘤分類(lèi)的研究結(jié)果可知，迭代模型 在分類(lèi)性能方面 通常優(yōu)于瀑布模型 。遞增方式就是從一個(gè) 初始集合 ?＝0T 開(kāi)始按照某一策略 選擇一個(gè)基因并加入到已 選擇基因 集合 iT 中 ， 則第 1?i 步所選則的基因子集}{1 gTT ii ??? ， iTGg ?? ，使 )()( 1 ii TAccTAcc ?? 成立， 直到獲得 滿(mǎn)足 期望的分類(lèi)準(zhǔn)確率 的候選信息基因子集 T 為止 ，例如， Momiao Xiong 等 [16]提 出 的 順序向前 搜索 (Sequential Forward Search, SFS)算法 就是一種遞增式信息基因選擇算法 ，其缺點(diǎn)是一旦往 T 中加入一個(gè)基因就不能在后續(xù) 搜索過(guò)程中將其從 T 中刪除 ；而遞減方式就是從一個(gè) 初始 集合 GT? 開(kāi)始按照某一個(gè)策略每次從集合 T 中刪除一個(gè) 或幾個(gè) 冗余基因直到獲得一個(gè)滿(mǎn)足需要的候選信息基因子集 T 為止 ，例如， 李穎新 等 [17, 18]采用 靈敏度分析和兩兩冗余分析方法剔除 冗余基因就是遞減方式的信息基因選擇方法 。 實(shí)驗(yàn)結(jié)果表明，基于混合方式的信息基因選擇算法的效果 通常 優(yōu)于其它兩種方式。 基因表達(dá)譜中 多數(shù)基因的表達(dá)與腫瘤無(wú)關(guān)， 這為信息基因選擇 帶來(lái)很大困難， 采用單一 方法很難 完成這一任務(wù)，因此，通常首先采用 一種稱(chēng)之為基因排序 (gene ranking)的方法對(duì)原始基因集合進(jìn)行粗選，其基本思想便是按照某種記分準(zhǔn)則對(duì)每一個(gè)基因 進(jìn)行記分，基因分值大小反映了基因的重要程度，然后按基因分值大小降序 排列基因并選擇排在前面的一定數(shù)量的基因作為選擇結(jié)果。李穎新等 [18]認(rèn)為在衡量基因含有樣本分類(lèi)信息多少的度量問(wèn)題上，還應(yīng)該考慮由于方差不同所帶 來(lái)的對(duì)樣本分類(lèi)的貢獻(xiàn)，從而可以更客觀(guān)地評(píng)價(jià)基因含有的分類(lèi)信息量， 為此他們對(duì) FSC 進(jìn)行了修訂， 稱(chēng)之為修訂的特征記分準(zhǔn)則 (Revised Feature Score Criterion, RFSC)， 如 式 (5)所示。 5 ))2/()l n((21))/()((41)( 22222 ???????? ????? iiiiiiiiigB F SC ???????? (6) 與式 (5)對(duì)比發(fā)現(xiàn)，二者在形式上比較相似，但式 (6)有堅(jiān)實(shí)的理論基礎(chǔ) ； 朱云華 等 [21]采用 Bhattacharyya 距離度量基因的分類(lèi)能力 并在 小圓藍(lán)細(xì)胞瘤（ Small Round Blue Cells Tumor， SRBCT） 數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn) 獲得了較好的 實(shí)驗(yàn) 結(jié)果 。 但 由于基因在細(xì)胞中存在共表達(dá)現(xiàn)象，所以 *G 中的基因往往是高度相關(guān)的，所以 從分類(lèi)角度考慮 還需要 從 *G 中剔除冗余基因，以