ＲＥ－ＯＥＭ：一種半結構化生物數據的信息抽取模型
2008-12-31 00:00:00曹順良劉杰王健劉念祖李亦學
計算機應用研究 2008年9期
摘 要：在分析半結構化生物數據特點的基礎上，提出了一種新的半結構化數據抽取模型REOEM。它將OEM數據模型和正則表達式有機地結合起來，不但能夠靈活方便地表示各種數據結構，而且能夠非常方便地進行模式匹配和數據的定位，為半結構化生物數據的抽取打下堅實基礎。
關鍵詞：半結構化；生物數據；抽取模型；OEM數據模型；正則表達式
中圖分類號：TP393.04 文獻標志碼：A
文章編號：1001-3695(2008)09-2647-04
REOEM:model for information extraction from semistructured biological data
CAO Shunliang1，2，LIU Jie2，WANG Jian3，LIU Nianzu2，LI Yixue4
（1.Dept. of Information Science， Shanghai Lixin University of Commerce， Shanghai 201620 ，China; 2.School of Management， Fudan University， Shanghai 200433 ，China; 3.School of Life Science， Shanghai University， Shanghai 200444， China; 4 Shanghai Center for Bioinformation Technology， Shanghai 200235， China)
Abstract:In the biological data integration process， it is key to extract information， with specific integration goal in mind， from semistructured data and represent this information in a structured manner.This paper proposed REOEM based on analysis of biological data characteristics. It combined OEM data model and regular expression to represent data structure. It facilitates data extraction from semistructured biological data by enabling convenient pattern matching and data locating.
Key words:semistructured; biological data; extraction model; OEM data model; regular expression
0 引言
在生物學數據中存在著大量的半結構化數據文件，這些數據文件是由標簽和相關的值所構成的具有一定規則的序列[1]。半結構化數據格式的優點是能夠表示更加復雜、具有層次（樹型）結構的信息，如一條序列包含多條參考文獻，每條參考文獻又可能包含多個作者，數據的表示具有很大的靈活性。然而這些格式的數據文件并不支持多個用戶的并發使用。如果沒有建立索引，整個文件必須進行順序的讀取，尋找匹配用戶輸入的數據效率將非常低下。此外，要指定只對數據文件的哪部分內容進行查詢幾乎是不可能的。例如一個用戶想查詢哺乳動物的序列，沒有辦法指定只搜索文件中的生物體（organism）那一節內容以加快查詢的速度。在對數據文件進行全文檢索時，不支持復雜的、組合的檢索條件，全文檢索還有可能返回錯誤的數據。例如考慮一個記錄有人類和老鼠的具有直系同源的基因的信息，每一個基因都記錄著它們在染色體中的位置。假設用戶想尋找所有與老鼠的10號染色體上的基因直系同源的人類基因的信息，簡單的文本查詢沒有辦法確定10號染色體指的是人類基因而不是老鼠的基因。最后，文本查詢也沒有簡單的方法從兩個相關的數據源中檢索出相關的數據。
為了克服半結構化數據的缺點，經常需要對半結構化數據文件進行數據抽取并轉換到其他數據模式（如關系數據模式）中，以方便數據的檢索和利用。在數據集成中，半結構化的數據模式的表示、數據的抽取和轉換是其關鍵步驟。
由于生物學數據缺乏統一的、固定的模式，數據往往是不規則的且經常變動，再加上生物資源的動態性、分布性、異構性等特點，使對生物學數據的信息抽取越來越困難。經分析表明，相當數量的生物學數據都以半結構化的形式存在，如何將這些半結構化的數據根據特定的數據集成的目標進行信息抽取并以結構化的方式進行表示是進行生物學數據集成的關鍵。信息抽取模型是進行信息抽取的前提，進行信息抽取模型的研究具有重要的理論價值和實際意義。
1 半結構化生物數據的格式及其特點
由于歷史原因，各種生物數據庫采用了不同的信息格式，如GBFF格式、ASN.1格式、CODATA格式、FASTA格式、Staden格式、GCG格式、Plain/Raw格式、Nexus格式、NBRF格式、Stockhom格式、MSF格式、XML格式等。通過分析發現，生物數據庫中絕大多數都采用文本文件的數據格式，這些文件絕大部分是半結構化的。下面以GBFF格式為例來說明生物學數據中半結構化數據的格式及其特點。GBFF是GenBank數據庫的基本信息單位，是最為廣泛使用的生物信息學序列格式之一[2]。以下是一個GBFF文件的例子： locus AAURRA 118 bp ssrRNA RNA 16JUN1986
definition A.auriculajudae (mushroom) 5S ribosomal RNA.
accession K03160
version K03160.1 GI:173593
keywords 5S ribosomal RNA; ribosomal RNA.
source A.auriculajudae (mushroom) ribosomal RNA.
organismAuricularia auriculajudae Eukaryota; Fungi; Eumycota; Basidiomycotina; Phragmobasidiomycetes;Heterobasidiomycetidae; Auriculariales; Auriculariaceae.
reference 1(bases 1 to 118)
authors Huysmans E，Dams E，Vandenberghe A and De Wachter R.
title The nucleotide sequences of the 5S rRNAs of four mushrooms and their use in studying the phylogenetic position of basidiomycetes among the eukaryotes
journal Nucleic Acids Res. 11， 2871-2880 (1983)
features location/qualifiers
rRNA 1..118
/note=\"5S ribosomal RNA\"
base count 27a 34c 34g 23t
origin 5′ end of mature rRNA.
1 atccacggcc ataggactct gaaagcactg catcccgtcc gatctgcaaa gttaaccaga
61 gtaccgccca gttagtacca cggtggggga ccacgcggga atcctgggtg ctgtggtt
//
LOCUS ABCRRAA 118 bp ssrRNA RNA 15SEP1990
definition Acetobacter sp.(strain MB 58) 5S ribosomal RNA， complete sequence.
accession M34766
version M34766.1 GI:173603
keywords 5S ribosomal RNA.
source Acetobacter sp. (strain MB 58) rRNA.
organismAcetobacter sp.Prokaryotae; Gracilicutes; Scotobacteria; Aerobic rods and cocci;Azotobacteraceae.
reference 1(bases 1 to 118)
authors Bulygina E S，Galchenko V F，Govorukhina N I，Netrusov A I，Nikitin D I，Trotsenko Y A and Chumakov K M.
title Taxonomic studies of methylotrophic bacteria by 5S ribosomal RNA sequencing
journal J. Gen. Microbiol. 136， 441446 (1990)
……（為節省頁面，該記錄的后面部分省略）
GBFF文件按域（field）可以劃分為三個部分：頭部包含整個記錄的信息（描述符）；第二部分包含了注釋這一記錄的特性；第三部分是核苷酸序列本身。所有序列數據記錄都在最后以“//”結尾，也可以將“//”看成記錄之間的分割符。
所有的GBFF都起始于locus行，行首為locus標記，接下來在行中第13個位置開始的為大于等于6個字母或數字構成的字符串為locus名稱，用來表示本記錄描述的基因座，然后出現的是序列的長度、分子類型、GenBank分類碼以及最后修訂日期。行中每一部分都出現在固定的位置上，每一部分之間用空格分割。Locus行下為definition行，該行主要對GenBank中所含的生物學意義作出總結。檢索號（accession）處在GenBank文件的第三行，它是序列記錄的惟一指針。
可以看出，在GBFF中具有一定的信息結構即模式，模式信息和數據信息是混合在一起的。要從這些數據文件中抽取出所需要的信息，給出文件中的信息結構是至關重要的。
經過分析可以看到，生物數據文本文件除了具有通常的半結構化數據的特點以外，它還有自己的一些特點：
a）一個文本文件通常由記錄構成，記錄與記錄之間有明顯的標記進行分割。
b）每一條記錄中由多個具有特定意義的對象構成，對象與對象之間出現的先后次序是相對固定的。
c）對于人來說可以非常容易地識別文件的結構，但對計算機來說并沒有提供類似于HTML那樣簡單的對象的定界符， 有些對象的數據抽取沒有合適的定界符可用，更為糟糕的是，被宣稱用做定界符的字符串可能會出現在文件中的任何位置（即噪聲數據）。
d）記錄中的對象是有層次的，如一條記錄中可能包括若干條參考文獻，每條參考文獻又可以分為作者、題目、發表日期等子對象，依此類推。
e）一些對象在每一條記錄中都必然出現，而有些對象是可選的（即可以出現也可以不出現），有些對象在一條記錄中允許出現多次。
f）由于生物數據庫具有自治的特點，數據文件模式的變化是經常發生的，如經常會增加一個對象或減少一個對象。對于抽取程序而言，相當于數據中出現了缺失和噪聲。
2 相關研究
數據模型用來表示要抽取的半結構化數據的數據模式。由于半結構化數據模型的重要性，近年來在這方面做了很多研究工作，提出了多種模型用來對半結構化的數據進行表示[3，4]。通常這些模型都是基于帶標記的有向圖，用來描述半結構化數據內在的不規則結構。TSIMMIS[5]項目采用了基于對象的OEM模型。一個OEM對象可以是原子類型也可以是復雜類型。復雜類型的OEM對象是一個對象引用的集合，這些引用指向組成這個復雜類型OEM對象的那些組件，這些引用可以是嵌套的。在文獻[3]中提出的用于UnQL查詢語言的數據模型和OEM模型非常相似；不同之處在于，UnQL數據模型沒有對象的概念，它使用一個樹集合來描述數據，樹中的葉子節點表示數據的實例。在文獻[4]中提出的數據模型也是用帶標記的有向圖來表示數據的一種模型。圖中每一個節點與一個對象相對應，從任何一個節點發出的邊都用不同的標記進行標志。其他比較有名的還有DataGuides[6~8]、一元算法模型[9]、模型定義語言ScmDL[10]等。無論是哪一種描述形式，其基礎都是采用帶標記的有向圖作為半結構化數據模型，該類模型的典型代表就是OEM模型[11]。本文構建的半結構化數據抽取模型REOEM就是建立在OEM基礎上的。
3 REOEM的構建
數據抽取模型用來說明需要從一個數據源中抽取的數據對象的組成結構，是進行數據抽取的重要組成部分。針對生物數據的特點，本文在OEM數據模型和正則表達式的基礎上提出了一種半結構化數據抽取模型REOEM。
3.1 OEM數據模型
OEM是自描述對象模型，專為表達半結構化數據而設計。它最初的目的是為異構數據源間的數據交換提供高度靈活的轉換工具[12]。
在這個數據模型中，每一個實體都是對象，每一個對象都有惟一的標志。對象分為兩類：原子對象和復雜對象。所謂原子對象是指該對象不再有子對象，而且其值的類型為基本原子類型，如integer、string、real等；復雜對象的值是對象引用（object references）的集合，每一個對象引用指向一個子對象，記做（label，oid）。
OEM中的每個對象具有如下結構：
labeltypevalueobjectID
其中：label是一個變長的字符串，用來表示一個對象以及這個對象所代表的含義type表示對象值的數據類型。每一個類型要么是一個原子類型（如integer、string、real等），要么是一個set類型。Value表示如果是一個原子類型的對象，則表示對象的值；如果是一個復雜類型的對象，則value表示對象引用，用{〈l1，oid1〉，…，〈ln，oidn〉}表示。其中li（i=1..n）為該對象的子對象的label；oidi為該對象子對象的objectID。ObjectID是對象的惟一標志。
OEM數據模型的主要特點是自描述性，沒有必要預先描述一個對象的結構，也不存在所謂固定模式（fixed schema）的概念。從某種意義上來說，每個對象包含了它自己的模式。OEM的這種自描述型的結構為異構的、動態的環境下進行數據的交換和轉換提供了高度的靈活性，如可以方便地在OEM圖中增加或刪除某個對象。這為半結構化的數據管理提供了一種比較理想的數據模型。但是在將OEM模型用于數據抽取時，則表現出相當的局限性，其主要缺陷是很難用OEM模型對需要抽取的數據進行準確的定位。
3.2 正則表達式
簡單地說，正則表達式就是一個字符構成的串，它定義了一個用來搜索匹配字符串的模式。正則表達式可以讓用戶通過使用一系列的特殊字符構建匹配模式，然后把匹配模式與數據文件、程序輸入以及Web頁面的表單輸入等目標對象進行比較，根據比較對象中是否包含匹配模式執行相應的程序。許多語言，包括Perl、PHP、Python、Java、JavaScript和JScript都支持用正則表達式處理文本。
為了能夠使用戶更加靈活地定制模式內容，正則表達式提供了專門的元字符。所謂元字符就是指那些在正則表達式中具有特殊意義的專用字符，可以用來規定其前面的子表達式在目標對象中的出現模式。較為常用的元字符如表1所示。
表1 正則表達式中比較常用的幾個元字符
元字符含 義
+子表達式必須在目標對象中連續出現一次或多次
*子表達式必須在目標對象中連續出現零次或多次
？子表達式必須在目標對象中連續出現零次或一次
{n}子表達式必須在目標對象中連續出現n次
{n，m}子表達式必須在目標對象中連續出現n到m次之間
\\s匹配任何空白字符，包括空格、制表符、換頁符、換行符等
.用于匹配除換行符之外的所有字符
\匹配一個換行符
()標記一個子表達式的開始和結束位置
除了以上所介紹的元字符之外，正則表達式中還具有另外一種較為獨特的專用字符，即定位符。定位符用于規定匹配模式在目標對象中的出現位置，較為常用的定位符包括：“^”“$”“\\b”以及“\\B”。其中，“^”定位符規定匹配模式必須出現在目標字符串的開頭；“$”定位符規定匹配模式必須出現在目標對象的結尾；“\\b”定位符規定匹配模式必須出現在目標字符串的頭或尾兩個邊界之一，而“\\B”定位符則規定匹配對象必須位于目標字符串的開頭和結尾兩個邊界之內，即匹配對象既不能作為目標字符串的開頭，也不能作為目標字符串的結尾。
為了能夠方便用戶更加靈活地設定匹配模式，正則表達式允許使用者在匹配模式中指定某一個范圍而不局限于具體的字符，如表達式/[A~Z]/將會與A~Z范圍內任何一個大寫字母相匹配。
構造正則表達式的方法和創建數學表達式的方法一樣，也就是用多種元字符與操作符將小的表達式結合在一起來創建更大的表達式。正則表達式的組件可以是單個的字符、字符集合、字符范圍、字符間的選擇或所有這些組件的任意組合。以下為一個文檔實例，它是KEGG數據庫中reaction的文件片段。
entry R00001
namePolyphosphate polyphosphohydrolase
definition Polyphosphate+H2OOligophosphate
equation C00890+C00001C02174
enzyme 3.6.1.10
///
entry R00002
name Reduced ferredoxin:dinitrogen oxidoreductase (ATPhydrolysing)
definition 16ATP+16H2O8 e-+8 H++16 Orthophosphate+16 ADP
equation 16 C00002+16 C000018 C05359+8 C00080+16 C00009+16 C00008
enzyme 1.18.6.1
///
entry R00004
name Pyrophosphate phosphohydrolase
definition Pyrophosphate + H2O2 Orthophosphate
equation C00013 + C000012 C00009
pathway path:RN00190 Oxidative phosphorylation
enzyme 3.6.1.1
///
enetry R00005
name Urea1carboxylate amidohydrolase
definition Urea1carboxylate+H2O2 CO2+2 NH3
equation C01010+C000012 C00011+2 C00014
pathway path:RN00220 Urea cycle and metabolism of amino groups
path:RN00910 Nitrogen metabolism
path:RN00791Atrazine degradation
enzyme 3.5.1.54
comment The yeast enzyme (but not that from green algae) also catalyses the reaction of EC 6.3.4.6 urea carboxylase， thus bringing about the hydrolysis of urea to CO2 and NH3 in the presence of ATP and bicarbonate.
R00774(6.3.4.6)
從上述的敘述中可以看出，正則表達式具有非常強大的定位能力和模式匹配能力，能夠有效地彌補OEM的缺陷。把OEM的表示方法與正則表達式有機地結合起來，將能夠很好地、細粒度地描繪要抽取文檔的數據結構，構建文檔的數據模式，有效地進行數據抽取。基于這些想法，本文創建了REOEM數據模型。
3.3 REOEM數據抽取模型
為了敘述的方便，本文以抽取文檔實例來介紹REOEM數據抽取模型。
REOEM數據模型是在OEM數據模型的基礎上擴展而成的。REOEM中的每個對象具有如下結構：
labeltypevalueobjectIDnumber
其中：label與OEM中的label意義相同，用來表示一個對象以及該對象所代表的含義；type表示對象的類型，有A、D和S三種取值（A表示該對象為屬性，即需要從文檔中抽取的數據；D表示該對象為一定界符，用來定位需要提取的屬性的值，定界符分為左定界符和右定界符兩類，位于屬性左邊的定界符稱左定界符，位于屬性右邊的定界符稱右定界符；S表示該對象為復雜對象。其中類型為A和D的對象為原子類型的對象）。如果type的值為A和D，即該對象是一個原子類型的對象，則value是由正則表達式構成的定界符或屬性的值的構成規則，程序或用戶可以根據該表達式進行模式匹配，從而進行數據的抽取。例如在文檔實例中，需要抽取entry行中的entryid屬性的值（如在第一條記錄中其值為R00001），通過分析可以得知，該值位于行首為標記entry后跟若干個空白符的后面，值的后面跟一個回車符。該值的左定界符對象的value值為“entry\\S*”，右定界符對象的value值為“\”，該屬性值的value值為“.*”。如果type的值為S，則value值的含義與OEM數據模型相同，即
Number表示該對象連續出現的次數，用正則表達式中的符號“+”“*”“？”{n}和{n，m}，其意義與表1中的相應符號含義相同。如果該位置的值為空，表示該對象在一條記錄中僅出現一次。
上述文檔用REOEM數據模型表示如下：
(reaction，S，{(entryrow，1)，(namerow，5)，(definitionrow，9)，(equationrow，%13)，(enzymerow，25)，(commentrow，29)}，0，*);
(entryrow，S，{(seg1，2)，(entryid，3)，(seg2，4)}，1，);
(seg1，D，entry\\S+，2，);
(entryid，A，.*，3，);
(seg2，D，\，4，);
(namerow，S，{(seg3，6)，(name，7)，(seg4，8)}，5，);
(seg3，D，name\\S+，6，);
(name，A，.*，7，);
(seg4，D，\，8，);
……
(commentrow，S，{(seg15，30)，(comment，31)，(seg16，32)}，29，?);
(seg15，D，comment\\S+，30， );
(comment，A，.*，31，);
(seg16，D，\，32，)
為了方便在REOEM中的每個對象之間用“;”分割，最后一個對象后面不跟任何符號。
可以非常方便地將REOEM數據模型表示的數據模式用一棵樹來表示，稱之為信息抽取樹，轉換后的結果如圖1所示。將信息抽取樹進行深度優先順序掃描，所得結果應與REOEM數據模型相同。
通過分析可以知道，以REOEM為數據模型的信息抽取樹具有如下一些特點：
a)自描述性。如同OEM數據模型，每個對象都包含了一個標簽用來表示該對象所具有的含義，每個對象本身都包含了自身結構的說明，如是原子類型的數據還是復合類型的數據。如果是原子類型，那么它是定界符還是需要抽取的屬性數據、定界符或者屬性的構成規則是什么（用正則表達式表示）；如果是復合類型，則它所包含的子對象有哪一些等。
b）層次性。可以明顯地看出數據之間具有層次結構，如reaction對象包含了entryrow、namerow、definitionrow、enzymerow以及commentrow等子對象，entryrow對象又包含seg1、entryid、seg2等對象，依此類推。
所有的葉子節點要么是定界符，要么是欲抽取的屬性數據，而所有的非葉子節點都是復合節點。
c）有序性。數據抽取樹是一棵有序樹，節點之間是有序的。對數據抽取樹按深度優先的次序進行掃描所獲得的葉子節點的排列順序與文檔的結構是一致的。
4 結束語
本文在分析半結構化生物數據格式的基礎上總結了半結構化生物數據本身所具有的特點，提出了一種新的半結構化數據抽取模型REOEM。REOEM將OEM數據模型和正則表達式有機地結合起來，不但能夠靈活方便地表示各種數據結構，而且能夠非常方便地進行模式匹配和數據的定位，為半結構化生物數據的抽取打下堅實基礎。
參考文獻：
［1］LACROIX Z.Bioinformatics:managing scientific data[M].[S.l.]:Morgan Kaufmann Publishers，2003.
[2]蔣彥，王小行，曹毅，等.基礎生物信息學及應用[M].北京：清華大學出版社，2003：5-6. [3]BUNEMAN P， DAVIDSON S， HILLEBRAND G.A query language and optimization techniques for unstructured data[J].ACM SIGMOD Record，1996，25（2）:505-516.
[4]BUNEMAN P，DEUTSCH S，TAN W.A deterministic model for semistructured data[C]//Proc of Workshop on Query Processing for Semistructured Data and NonStandard Data Formats.1999.
[5]PAPAKONSTANTINOU Y，GARCIA M H，WIDOM J.Object exchange across heterogeneous information sources[C]//Proc of the 11th International Conference on Data Engineering.Washington DC:IEEE Computer Society，1995:251-260.
[6]GOLDMAN R，WIDOM J.Data guides:enabling query formulation and optimization in semistructured databases[C]//Proc of the 23rdInternational Confernence on Very Large Databases.[S.l.]:Morgan Kaufmann，1997:436-445.
[7]GOLDMAN R，WIDOM J.Approximate dataguides[C]//Proc of the Workshop on Query Processing for Semistructured Data and NonStandard Data Formats.1999.
[8]GOLDMAN K R.Integrated query and search of databases，XML，and the Web[D].Standford:Stanford University，2000.
NESTOROV S，ABITEBOUL S，MOTWANI R.Inferring structure in semistructured data[J].ACM SIGMOD Record，1997，26（4）：39-43.
[10]BEERI C，MOLI T.Schemas for integration and translation of structured and semistructured data[C]//Proc of the 7th International Conference on Database Theory.London:SpringerVerlag，1999:296-313
[11]PAPAKONSTAMTINOUS Y，GARCIAMOLINA H，WIIDOM J.Object exchange across heterogeneous information sources[C]//Proc of the 11th International Conference on Data Engineering.Washington DC:IEEE Computer Society，1995:251-260.
[12]BUNEMAN P.Semistructured data[C]//Proc of the 16th ACM Symposium on Principles of Database Systems.New York:ACM Press，1997:117121.
