基于動(dòng)態(tài)規(guī)劃的雙序列比對(duì)算法構(gòu)件設(shè)計(jì)與實(shí)現(xiàn)

石海鶴 周衛(wèi)星

(江西師范大學(xué)計(jì)算機(jī)信息工程學(xué)院 南昌 330022)

序列比對(duì)是一種通過(guò)排列基因組序列來(lái)識(shí)別序列相似性區(qū)域，從而獲得待比對(duì)序列之間的功能、結(jié)構(gòu)或進(jìn)化關(guān)系的技術(shù).隨著人類基因組計(jì)劃的實(shí)施，測(cè)序技術(shù)的發(fā)展產(chǎn)生了大量的有關(guān)生物分子的原始序列數(shù)據(jù)，例如，Illumina HiSeqX Ten在3天之內(nèi)可以產(chǎn)生大約30億個(gè)2×150 bp的雙端測(cè)序數(shù)據(jù)[1].面對(duì)如此豐富的基因組序列數(shù)據(jù)，如何高效處理和分析這些豐富的基因組序列數(shù)據(jù)，如比較兩序列之間的相似區(qū)域和保守性位點(diǎn)，尋求序列同源結(jié)構(gòu)，揭示生物遺傳、變異和進(jìn)化關(guān)系等，成為了序列比對(duì)算法研究的主要?jiǎng)恿χ?

研究表明，計(jì)算機(jī)的微處理性能和存儲(chǔ)設(shè)備容量平均每18～24個(gè)月增長(zhǎng)1倍，而基因組測(cè)序數(shù)據(jù)則平均4～5月就增長(zhǎng)1倍，這成為了高性能計(jì)算發(fā)展史中一個(gè)前所未有的挑戰(zhàn)，因此序列比對(duì)算法的時(shí)空開(kāi)銷和精準(zhǔn)度成為生物序列比對(duì)過(guò)程中的關(guān)鍵因素之一.由于序列比對(duì)屬于NP-hard問(wèn)題，而運(yùn)籌學(xué)中動(dòng)態(tài)規(guī)劃策略多用于解決多階段決策過(guò)程最優(yōu)化問(wèn)題，因此，動(dòng)態(tài)規(guī)劃策略被廣泛應(yīng)用于序列比對(duì)算法之中.這里我們主要針對(duì)基于動(dòng)態(tài)規(guī)劃的雙序列比對(duì)算法(dynamic programming-based pairwise sequence alignment algorithm, DPPSAA)領(lǐng)域開(kāi)展研究.

在雙序列比對(duì)算法中最為經(jīng)典的確定性雙序列比對(duì)算法有基于全局比對(duì)的NW算法[2](Needleman-Wunsch algorithm)、基于局部比對(duì)的SW算法[3](Smith-Waterman algorithm)和準(zhǔn)全局比對(duì)算法.在后續(xù)的研究中，發(fā)展出了基于以上算法進(jìn)行優(yōu)化[4-6]或作為主要比對(duì)策略[7-9]的系列算法.

目前，比對(duì)算法的研究大部分集中于序列相似性分析領(lǐng)域中的特定問(wèn)題[10-13]或者特定算法優(yōu)化[14-16]，而較少面向于整個(gè)問(wèn)題域，難以得到一個(gè)具有更高抽象層次且適用于整個(gè)序列相似性分析領(lǐng)域的算法構(gòu)件庫(kù)，在一定程度上導(dǎo)致了序列比對(duì)算法的冗余以及人為選擇算法可能造成的誤差等問(wèn)題，也使得人們難以有效地了解算法結(jié)構(gòu)，無(wú)法保證算法的正確使用，在一定程度上降低了序列相似性分析結(jié)果的準(zhǔn)確性.由于現(xiàn)有算法的專用性和低抽象性，不僅導(dǎo)致研究人員需要花費(fèi)大量時(shí)間去學(xué)習(xí)和使用該類算法，降低了算法的可維護(hù)性和復(fù)用性，而且難以定位和解決算法產(chǎn)生的錯(cuò)誤，加重了序列相似性分析的負(fù)擔(dān).

通過(guò)深入分析DPPSAA領(lǐng)域，本文設(shè)計(jì)和實(shí)現(xiàn)了該領(lǐng)域抽象泛型算法構(gòu)件庫(kù)，提高了序列相似性分析領(lǐng)域算法可靠性和開(kāi)發(fā)效率.首先對(duì)DPPSAA領(lǐng)域進(jìn)行特征分析，提取出其中的通用和可變特征以及它們之間的約束與依賴關(guān)系，建立了一致的領(lǐng)域構(gòu)件模型，基于此設(shè)計(jì)了算法構(gòu)件交互模型，進(jìn)一步利用新型高可靠軟件開(kāi)發(fā)平臺(tái)PAR[17-19]中高抽象程序設(shè)計(jì)語(yǔ)言Apla(abstract programming language)進(jìn)行形式化實(shí)現(xiàn)，形成了一個(gè)高抽象DPPSAA構(gòu)件庫(kù)，以期自動(dòng)或半自動(dòng)裝配構(gòu)件產(chǎn)生特定領(lǐng)域序列比對(duì)算法，甚至于裝配出更為高效的新型序列比對(duì)算法.

1 比對(duì)算法的建模過(guò)程

1.1 領(lǐng)域分析

面向特征的領(lǐng)域分析[20](feature oriented domain analysis, FODA)是由軟件工程研究所(Software Engineering Institute， SEI)于1990年首次提出的一種領(lǐng)域分析方法，主要包含上下文分析以及特征建模2個(gè)階段[21].其中上下文分析主要由界定待研究領(lǐng)域需求范圍以及領(lǐng)域的輸出與輸入構(gòu)成，該階段的成功實(shí)施能夠保證特征建模過(guò)程中被選取特征的有效性和可靠性.特征建模階段則包含了特征選取與建立、特征關(guān)系描述以及特征模型建立等過(guò)程，在該階段需要對(duì)被研究領(lǐng)域進(jìn)行分析，充分了解其功能性特征和非功能性特征，并找出特征之間的約束和依賴關(guān)系以及優(yōu)先級(jí)等附加信息，進(jìn)而獲得該領(lǐng)域的主次要特征，建立一種具有更高抽象層次的特征模型或者構(gòu)件框架.

特征建模階段主要包含以下4種特征：強(qiáng)制特征(mandatory)、可變特征(optional)、OR特征、XOR特征.強(qiáng)制特征表示領(lǐng)域內(nèi)的所有實(shí)例都必須包含的特征，可變特征表示領(lǐng)域中實(shí)例的一個(gè)可選特征，XOR特征表示領(lǐng)域中實(shí)例有且只能選擇一組XOR特征中的一個(gè)特征，OR特征表示領(lǐng)域中實(shí)例至少包含了一組OR特征中的一個(gè)特征，特征表示如圖1所示.特征建模清晰地刻畫了特征模型構(gòu)建過(guò)程中所需的各類特征，是識(shí)別和捕捉差異性和可變性的關(guān)鍵技術(shù).

Fig. 1 Feature graph圖1 特征圖

圖1中強(qiáng)制特征被末端為實(shí)心圓的邊所指向，可變特征被末端為空心圓的邊所指向，XOR特征被一組用弧連接的邊所指向，OR特征被一組用實(shí)心弧連接的邊所指向.這4種特征是特征建模中的主要屬性，也是特征模型的重要組成部分，代表了領(lǐng)域中的通用和可變屬性，同時(shí)它們之間的約束以及依賴關(guān)系則需通過(guò)特征內(nèi)在的層次結(jié)構(gòu)關(guān)系、領(lǐng)域業(yè)務(wù)邏輯設(shè)計(jì)的約束關(guān)系以及運(yùn)行時(shí)依賴關(guān)系來(lái)表示.

1.2 特征建模流程

以FODA為基礎(chǔ)，我們?cè)谄浜笤鎏砹祟I(lǐng)域?qū)崿F(xiàn)階段，即將建立的特征作為構(gòu)件進(jìn)行構(gòu)件交互模式設(shè)計(jì)和形式化實(shí)現(xiàn)，建立抽象構(gòu)件庫(kù).需要注意的是，由于建立的構(gòu)件之間的交互性，程序人員使用C，C++或Java等低抽象層次高級(jí)編程語(yǔ)言進(jìn)行代碼編程時(shí)，不僅增加了特征之間的關(guān)聯(lián)性與復(fù)雜性，而且難以讓使用者對(duì)整個(gè)構(gòu)件庫(kù)有具體和全面的了解.因此需要使用一種具有高抽象性的編程語(yǔ)言來(lái)實(shí)現(xiàn)這些構(gòu)件，以至不用在意算法構(gòu)件的具體實(shí)現(xiàn)細(xì)節(jié)，而能夠清晰地了解這些算法構(gòu)件的功能以及它們之間的交互關(guān)系.例如在本文中主要利用Apla語(yǔ)言來(lái)實(shí)現(xiàn)DPPSAA領(lǐng)域構(gòu)件.

基于以上介紹，對(duì)具體領(lǐng)域進(jìn)行分析時(shí)，領(lǐng)域構(gòu)件庫(kù)建立流程圖如圖2所示:

Fig. 2 Flow chart of domain analysis圖2 領(lǐng)域分析流程圖

1.3 DPPSAA領(lǐng)域特征建模

特征模型描述了領(lǐng)域內(nèi)實(shí)例的通用和可變特征以及它們之間的約束與依賴關(guān)系，是在特征建模過(guò)程中構(gòu)建的，一般由描述特征層次關(guān)系的特征圖和相關(guān)的文本描述組成.其中特征圖通常使用具有不同層次的樹(shù)狀結(jié)構(gòu)來(lái)表示，在該結(jié)構(gòu)中包含了1組節(jié)點(diǎn)、1組節(jié)點(diǎn)之間的定向邊以及兩邊之間的關(guān)系描述.其中1個(gè)節(jié)點(diǎn)代表一個(gè)特征，具有唯一的標(biāo)識(shí)符;節(jié)點(diǎn)之間的定向邊將特征連結(jié)成樹(shù)結(jié)構(gòu);兩邊之間的關(guān)系描述則代表特征之間的關(guān)系，是對(duì)特征節(jié)點(diǎn)的劃分.同時(shí)特征模型中的文本描述則表示了特征的語(yǔ)義描述、原理以及約束和默認(rèn)依賴規(guī)則等信息.

因此，針對(duì)基于動(dòng)態(tài)規(guī)劃的雙序列比對(duì)算法領(lǐng)域，建模過(guò)程有3方面：

1) 上下文分析.該算法領(lǐng)域的范圍被限制為一種在生物序列相似性分析領(lǐng)域中以動(dòng)態(tài)規(guī)劃為主要罰分策略、雙序列比對(duì)為主要比對(duì)方式的算法形式.

2) 特征建模.我們利用特征建模方法[22]對(duì)該領(lǐng)域進(jìn)行特征建模，即從分析領(lǐng)域中的服務(wù)(service)、功能(function)以及行為(behavior)特點(diǎn)入手構(gòu)建特征模型.比對(duì)操作服務(wù)是該領(lǐng)域中的核心服務(wù)，通過(guò)控制序列比對(duì)過(guò)程中的比對(duì)方式和各算法特征之間的執(zhí)行優(yōu)先級(jí)以及組合方式來(lái)實(shí)現(xiàn)使用者定義的序列比對(duì)算法.通過(guò)分析雙序列比對(duì)算法中的一些主要執(zhí)行步驟，可以將該比對(duì)操作服務(wù)進(jìn)一步劃分為檢查序列合法性、得分矩陣操作、動(dòng)態(tài)規(guī)劃算法方式選擇、記住得分來(lái)源、回溯和比對(duì)結(jié)果輸出等功能，同時(shí)得分矩陣初始化、動(dòng)態(tài)規(guī)劃方式選擇以及檢查序列合法性作為3個(gè)必選的功能.在上述分析的基礎(chǔ)上，輸出方式是比對(duì)結(jié)果輸出的顯著行為特點(diǎn)，包括比對(duì)序列輸出和比對(duì)得分輸出兩種主要行為特點(diǎn)，且二者屬于OR特征.動(dòng)態(tài)規(guī)劃方式可以分為全局動(dòng)態(tài)規(guī)劃方式、準(zhǔn)全局動(dòng)態(tài)規(guī)劃方式、局部動(dòng)態(tài)規(guī)劃方式3種，三者為XOR特征.我們根據(jù)上述分析對(duì)該領(lǐng)域建立了特征模型，如圖3所示：

Fig. 3 DPPSAA feature model圖3 DPPSAA特征模型

3) 領(lǐng)域?qū)崿F(xiàn).該過(guò)程針對(duì)已建立的特征模型進(jìn)行DPPSAA領(lǐng)域算法構(gòu)件交互設(shè)計(jì)并使用Apla語(yǔ)言形式化實(shí)現(xiàn).

2 比對(duì)算法構(gòu)件的設(shè)計(jì)與實(shí)現(xiàn)

2.1 DPPSAA領(lǐng)域算法構(gòu)件交互設(shè)計(jì)

不同構(gòu)件通過(guò)交互實(shí)現(xiàn)完整的算法構(gòu)件庫(kù)，而算法構(gòu)件的交互則需要由其包含的特征之間的約束以及依賴關(guān)系來(lái)體現(xiàn).因此針對(duì)1.3節(jié)建立的特征模型，我們對(duì)DPPSAA領(lǐng)域的算法構(gòu)件交互模型進(jìn)行了設(shè)計(jì).

通過(guò)分析整個(gè)DPPSAA領(lǐng)域得知，算法主要包括3個(gè)主要變化過(guò)程特征：得分矩陣操作、動(dòng)態(tài)規(guī)劃算法方式以及比對(duì)結(jié)果輸出.因此，我們將特征模型中的這些特征以及檢查序列合法性作為主要構(gòu)件，其他特征以及相關(guān)數(shù)據(jù)結(jié)構(gòu)作為輔助構(gòu)件，并根據(jù)其優(yōu)先級(jí)建立了構(gòu)件間的交互模型，如圖4所示:

Fig. 4 Algorithm components interaction model圖4 算法構(gòu)件交互模型

圖4中實(shí)線所連接的節(jié)點(diǎn)表示為DPPSAA領(lǐng)域中所必須含有的基本構(gòu)件，即對(duì)應(yīng)于特征模型中的4個(gè)強(qiáng)制特征，實(shí)線箭頭所代表的方向表示4個(gè)構(gòu)件的執(zhí)行優(yōu)先級(jí)為由高到低；點(diǎn)連線箭頭表明在算法執(zhí)行過(guò)程中2個(gè)構(gòu)件之間的交互，如在圖4中，當(dāng)比對(duì)結(jié)果輸出構(gòu)件選擇得分輸出時(shí)，則需要使用得分矩陣操作構(gòu)件中的獲取元素得分操作；虛線箭頭則代表在算法組裝過(guò)程中所需的數(shù)據(jù)、結(jié)構(gòu)以及關(guān)聯(lián)操作等，如在得分矩陣操作構(gòu)件中需要使用2個(gè)抽象數(shù)據(jù)類型(abstract data type， ADT)：罰分模型ADT和得分矩陣元素ADT，且罰分模型ADT同時(shí)作用于動(dòng)態(tài)規(guī)劃算法方式構(gòu)件等.

2.2 Apla形式化實(shí)現(xiàn)

Apla語(yǔ)言可以直接使用抽象數(shù)據(jù)類型和抽象過(guò)程編寫程序，因此能夠更抽象地描述算法問(wèn)題，并易于對(duì)其進(jìn)行正確性驗(yàn)證，保證了程序正確性和可靠性.

PAR方法和PAR平臺(tái)包含循環(huán)不變式的新定義和新的開(kāi)發(fā)策略、統(tǒng)一的算法程序設(shè)計(jì)方法、新的算法表示方法、自定義算法設(shè)計(jì)語(yǔ)言和抽象程序設(shè)計(jì)語(yǔ)言等關(guān)鍵技術(shù).它集成涵蓋了泛型、生成式、模型驅(qū)動(dòng)和構(gòu)件組裝等新型軟件開(kāi)發(fā)技術(shù)，其系列程序自動(dòng)生成系統(tǒng)可將一個(gè)正確的Apla程序自動(dòng)轉(zhuǎn)換成C++，Java，Delphi等高級(jí)語(yǔ)言程序.因此，本文利用該語(yǔ)言形式化實(shí)現(xiàn)并建立了DPPSAA領(lǐng)域算法構(gòu)件庫(kù)，不僅可高抽象表示算法程序的功能特性與非功能特性，而且能夠直觀地展示各算法構(gòu)件之間的約束以及依賴關(guān)系.這樣既減少了各構(gòu)件之間的干擾，降低了算法程序的復(fù)雜性，提高了算法構(gòu)件安全性，又消除了傳統(tǒng)算法設(shè)計(jì)方式中算法與數(shù)據(jù)難以分離的問(wèn)題，提高了構(gòu)件裝配產(chǎn)生算法的可復(fù)用性和可維護(hù)性，同時(shí)使用該算法構(gòu)件庫(kù)時(shí)，我們只需關(guān)注算法功能即可，而不用在意具體構(gòu)件實(shí)現(xiàn)細(xì)節(jié)，從而提高了算法設(shè)計(jì)效率.

下面展示了對(duì)DPPSAA領(lǐng)域構(gòu)件的Apla程序?qū)崿F(xiàn).

1) 罰分模型以及得分矩陣元素結(jié)構(gòu)設(shè)計(jì)

首先我們將罰分模型設(shè)置為一個(gè)ADT，這里我們?yōu)榻忉尫奖?，只使用固定空位罰分策略，與擴(kuò)展罰分時(shí)操作類似.其中罰分模型的ADT定義為

define ADTpenaltyMatrix(sometypeelem);

match:integer;

mismatch:integer;

space:integer;

enddef.

其中sometype為Apla語(yǔ)言中的關(guān)鍵字，用來(lái)定義類型變量.其中的match，mismatch，space分別表示罰分模型中的匹配罰分值、錯(cuò)配罰分值以及空位罰分值.

在得分矩陣中，由于序列比對(duì)結(jié)果輸出時(shí)需要進(jìn)行回溯操作，因此我們將得分矩陣中的元素定義為一個(gè)ADT，命名為H_Struct，該ADT中包含了整型變量value和boolean型的數(shù)組dp_direct，前者表示2個(gè)字符比對(duì)得分值，后者表示該得分值的來(lái)源(其中true代表對(duì)應(yīng)得分來(lái)源為真，false代表為假).并且數(shù)組內(nèi)的元素含義如圖5所示，4個(gè)方框分別代表得分矩陣中的4個(gè)元素，3個(gè)箭頭分別表示(i，j)中的得分來(lái)源為上、左和對(duì)角元素，分別用數(shù)組dp_direct下標(biāo)0,1,2對(duì)應(yīng)的數(shù)組元素來(lái)表示.

Fig. 5 Score source of score matrix element圖5 得分矩陣元素的得分來(lái)源

該ADT定義為

define ADTH_Struct(sometypeelem);

value:integer;

dp_direct:array[0:3,boolean];

enddef.

2) 得分矩陣操作

該構(gòu)件被定義為一個(gè)ADT類型，因?yàn)樵诓煌腄PPSAA中得分矩陣初始化方式不同，因此在該ADT內(nèi)部包含了一個(gè)泛型子程序Memory_Score_of_Matrix，并將Init_score_matrix方法作為它的泛型參數(shù)，使得泛型子程序可以支持實(shí)例化具有不同得分矩陣初始化方式的比對(duì)算法，即當(dāng)使用不同的方法參數(shù)實(shí)例化Init_score_matrix時(shí)，將返回不同的得分矩陣.同時(shí)在該ADT中還包含了一些常用的得分矩陣操作，如求矩陣最大得分、矩陣元素取值操作和賦值操作等.

define ADTscore_matrix_mani(sometypeelem);

procedureapply_memory(length_s:integer,length_t:integer);

procedureMemory_Score_of_Matrix(procInit_score_matrix());

functionMax_score_of_Matrix:integer;

functionthe_Last_element_score:integer;

functionget_value(i:integer;j:integer):integer;

procedureset_value(i:integer;j:integer;score:integer);

enddef.

其中該ADT類型名為score_matrix_mani，且?guī)в幸粋€(gè)類型參數(shù)elem；apply_memory泛型子程序的作用是根據(jù)整型變量length_s和length_t值為score_matrix_mani動(dòng)態(tài)分配內(nèi)存空間；函數(shù)Max_score_of_Matrix和the_Last_element_score分別表示獲取score_matrix_mani中得分最大值以及最后一個(gè)元素的得分值；get_value以及set_value分別為獲取和設(shè)置score_matrix_mani中元素得分值，(i,j)(0≤i≤length_s,0≤j≤length_t表示對(duì)應(yīng)元素的下標(biāo)，length_s和length_t分別表示兩比對(duì)序列的長(zhǎng)度.

3) 動(dòng)態(tài)規(guī)劃算法方式選擇

該構(gòu)件也被定義為泛型ADT，可以支持不同的序列比對(duì)算法所使用的動(dòng)態(tài)規(guī)劃得分模式，得分模式的變化主要依靠泛型子程序dp_align_score來(lái)實(shí)現(xiàn)，同時(shí)該ADT類型中還包括求2字符的最大比對(duì)得分操作max_score_of_char，函數(shù)中的3個(gè)參數(shù)分別表示不同來(lái)源的罰分值.

define ADTdp_mode(sometypeelemMatrix);

functionmax_score_of_char(up_score:integer;left_score:integer;diag_score:integer):integer;

proceduredp_align_scores(s:String;t:String;sM:penaltyMatrix;procset_and_remember(sometypeelemMatrix;length_s:integer;length_t:integer));

enddef.

這里elemMatrix是一個(gè)類型參數(shù)；函數(shù)set_and_remember是泛型子程序dp_align_score的泛型參數(shù)，該函數(shù)的功能為記錄得分矩陣中各元素的得分值以及得分來(lái)源，可以被用于各種動(dòng)態(tài)規(guī)劃罰分模型的實(shí)例化.

4) 檢查序列合法性

檢查序列是否屬于字符集{A,T,C,G}(默認(rèn)為DNA序列，如果為其他序列，加入對(duì)應(yīng)表示字符即可，如果為RNA序列，則將G換為U即可).

procedurecheck(s,t:String).

其中s和t都為字符串類型.

5) 記住得分來(lái)源

該構(gòu)件表示記住(i，j)處得分的來(lái)源，即將(i，j)處中對(duì)應(yīng)的方向標(biāo)志賦值為true.其為回溯階段輸出序列比對(duì)結(jié)果提供支持.

procedurermb_source(i:integer;j:integer).

6) 回溯

該構(gòu)件的Apla語(yǔ)言定義為

proceduretraceback(procprint_align();procprint_extrude()=NULL).

在回溯過(guò)程中，一般由短序列比對(duì)區(qū)間回溯和兩端突出回溯組成，其中短序列比對(duì)區(qū)間回溯表示從2序列匹配的第1個(gè)序列字符開(kāi)始，到最后匹配的字符結(jié)束位置之間的字符區(qū)間序列輸出，兩端突出回溯則表示從頭開(kāi)始到第1個(gè)匹配字符的前一個(gè)字符區(qū)間序列輸出或者最后一個(gè)匹配字符的下一個(gè)字符到最后所有字符序列對(duì)應(yīng)輸出.在trackback泛型子程序中分別由print_align和print_extrude表示，并且在默認(rèn)配置下print_extrude為空，即為全局比對(duì).

7) 比對(duì)結(jié)果輸出

這里將該構(gòu)件定義成一個(gè)泛型子程序.

procedureop_mode(funcfinally_score():integer;proctraceback(procprint_align();procprint_extrude()=NULL)).

在此泛型子程序定義中,函數(shù)finally_score功能為輸出最終比對(duì)得分.

8) 比對(duì)操作

為了能夠?qū)崿F(xiàn)現(xiàn)有的序列比對(duì)算法，需要對(duì)上述算法構(gòu)件進(jìn)行人工裝配，因此將比對(duì)操作服務(wù)定義為一個(gè)泛型子程序，并將各功能作為其參數(shù)，使之能夠支持裝配產(chǎn)生DPPSAA.

procedurealign_manipulation(op_mode(funcfinally_score():integer;proctraceback(procprint_align();procprint_extrude()=NULL));ADTdp_mode(eM:elemMatrix);sometypeelemMatrix;result:boolean;eM:elemMatrix;s:String;t:String)).

該算法構(gòu)件align_manipulation主要包含4個(gè)參數(shù)：比對(duì)輸出構(gòu)件op_mode、回溯構(gòu)件traceback、自定義泛型ADTdp_mode以及待比對(duì)序列s和t.其中elemMatrix表示為一個(gè)類型參數(shù)，并且后面4個(gè)變量參數(shù)為在主程序中實(shí)例化參數(shù)所需代入的.這樣我們就可以通過(guò)手工裝配該子程序，以達(dá)到實(shí)現(xiàn)相應(yīng)比對(duì)算法的目的.

3 NW算法的裝配實(shí)現(xiàn)

通過(guò)第2節(jié)的介紹，可以較清晰地了解到整個(gè)DPPSAA領(lǐng)域構(gòu)件庫(kù)的建立過(guò)程，下面我們利用上述構(gòu)件庫(kù)來(lái)裝配實(shí)現(xiàn)基于全局的雙序列比對(duì)算法NW，程序?yàn)?/p>

program para;

const

procedureInit_score_matrixNW(sometype

elemMatrix);

①

var

i,j:integer;H:elemMatrix;

begin

foreach(i,j:0≤i,j

length_t:…;);

②

end;

procedureset_and_remember(length_s:

integer;length_t:integer;sometype

elemMatrix);

③

var

i,j:integer;

begin

foreach(i,j:0≤i,j

length_t:…;)；

④

end;

ADTpM:newpenaltyMatrix();

ADTstruct:newH_struct();

ADTmatrix:newscore_matrix_mani(struct);

ADTdp_NW:newdp_mode(matrix);

var

dp_g:dp_NW;

begin

dp_g.dp_align_score(matrix,set_and_

remember(sometypeelemMatrix;

length_s:integer;length_t:integer));

⑤

end;

procedurealign_manipulation(sometype

elemMatrix;ADTdp_mode(eM:elemMatrix);

op_mode(funcfinally_score():integer;

proctraceback(procprint_align();

procprint_extrude()=NULL);

result:boolean;eM:elemMatrix;

s:String;t:String);

⑥

begin

if(result)

write(“The alignment score is:”,

finally_score());

else

traceback(print_align,print_extrude);

end;

procedureNW:newalign_manipulation(score_matrix_mani,dp_g,op_mode(print_align));

⑦

begin

⑧

check(s,t);

matrix.apply_memory(s.length(),

t.length());

matrix.Memory_Score_of_Matrix(Init_

score_matrixNW(matrix));

NW(false,matrix,s,t);

end.

在上面程序中，過(guò)程①為得分矩陣初始化的不同實(shí)例化方式；代碼塊②和④由于得分矩陣初始化過(guò)程占用篇幅過(guò)大，因此用…表示；過(guò)程③則為記錄比對(duì)得分值以及得分來(lái)源的實(shí)例化；⑤則表示NW算法的動(dòng)態(tài)規(guī)劃算法的實(shí)例化；泛型子程序⑥則表示在步驟⑦實(shí)例化NW算法對(duì)象時(shí)內(nèi)部所要執(zhí)行的算法構(gòu)件間的關(guān)聯(lián)操作；⑧以下的代碼塊為主程序.

4 實(shí)驗(yàn)及其結(jié)果分析

目前，由于Apla語(yǔ)言無(wú)法在PAR平臺(tái)上直接運(yùn)行，本節(jié)利用PAR平臺(tái)C++程序生成系統(tǒng)，將組裝NW算法過(guò)程中所需的Apla算法構(gòu)件代碼轉(zhuǎn)換為相對(duì)應(yīng)的C++代碼.

Apla代碼中只包含數(shù)據(jù)成員的ADT算法構(gòu)件被轉(zhuǎn)換為C++中的結(jié)構(gòu)體，如penaltyMatrix以及H_Struct等，其結(jié)果為

structpenaltyMatrix

{

intmatch;

intmismatch;

intspace;

};

structH_Struct

{

intvalue;

booldp_direct[3];

}.

含有數(shù)據(jù)成員和成員函數(shù)的ADT則被轉(zhuǎn)換為C++函數(shù)中的類，如score_matrix_mani,dp_mode等，其中大括號(hào)內(nèi)的省略號(hào)表示函數(shù)體，且Sequence類將2個(gè)待比對(duì)序列作為其數(shù)據(jù)成員.其轉(zhuǎn)換的部分結(jié)果如圖6所示.

同時(shí)，Apla代碼中的泛型子程序和泛型函數(shù)等被轉(zhuǎn)換為C++中獨(dú)立的類成員函數(shù)，降低構(gòu)件間的耦合性.其中，主調(diào)函數(shù)與主調(diào)函數(shù)泛型參數(shù)之間的關(guān)系被轉(zhuǎn)換為C++中的函數(shù)指針，即將泛型參數(shù)轉(zhuǎn)換為主調(diào)函數(shù)的指針函數(shù)參數(shù)，從而具有與Apla程序同樣的多態(tài)性特征，如traceback泛型子程序的C++轉(zhuǎn)換結(jié)果如圖7所示.

可將Apla算法構(gòu)件代碼轉(zhuǎn)換成可執(zhí)行的C++代碼，最后利用轉(zhuǎn)換后的算法構(gòu)件進(jìn)行手工裝配NW算法(即將服務(wù)align_manipulation轉(zhuǎn)換為主函數(shù))如圖8所示，并輸出代碼結(jié)果如圖9所示.

Fig. 6 Result of ADT transformation圖6 ADT轉(zhuǎn)換結(jié)果

Fig. 7 Result of generic program transformation圖7 泛型子程序轉(zhuǎn)換結(jié)果

Fig. 8 C++ assembly process of NW圖8 NW的C++裝配過(guò)程

Fig. 9 NW alignment result圖9 NW比對(duì)結(jié)果

在PAR平臺(tái)的支撐下，我們以半自動(dòng)的方式將上述Apla語(yǔ)言編寫的DPPSAA算法構(gòu)件程序轉(zhuǎn)換成C++代碼，并裝配形成NW算法.經(jīng)實(shí)際運(yùn)行NW算法檢測(cè)，算法的運(yùn)行結(jié)果與原本NW算法結(jié)果一致.使用DPPSAA領(lǐng)域構(gòu)件裝配形成的具體雙序列比對(duì)算法，不但提高了裝配算法程序的可靠性、執(zhí)行效率以及可維護(hù)性，而且可以根據(jù)客戶需求進(jìn)行手工裝配形成指定算法，增強(qiáng)了DPPSAA算法構(gòu)件的通用性.

在下一步研究工作中，為實(shí)現(xiàn)自動(dòng)化裝配DPPSAA領(lǐng)域算法，我們將使用產(chǎn)生式編程的相關(guān)方法學(xué)來(lái)開(kāi)展工作，為進(jìn)一步裝配生成奠定了基礎(chǔ)，可望裝配形成一種相較于現(xiàn)有算法具有更高執(zhí)行效率和更低內(nèi)存消耗的新型雙序列比對(duì)算法.

5 相關(guān)研究比較

針對(duì)序列比對(duì)算法研究的不同方面，國(guó)內(nèi)外學(xué)者通過(guò)使用并融合相關(guān)方法學(xué)技術(shù)開(kāi)展了較多研究工作，可分為3個(gè)方面：

1) 基于代數(shù)方法的研究.比勒費(fèi)爾德大學(xué)的Giegerich等人[23-25]提出了一種面向系統(tǒng)族的基于代數(shù)結(jié)構(gòu)的新型動(dòng)態(tài)規(guī)劃構(gòu)造算法，通過(guò)利用代數(shù)數(shù)據(jù)類型概念將動(dòng)態(tài)規(guī)劃算法過(guò)程形式化定義為2個(gè)階段：識(shí)別階段和評(píng)價(jià)階段.在具體應(yīng)用過(guò)程中，算法通過(guò)迭代進(jìn)行這2個(gè)階段，可為序列比對(duì)算法領(lǐng)域內(nèi)待生成算法提供一種更具一般性的生成范式，簡(jiǎn)化了算法開(kāi)發(fā)過(guò)程，提高了生成算法的正確性和可靠性.

2) 基于有限狀態(tài)機(jī)的研究.賓夕法尼亞大學(xué)的Searls等人[26]提出了一種基于有限狀態(tài)機(jī)和具有自適應(yīng)加權(quán)的序列比對(duì)算法生成方法.該算法利用有限狀態(tài)機(jī)模型形式化表示序列比對(duì)過(guò)程中的罰分、比對(duì)以及動(dòng)態(tài)規(guī)劃過(guò)程，并對(duì)比對(duì)過(guò)程中的不同堿基字符比對(duì)結(jié)果(匹配、錯(cuò)配以及空位)進(jìn)行自適應(yīng)加權(quán)，能夠快速地生成新型序列比對(duì)算法.算法能夠支持可視化編程.

3) 基于算法優(yōu)化的研究.算法優(yōu)化是指為了提高已有算法處理問(wèn)題能力而進(jìn)行研究的過(guò)程.文獻(xiàn)[27]采用經(jīng)典的脈動(dòng)陣列結(jié)構(gòu)的并行加速器體系結(jié)構(gòu)來(lái)提高序列加載、比對(duì)和結(jié)果收集效率的數(shù)據(jù)通路，并且利用Hash索引優(yōu)化技術(shù)過(guò)濾比對(duì)過(guò)程中的非相似行序列，增強(qiáng)了序列比對(duì)算法的性能.為了提高序列比對(duì)算法的準(zhǔn)確度，文獻(xiàn)[28-29]等利用改進(jìn)的隱馬爾可夫模型對(duì)序列比對(duì)算法進(jìn)行優(yōu)化.

6 結(jié)束語(yǔ)

序列比對(duì)作為生物序列分析中的關(guān)鍵問(wèn)題，其算法及應(yīng)用研究受到廣泛關(guān)注，然而，尚未有工作將其視為一個(gè)專門領(lǐng)域從高抽象層次開(kāi)展研究，從而提高算法可靠性和開(kāi)發(fā)效率、降低算法次優(yōu)解及誤差等問(wèn)題出現(xiàn)的概率.我們采用特征建模，分析和提取出基于動(dòng)態(tài)規(guī)劃雙序列比對(duì)算法領(lǐng)域的通用以及可變特征，并利用高抽象語(yǔ)言進(jìn)行形式化實(shí)現(xiàn)，以期能夠以自動(dòng)或者半自動(dòng)方式進(jìn)行形式化組裝生成特定問(wèn)題的求解算法，從而降低人工選擇算法進(jìn)行序列相似性分析的錯(cuò)誤發(fā)生率以及時(shí)間開(kāi)銷，提高算法執(zhí)行效率，甚至于裝配出一種更為高效的基于動(dòng)態(tài)規(guī)劃的新型序列比對(duì)算法.

本文首先提出了一種領(lǐng)域建模過(guò)程，包括上下文分析、特征建模以及領(lǐng)域?qū)崿F(xiàn)3個(gè)主要階段；其次通過(guò)分析DPPSAA領(lǐng)域的一般執(zhí)行過(guò)程，抽取出算法的通用以及可變特征，并建立領(lǐng)域特征模型；然后對(duì)建立的構(gòu)件特征模型進(jìn)行構(gòu)件交互設(shè)計(jì)，同時(shí)利用Apla語(yǔ)言形式化實(shí)現(xiàn)這些算法構(gòu)件，并通過(guò)手工裝配生成了NW算法實(shí)例；最后利用PAR平臺(tái)C++程序生成系統(tǒng)將Apla程序轉(zhuǎn)換為C++可運(yùn)行程序，轉(zhuǎn)換結(jié)果以及算法運(yùn)行結(jié)果展示了其具有一定的實(shí)用性.由于Apla的高抽象性，建立的一系列泛型構(gòu)件，如dp_mode，result_op等，保證了構(gòu)件裝配后的算法多樣性，也能夠較好地展示出算法特征之間的聯(lián)系.

我們對(duì)整個(gè)DPPSAA領(lǐng)域進(jìn)行了精確分析，對(duì)其各功能特性與非功能特性有充分的了解，同時(shí)在算法設(shè)計(jì)過(guò)程中建立了特征模型以及構(gòu)件交互設(shè)計(jì)，從而有利于算法構(gòu)件庫(kù)的學(xué)習(xí)和使用；另外，使用高抽象語(yǔ)言Apla形式化實(shí)現(xiàn)算法構(gòu)件，不僅易于對(duì)Apla算法程序進(jìn)行正確性驗(yàn)證，保證算法構(gòu)件庫(kù)的可靠性，而且在使用過(guò)程中可利用泛型編程機(jī)制快速發(fā)現(xiàn)和定位算法中的錯(cuò)誤，提高算法構(gòu)件庫(kù)的魯棒性.

本文研究DPPSAA領(lǐng)域的主要方法學(xué)思想和成果，不僅適用于DNA序列比對(duì)算法，理論上對(duì)于一些其他的生物序列分析算法領(lǐng)域也具有參考價(jià)值和實(shí)用價(jià)值，例如基因組裝過(guò)程中的基于de bruijn graph結(jié)構(gòu)的組裝算法[30-32].下一步的研究尚需擴(kuò)充本文結(jié)果在生物序列分析算法領(lǐng)域的應(yīng)用范圍，同時(shí)基于PAR平臺(tái)實(shí)現(xiàn)算法構(gòu)件庫(kù)的自動(dòng)或半自動(dòng)裝配.