Aleksejs+Udris　劉巖

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

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）13-0077-03

1目標

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

2 介紹

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

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

3 后綴樹

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

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

3.1 Ukkonen后綴樹算法

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

3.2 BioJava

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

3.3 LibSea

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

3.3.1 LibSea元數據

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

[Graph

{### metadata ###

@name = “OurSuffixTree”；

@description=”Description of the suffix tree”；

@numNodes=6；

@numLinks=5

@numPath=0；

@numPathLinks=0； ]

3.3.2 LibSea結構數據

結構數據定義了節(jié)點與圖表之間的連接。圖表的邊緣必須總是定向的。這個連接包含從源到目的地的一個列表。線13的節(jié)點0到1的第一個鏈接的鏈接下標為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屬性資料

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

[@linkValues=[

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

]； ]

這個線表明，紅色映射到了指數為1的圖表節(jié)點。

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

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

4 Walrus

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

5 實現

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

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

3）實現這個記錄類別的原因是對母樹節(jié)點和子樹節(jié)點的信息進行維護，因為這些信息是無法從BioJava類別當中直接獲取的。Ukkonen后綴樹類存儲了大部分關于被保護的子類實體的節(jié)點—SimpleNode的信息。Java遺傳機制使得從這些被保護的實體當中獲取和檢索信息成為不可能的事情。從樹種可以獲得的關于節(jié)點的唯一信息是節(jié)點標簽。記錄類作為容器，實現了保存必要信息以維持后綴樹結構的目的。這個類別有（）集和獲得（）方法，且無法從構造器當中獲得任何參數。

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

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

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

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

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

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

6 結果

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

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

2）這個系統(tǒng)創(chuàng)建了可以保存關于節(jié)點和后綴樹信息的記錄列表?？梢詮腢kkonen后綴樹被保護實體或直接用這個系統(tǒng)計算獲取所需信息。

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

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

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

7 結束語

這個項目的目的在于尋找一種可以用三維結構展示后綴樹的方法，這個方法可以給用戶可視化地呈現不斷增加的數據。

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

參考文獻：

[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/.