【正文】 基金項目：湖南省 自然科學 杰出青年基金 項目（ 06JJ1010） 作者簡介：王樹林（ 1966） 男，四川達縣，博士生，主要研究方向 ：生物信息學、軟件工程和復雜系統(tǒng)。王戟（ 1969），男，博士，教授，博士生導師， CCF 高級會員，研究方向：軟件理論、高可信軟件、 Agent 軟件方法學和生物信息 學 。 陳火旺（ 1936），男， 福建安溪，教授，博士生導師，中國工程院院士，主要研究領域為：軟件理論、人工智能和軟件工程 。 腫瘤 信息基因 啟發(fā)式 寬度優(yōu)先 搜索 算法研究 王樹林 1,2 王戟 1 陳火旺 1 李樹濤 3 張波云 1 (1 國防科技大學計算機學院 , 湖南長沙 , 410073) （ 2 湖南大學計算機與通信學院 , 湖南長沙 , 410082） (3 湖南大學電氣與工程學院 , 湖南長沙 , 410082) 摘要 : 基于基因表達譜的腫瘤檢測 方法有望 成為 臨床醫(yī)學上一種快速而有效的腫瘤 分子 診斷方法，但由于基因表達譜數(shù)據(jù)存在維數(shù)過高、樣本量很小以及噪音 很大 等特點，使得 腫瘤 信息基因 選擇 成為一件 有 挑戰(zhàn)性的工作。 根據(jù)腫瘤基因表達 譜 樣本集 的特點，提出一種 以 支持向量機分類性能 為評估準則的 尋找信息基因的啟發(fā)式寬度優(yōu)先 搜索算法，其 優(yōu)點是能夠 同時 搜索 到 基因 數(shù)量盡可能少而分類能力 盡可能強的多個信息基因 子 集。 實驗采用 了 三種腫瘤 樣本 集 以 驗證 新 算法 的 可行性和 有效性 ， 對于急性白血病 、難以分類的結腸癌和多腫瘤亞型的小圓藍細胞瘤樣本集 ， 分別 只需 4 和 4 個 信息 基因就能獲得 100％的4折 交叉驗證識別準確率 。 與其它 優(yōu)秀的 腫瘤分類 方法相比，實驗結果 在 信息基因數(shù)量及其 分類性能方面 具有明顯的優(yōu)越性 。 為避免樣本集的不同劃分對分類性能的影響，提出一種能夠更加客觀地反映信息基因子集分類 性能 的全 折交叉驗證評估方法 。 關鍵詞 : 基因表達譜； 腫瘤 分類； 信息 基因選擇； 支持向量機 ；全折交叉驗證 方法 中圖 法 分類號： 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。 基金項目：湖南省 自然科學 杰出青年基金 項目（ 06JJ1010） 作者簡介：王樹林（ 1966） 男，四川達縣，博士生，主要研究方向 ：生物信息學、軟件工程和復雜系統(tǒng)。王戟（ 1969），男，博士，教授，博士生導師， CCF 高級會員，研究方向：軟件理論、高可信軟件、 Agent 軟件方法學和生物信息 學 。 陳火旺（ 1936），男， 福建安溪，教授，博士生導師，中國工程院院士，主要研究領域為：軟件理論、人工智能和軟件工程 。 fullfold crossvalidated method 1 引言 繼人類基因組計劃的順利完成， 一個規(guī)模更宏大的腫瘤基因組 國際合作 項目 開始付諸實施，該 項目 預計 在未來 10 到 15 年內完成， 我國科學家也積極投身 到這一國際合作項目中來 。項目的 目的是全面發(fā)現(xiàn)導致腫瘤發(fā)生 發(fā)展 的遺傳變異，揭示基因變異與腫瘤的關系，發(fā)現(xiàn)腫瘤早期發(fā)生的分子標記和藥靶基因等，到那時人類將 能夠深入理解 腫瘤 的發(fā)生與 發(fā)展過程，并能夠采取有效 方 法 治療腫瘤，使人類攻克腫瘤的夢想成為現(xiàn)實 。 1999 年， Golub 等 [1]發(fā) 表了一篇采用 基因表達譜分類 急性白血病亞型的文章， 開創(chuàng) 了 基于基因表達譜的腫瘤分類 問題研究的先河 ， 此后 科學家們 已 陸續(xù)提出很多 腫瘤分類方 法 [2]， 使 這一領域很快成為生物信息學的一個研究熱點 。 現(xiàn)代醫(yī)學認為，腫瘤的發(fā)生發(fā)展必定表現(xiàn)在相關基因 在不同組織中 的表達差異上，因此，借助基因表達譜樣本診斷腫瘤及其亞型必將成為一種快速準確的臨床診斷方法， 阮曉鋼 [3]等采用生物信息學方法分析和研究了腫瘤信息基因的發(fā)現(xiàn)及其表達模式問題， 將不同組織類型的腫瘤整合為一個整體加以研究，并 從信息學角度論證 了 腫瘤信息基因在腫瘤樣本中特異表達的普遍性與客觀性。 由于目前發(fā)布的腫瘤樣本集存在樣本類別不均衡現(xiàn)象，這也會影響分類器的性能， 李建 中等 [4]針對 樣本集中樣本類別的不平衡性 提出 一種與數(shù)據(jù)分布模型無關的基因選擇方法，并在兩種腫瘤數(shù)據(jù)集上驗證了這種方法的有效性和穩(wěn)健性。 盡管針對腫瘤分類問題已開展了大量研究，但是到 目前為止人們仍然不能確切地知道 最少需要多少基因 才能 以最高分類準確率分類腫瘤樣本 以及像這樣的信息基因子集的數(shù)量有多少 。 模式 分類方法主要分為 無監(jiān)督 的聚類 方法 和有 監(jiān)督 的學習 方法 兩 大 類。 無監(jiān)督的腫瘤 樣本聚 類方法 通過樣本的相似性度量 能夠發(fā)現(xiàn)腫瘤樣本集的結構特征， 即相似的樣本自然聚成一類 [5， 6]， 像 自組織映射(SelfOrganizing Maps, SOM)這種聚類方法在腫瘤分類領域 亦 得到廣泛應用 [7]， 其優(yōu)點是有助于 發(fā)現(xiàn)新的腫瘤亞型 ；但在腫瘤分類領域更主要的是采用有監(jiān)督分類方法，因為它能充分利用樣本的已知類別信息 。 有監(jiān)督分類方法主要有： k近鄰 (kNearest Neighbor， kNN)[8]、 分類樹 [9]、支持向量機 (Support Vector Machines, SVM)[10， 11]、粗糙集 (Rough Set theory, RS)[12]、人工神經網絡 (Artificial Neural Networks， ANN)[13]和多層感 知機 (Multilayer Perceptron, MLP) [14]等 經典通用的分類方法，其優(yōu)點是 能夠根據(jù) 已知 的樣本 類別信息 進行學習，提取樣本分類知識 ， 這些方法都已成功 地 應用于腫瘤分類領域。 提高分類 器對腫瘤樣本集的分類性能的 一個 關鍵 任務 是 選擇分類能力 盡可能 強的 腫瘤 信息基因，但由于目前的基因表達譜樣本 集 具有高維和小樣本特點以及 存在噪音大和信息冗余 等 諸多 因素 而使 腫瘤 分類問題成為一件有挑戰(zhàn)性的工作。 雖然近幾年已提出許多解決信息基因選擇問題的 新方 法 [2]， 但對這個問題的研究還不夠 理想。腫瘤分類領域 的一個目標是 采用盡可能少的信息基因 以 獲得盡可能高的樣本分類準確率，其理由是： (1)選擇盡可能少的信息基因也就意味著 盡可能多地去掉了 包含在樣本中的噪音 ； (2)意味著減少腫瘤診斷成本 ； (3)分類準確率高的信息基因通常與腫瘤的發(fā)生發(fā)展存在緊密聯(lián)系 。 事實上，僅采用一種基因選擇方法很難選出 滿足這一條件的 信息基因子集。 因此， 信息基因的選擇 通常 分為兩個階段，首先采用Filter 方法 從成千上萬的基因中 初選 出一定數(shù)量的 信息基因 以大幅降低 基因 搜索空間 ，然后再進一步采用Wrapper 方法 精選 出滿足目標條件的 信息基因 子集。 本文在獲得了腫瘤樣本集的基本結構的先驗知識的 基礎上提出一種基于 SVM 的 FilterWrapper 混合 方法 來搜索腫瘤信息基因，其 本質是一種 以腫瘤樣本集的分類性能作為 啟發(fā) 式 反饋信息 的寬度優(yōu)先搜索算法， 最 后 采用 了三 種腫瘤樣本集進行實驗以驗證 所設計的 啟發(fā)式 算法的 可行性和有效性 。 2 腫瘤 亞型 分類問題 描述 設 },{ 1 nggG ?? 表示 基因表達譜數(shù)據(jù)集中所有基因構 成的一個基因全集 ，其中 )1( nigi ?? 表示一個基因， nG? 表示基因總 數(shù)。設 },{ 1 mssS ?? 表示由基因表達譜 樣本所構成的樣本集合，其中 mS? 表示樣本 數(shù)量，每一個樣本 )1( misi ?? 表示在特定 條件下 由 所有基因的表達值 構成的向量 ， 則 ni Rs? )1( mi?? 是一個 n 維空間向量。由所有的樣本及其所 屬 類別 組成的基因表達矩陣 M 可表示為 ： 3 ????????????????????C l a s smnmmmnnlllxxxxxxxxxM ???? ???? ?????????21g e n e sn,2,1,22,21,2,12,11,1 其中 jix, 表示基因 jg 在樣本 is 中的基因表達值，通常情況下 nm?? 。矩陣 M 的一行表示同一條件下所有基因的基因表達譜，構成 n 維空間的一個 點，而矩陣 M 的一列表示一個基因在不同條件下的表達情況 。Class 表示樣本 的 所屬類別 集合 ， 即 },{ 1 kccClass ?? ， 其中 kClass ? 表示樣本類別總數(shù) 。 實際上 由于腫瘤 樣