【正文】 也可以選擇 分類能力大于某一閾 值的所有節(jié)點作為待擴展節(jié)點，這種情況下需要為每一層設置不同的 閾值，且下一層的閾值大于上一層的閾 值 ， 顯然這會 導致每一層所 選擇的待擴展結(jié)點的數(shù)量不同，但 優(yōu)點是增加了算法的適應性，其中 閾 值的設 定非常關(guān)鍵 。 HBSA 擴展 搜索樹是 在 HBSA 算法搜索信息基因子集的過程中生成的，首先生成一個根結(jié)點，其值設定為： ?? ， ??pathN .10 ， ?parentN ， ?cN ， 并 對 根結(jié)點擴展 p 個結(jié)點 ， 且 置}{.1 jj gsetN ? ， }{.1 jj gpathN ? ， 且 pjGg j ??? 1,* ，然后對這 p 個結(jié)點進行第 2 層擴展， 因為 *G 是初選出來的 信息 基因集合，所以其結(jié)點擴展實際上已經(jīng)利用了單個基因的分類能力啟發(fā)信息 )( jgBFSC ，每一個結(jié)點 pjN j ??1,1 擴展 1?p 個 子 結(jié)點 ， 則第 2 層結(jié)點共有 )1( ?pp 個結(jié)點， 且置 }{.2 ij gsetN ? ，p a t hp a r e n tNs e tNp a t hN jjj .... 222 ?? ， ).(. 22 p a thNA cccN jj ? ， p a t hp a r e n tNgGg jii ..2* ??? ， 6 )1(1 ??? ppj ， pi??1 ， 再把 第 2 層的所有結(jié)點 按 降序排列， 檢查 ).m ax(arg2)1(1m a x cN jA c c ppj ????是否 滿足要求，如果滿足，則 算法 找到了滿足條件的基因子集，否則 選擇 排在 前 面的 p 個結(jié)點作為擴展結(jié)點，繼續(xù)類似搜索。 陸巍等 [23]分別采用這兩種非參數(shù)秩和檢驗方法以選擇腫瘤相關(guān)基因并分類腫瘤樣本集 亦 獲得了很好的實驗結(jié)果。 2 2 2 221111( ) ( ( ( ) / ( ) ) l n(( ) / ( 2 ) ) ) / 242cc j k j k j k j ki i i i i i i i ijkkjBFS C g ? ? ? ? ? ? ? ??? ?? ? ? ? ??? (7) 秩和檢驗方法 采用 Bhattacharyya 距離及其變體需要假設數(shù)據(jù)服從高斯分布才能獲得最佳效果，而 當數(shù)據(jù)不服從高斯分布時，這些信息基因選擇方法便不能獲得最佳實驗結(jié)果 ,采用 Bhattacharyya 距離度量基因的分類能力便失去了理論基礎 。 5 ))2/()l n((21))/()((41)( 22222 ???????? ????? iiiiiiiiigB F SC ???????? (6) 與式 (5)對比發(fā)現(xiàn)，二者在形式上比較相似，但式 (6)有堅實的理論基礎 ； 朱云華 等 [21]采用 Bhattacharyya 距離度量基因的分類能力 并在 小圓藍細胞瘤（ Small Round Blue Cells Tumor， SRBCT） 數(shù)據(jù)集上進行實驗 獲得了較好的 實驗 結(jié)果 。 基因表達譜中 多數(shù)基因的表達與腫瘤無關(guān)， 這為信息基因選擇 帶來很大困難， 采用單一 方法很難 完成這一任務，因此，通常首先采用 一種稱之為基因排序 (gene ranking)的方法對原始基因集合進行粗選，其基本思想便是按照某種記分準則對每一個基因 進行記分，基因分值大小反映了基因的重要程度，然后按基因分值大小降序 排列基因并選擇排在前面的一定數(shù)量的基因作為選擇結(jié)果。遞增方式就是從一個 初始集合 ?＝0T 開始按照某一策略 選擇一個基因并加入到已 選擇基因 集合 iT 中 ， 則第 1?i 步所選則的基因子集}{1 gTT ii ??? ， iTGg ?? ，使 )()( 1 ii TAccTAcc ?? 成立， 直到獲得 滿足 期望的分類準確率 的候選信息基因子集 T 為止 ，例如， Momiao Xiong 等 [16]提 出 的 順序向前 搜索 (Sequential Forward Search, SFS)算法 就是一種遞增式信息基因選擇算法 ，其缺點是一旦往 T 中加入一個基因就不能在后續(xù) 搜索過程中將其從 T 中刪除 ；而遞減方式就是從一個 初始 集合 GT? 開始按照某一個策略每次從集合 T 中刪除一個 或幾個 冗余基因直到獲得一個滿足需要的候選信息基因子集 T 為止 ，例如， 李穎新 等 [17, 18]采用 靈敏度分析和兩兩冗余分析方法剔除 冗余基因就是遞減方式的信息基因選擇方法 。 通常，分類算法按其子過程有無反饋可分為 Filter 方法和 Wrapper 方法 [15]，但由于 腫瘤分類 過程 模型的復雜性 以及分類方法的不斷進步 ， 其過程模型也越來越復雜，所以， 沿用軟件工程學中軟件 開發(fā)過程模型 的分類準則對腫瘤分類過程模型進行分類，可 分為 兩種：瀑布模型和迭代模型。 由于基因總數(shù) n 通常很大，所以 在 n2 的 基因空間 內(nèi)使用窮舉 搜索方法發(fā)現(xiàn) *A 是一個不現(xiàn)實的方法 ，因此 ，需要設計 壓縮搜索空間的啟發(fā)式 搜索 算法 來漸進達到這一目標 。到目前為止，科學家們并不 完全 清楚哪些基因 是與特 定腫瘤相關(guān)的以及與腫瘤相關(guān)的 基因 數(shù)量是多少，因此，可以 假設 對于特定的腫瘤樣本集 其分類能力 最 強的基因子集 T 是與腫瘤相關(guān)的基因，從生物醫(yī)學角度考慮，這一假設 也有一定的合理性 。矩陣 M 的一行表示同一條件下所有基因的基因表達譜，構(gòu)成 n 維空間的一個 點，而矩陣 M 的一列表示一個基因在不同條件下的表達情況 。 本文在獲得了腫瘤樣本集的基本結(jié)構(gòu)的先驗知識的 基礎上提出一種基于 SVM 的 FilterWrapper 混合 方法 來搜索腫瘤信息基因，其 本質(zhì)是一種 以腫瘤樣本集的分類性能作為 啟發(fā) 式 反饋信息 的寬度優(yōu)先搜索算法， 最 后 采用 了三 種腫瘤樣本集進行實驗以驗證 所設計的 啟發(fā)式 算法的 可行性和有效性 。 雖然近幾年已提出許多解決信息基因選擇問題的 新方 法 [2]， 但對這個問題的研究還不夠 理想。 模式 分類方法主要分為 無監(jiān)督 的聚類 方法 和有 監(jiān)督 的學習 方法 兩 大 類。 1999 年， Golub 等 [1]發(fā) 表了一篇采用 基因表達譜分類 急性白血病亞型的文章， 開創(chuàng) 了 基于基因表達譜的腫瘤分類 問題研究的先河 ， 此后 科學家們 已 陸續(xù)提出很多 腫瘤分類方 法 [2]， 使 這一領(lǐng)域很快成為生物信息學的一個研究熱點 。王戟（ 1969），男，博士，教授，博士生導師， CCF 高級會員，研究方向：軟件理論、高可信軟件、 Agent 軟件方法學和生物信息 學 。 tumor classification。 實驗采用 了 三種腫瘤 樣本 集 以 驗證 新 算法 的 可行性和 有效性 ， 對于急性白血病 、難以分類的結(jié)腸癌和多腫瘤亞型的小圓藍細胞瘤樣本集 ， 分別 只需 4 和 4 個 信息 基因就能獲得 100％的4折 交叉驗證識別準確率 。王戟（ 1969），男，博士，教授，博士生導師， CCF 高級會員，研究方向：軟件理論、高可信軟件、 Agent 軟件方法學和生物信息 學 。 陳火旺（ 1936），男， 福建安溪，教授，博士生導師，中國工程院院士，主要研究領(lǐng)域為：軟件理論、人工智能和軟件工程 。 與其它 優(yōu)秀的 腫瘤分類 方法相比，實驗結(jié)果 在 信息基因數(shù)量及其 分類性能方面 具有明顯的優(yōu)越性 。 informative gene selection。 陳火旺（ 1936），男， 福建安溪，教授，博士生導師，中國工程院院士，主要研究領(lǐng)域為：軟件理論、人工智能和軟件工程 。 現(xiàn)代醫(yī)學認為，腫瘤的發(fā)生發(fā)展必定表現(xiàn)在相關(guān)基因 在不同組織中 的表達差異上，因此，借助基因表達譜樣本診斷腫瘤及其亞型必將成為一種快速準確的臨床診斷方法， 阮曉鋼 [3]等采用生物信息學方法分析和研究了腫瘤信息基因的發(fā)現(xiàn)及其表達模式問題， 將不同組織類型的腫瘤整合為一個整體加以研究，并 從信息學角度論證 了 腫瘤信息基因在腫瘤樣本中特異表達的普遍性與客觀性。 無監(jiān)督的腫瘤 樣本聚 類方法 通過樣本的相似性度量 能夠發(fā)現(xiàn)腫瘤樣本集的結(jié)構(gòu)特征， 即相似的樣本自然聚成一類 [5， 6]， 像 自組織映射(SelfOrganizing Maps, SOM)這種聚類方法在腫瘤分類領(lǐng)域 亦 得到廣泛應用 [7]， 其優(yōu)點是有助于 發(fā)現(xiàn)新的腫瘤亞型 ；但在腫瘤分類領(lǐng)域更主要的是采用有監(jiān)督分類方法，因為它能充分利用樣本的已知類別信息 。腫瘤分類領(lǐng)域 的一個目標是 采用盡可能少的信息基因 以 獲得盡可能高的樣本分類準確率，其理由是： (1)選擇盡可能少的信息基因也就意味著 盡可能多地去掉了 包含在樣本中的噪音 ； (2)意味著減少腫瘤診斷成本 ； (3)分類準確率高的信息基因通常與腫瘤的發(fā)生發(fā)展存在緊密聯(lián)系 。 2 腫瘤 亞型 分類問題 描述 設 },{ 1 nggG ?? 表示 基因表達譜數(shù)據(jù)集中所有基因構(gòu) 成的一個基因全集 ，其中 )1( nigi ?? 表示一個基因， nG? 表示基因總 數(shù)。Class 表示樣本 的 所屬類別 集合 ， 即 },{ 1 kccClass ?? ， 其中 kClass ? 表示樣本類別總數(shù) 。 設 )(TAcc 表示基因子集 T 對樣本集的分類能力， 則問題的目標可形式化表示為 式（ 1）、（ 2）和（ 3）。 3 腫瘤分類 過程 模型 與實現(xiàn)算法 腫瘤分類過程模型 腫瘤分類是模式分類 方法在 生物 醫(yī)學領(lǐng)域 的一個具體應用，因此， 腫瘤分類過程模型同樣與模式分類過程模型具有相似性 ， 主要 分為 五個階段： 基因 表達譜數(shù)據(jù)獲取、基因表達譜數(shù)據(jù)預處理、 特征抽取或 信息基因選擇 、 分類模型建立以 及 分類 預測與 評估 ，如圖 1 所示， 虛線的左邊部分是一個生物醫(yī)學過程，而其右邊部分是一個信息處理過程 。實際上，瀑布模型和迭代模型是對 Filter 方法和 Wrapper方法在概念上的延伸，使之更適合 于 復雜的腫 瘤分類過程模型?；旌戏绞絼t是從一個隨機產(chǎn)生的 初始集合 T 或 ??T 開始按照一定的策略從集合 T 中刪除基因或往集合 T 中增加基因直到獲 到滿足需要的候選信息基因集合 T 為止 ，例如 ， 順序向前浮動搜索 （ Sequential Forward Floating Search， SFFS） 算法 [16]與 基于遺傳算法 (Geic Algorithm， GA)的信息基因選擇算 法 [19]。 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ū) 分 正類樣本和負類 樣本的 分類 能力大小。 具體方法是 首先 以式 (6)為每一個基因 niGgi ??? 1, 計算其 BFSC 值，然后按照BFSC 值大小對全部基因進行降序排列并選擇前 p 個基因作為初選信息基因集合 *G ，通常 np?? ，不 妨記 為 }1|{* pjgG j ??＝ 。鄧林等 [22]采用峰度和偏度對結(jié)腸癌數(shù)據(jù)集、白血病數(shù)據(jù)集和乳腺癌數(shù)據(jù)集以實驗的方式進行了正態(tài)性檢驗，零假設是樣本服從高斯分布，所選取的顯著性水平為 ，實驗表明這三種 腫瘤數(shù)據(jù)集都不服從高斯分布，并由此推斷腫瘤數(shù)據(jù)集不服從高斯分布是普遍的； 然后 他們采用 Wilcoxon 秩和檢驗方法進行信息基因選擇并以 SVM 為分類器獲得了很好的實驗結(jié)果 ， 并 從理論分析上和實驗驗證上論證了秩和檢驗方法優(yōu)于 t 檢驗方法 。 信息基因精選 我們曾采用因子分析方法從基因表達譜樣本 抽取 潛在 因子 [24]以 及 采用獨立分量分析方法從基因表達譜中抽取獨立分量 [25]以 用于 SVM 對 兩種 腫瘤樣本 集 （結(jié)腸癌和 急性 白血病） 進行分類，實驗結(jié)果表明，當抽取的因子數(shù)量或獨立分量的個數(shù)較少時，其分類性能 很高 ， 較多時其分類性能反而降 低，由此 推測基因表達譜中的信息基因數(shù)量較少時 (具體地說，只需 3 個或 4 個信息基因 )就可以獲得很高的分類 性能 [2]。 需要注意的是，不同節(jié)點的路徑 所代 表的信息基因集 在不考慮順序的前提下可能相同，因此在計算節(jié)點的分類性能時如果發(fā)現(xiàn)前面已計算過，則該節(jié)點的分類性能 記為 0 以避免擴展不 必要的節(jié)點。 10N…… 11N21NpN112N12?pN…… )1(2?ppN…… 21N}{ 1?pg}{ pg}{ pg}{ 1g}{ 2g}{ 2g? 圖 2 啟發(fā)式寬度優(yōu)先 搜索信息基因 子集 示意圖 HBSA算法 實現(xiàn) 在獲得最佳信息基因子集 *A 的過程中， 并不需要真正構(gòu)造搜索樹， 只需保留每一 次搜索到的滿足給定要求的信息基因 子集及其分類性能指標就能達到預期目標 。 算法： HBSA(M , p ,w ,Depth )； 輸入 ： 基因 表達譜 M ,p 為初選信息基因 個數(shù) , w 為選擇的基因子集個數(shù)， Depth 為迭代深度 ； 輸出 ： 最佳 信息基因集合 *A ； 1. For each