【正文】 基金項(xiàng)目：湖南省 自然科學(xué) 杰出青年基金 項(xiàng)目（ 06JJ1010） 作者簡(jiǎn)介：王樹(shù)林（ 1966） 男，四川達(dá)縣，博士生，主要研究方向 ：生物信息學(xué)、軟件工程和復(fù)雜系統(tǒng)。王戟（ 1969），男，博士，教授，博士生導(dǎo)師， CCF 高級(jí)會(huì)員，研究方向：軟件理論、高可信軟件、 Agent 軟件方法學(xué)和生物信息 學(xué) 。 陳火旺（ 1936），男， 福建安溪，教授，博士生導(dǎo)師，中國(guó)工程院院士，主要研究領(lǐng)域?yàn)椋很浖碚?、人工智能和軟件工?。 腫瘤 信息基因 啟發(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)性的工作。 根據(jù)腫瘤基因表達(dá) 譜 樣本集 的特點(diǎn)，提出一種 以 支持向量機(jī)分類性能 為評(píng)估準(zhǔn)則的 尋找信息基因的啟發(fā)式寬度優(yōu)先 搜索算法，其 優(yōu)點(diǎn)是能夠 同時(shí) 搜索 到 基因 數(shù)量盡可能少而分類能力 盡可能強(qiáng)的多個(gè)信息基因 子 集。 實(shí)驗(yàn)采用 了 三種腫瘤 樣本 集 以 驗(yàn)證 新 算法 的 可行性和 有效性 ， 對(duì)于急性白血病 、難以分類的結(jié)腸癌和多腫瘤亞型的小圓藍(lán)細(xì)胞瘤樣本集 ， 分別 只需 4 和 4 個(gè) 信息 基因就能獲得 100％的4折 交叉驗(yàn)證識(shí)別準(zhǔn)確率 。 與其它 優(yōu)秀的 腫瘤分類 方法相比，實(shí)驗(yàn)結(jié)果 在 信息基因數(shù)量及其 分類性能方面 具有明顯的優(yōu)越性 。 為避免樣本集的不同劃分對(duì)分類性能的影響，提出一種能夠更加客觀地反映信息基因子集分類 性能 的全 折交叉驗(yàn)證評(píng)估方法 。 關(guān)鍵詞 : 基因表達(dá)譜； 腫瘤 分類； 信息 基因選擇； 支持向量機(jī) ；全折交叉驗(yàn)證 方法 中圖 法 分類號(hào)： TP391 Heuristic Breadthfirst Search Algorithm for Informative Gene Selection Based on Gene Expression Profiles Shulin Wang1,2, Ji Wang1, Huowang Chen1,Shutao Li3, and Boyun Zhang1 (1 School of Computer Science, National University of Defense Technology, Changsha Hunan, 410073, China) (2 School of Computer and Communication, Hunan University, Changsha Hunan, 410082, China) (3 College of Electrical and Information 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。 tumor classification。 informative gene selection。 support vector machines。 基金項(xiàng)目：湖南省 自然科學(xué) 杰出青年基金 項(xiàng)目（ 06JJ1010） 作者簡(jiǎn)介：王樹(shù)林（ 1966） 男，四川達(dá)縣，博士生，主要研究方向 ：生物信息學(xué)、軟件工程和復(fù)雜系統(tǒng)。王戟（ 1969），男，博士，教授，博士生導(dǎo)師， CCF 高級(jí)會(huì)員，研究方向：軟件理論、高可信軟件、 Agent 軟件方法學(xué)和生物信息 學(xué) 。 陳火旺（ 1936），男， 福建安溪，教授，博士生導(dǎo)師，中國(guó)工程院院士，主要研究領(lǐng)域?yàn)椋很浖碚?、人工智能和軟件工?。 fullfold crossvalidated method 1 引言 繼人類基因組計(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) 。項(xiàng)目的 目的是全面發(fā)現(xiàn)導(dǎo)致腫瘤發(fā)生 發(fā)展 的遺傳變異，揭示基因變異與腫瘤的關(guān)系，發(fā)現(xiàn)腫瘤早期發(fā)生的分子標(biāo)記和藥靶基因等，到那時(shí)人類將 能夠深入理解 腫瘤 的發(fā)生與 發(fā)展過(guò)程，并能夠采取有效 方 法 治療腫瘤，使人類攻克腫瘤的夢(mèng)想成為現(xiàn)實(shí) 。 1999 年， Golub 等 [1]發(fā) 表了一篇采用 基因表達(dá)譜分類 急性白血病亞型的文章， 開(kāi)創(chuàng) 了 基于基因表達(dá)譜的腫瘤分類 問(wèn)題研究的先河 ， 此后 科學(xué)家們 已 陸續(xù)提出很多 腫瘤分類方 法 [2]， 使 這一領(lǐng)域很快成為生物信息學(xué)的一個(gè)研究熱點(diǎn) 。 現(xiàn)代醫(yī)學(xué)認(rèn)為，腫瘤的發(fā)生發(fā)展必定表現(xiàn)在相關(guān)基因 在不同組織中 的表達(dá)差異上，因此，借助基因表達(dá)譜樣本診斷腫瘤及其亞型必將成為一種快速準(zhǔn)確的臨床診斷方法， 阮曉鋼 [3]等采用生物信息學(xué)方法分析和研究了腫瘤信息基因的發(fā)現(xiàn)及其表達(dá)模式問(wèn)題， 將不同組織類型的腫瘤整合為一個(gè)整體加以研究，并 從信息學(xué)角度論證 了 腫瘤信息基因在腫瘤樣本中特異表達(dá)的普遍性與客觀性。 由于目前發(fā)布的腫瘤樣本集存在樣本類別不均衡現(xiàn)象，這也會(huì)影響分類器的性能， 李建 中等 [4]針對(duì) 樣本集中樣本類別的不平衡性 提出 一種與數(shù)據(jù)分布模型無(wú)關(guān)的基因選擇方法，并在兩種腫瘤數(shù)據(jù)集上驗(yàn)證了這種方法的有效性和穩(wěn)健性。 盡管針對(duì)腫瘤分類問(wèn)題已開(kāi)展了大量研究，但是到 目前為止人們?nèi)匀徊荒艽_切地知道 最少需要多少基因 才能 以最高分類準(zhǔn)確率分類腫瘤樣本 以及像這樣的信息基因子集的數(shù)量有多少 。 模式 分類方法主要分為 無(wú)監(jiān)督 的聚類 方法 和有 監(jiān)督 的學(xué)習(xí) 方法 兩 大 類。 無(wú)監(jiān)督的腫瘤 樣本聚 類方法 通過(guò)樣本的相似性度量 能夠發(fā)現(xiàn)腫瘤樣本集的結(jié)構(gòu)特征， 即相似的樣本自然聚成一類 [5， 6]， 像 自組織映射(SelfOrganizing Maps, SOM)這種聚類方法在腫瘤分類領(lǐng)域 亦 得到廣泛應(yīng)用 [7]， 其優(yōu)點(diǎn)是有助于 發(fā)現(xiàn)新的腫瘤亞型 ；但在腫瘤分類領(lǐng)域更主要的是采用有監(jiān)督分類方法，因?yàn)樗艹浞掷脴颖镜囊阎悇e信息 。 有監(jiān)督分類方法主要有： k近鄰 (kNearest Neighbor， kNN)[8]、 分類樹(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)典通用的分類方法，其優(yōu)點(diǎn)是 能夠根據(jù) 已知 的樣本 類別信息 進(jìn)行學(xué)習(xí)，提取樣本分類知識(shí) ， 這些方法都已成功 地 應(yīng)用于腫瘤分類領(lǐng)域。 提高分類 器對(duì)腫瘤樣本集的分類性能的 一個(gè) 關(guān)鍵 任務(wù) 是 選擇分類能力 盡可能 強(qiáng)的 腫瘤 信息基因，但由于目前的基因表達(dá)譜樣本 集 具有高維和小樣本特點(diǎn)以及 存在噪音大和信息冗余 等 諸多 因素 而使 腫瘤 分類問(wèn)題成為一件有挑戰(zhàn)性的工作。 雖然近幾年已提出許多解決信息基因選擇問(wèn)題的 新方 法 [2]， 但對(duì)這個(gè)問(wèn)題的研究還不夠 理想。腫瘤分類領(lǐng)域 的一個(gè)目標(biāo)是 采用盡可能少的信息基因 以 獲得盡可能高的樣本分類準(zhǔn)確率，其理由是： (1)選擇盡可能少的信息基因也就意味著 盡可能多地去掉了 包含在樣本中的噪音 ； (2)意味著減少腫瘤診斷成本 ； (3)分類準(zhǔn)確率高的信息基因通常與腫瘤的發(fā)生發(fā)展存在緊密聯(lián)系 。 事實(shí)上，僅采用一種基因選擇方法很難選出 滿足這一條件的 信息基因子集。 因此， 信息基因的選擇 通常 分為兩個(gè)階段，首先采用Filter 方法 從成千上萬(wàn)的基因中 初選 出一定數(shù)量的 信息基因 以大幅降低 基因 搜索空間 ，然后再進(jìn)一步采用Wrapper 方法 精選 出滿足目標(biāo)條件的 信息基因 子集。 本文在獲得了腫瘤樣本集的基本結(jié)構(gòu)的先驗(yàn)知識(shí)的 基礎(chǔ)上提出一種基于 SVM 的 FilterWrapper 混合 方法 來(lái)搜索腫瘤信息基因，其 本質(zhì)是一種 以腫瘤樣本集的分類性能作為 啟發(fā) 式 反饋信息 的寬度優(yōu)先搜索算法， 最 后 采用 了三 種腫瘤樣本集進(jìn)行實(shí)驗(yàn)以驗(yàn)證 所設(shè)計(jì)的 啟發(fā)式 算法的 可行性和有效性 。 2 腫瘤 亞型 分類問(wèn)題 描述 設(shè) },{ 1 nggG ?? 表示 基因表達(dá)譜數(shù)據(jù)集中所有基因構(gòu) 成的一個(gè)基因全集 ，其中 )1( nigi ?? 表示一個(gè)基因， nG? 表示基因總 數(shù)。設(shè) },{ 1 mssS ?? 表示由基因表達(dá)譜 樣本所構(gòu)成的樣本集合，其中 mS? 表示樣本 數(shù)量，每一個(gè)樣本 )1( misi ?? 表示在特定 條件下 由 所有基因的表達(dá)值 構(gòu)成的向量 ， 則 ni Rs? )1( mi?? 是一個(gè) n 維空間向量。由所有的樣本及其所 屬 類別 組成的基因表達(dá)矩陣 M 可表示為 ： 3 ????????????????????C l a s smnmmmnnlllxxxxxxxxxM ???? ???? ?????????21g e n e sn,2,1,22,21,2,12,11,1 其中 jix, 表示基因 jg 在樣本 is 中的基因表達(dá)值，通常情況下 nm?? 。矩陣 M 的一行表示同一條件下所有基因的基因表達(dá)譜，構(gòu)成 n 維空間的一個(gè) 點(diǎn)，而矩陣 M 的一列表示一個(gè)基因在不同條件下的表達(dá)情況 。Class 表示樣本 的 所屬類別 集合 ， 即 },{ 1 kccClass ?? ， 其中 kClass ? 表示樣本類別總數(shù) 。 實(shí)際上 由于腫瘤 樣