【正文】 ccu ra cy ? ； 16. iter:=iter+1。 //對數組按降序排列 7 5. *G :=Selected(G ,B, p )。 算法： HBSA(M , p ,w ,Depth )； 輸入 ： 基因 表達譜 M ,p 為初選信息基因 個數 , w 為選擇的基因子集個數， Depth 為迭代深度 ； 輸出 ： 最佳 信息基因集合 *A ； 1. For each gene Ggj? do 2. B[j]:= )( jgBFSC 。 111 ,1 1 ,1 ,{ } { }ppww w pggT a aCMT a a????????? (8) 采用 行標記向量 ),( 21 wTTTR o w ?? 依次標記 CM 的每一行，其中 iT ( wi??1 )表示 已選擇的信息基因子集 ， 采用列標記向量 }){},{},({ 21 pgggC o l u m n ?? 依次標記 CM 的每一列 ，其中 *Ggk? ，pk??1 ， 而 ])[][(, jC o l u m niR o wA c ca ji ?＝ ， 其中 wi??1 ， pj??1 。 10N…… 11N21NpN112N12?pN…… )1(2?ppN…… 21N}{ 1?pg}{ pg}{ pg}{ 1g}{ 2g}{ 2g? 圖 2 啟發(fā)式寬度優(yōu)先 搜索信息基因 子集 示意圖 HBSA算法 實現 在獲得最佳信息基因子集 *A 的過程中， 并不需要真正構造搜索樹， 只需保留每一 次搜索到的滿足給定要求的信息基因 子集及其分類性能指標就能達到預期目標 。雖然從局部看選擇 信息 基因的方式采用的是遞增方式，但宏觀看 則是混合方式，因為 那些 沒有潛力的基因組合在搜索過程中被拋棄了 。 需要注意的是，不同節(jié)點的路徑 所代 表的信息基因集 在不考慮順序的前提下可能相同，因此在計算節(jié)點的分類性能時如果發(fā)現前面已計算過，則該節(jié)點的分類性能 記為 0 以避免擴展不 必要的節(jié)點。 圖 2 示意了一棵 HBSA 擴展 搜索樹， 樹的每一結點采用 jiN 標記， 其中 i 表示樹 中結點的 層號 ( pi??0 )，層號 i 最大為 p ， p 表示初選信息基因的數量， j 表示樹的第 i 層的所有結點的順序編號， 而 采用 setNji . 表示該結點對應的一個單基因集合， parentNji . 指向 jiN 的父結點， pathNji . 表示 從根結點 10N 到其自身結點 jiN 的一條 路徑 ，顯然路徑長度為 i ， 其 路徑 的值 是 該路徑上的結點所代表 單基因集 的并集 ，即 s e tNp a thp a r e n tNp a thN jijiji .... ?? ， ).(. p a thNA cccN jiji ? 表示基因子集 pathji . 對腫瘤樣本集的分類性能 ，同時也作為 結點 是否被 擴展的啟發(fā)式信息 。 信息基因精選 我們曾采用因子分析方法從基因表達譜樣本 抽取 潛在 因子 [24]以 及 采用獨立分量分析方法從基因表達譜中抽取獨立分量 [25]以 用于 SVM 對 兩種 腫瘤樣本 集 （結腸癌和 急性 白血?。?進行分類，實驗結果表明，當抽取的因子數量或獨立分量的個數較少時，其分類性能 很高 ， 較多時其分類性能反而降 低，由此 推測基因表達譜中的信息基因數量較少時 (具體地說，只需 3 個或 4 個信息基因 )就可以獲得很高的分類 性能 [2]。秩和檢驗方法主要有兩種：適合于二分類問題的 Wilcoxon 秩和檢驗方法和適合 于多分類問題的 KruskalWallis 秩和檢驗方法。鄧林等 [22]采用峰度和偏度對結腸癌數據集、白血病數據集和乳腺癌數據集以實驗的方式進行了正態(tài)性檢驗，零假設是樣本服從高斯分布，所選取的顯著性水平為 ，實驗表明這三種 腫瘤數據集都不服從高斯分布，并由此推斷腫瘤數據集不服從高斯分布是普遍的； 然后 他們采用 Wilcoxon 秩和檢驗方法進行信息基因選擇并以 SVM 為分類器獲得了很好的實驗結果 ， 并 從理論分析上和實驗驗證上論證了秩和檢驗方法優(yōu)于 t 檢驗方法 。 然而 式（ 6） 只適合于兩類樣本的基因分值計算，為了能夠計算多腫瘤亞型的基因分值，可把 式 （ 6） 進 一步修改 為式（ 7）的 形式，也就是說，首先計算 樣本集中 每兩個 腫瘤亞型 的基因 Bhattacharyya 距離 再求其和作為該基因的分值 以度量該基因的分類能力 。 具體方法是 首先 以式 (6)為每一個基因 niGgi ??? 1, 計算其 BFSC 值，然后按照BFSC 值大小對全部基因進行降序排列并選擇前 p 個基因作為初選信息基因集合 *G ，通常 np?? ，不 妨記 為 }1|{* pjgG j ??＝ 。 ))2/()l n(()/()()( 22 ???????? ????? iiiiiiiiigR F SC ???????? (5) 更進一步， 如 果 假設兩類樣本 的 分布都服從 高斯 分布，則可根據基因 ig 采用 Bhattacharyya 距離 [20]作為兩類 樣本 的可分性判據 ，稱之為 Bhattacharyya特征記分準則 (Bhattacharyya Feature Score Criterion， BFSC)，即 以式 (6)來度量 基因 ig 的分類能力 。 Bhattacharyya 特征記分準則 Golub 等 [1]采用特征記分準則 (Feature Score Criterion, FSC)對每一個基因計算其分值 , 然后按分值降序排列基因， 基因的分值通過 式 (4)計算 ： ( ) ( ) /( )i i i i iF SC g ? ? ? ?? ? ? ?? ? ? (4) 其中 ?i? 表示基因 ig 的正類 樣本的均值， ?i? 表示 ig 的負類 樣本的均值；而 ?i? 表示 ig 的 正類樣本 的標準差，?i? 表示 ig 的 負類樣本 的標準差，基因分值的大小表明該基因能夠區(qū) 分 正類樣本和負類 樣本的 分類 能力大小。 信息基 因初選 由于基因表達譜存在維數高、噪音大以及 冗余信息多等特點 ， 所以 在分類前需要采用各種 方法 對基因表達譜數據進行 降維、去噪和剔除冗余基因 等處理，以 最大限度地提高腫瘤樣本的分類性能。混合方式則是從一個隨機產生的 初始集合 T 或 ??T 開始按照一定的策略從集合 T 中刪除基因或往集合 T 中增加基因直到獲 到滿足需要的候選信息基因集合 T 為止 ，例如 ， 順序向前浮動搜索 （ Sequential Forward Floating Search， SFFS） 算法 [16]與 基于遺傳算法 (Geic Algorithm， GA)的信息基因選擇算 法 [19]。 4 基 因 表 達 譜數 據 獲 取數 據 預 處 理特 征 抽 取 或 信 息 基因 選 擇分 類 模 型 建 立分 類 預 測 與 評 估 圖 1 腫瘤分類過程模型 通常， 信息基因的選擇方式可分為 三種： 遞增方式 、 遞減方式 和混合方式 。實際上，瀑布模型和迭代模型是對 Filter 方法和 Wrapper方法在概念上的延伸，使之更適合 于 復雜的腫 瘤分類過程模型。 在腫瘤分類領域，分類模型建立 主要是采用訓練樣本集對統(tǒng)計學習分類器進行分類訓練以獲得分類模型；分類預測與評估則是采用測試樣本集對分類模型進行評估，推斷分類模型的泛化能力。 3 腫瘤分類 過程 模型 與實現算法 腫瘤分類過程模型 腫瘤分類是模式分類 方法在 生物 醫(yī)學領域 的一個具體應用，因此， 腫瘤分類過程模型同樣與模式分類過程模型具有相似性 ， 主要 分為 五個階段： 基因 表達譜數據獲取、基因表達譜數據預處理、 特征抽取或 信息基因選擇 、 分類模型建立以 及 分類 預測與 評估 ，如圖 1 所示， 虛線的左邊部分是一個生物醫(yī)學過程，而其右邊部分是一個信息處理過程 。 事實上，最佳信息基因子集可能不是唯一的， 因此，由所有最佳信息基因子集 *T 構成一個集合可表示為 * * * *{ | }A T T P T?? ， 滿 足 最 佳 信 息 基 因 條 件。 設 )(TAcc 表示基因子集 T 對樣本集的分類能力， 則問題的目標可形式化表示為 式（ 1）、（ 2）和（ 3）。 腫瘤分類問題的關鍵是要解決如何根據基因表達譜 M 從 基因 空間 G 中選擇與腫瘤有關的 信息 基因 子集 T ， 在 ||G 很大 且沒有先驗知識的情況下 ，從 2 GP ? 搜索信息基因子集 T 是 一個難以解決的 NP難問題。Class 表示樣本 的 所屬類別 集合 ， 即 },{ 1 kccClass ?? ， 其中 kClass ? 表示樣本類別總數 。由所有的樣本及其所 屬 類別 組成的基因表達矩陣 M 可表示為 ： 3 ????????????????????C l a s smnmmmnnlllxxxxxxxxxM ???? ???? ?????????21g e n e sn,2,1,22,21,2,12,11,1 其中 jix, 表示基因 jg 在樣本 is 中的基因表達值，通常情況下 nm?? 。 2 腫瘤 亞型 分類問題 描述 設 },{ 1 nggG ?? 表示 基因表達譜數據集中所有基因構 成的一個基因全集 ，其中 )1( nigi ?? 表示一個基因， nG? 表示基因總 數。 因此， 信息基因的選擇 通常 分為兩個階段，首先采用Filter 方法 從成千上萬的基因中 初選 出一定數量的 信息基因 以大幅降低 基因 搜索空間 ，然后再進一步采用Wrapper 方法 精選 出滿足目標條件的 信息基因 子集。腫瘤分類領域 的一個目標是 采用盡可能少的信息基因 以 獲得盡可能高的樣本分類準確率，其理由是： (1)選擇盡可能少的信息基因也就意味著 盡可能多地去掉了 包含在樣本中的噪音 ； (2)意味著減少腫瘤診斷成本 ； (3)分類準確率高的信息基因通常與腫瘤的發(fā)生發(fā)展存在緊密聯系 。 提高分類 器對腫瘤樣本集的分類性能的 一個 關鍵 任務 是 選擇分類能力 盡可能 強的 腫瘤 信息基因，但由于目前的基因表達譜樣本 集 具有高維和小樣本特點以及 存在噪音大和信息冗余 等 諸多 因素 而使 腫瘤 分類問題成為一件有挑戰(zhàn)性的工作。 無監(jiān)督的腫瘤 樣本聚 類方法 通過樣本的相似性度量 能夠發(fā)現腫瘤樣本集的結構特征， 即相似的樣本自然聚成一類 [5， 6]， 像 自組織映射(SelfOrganizing Maps, SOM)這種聚類方法在腫瘤分類領域 亦 得到廣泛應用 [7]， 其優(yōu)點是有助于 發(fā)現新的腫瘤亞型 ；但在腫瘤分類領域更主要的是采用有監(jiān)督分類方法，因為它能充分利用樣本的已知類別信息 。 盡管針對腫瘤分類問題已開展了大量研究，但是到 目前為止人們仍然不能確切地知道 最少需要多少基因 才能 以最高分類準確率分類腫瘤樣本 以及像這樣的信息基因子集的數量有多少 。 現代醫(yī)學認為，腫瘤的發(fā)生發(fā)展必定表現在相關基因 在不同組織中 的表達差異上，因此，借助基因表達譜樣本診斷腫瘤及其亞型必將成為一種快速準確的臨床診斷方法， 阮曉鋼 [3]等采用生物信息學方法分析和研究了腫瘤信息基因的發(fā)現及其表達模式問題， 將不同組織類型的腫瘤整合為一個整體加以研究，并 從信息學角度論證 了 腫瘤信息基因在腫瘤樣本中特異表達的普遍性與客觀性。項目的 目的是全面發(fā)現導致腫瘤發(fā)生 發(fā)展 的遺傳變異，揭示基因變異與腫瘤的關系，發(fā)現腫瘤早期發(fā)生的分子標記和藥靶基因等，到那時人類將 能夠深入理解 腫瘤 的發(fā)生與 發(fā)展過程，并能夠采取有效 方 法 治療腫瘤，使人類攻克腫瘤的夢想成為現實 。 陳火旺（ 1936），男， 福建安溪，教授，博士生導師，中國工程院院士，主要研究領域為：軟件理論、人工智能和軟件工程 。 基金項目：湖南省 自然科學 杰出青年基金 項目（ 06JJ1010） 作者簡介：王樹林（ 1966） 男，四川達縣，博士生，主要研究方向 ：生物信息學、軟件工程和復雜系統(tǒng)。 informative gene selection。 關鍵詞 : 基因表達譜； 腫瘤 分類； 信息 基因選擇； 支持向量機 ；全折交叉驗證 方法 中圖 法 分類號： 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 Infor