SUFFIX TREE 文件生成器

Aleksejs+Udris　劉巖

摘要：后綴樹是一個(gè)功能強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，可以用于計(jì)算機(jī)科學(xué)執(zhí)行字符串后處理操作。使用樹結(jié)構(gòu)的一個(gè)挑戰(zhàn)是，隨著樹的生長(zhǎng)、樹的結(jié)構(gòu)變得難以想象。該文的項(xiàng)目就是針對(duì)后綴樹的這一問題，通過使用三維空間來改善樹的呈現(xiàn)效果。項(xiàng)目的目的將允許用戶在沒有重疊顯示的情況下，大幅增加從屏幕上獲得的數(shù)據(jù)量。這個(gè)項(xiàng)目將著眼于渲染定向圖，如在雙曲空間的后綴樹。

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）13-0077-03

1目標(biāo)

這個(gè)項(xiàng)目是為了在屏幕上通過提供一個(gè)有效的數(shù)據(jù)管理方法，從而改善當(dāng)前DNA字符串后綴樹結(jié)構(gòu)的可視化水平。為了實(shí)現(xiàn)這個(gè)項(xiàng)目，從輸入DNA字符串樣本和翻譯獲得結(jié)構(gòu)到LibSea圖格式都使用BioJava生物信息學(xué)庫來構(gòu)造后綴樹結(jié)構(gòu)。這種格式是為了使處理資源消耗最小化，并且可以在雙曲空間里用作海象源工具來顯示和導(dǎo)航指示圖。

2 介紹

在過去的幾年中，可用的生物數(shù)據(jù)結(jié)構(gòu)體積，如DNA和蛋白質(zhì)序列大大增加。計(jì)算機(jī)硬件的不斷發(fā)展使得它可以處理和分析越來越多從生物中檢索到的數(shù)據(jù)信息。這種增長(zhǎng)使生物信息學(xué)領(lǐng)域得到提升和發(fā)展。隨著領(lǐng)域的發(fā)展，要求新數(shù)據(jù)結(jié)構(gòu)能有效的存儲(chǔ)和分析，從而獲得所需信息。

后綴樹是一個(gè)有向圖的數(shù)據(jù)結(jié)構(gòu)，在生物信息學(xué)領(lǐng)域被用于支持高效和強(qiáng)大的運(yùn)作。[1] 例如，模式匹配， 近似模式匹配， 尋找共同的子字符串， 文本壓縮等。所有這些都可以應(yīng)用于研究和分析顯示為字符串的DNA序列。[2-3]然而，當(dāng)后綴樹被用于構(gòu)造信息結(jié)構(gòu)圖的時(shí)候，是非常大的，例如DNA序列，加工信息的大小為顯示結(jié)果創(chuàng)造了一個(gè)重大的困難。就是數(shù)據(jù)顯示可能因過大而不可讀。

3 后綴樹

字符串S的符號(hào)m的后綴樹T是一個(gè)帶根節(jié)點(diǎn)的有向樹。這樣一個(gè)后綴樹具有精確的m葉子被標(biāo)記為從1到m的值（圖1）。后綴樹的每一個(gè)內(nèi)部節(jié)點(diǎn)都至少有兩個(gè)子節(jié)點(diǎn)，每一個(gè)樹的邊緣都包含了一個(gè)非空的S子串。同一個(gè)節(jié)點(diǎn)不同邊緣的符號(hào)不能擁有相同的標(biāo)簽。一個(gè)后綴樹結(jié)構(gòu)的關(guān)鍵特性是每一個(gè)葉節(jié)點(diǎn)i， 根點(diǎn)到i的標(biāo)簽串聯(lián)通常會(huì)返回從節(jié)點(diǎn)i位置開始的S的準(zhǔn)確后綴。這意味著，這個(gè)路徑寫為S[i...m]。[2，10]

通常終止符號(hào)$被加到S的末尾，并被用于防止S最后一個(gè)后綴與另外一個(gè)給定的字符串的后綴的前綴相配。在這類事例當(dāng)中，樹可能無法滿足上述結(jié)構(gòu)的定義。為了防止S最后一個(gè)后綴與終止符的給定輸入串的前綴匹配。終止符$被添加到了開始符列。

3.1 Ukkonen后綴樹算法

Ukkonen算法構(gòu)建了一個(gè)后綴樹的簡(jiǎn)化版本，之后轉(zhuǎn)變成了S字串的真實(shí)后綴樹。一串字符簡(jiǎn)化的后綴樹，是一種從沒有樹邊緣終止符存在，并消除了無標(biāo)簽邊緣，以及沒有滿足關(guān)鍵特性，且子節(jié)點(diǎn)2個(gè)以下的節(jié)點(diǎn)的S$中得到的后綴樹[10]。Ukkonen的算法是構(gòu)成了每個(gè)S[1…i]前綴的Ti的簡(jiǎn)化后綴樹，以T1開始，增加值到i，直到樹Tm完整。完整的后綴樹S是根據(jù)O（m）時(shí)間內(nèi)的Tm而構(gòu)造的[10]（圖2）。

3.2 BioJava

BioJava平臺(tái)下的一個(gè)開源工程項(xiàng)目，旨在為處理和分析生物學(xué)數(shù)據(jù)提供程序庫。BioJava項(xiàng)目的目的是推進(jìn)生物信息學(xué)應(yīng)用程序的發(fā)展[11]。這個(gè)項(xiàng)目使用了BioJavaAPI版本1.7.1。盡管從來沒有BioJava庫的版本，最新版本的數(shù)據(jù)庫中沒有本項(xiàng)目所必須的類別。Ukkonen后綴樹和前綴樹不屬于BioJava更新的管理類別當(dāng)中。

3.3 LibSea

概述：LibSea是由CAIDA團(tuán)隊(duì)開發(fā)的圖表文件格式，從而以一種有彈性，可擴(kuò)展并可以儲(chǔ)存的方式去呈現(xiàn)大量的數(shù)據(jù)結(jié)構(gòu)。通過這種格式，用戶可以使用節(jié)點(diǎn)，邊緣和路徑鏈環(huán)元素等對(duì)需要的定向圖的拓?fù)浣Y(jié)構(gòu)進(jìn)行定義。在圖表所有元素當(dāng)中會(huì)有額外的數(shù)據(jù)，作為其屬性特征。圖表格式在可提供的屬性數(shù)量上沒有限制，且可以為這些屬性接收不同的數(shù)據(jù)類型[17]。LibSea以圖表擴(kuò)展名形式儲(chǔ)存為文本文件。圖表文件的結(jié)構(gòu)由5部分組成：元數(shù)據(jù)，結(jié)構(gòu)數(shù)據(jù)，屬性數(shù)據(jù)，可視化提示和界面提示[17]。

3.3.1 LibSea元數(shù)據(jù)

這個(gè)部分包含了關(guān)于圖表的信息，比如圖表名字，提供的描述，節(jié)點(diǎn)數(shù)量，邊緣數(shù)量，路徑數(shù)量，和路徑鏈環(huán)數(shù)量等。每個(gè)節(jié)點(diǎn)，每個(gè)邊緣和路徑都含有指定的指標(biāo)，這些指標(biāo)可用于連接文件中的字符實(shí)體。編號(hào)以0開始，所以整個(gè)字符實(shí)體給定的下標(biāo)也是從0到特定實(shí)體-1。

[Graph

{### metadata ###

@name = “OurSuffixTree”；

@description=”Description of the suffix tree”；

@numNodes=6；

@numLinks=5

@numPath=0；

@numPathLinks=0； ]

3.3.2 LibSea結(jié)構(gòu)數(shù)據(jù)

結(jié)構(gòu)數(shù)據(jù)定義了節(jié)點(diǎn)與圖表之間的連接。圖表的邊緣必須總是定向的。這個(gè)連接包含從源到目的地的一個(gè)列表。線13的節(jié)點(diǎn)0到1的第一個(gè)鏈接的鏈接下標(biāo)為0。

[{### structural data ###

@links=[

{ @source = 0； @destination=1； }，

{ @source = 0； @destination=2； }，

{ @source = 0； @destination=3； }，

{ @source = 3； @destination=4； }，

{ @source = 3； @destination=5； }，

]；

@paths=； ]

3.3.3 LibSea屬性資料

屬性可以提供圖表字符實(shí)體的數(shù)據(jù)連接。圖表節(jié)點(diǎn)，鏈接和路徑可能保護(hù)任何屬性數(shù)量。每個(gè)屬性都可以表示為單一類型的一列。圖表的所有屬性都可以表現(xiàn)為以一個(gè)單一的屬性定義表。列表的每個(gè)條目定義了這個(gè)屬性的名稱和類型。屬性方塊保護(hù)三個(gè)列表：節(jié)點(diǎn)值，鏈接值和路徑值。這些列表使用{ id； value }配對(duì)，組成了從圖表字符實(shí)體指標(biāo)到列表中值的制圖。

[@linkValues=[

{ @id=1； @value={ 1.0f； 0.0f； 0.0f； }； }

]； ]

這個(gè)線表明，紅色映射到了指數(shù)為1的圖表節(jié)點(diǎn)。

3.3.4 LibSea可視化提示和界面提示

這兩個(gè)部分是作為輔助物為Walrus工具提供額外信息的?？梢暬徒孛嫣崾究梢灾付ㄤ秩具x擇器和過濾器或菜單，然后在圖表被載入到渲染工具之后變得活躍起來。由于有些功能不支持，所以，這些部分并沒有被用到這個(gè)項(xiàng)目當(dāng)中來。

4 Walrus

Walrus是一個(gè)在三維空間里渲染大型定向圖的獨(dú)立工具。這個(gè)工具可以使用三維雙曲線幾何學(xué)來渲染一個(gè)范圍內(nèi)的圖表。關(guān)于與屏幕的距離，每個(gè)節(jié)點(diǎn)都被放大了。這個(gè)物體距離屏幕越遠(yuǎn)，用戶看到的也就越小。（圖3）

5 實(shí)現(xiàn)

1）GUI.java構(gòu)建了可以進(jìn)行輔助性測(cè)試操作的框架。GUI等級(jí)構(gòu)建了一個(gè)類別樹的事例，并可以使用輸入串序列來讀取文本文件，和運(yùn)行腳本類的主要功能，從而生成LibSea圖表文件。

2） Record.java類別創(chuàng)建了一系列可以保存BioJavaUkkonen后綴樹圖表節(jié)點(diǎn)不可用參數(shù)的記錄。

3）實(shí)現(xiàn)這個(gè)記錄類別的原因是對(duì)母樹節(jié)點(diǎn)和子樹節(jié)點(diǎn)的信息進(jìn)行維護(hù)，因?yàn)檫@些信息是無法從BioJava類別當(dāng)中直接獲取的。Ukkonen后綴樹類存儲(chǔ)了大部分關(guān)于被保護(hù)的子類實(shí)體的節(jié)點(diǎn)—SimpleNode的信息。Java遺傳機(jī)制使得從這些被保護(hù)的實(shí)體當(dāng)中獲取和檢索信息成為不可能的事情。從樹種可以獲得的關(guān)于節(jié)點(diǎn)的唯一信息是節(jié)點(diǎn)標(biāo)簽。記錄類作為容器，實(shí)現(xiàn)了保存必要信息以維持后綴樹結(jié)構(gòu)的目的。這個(gè)類別有（）集和獲得（）方法，且無法從構(gòu)造器當(dāng)中獲得任何參數(shù)。

4） Script.java（腳本.java）使用從類別樹種獲得的信息創(chuàng)建一個(gè)記錄列表，并使用記錄中可用的信息生成LibSea格式的文件。

5）腳本類別為該項(xiàng)目的分類提供了必要的處理。腳本構(gòu)造器需要兩個(gè)參數(shù)：公共腳本public Script（樹t，連成一列），腳本將從t代表的樹種構(gòu)建圖表文件，然后就把獲取文件的路徑打印出來。這個(gè)類別有兩種主要方法：運(yùn)行腳本runScript（）和編寫圖表writeGraph（）。

6）公共voidrunScript（） 方式可以從樹中檢索出一列節(jié)點(diǎn)，并創(chuàng)建一系列的記錄列表。如之前所述，腳本必須創(chuàng)建一系列信息記錄，以維護(hù)Ukkonen后綴樹結(jié)構(gòu)。

7）這個(gè)方法是以將樹根加到數(shù)組當(dāng)中為開端。再根源加到了數(shù)組當(dāng)中之后，腳本可以確定每個(gè)節(jié)點(diǎn)的根源，并檢測(cè)數(shù)組當(dāng)中的元素。給定的當(dāng)前節(jié)點(diǎn)n， 節(jié)點(diǎn)n-1是n的有效根源，如果：n的標(biāo)簽是以n-1的標(biāo)簽開始，n-1不需要終止符號(hào)$或它并不是樹的根源。當(dāng)這個(gè)迭代完成了runScript（）方式就可以對(duì)腳本類別-writeGraph（）所要求的第二個(gè)主要功能進(jìn)行實(shí)現(xiàn)。

8）writeGraph（）創(chuàng)建了一個(gè)BufferedWriter的實(shí)體，并編寫了五個(gè)LibSea格式字符串到輸出文件當(dāng)中。字符串是通過援引輔助方法而生產(chǎn)的。每個(gè)輔助方法都可以創(chuàng)建LibSea圖表文件所要求的五個(gè)部分的其中一個(gè)部分。

9） Tree.java從BioJavaorg和biojava符號(hào)程序包擴(kuò)展為Ukkonen后綴樹類別，并創(chuàng)建Ukkonen后綴樹結(jié)構(gòu)。這種擴(kuò)展在獲取隱藏在Ukkonen后綴樹類別當(dāng)中的所有節(jié)點(diǎn)AllNodes （）和標(biāo)簽Label（SuffixNoden） （后綴節(jié)點(diǎn)n）時(shí)是必要的。

6 結(jié)果

成熟的系統(tǒng)成功地為可視化工具Walrus構(gòu)建了LibSea圖表。

1）工具可以讀取保護(hù)字符串序列的文件并使用Ukkonen算法構(gòu)建后綴樹。這個(gè)計(jì)算方法是由BioJava程序庫為生物資訊v 1.7.1提供。

2）這個(gè)系統(tǒng)創(chuàng)建了可以保存關(guān)于節(jié)點(diǎn)和后綴樹信息的記錄列表。可以從Ukkonen后綴樹被保護(hù)實(shí)體或直接用這個(gè)系統(tǒng)計(jì)算獲取所需信息。

3）腳本類別恢復(fù)了記錄列表中遺失的結(jié)構(gòu)，并創(chuàng)建LibSea圖表文件。

4）該系統(tǒng)與保護(hù)4個(gè)字母“ACGT”的序列一起操作。系統(tǒng)可以指定顏色屬性到構(gòu)建這個(gè)字母集的節(jié)點(diǎn)。

然后，LibSea圖表構(gòu)造時(shí)間受到制定后綴樹制定節(jié)點(diǎn)和邊緣屬性數(shù)量的影響。我們從圖表節(jié)點(diǎn)制定屬性數(shù)量增加的長(zhǎng)序列中，看到圖表文件產(chǎn)生速度的明顯變慢。

7 結(jié)束語

這個(gè)項(xiàng)目的目的在于尋找一種可以用三維結(jié)構(gòu)展示后綴樹的方法，這個(gè)方法可以給用戶可視化地呈現(xiàn)不斷增加的數(shù)據(jù)。

由于某些Walrus限制，這個(gè)系統(tǒng)并不支持后綴樹所有功能。然而，這些優(yōu)勢(shì)的結(jié)合可以提供比二維后綴樹應(yīng)用更高的可視化水平[16-17]。

參考文獻(xiàn)：

[1] Mehta D P， Sartaj Sahni.Handbook of Data Structures and Applications[M]. London： Chapman and Hall/CRC， 2004： 1387.

[2] Dan Gusfield. Algorithms on strings， trees， and sequences computer science and computational biology[M]. Cambridge University Press， 1997：110-140.

[3] Aluru， Srinivas. Handbook of Computational Molecular Biology[M]. London： Chapman and Hall/CRC， 2005：1104.

[4] Frank Klawonn. Introduction to Computer Graphics： Using Java 2D and 3D （Undergraduate Topics in Computer Science） [M]. Springer， 2008：286.

[5] BioJava - Open-Source libraries for bioinformatics[EB/OL]. Available： http：//biojava.org/wiki/Main_Page.

[6] Gregg A Helt， Suzanna Lewis， Ann E Loraine， et al. BioViews： Java-Based Tools for Genomic Data Visualization[EB/OL].（1998）[2015-12-15].http：//genome.cshlp.org/content/8/3/291.full#abstract-1.

[7] Ivan Herman，MaylisDelest，Guy Melancon.Tree Visualisation and Navigation Clues for Information Visualisation. （1998）[2015-12-14].http：//onlinelibrary.wiley.com/doi/10.1111/1467-8659.00235/pdf.

[8] Alexandru Edgar Ghitza， Philippe-Antoine Warda. （.）. Growing A Suffix Tree[EB/OL]. （2015-12-19）[2016-02-20]. http：//pauillac.inria.fr/～quercia/documents-info/Luminy-98/albert/JAVA+html/SuffixTreeGrow.html.

[9] Bertini E. Eurographics/ IEEE-VGTC Symposium on Visualization[C].Computer graphics forum，2009，28（3）.

[10] Ukkonen E. On-line construction of suffix trees[J]. Algorithmica，1995， 14（3）.

[11] Havsiyevych I. Suffix Trees： Java Applet[EB/OL].（2009）[2016-03-19].http：//illya-keeplearning.blogspot.hk/2009/06/suffix-trees-java-applet-sources.html.

[12] Holland R， Down T A， Pocock M， et al. BioJava： an open-source framework for bioinformatics[J]. Bioinformatics，2008， 24（18）：2096-2097.

[13] Kay M.String Alignment Using Suffix Trees[D]. Stanford University， 2000.

[14] Munzner T.INTERACTIVE VISUALIZATION OF LARGE GRAPHS AND NETWORKS[EB/OL].（2000）[2016-03-19]. https：//graphics.stanford.edu/papers/munzner_thesis/all.onscree n.pdf.

[15] Weiner P.Linear pattern matching algorithm[C]. 14th Annual IEEE Symposium on Switching Automata Theory， 1973：1.

[16] Shlomo Yona. ANSI C implementation of a Suffix Tree[EB/OL].（2002）[2016-02-19].http：//biit.cs.ut.ee/～vilo/edu/2002-03/Tekstialgoritmid_I/Software/Loeng5_Suffix_Trees/Suffix_Trees/cs.haifa.ac.il/shlomo/suffix_tree/.

[17] CAIDA.Walrus - Graph Visualization Tool[EB/OL].（2005）[2016-03-05].http：//www.caida.org/tools/visualization/walrus/.