基于隱馬爾可夫模型的轉(zhuǎn)錄因子文本挖掘算法

吳曉洲, 萬(wàn)里明, 韓霄松, 梁艷春, 吳春國(guó),3

(1. 吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室, 長(zhǎng)春 130012; 2. 中國(guó)人民解放軍空軍裝備研究院 裝備總體論證研究所, 北京 100076; 3. 上海理工大學(xué) 管理學(xué)院, 上海 200093)

本文基于文獻(xiàn)[1-2]提出一種基于隱馬爾可夫模型的轉(zhuǎn)錄因子文本挖掘算法HMM-TFM(hidden Markov model based transcription factor name mining), 使用隱馬爾可夫模型在英文文獻(xiàn)中識(shí)別轉(zhuǎn)錄因子名稱, 該方法HMM易于建立, 不需要大規(guī)模的轉(zhuǎn)錄因子實(shí)體詞庫(kù)與規(guī)則集.

1 基于隱馬爾可夫模型的轉(zhuǎn)錄因子文本挖掘算法

隱馬爾可夫模型HMM由一個(gè)五元組(ΩX,ΩO,A,B,π)表示, 其中:ΩX={X1,…,XN}表示隱藏狀態(tài)集合;ΩO={O1,…,OM}表示觀察值集合;A=(aij)表示狀態(tài)轉(zhuǎn)移概率矩陣;B=(bi(k))表示觀察值概率矩陣;π=(π1,…,πN)是初始狀態(tài)[3]. 通常簡(jiǎn)略地將隱馬爾可夫模型表示成三元組的形式λ={A,B,π}. 觀察值集合與隱藏狀態(tài)集合的選擇對(duì)算法的性能至關(guān)重要.

HMM-TFM首先將文獻(xiàn)以自然語(yǔ)句為單位處理成觀察值序列, 每個(gè)單詞對(duì)應(yīng)一個(gè)觀察值. 一些在自然語(yǔ)言中頻繁出現(xiàn)的常用單詞, 如連接詞、 介詞、 系動(dòng)詞等, 由于其數(shù)量較少, 可標(biāo)記其真實(shí)詞性, 并以真實(shí)詞性作為其觀察值, 其他單詞的觀察值是根據(jù)后綴判斷的詞性. 本文的觀察值集合為

ΩO={verb,adv,conj,art,prep,adj,be,noun,punctuation,unknown},

其中: verb表示動(dòng)詞; adv表示副詞; conj表示連接詞; art表示冠詞; prep表示介詞; adj表示形容詞; be表示系動(dòng)詞; noun表示名詞; 有從句出現(xiàn)時(shí), 若不考慮標(biāo)點(diǎn)符號(hào)會(huì)使句子語(yǔ)法結(jié)構(gòu)變得混亂, 則punctuation表示標(biāo)點(diǎn)符號(hào)也作為一種觀察值; unknown表示根據(jù)后綴無(wú)法判斷詞性的單詞. 高頻詞和后綴到觀察值的映射關(guān)系列于表1. 由表1可見(jiàn), 映射關(guān)系可判斷多數(shù)單詞的詞性. 如后綴“-ment”對(duì)應(yīng)觀察值noun, 后綴“-ate”對(duì)應(yīng)觀察值verb. 在本文使用的訓(xùn)練樣本中, 共出現(xiàn)1 095個(gè)不同的單詞, 其中只有370個(gè)單詞根據(jù)該映射表不能判斷詞性, 即訓(xùn)練樣本的觀察值序列中, unknown的比例較小.

表1 高頻單詞與后綴到觀察值的映射關(guān)系Table 1 Relationship of high-frequency words, suffixes and observations mapping

HMM-TFM算法中隱藏狀態(tài)表示單詞在實(shí)際語(yǔ)境中的真實(shí)詞性, 本文的隱藏狀態(tài)集合為

ΩX={verb,adv,conj,punctuation,art,prep,adj,be,noun,tf},

其中, 狀態(tài)tf為表示轉(zhuǎn)錄因子的單詞,其他隱藏狀態(tài)的含義與觀察值集合中對(duì)應(yīng)元素的含義相同, 但觀察值通過(guò)判斷后綴得到詞性, 而隱藏狀態(tài)通過(guò)人工標(biāo)記或HMM解碼得到當(dāng)前語(yǔ)境中的真實(shí)詞性.

為了高效過(guò)濾掉與轉(zhuǎn)錄因子無(wú)關(guān)的語(yǔ)句,本文定義一個(gè)謂語(yǔ)集, 通過(guò)語(yǔ)句的謂語(yǔ)判斷其是否與轉(zhuǎn)錄因子的描述相關(guān). 謂語(yǔ)集中包含8個(gè)元素, 是通過(guò)人工閱讀50篇轉(zhuǎn)錄因子相關(guān)文獻(xiàn)總結(jié)出的動(dòng)詞, 這些動(dòng)詞在文獻(xiàn)中通常作為謂語(yǔ)描述轉(zhuǎn)錄因子與啟動(dòng)子的調(diào)控或結(jié)合關(guān)系. 因此, 在將文獻(xiàn)中語(yǔ)句處理成觀察值序列時(shí), 只需處理謂語(yǔ)集中元素出現(xiàn)的語(yǔ)句. 與建立轉(zhuǎn)錄因子名稱的詞庫(kù)相比, 使用謂語(yǔ)集更簡(jiǎn)單易行. 謂語(yǔ)集中元素如下：

predicate{repress,bind,transactivate,regulate,activate,suppress,upregulate,downregulate}.

謂語(yǔ)集中元素作為謂語(yǔ)出現(xiàn)在語(yǔ)句中時(shí), 轉(zhuǎn)錄因子可能出現(xiàn)在主語(yǔ)或主語(yǔ)從句中. 語(yǔ)句中動(dòng)詞后面的部分是賓語(yǔ)、 賓語(yǔ)從句或修飾賓語(yǔ)的定語(yǔ). 在使用謂語(yǔ)篩選語(yǔ)句后, 對(duì)于主動(dòng)語(yǔ)態(tài)語(yǔ)句, 轉(zhuǎn)錄因子的名稱不會(huì)出現(xiàn)在謂語(yǔ)后面, 因此在將語(yǔ)句處理成觀察值序列時(shí), 可不考慮動(dòng)詞后面的部分； 類似地, 對(duì)于被動(dòng)語(yǔ)態(tài)語(yǔ)句, 則只處理謂語(yǔ)后面的部分. 理論上, 這樣處理可縮短時(shí)間序列的長(zhǎng)度, 從而降低HMM-TFM算法的時(shí)間復(fù)雜度和空間復(fù)雜度.

2 實(shí)驗(yàn)結(jié)果

以“transcription factor”和“promoter”為關(guān)鍵詞在科技引文數(shù)據(jù)庫(kù)中進(jìn)行文獻(xiàn)的采集, 選出50篇英文文獻(xiàn)作為HMM-TFM算法的訓(xùn)練集. 經(jīng)過(guò)人工篩選后共得到969條包含謂語(yǔ)集中動(dòng)詞的語(yǔ)句, 選出其中100條作為訓(xùn)練樣本. 通過(guò)人工標(biāo)記詞性得到這些語(yǔ)句的隱藏狀態(tài)序列, 觀察值序列通過(guò)上述方法獲得. 訓(xùn)練得到的初始概率向量為π={0.070 18,0.162 36,0.092 97,0.001 17,0.162 07,0.116 43,0.069 65,0.000 29,0.231 78,0.093 09}. 狀態(tài)轉(zhuǎn)移概率矩陣和觀察值概率矩陣分別列于表2和表3.

由于文獻(xiàn)長(zhǎng)度影響單詞的總得分, 而且有的文獻(xiàn)會(huì)同時(shí)提到若干個(gè)轉(zhuǎn)錄因子, 因此選擇一個(gè)固定的閾值或取最高得分并不合適. 對(duì)于每篇文獻(xiàn), HMM-TFM算法選擇最高分單詞得分的80%作為閾值. 實(shí)驗(yàn)結(jié)果表明, 當(dāng)文獻(xiàn)中只提到一種轉(zhuǎn)錄因子時(shí), 其得分明顯高于其他單詞, 不會(huì)因?yàn)閷㈤撝到档偷阶罡叩梅值?0%而將其他單詞識(shí)別為轉(zhuǎn)錄因子名稱. 而文獻(xiàn)中出現(xiàn)多個(gè)轉(zhuǎn)錄因子時(shí), 這些單詞的得分較接近, 這種閾值設(shè)定方法能夠避免轉(zhuǎn)錄因子的遺漏.

表2 狀態(tài)轉(zhuǎn)移概率矩陣Table 2 State transition probability matrix

表3 觀察值概率矩陣Table 3 Observation likelihood matrix

為了測(cè)試HMM-TFM算法的準(zhǔn)確性, 本文在Pubmed上以“transcription factor”為關(guān)鍵詞選擇150篇文獻(xiàn)作為實(shí)驗(yàn)樣本, 通過(guò)人工閱讀標(biāo)記出190個(gè)轉(zhuǎn)錄因子名稱. HMM-TFM算法共找到181個(gè)表示轉(zhuǎn)錄因子的單詞, 其中有141個(gè)與人工標(biāo)記結(jié)果一致. 實(shí)驗(yàn)結(jié)果表明, HMM-TFM的查全率和查準(zhǔn)率分別為74.2%和77.9%. 與文獻(xiàn)[4-5]中算法性能接近, 但不需要使用轉(zhuǎn)錄因子名稱詞庫(kù), 通過(guò)HMM標(biāo)記單詞詞性減少了工作量, 更簡(jiǎn)單易行.

[1] ZHOU De-yu, HE Yu-lan, Kwoh C K. Semi-supervised Learning of the Hidden Vector State Model for Extracting Protein-Protein Interactions [J]. Artificial Intelligence in Medicine, 2007, 41(3): 209-222.

[2] LIU Jie-bin, SONG Mao-qiang, ZHAO Fang, et al. Second-Order Hidden Markov Model Based on Context [J]. Computer Engineering, 2010, 36(10): 231-233.

[3] ZOU Ling-yun, WANG Zheng-zhi, WANG Yong-xian, et al. Combined Prediction of Transmembrane Topology and Signal Peptide of Beta-Barrel Proteins: Using a Hidden Markov Model and Genetic Algorithms [J]. Computers in Biology and Medicine, 2010, 40(7): 621-628.

[4] Fundel K, Guttler D, Zimmer R, et al. A Simple Approach for Protein Name Identification: Prospects and Limits [J]. BMC Bioinformatics, 2005, 6(Suppl 1): 1-15.

[5] Yang Q, Zheng G Y, Xiong Y, et al. Qnet-BSTM: An Algorithm for Mining Transcription Factor Binding Site from Literature [J]. Journal of Computer Research and Development, 2008, 45(Suppl 1): 323-329.