MultipleHelix:一種借鑒DNA螺旋結(jié)構(gòu)的層次數(shù)據(jù)可視化方法

王大衛(wèi)

摘要：借鑒DNA螺旋結(jié)構(gòu)的可視化方法可以降低節(jié)點(diǎn)布局復(fù)雜度，減少視覺(jué)雜亂，提升用戶體驗(yàn)，在分析層次數(shù)據(jù)關(guān)聯(lián)時(shí)有著一定的價(jià)值和優(yōu)勢(shì)。針對(duì)層次數(shù)據(jù)的可視需求，在傳統(tǒng)節(jié)點(diǎn)鏈接法的基礎(chǔ)上綜合圓環(huán)布局、螺旋布局、旋轉(zhuǎn)交互等可視技術(shù)，提出一種基于螺旋結(jié)構(gòu)的可視化方法MultipleHelix。利用MultipleHelix可視方法對(duì)網(wǎng)絡(luò)課程層次數(shù)據(jù)進(jìn)行可視化分析與展示。

關(guān)鍵詞： 層次數(shù)據(jù)螺旋結(jié)構(gòu) 數(shù)據(jù)可視化

一、引言

隨著互聯(lián)網(wǎng)、云計(jì)算、物聯(lián)網(wǎng)等信息技術(shù)的蓬勃發(fā)展，信息技術(shù)與人類經(jīng)濟(jì)、科研、生活等方方面面進(jìn)行了高度融合，產(chǎn)生超越任何年代的海量數(shù)據(jù)。通常，數(shù)據(jù)的分析往往離不開(kāi)機(jī)器和人的相互協(xié)作。所以數(shù)據(jù)分析一般從兩個(gè)維度展開(kāi)一是從機(jī)器或計(jì)算機(jī)的角度出發(fā)，強(qiáng)調(diào)機(jī)器的計(jì)算能力和人工智能，以各種高性能處理算法、智能搜索與挖掘算法等為主要內(nèi)容;另一個(gè)維度以人作為分析主體和需求主體出發(fā)，強(qiáng)調(diào)基于人機(jī)交互的、符合人的認(rèn)知規(guī)律的分析方法，這一分支以數(shù)據(jù)可視化為主要代表。

層次數(shù)據(jù)是一種常見(jiàn)的數(shù)據(jù)類型，例如文件系統(tǒng)、網(wǎng)絡(luò)課程數(shù)據(jù)、地域經(jīng)濟(jì)等都是典型的層次數(shù)據(jù)。經(jīng)典層次數(shù)據(jù)可視化方法有節(jié)點(diǎn)鏈接法和空間填充法2中表現(xiàn)形式。空間填充法的典型代表為樹(shù)圖（Treemap），該方法能充分利用顯示空間，通過(guò)利用填充面積、填充顏色填充文理等方法進(jìn)行節(jié)點(diǎn)標(biāo)注但在層次關(guān)系的體現(xiàn)上略顯晦澀。傳統(tǒng)的節(jié)點(diǎn)鏈接法利用直線或曲線鏈接各層次數(shù)據(jù)節(jié)點(diǎn)，能充分體現(xiàn)數(shù)據(jù)的層次和關(guān)聯(lián)特性。但是伴隨數(shù)據(jù)量的急劇增大，節(jié)點(diǎn)鏈接法的深度和廣度快速增加，伴隨而來(lái)的是節(jié)點(diǎn)布局困難，節(jié)點(diǎn)覆蓋等問(wèn)題。為有效概覽層次數(shù)據(jù)整體結(jié)構(gòu)，清晰展示層次信息，改善用戶交互，本文借鑒DNA螺旋結(jié)構(gòu)，將層次數(shù)據(jù)節(jié)點(diǎn)類比為堿基，將數(shù)據(jù)間層次關(guān)系曲線類比為磷酸骨架，擬以多層次的多螺旋結(jié)構(gòu)來(lái)展示層次數(shù)據(jù)，提出一種名為MultipleHelix層次數(shù)據(jù)可視化布局算法。

二、相關(guān)工作

作為數(shù)據(jù)的重要組成部分，層次數(shù)據(jù)的可視分析與展示是數(shù)據(jù)可視化工作的重要議題之一。Lamping J等人提出雙曲樹(shù)（HyperbolicTree），它將更多的空間分給用戶關(guān)注的部分分支。根節(jié)點(diǎn)在正中，子節(jié)點(diǎn)通過(guò)雙曲平面布局，雙曲平面的弧線長(zhǎng)度隨層次結(jié)構(gòu)的深度增長(zhǎng)而正比增長(zhǎng)。Battista GD等人提出了徑向樹(shù)（Radial Tree），它將不同層次的節(jié)點(diǎn)分配到不同半徑的同心圓上，根節(jié)點(diǎn)在圓心處，節(jié)點(diǎn)到圓心距離是節(jié)點(diǎn)的深度。與此同時(shí)，學(xué)者也在不斷探索層次數(shù)據(jù)的3D展示技術(shù)。Kreuseler M等人提出魔法眼（Magic Eye View），首次運(yùn)用Walker布局算法將層次結(jié)構(gòu)進(jìn)行放射狀布局，將平面布局結(jié)果中的節(jié)點(diǎn)從笛卡爾坐標(biāo)系轉(zhuǎn)換到半球面上，然后再將布局結(jié)果投影回半球?qū)?yīng)的2D圓面上。軸環(huán)柱型樹(shù)（Collapsible CylindricalTrees）將非根節(jié)點(diǎn)映射到可旋轉(zhuǎn)的柱體表面，用戶利用轉(zhuǎn)動(dòng)交互顯示或隱藏節(jié)點(diǎn)。

1953年2月，沃森（ Watson）、克里克（Crick）通過(guò)維爾金斯看到了富蘭克林（Rosalind Franklin）在1951年11月拍攝的一張十分漂亮的DNA晶體X射線衍射照片，激發(fā)了他們的靈感。他們分析出螺旋參數(shù)并提出了DNA螺旋結(jié)構(gòu)。DNA是磷酸骨架與堿基對(duì)組成的雙鏈結(jié)構(gòu)，DNA雙鏈在空間上是一個(gè)帶狀幾何曲面。DNA雙鏈可以圍繞螺旋軸進(jìn)行空間旋轉(zhuǎn)，形成DNA螺旋結(jié)構(gòu)如圖l所示。

DNA分子由兩條長(zhǎng)鏈組成，這兩條長(zhǎng)鏈按反向平行方式盤旋成雙螺旋結(jié)構(gòu)。其中每條鏈上的一個(gè)核苷酸（也稱堿基，有A、T、G、C四種）以脫氧核糖與另一個(gè)核苷酸上的磷酸基團(tuán)結(jié)合，形成主鏈的基本骨架，并排列在主鏈的外側(cè)，堿基位于主鏈內(nèi)側(cè)。兩條DNA分子鏈上的核苷酸堿基總是互補(bǔ)配對(duì)的（A只和T配對(duì)，G只和C配對(duì)）。

三、MultipleHelix布局算法

MultipleHelix布局算法包含兩大類布局：圓環(huán)布局和螺旋布局。

圓環(huán)布局，即從集合中取出第k層有序數(shù)據(jù)（數(shù)據(jù)個(gè)數(shù)記做n），以固定半徑生成節(jié)點(diǎn)球體，按逆時(shí)針?lè)较蚶L制到平面X=m（m為常數(shù)）上，如圖3所示。因各節(jié)點(diǎn)球體球心X軸坐標(biāo)固定，為簡(jiǎn)化布局計(jì)算，可將各節(jié)點(diǎn)球體投影到x=0平面。各節(jié)點(diǎn)球體球心在X=0平面上的投影，應(yīng)滿足某一圓形方程，將該圓記做A，如圖4所示。若以過(guò)圓A圓心的直線與圓A相交的點(diǎn)P為起始位置，按逆時(shí)針均勻布局各節(jié)點(diǎn)，則對(duì)于任意節(jié)點(diǎn)Nodek而言，過(guò)其投影圓圓心和圓A圓心做一條直線l，該直線與X軸的夾角

。因此，任意幾點(diǎn)

投影圓圓心的z坐標(biāo)和Y坐標(biāo)應(yīng)滿足方程組：

。

螺旋布局，即從集合S，中取出第k+l層有序數(shù)據(jù)，按節(jié)點(diǎn)Nodek.F，進(jìn)行分組，即按父節(jié)點(diǎn)是否相同進(jìn)行分組。取出每組數(shù)據(jù)，以父節(jié)點(diǎn)元素起始位置為參照，按圓環(huán)布局的同時(shí)，沿X軸正向有△x的增量，如圖5所示。設(shè)父節(jié)點(diǎn)的坐標(biāo)為（x0，y0，z0），則對(duì)于任意子節(jié)點(diǎn)Nodex而言，其坐標(biāo)滿足以下方程組：

2算法描述

MultipleHelix布局算法首先將輸入節(jié)點(diǎn)按主次關(guān)鍵字排序，然后對(duì)奇數(shù)層數(shù)據(jù)做圓環(huán)布局，對(duì)偶數(shù)層數(shù)據(jù)做螺旋布局。詳盡描述如下：

MultipleHelix（S，n）

輸入：層次數(shù)據(jù)節(jié)點(diǎn)集合

，n為數(shù)據(jù)層數(shù)。

A.將輸入節(jié)點(diǎn)集合s按主次關(guān)鍵字排序，得到行列有序的集合Sr。

B.令i從1到n依次取值：

如果l等于1，靠屏幕左邊平行于YOZ平面做圓環(huán)布局。

否則，判定i的奇偶性。如果i為奇數(shù)，以Node，F(xiàn)j節(jié)點(diǎn)球體球心為中心，做圓環(huán)布局，否則以Node，，F(xiàn)j節(jié)點(diǎn)球體球心為起始位置做螺旋布局。

四、網(wǎng)絡(luò)課程層次數(shù)據(jù)的可視化展示

將MultipleHelix方法應(yīng)用于網(wǎng)絡(luò)課程層次數(shù)據(jù)，以幫助師生分析課程的層次結(jié)構(gòu)，包括章節(jié)的直接關(guān)系，以及章節(jié)間的先行 后續(xù)的間接關(guān)系。

首先，對(duì)章數(shù)據(jù)進(jìn)行圓環(huán)布局，用不同顏色代表不同章節(jié)。其實(shí)，提取節(jié)數(shù)據(jù)，對(duì)其進(jìn)行螺旋布局，用父節(jié)點(diǎn)章數(shù)據(jù)的顏色渲染節(jié)數(shù)據(jù)。最后，對(duì)章數(shù)據(jù)間、節(jié)數(shù)據(jù)間、章 節(jié)數(shù)據(jù)間進(jìn)行連線。本文采用three.js進(jìn)行三維建模，利用web平臺(tái)展示相應(yīng)數(shù)據(jù)，如圖6所示。圖中A區(qū)為傳統(tǒng)章節(jié)導(dǎo)航目錄，B區(qū)為層次數(shù)據(jù)MultipleHelix布局效果，C區(qū)為參數(shù)面板，D區(qū)為選中節(jié)點(diǎn)信息，E區(qū)為圖例。

本可視平臺(tái)的可視交互信息輸入方式有：導(dǎo)航點(diǎn)擊、參數(shù)面板修改和用戶選擇和旋轉(zhuǎn)。用戶點(diǎn)擊A區(qū)導(dǎo)航項(xiàng)，B區(qū)相應(yīng)節(jié)點(diǎn)高亮、直接間接連線，C區(qū)顯示該節(jié)點(diǎn)屬性，D區(qū)顯示該選中節(jié)點(diǎn)信息。如圖5-A所示，為選擇導(dǎo)航菜單的13.3節(jié)B區(qū)效果圖。參數(shù)面板可調(diào)節(jié)指定數(shù)據(jù)節(jié)點(diǎn)的半徑、顏色等信息。用戶選擇交互輸入，同點(diǎn)擊A區(qū)導(dǎo)航項(xiàng)效果相同，只是數(shù)據(jù)輸入方式不同。因?yàn)楸究梢暬脚_(tái)采用的是3D展示方式，存在一定的遮擋。為避免這一問(wèn)題帶來(lái)的影響，本系統(tǒng)引進(jìn)了旋轉(zhuǎn)操作。用戶點(diǎn)擊鼠標(biāo)左鍵不放，即可對(duì)層次數(shù)據(jù)進(jìn)行旋轉(zhuǎn)。如圖7所示，為MultipleHelix模型旋轉(zhuǎn)后的幾個(gè)經(jīng)典視角效果圖。

五、典型方法對(duì)比分析

由于層次可視化技術(shù)在層次結(jié)構(gòu)數(shù)據(jù)的分析與展現(xiàn)上良好的性能，它已然成為人們分析和駕馭層次信息的有力工具。層次數(shù)據(jù)可視化并不是簡(jiǎn)單地對(duì)層次結(jié)構(gòu)進(jìn)行圖形展示，而是優(yōu)美且客觀的展示層次結(jié)構(gòu)和信息。對(duì)于層次可視化技術(shù)沒(méi)有公認(rèn)的衡量標(biāo)準(zhǔn)，參考大量有關(guān)層次可視化評(píng)價(jià)文獻(xiàn)，認(rèn)為層次可視化技術(shù)的設(shè)計(jì)目標(biāo)主要應(yīng)包含如下幾個(gè)方面：

1）可視化結(jié)果在適當(dāng)位置顯示，能清晰展示層次結(jié)構(gòu);

2）合理顯示用戶關(guān)心的屬性，易于詳細(xì)觀察細(xì)節(jié)信息;

3）擁有良好人機(jī)交互，瀏覽過(guò)程中保持上下文信息，有效防止迷航;

4）經(jīng)常使用能輕松在可視化結(jié)果的任何區(qū)域找到針對(duì)任務(wù)的特定信息，可視化結(jié)果具有一致性。

本文MultipleHelix可視化方法，為借鑒DNA組織結(jié)構(gòu)的3D節(jié)點(diǎn)鏈接層次化可視技術(shù)。常用的3D節(jié)點(diǎn)鏈接層次化可視技術(shù)有：圓錘樹(shù)、魔法眼、軸環(huán)柱型樹(shù)。針對(duì)上述設(shè)計(jì)目標(biāo)，結(jié)合文獻(xiàn)[2]中的分析，MultipleHelix可視化方法與上述三種方法的比較如表1所示。

六、結(jié)語(yǔ)

本文借鑒DNA組織結(jié)構(gòu)，提出一種3D的層次數(shù)據(jù)可視化方法，該方法能清晰展示數(shù)據(jù)層次結(jié)構(gòu)，人機(jī)交互良好，擁有不錯(cuò)的層次數(shù)據(jù)展示效果。未來(lái)在MultipleHelix布局中將針對(duì)關(guān)系邊應(yīng)用邊綁定技術(shù)和渲染技術(shù)進(jìn)行邊優(yōu)化，或?qū)で蟾玫倪呎宫F(xiàn)方式，減少視覺(jué)。在數(shù)據(jù)組織方面，可借鑒DNA的半保留復(fù)制、DNA重組等生物特性。本文可視化方法還可應(yīng)用于教育、金融、食品等多個(gè)領(lǐng)域，對(duì)具有間接關(guān)系的層次數(shù)據(jù)進(jìn)行可視化和可視分析。

參考文獻(xiàn)

[1]Lampingj， RaoR， PirolliP.A focus+context technique baseri onhyperbolic geometry forvisualizing large hierarchies[C] .In：Proc.of the SIGCHI Conferenceon Human Factorsin Computing Systems，Denver， ACMPress， 40L-408.

[2]BattistaGD， EadesP， TanrassiaR， etal. Graph drawing： algorithmsfor the visualization of graphs[ M] .UpperSaddleRiver：PrenticeHall，1998

[3] Kreuseler M， LopezN， SchumannH.Ascalable frameworkfor information visualization[C].In：Proc.of IEEE SymposiumonInformation Visualization， InfoVis，SaltLakeCity， IEEEComputerSociety， 2000， 27-36.

[4]DachseltR， Ebertj.Collapsible cylindrical trees：a fast hierarchicalnavigation technique[c].In：Proc.ofIEEE Symposiumon InformlationVisualization， InfoVis， SanDiego， IEEEComputerSo-ciety， 2001，79-86

[5]Wang Ying，Shi Xuguang. Study on the Relationship betweenDNA Free Energy and DNA Space Geometry[J]. Journal of Bionrathematics，2017，32（4）：483-49L （in Chinese）（王穎，史旭光.DNA自由能與DNA空間幾何構(gòu)型關(guān)系研究.生物數(shù)學(xué)學(xué)報(bào).2017，32（4）：483-491）

[6]陳穎.一種基于DNA雙螺旋結(jié)構(gòu)的數(shù)據(jù)起源模型，現(xiàn)代圖書情報(bào)技術(shù).2008-10：11-15