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