多序列比對算法族的形式化設(shè)計與生成*

張旭初，石海鶴

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

1 引言

高通量測序技術(shù)[1]的飛速發(fā)展推進(jìn)了國際上眾多基因組計劃[2]的實施，生物信息學(xué)[3]領(lǐng)域生成了海量的數(shù)據(jù)，促使生物信息大數(shù)據(jù)逐漸形成，且規(guī)模還在不斷增長。目前生物信息學(xué)面臨的一大挑戰(zhàn)就是如何快速準(zhǔn)確地分析這些數(shù)據(jù)，序列比對是對生物序列數(shù)據(jù)進(jìn)行研究的基本途徑和方法[4]，其原理符合生物學(xué)中的相關(guān)化學(xué)基礎(chǔ)。

多序列比對是序列比對的重要組成部分，在序列信息分析、蛋白質(zhì)功能分析、測序數(shù)據(jù)的基因糾錯等方面應(yīng)用廣泛。多序列比對結(jié)果往往為相關(guān)的生物學(xué)研究提供基礎(chǔ)或依據(jù)，其算法的性能至關(guān)重要。多序列比對結(jié)果的準(zhǔn)確程度在于它是否可以盡可能準(zhǔn)確地顯示相關(guān)的生物學(xué)意義，為了量化這一標(biāo)準(zhǔn)，直觀地評判多序列比對結(jié)果的優(yōu)劣，研究人員引入了目標(biāo)函數(shù)這一數(shù)學(xué)模型。比對和函數(shù)[5]是目前被廣泛認(rèn)可的目標(biāo)函數(shù)，它的理論基礎(chǔ)是得分函數(shù)具有可加性，通過雙序列比對得分和來評估多序列比對結(jié)果。后續(xù)研究人員提出了準(zhǔn)確性更高的一致性函數(shù)[6]，它反映了比對結(jié)果和雙序列比對擴展庫之間的一致性程度?；谙嚓P(guān)目標(biāo)函數(shù)的多序列比對問題已被證明是NP難題[7]，因此研究人員只能致力于尋找該問題的近似最優(yōu)解。在目標(biāo)函數(shù)的研究中，相關(guān)參數(shù)的優(yōu)化選擇也是一個重點[8]，實際應(yīng)用時，合適的目標(biāo)函數(shù)選擇與合適的參數(shù)設(shè)置可以大大提高多序列比對算法結(jié)果的質(zhì)量。

多序列比對算法主要有精準(zhǔn)比對算法和近似比對算法。然而，精準(zhǔn)比對算法由于其對計算機資源的消耗過高，無法應(yīng)用于實際研究，不予贅述。近似比對算法為了降低多序列比對問題的復(fù)雜性，對比對結(jié)果的準(zhǔn)確性進(jìn)行了妥協(xié)，主要包括啟發(fā)式比對算法和隨機概率型比對算法等。啟發(fā)式比對算法主要包括漸進(jìn)式比對算法[9]和迭代比對算法[10]。漸進(jìn)式比對算法思想于1987年由Feng等人提出，他們認(rèn)為參與多序列比對的序列之間存在一定的進(jìn)化關(guān)系，可沿著進(jìn)化關(guān)系對序列進(jìn)行逐步比對，直至所有的序列都比對完成。因此，在進(jìn)行漸進(jìn)式比對之前，如何尋找隱含在序列組中的進(jìn)化順序至關(guān)重要。1994年，Thompson等人[11]實現(xiàn)了漸進(jìn)式比對算法思想，提出了ClustalW算法。漸進(jìn)式多序列比對算法的主要缺點在于它的“一旦空位，永遠(yuǎn)空位”原則，比對過程中產(chǎn)生的錯誤會一直影響序列比對過程，以致算法難以獲得比對問題的近似最優(yōu)解，降低了算法精度，更無法處理大規(guī)模數(shù)據(jù)。2005年，Lassmann等人[12]運用Wu-Manber近似字符串匹配算法優(yōu)化了距離矩陣的計算與漸進(jìn)式比對的操作，進(jìn)而提出了Kalign算法，它在數(shù)據(jù)量較大和距離較遠(yuǎn)的序列比對中更準(zhǔn)確，消耗時間更短，該算法還在不斷改進(jìn)以適應(yīng)數(shù)據(jù)量劇增的多序列比對需求[13]。此外，研究人員還提出了通過尋找中心序列來進(jìn)行漸進(jìn)式比對的HAlign算法[14]。目前研究人員主要使用迭代思想和一致性函數(shù)2種策略來優(yōu)化漸進(jìn)式比對。2000年，Notredame等人[15]提出的T-COFFEE算法，就是利用一致性函數(shù)對漸進(jìn)式比對算法進(jìn)行了優(yōu)化，提高了比對結(jié)果的質(zhì)量，但增加了比對時間。迭代比對思想運用可快速生成比對的算法，在產(chǎn)生初步比對結(jié)果后，通過相應(yīng)的迭代操作來改進(jìn)，直到比對結(jié)果不再優(yōu)化或是已達(dá)到既定迭代次數(shù)為止。利用迭代比對思想，可以提高漸進(jìn)式比對算法的魯棒性，優(yōu)化漸進(jìn)式比對前期錯誤無法改進(jìn)的缺陷，同時也擴寬了算法的適用范圍，這類算法常見的有MAFFT[16]、MUSCLE[17]等。除此之外，通過隨機概率算法如蟻群算法[18]、隱馬爾可夫模型[19]、人工蜂群算法[20]等來進(jìn)行迭代比對也取得了較好的成果。

由于雙序列比對可對序列之間的相似性進(jìn)行刻畫，因此常被用于輔助多序列比對。Needleman-Wunsch算法[21]是最經(jīng)典的全局雙序列比對算法，而Smith-Waterman算法[22]則用于解決局部雙序列比對問題，它們均基于動態(tài)規(guī)劃思想。然而，標(biāo)準(zhǔn)動態(tài)規(guī)劃算法在處理序列組的兩兩比對時，內(nèi)存空間占用過大，時間復(fù)雜度較高，后續(xù)出現(xiàn)了優(yōu)化空間復(fù)雜度的Hirschberg算法[23]、快速序列聯(lián)配FA(Fast Alignment)算法[24]和優(yōu)化的全局雙序列比對OGP(Optimized Global Pairwise)算法[25]等。在對結(jié)果準(zhǔn)確性要求不高的情況下，可以采用啟發(fā)式近似比對算法來處理較長序列的比對，這一類算法包括FASTA[26]、BLAST[27]、MUMmer[28]和AVID[29]等，其中前兩者主要用于參考基因組的相似性序列搜索。

在生物信息學(xué)的研究中，分析物種的進(jìn)化歷史、確認(rèn)各個物種之間的親緣關(guān)系也是一個熱點問題。構(gòu)建系統(tǒng)發(fā)生樹(Phylogenetic Tree)可以直觀地展現(xiàn)物種之間的進(jìn)化關(guān)系和進(jìn)化距離。同時，在多序列比對算法中，系統(tǒng)發(fā)生樹也可作為指導(dǎo)樹來指導(dǎo)比對操作。建立系統(tǒng)發(fā)生樹主要有3種方法：距離矩陣法[30]、最大簡約法[31]和最大似然法[32]。距離矩陣法是目前最常用的方法，它根據(jù)序列間兩兩比對的結(jié)果經(jīng)過相應(yīng)的計算建立距離矩陣，然后用聚類算法根據(jù)距離矩陣構(gòu)造系統(tǒng)發(fā)生樹。計算距離的方式?jīng)Q定著系統(tǒng)發(fā)生樹的質(zhì)量，而序列距離的計算通常受到遺傳模型的影響。

目前，多序列比對算法族MSAA(Multiple Sequence Alignment Algorithm)的研究主要集中在特定算法特定步驟上的優(yōu)化[33,34]，或是對算法進(jìn)行并行化實現(xiàn)[35]，算法的比對效率和準(zhǔn)確性提升對不同序列產(chǎn)生的優(yōu)化效果有所不同。由于多序列比對算法的種類多樣性和結(jié)構(gòu)復(fù)雜性，許多使用者無法恰當(dāng)選擇符合序列特點的算法，在應(yīng)用過程中可能產(chǎn)生不必要的誤差。因此，從領(lǐng)域抽象層次對多序列比對算法開展研究極為必要。通過分析和提取MSAA領(lǐng)域的共性和異性，形式化構(gòu)建算法理論框架，進(jìn)而生成特定的MSAA領(lǐng)域算法，將有助于提高M(jìn)SAA領(lǐng)域算法的可靠性和開發(fā)效率。

本文后續(xù)在已有工作的基礎(chǔ)上對MSAA的形式化設(shè)計與生成進(jìn)行闡述。相關(guān)的理論與方法學(xué)主要是領(lǐng)域工程、形式化方法PAR(Partition-And-Recur)[36 - 41]和產(chǎn)生式編程GP(Generative Programming)[42]等?；诋a(chǎn)生式編程思想，運用面向特征的領(lǐng)域建模方法FODM(Feature-Oriented Domain Model)[43]對MSAA算法族進(jìn)行領(lǐng)域分析，建立MSAA領(lǐng)域特征模型，并設(shè)計相應(yīng)的算法生成架構(gòu)與構(gòu)件交互模型。進(jìn)一步運用PAR予以形式化實現(xiàn)，從而建立Apla高抽象構(gòu)件庫，將Apla構(gòu)件進(jìn)行組裝并轉(zhuǎn)換，生成可執(zhí)行的算法，最后運用實際的DNA序列對生成的算法進(jìn)行實驗分析。

2 相關(guān)方法

2.1 領(lǐng)域工程

領(lǐng)域工程[44]是軟件復(fù)用的基礎(chǔ)過程，它的目的是在某一特定領(lǐng)域中獲取并運用可重用資源，高效、低成本地開發(fā)高質(zhì)量的軟件。領(lǐng)域工程主要對領(lǐng)域進(jìn)行分析、設(shè)計與實現(xiàn)。領(lǐng)域分析包括系統(tǒng)范圍界定、領(lǐng)域需求定義、相關(guān)術(shù)語分析等一系列活動，最終將結(jié)果都反映在領(lǐng)域模型中。領(lǐng)域設(shè)計完成了領(lǐng)域中系統(tǒng)族的架構(gòu)設(shè)計，識別了相應(yīng)的功能以及相關(guān)的約束條件，除此之外還對后續(xù)實現(xiàn)過程制定了計劃。領(lǐng)域?qū)崿F(xiàn)運用合適的技術(shù)完成對架構(gòu)、組件等可復(fù)用資源的開發(fā)。這3個階段在實際應(yīng)用時采用逐步求精的思想，隨時根據(jù)需求的變化對已完成的成果進(jìn)行修改和完善。

領(lǐng)域分析是領(lǐng)域工程的基礎(chǔ)，所生成的領(lǐng)域模型影響后續(xù)工作的質(zhì)量，通常采用自頂向下和自底向上結(jié)合的方式，反復(fù)進(jìn)行領(lǐng)域分析活動。自頂向下分析考慮較多的是領(lǐng)域中未來系統(tǒng)所要滿足的需求，自底向上分析則較多考慮目前已有的系統(tǒng)以及之前開發(fā)所積累的可復(fù)用資源。為了高效地進(jìn)行領(lǐng)域分析活動，張偉等人[43]提出了一種特征建模方法FODM，該方法重點考慮了領(lǐng)域中的服務(wù)、功能和行為特點等特征，論述了一種特征模型的展現(xiàn)形式及其詳細(xì)建模過程。

2.2 PAR

PAR[36]包括一種切實可行的形式化方法以及相應(yīng)的支持平臺。PAR平臺包括需求設(shè)計語言SNL(Structured Natural Language)、算法建模語言Radl、抽象程序設(shè)計語言Apla、一系列轉(zhuǎn)換規(guī)則及自動轉(zhuǎn)換工具。PAR注重于算法的設(shè)計與實現(xiàn)，支持目前主流的大多數(shù)算法設(shè)計技術(shù)，包含新式的循環(huán)不變式開發(fā)策略，實現(xiàn)了分布式事務(wù)處理系統(tǒng)以及關(guān)系數(shù)據(jù)庫機制。運用PAR方法開發(fā)算法，可以對算法有更深刻的理解，避免產(chǎn)生對設(shè)計方法的選擇困難問題。敏捷的泛型機制是PAR的重要特性之一，無論數(shù)據(jù)類型、數(shù)據(jù)值、計算操作還是用戶自定義ADT(Abstract Data Type)均可以是泛型參數(shù)。Apla可以直接使用抽象數(shù)據(jù)類型和抽象過程編寫程序，它既有數(shù)學(xué)語言簡潔的優(yōu)點，也有表達(dá)無歧義的特點，其語言本身的高抽象性，十分適合描述抽象算法程序。下面介紹一下Apla泛型的實現(xiàn)機制與約束機制。

(1)Apla包括類型變量、類型域、操作變量、操作域、ADT變量和ADT域的概念，分別使用sometype、someaction和someadt表示類型域、操作域和ADT域，實現(xiàn)了類型、函數(shù)、程序、自定義ADT等的參數(shù)化操作。實例化過程中可傳入符合相關(guān)屬性條件的實參來實現(xiàn)不同的程序單元。

(2)泛型約束詳細(xì)描述了泛型參數(shù)的類型和構(gòu)成，泛型約束機制的實現(xiàn)可大大提高泛型程序的可靠性，是真正實現(xiàn)泛型編程的必要條件之一。PAR平臺對基本數(shù)據(jù)類型、ADT類型、子程序類型等泛型參數(shù)實現(xiàn)了相關(guān)泛型約束，提出了相應(yīng)的約束描述、匹配和檢測機制，且仍在不斷的完善中[45]。

除此之外，PAR平臺還支持將Apla轉(zhuǎn)換為C++、Java、C#、Delphi等可執(zhí)行的高級程序設(shè)計語言，對于構(gòu)件的開發(fā)有著較好的支持。PAR建立了2條形式化開發(fā)程序的途徑，其平臺架構(gòu)如圖1所示。第1條是對于量化問題而言，PAR方法可以將SNL需求模型轉(zhuǎn)換為Radl規(guī)約模型，繼而轉(zhuǎn)換為Radl算法模型，再進(jìn)一步轉(zhuǎn)換為Apla抽象程序模型，最后轉(zhuǎn)換為可直接運行的高級語言程序。第2條途徑是對于非量化問題，可以直接通過SNL需求模型手工設(shè)計Apla程序，并輔以相應(yīng)的形式化證明，再將Apla程序轉(zhuǎn)換為可執(zhí)行程序。

Figure 1 Architecture of PAR platform圖1 PAR平臺架構(gòu)

2.3 產(chǎn)生式編程

產(chǎn)生式編程GP是一種新型的軟件范型，符合軟件復(fù)用的思想，使用組件并以一種自動化的方式來制作軟件產(chǎn)品，對解決“軟件危機”有重要的意義。實現(xiàn)GP要經(jīng)過2個步驟。首先是將目前的軟件開發(fā)模式轉(zhuǎn)變?yōu)閷浖到y(tǒng)族的開發(fā)，然后還需要開發(fā)產(chǎn)生器來對組件進(jìn)行自動裝配。GP是領(lǐng)域工程運用的一個實例，它需要充分利用現(xiàn)有的領(lǐng)域知識完成相應(yīng)領(lǐng)域的構(gòu)件開發(fā)，最終利用產(chǎn)生器通過構(gòu)件裝配的方式開發(fā)領(lǐng)域中的新軟件，無需按照軟件工程的步驟從頭開始編程。

產(chǎn)生式編程的目的是實現(xiàn)對組件和應(yīng)用程序的生產(chǎn)自動化，其關(guān)鍵的部分是對系統(tǒng)族建立領(lǐng)域模型。產(chǎn)生式領(lǐng)域模型包含3部分：問題空間、解空間和相應(yīng)的配置知識。問題空間中主要包括應(yīng)用程序員和用戶對系統(tǒng)的需求，需求一般利用程序的概念和特征進(jìn)行描述；解空間包括可以解決需求問題的相關(guān)組件以及各組件的組合模式，并要求達(dá)到最大的可組合性，且組合間的冗余要達(dá)到最小，還必須盡可能實現(xiàn)組件的最高重用性。配置知識則是問題空間與解空間的映射關(guān)系，避免了非法特征組合的出現(xiàn)，且對特征的默認(rèn)參數(shù)與規(guī)則進(jìn)行了設(shè)置。

3 MSAA建模

3.1 領(lǐng)域分析過程

本節(jié)建立在對目前常用的多序列比對算法研究的基礎(chǔ)上，對先前的研究結(jié)果進(jìn)行擴展[46]，利用FODM的建模方法對MSAA領(lǐng)域中的服務(wù)S(Service)、功能F(Function)、行為特點B(Behavior characteristics)進(jìn)行特征建模。 多序列比對服務(wù)是MSAA領(lǐng)域的核心服務(wù)，該領(lǐng)域中的主要功能有雙序列比對算法PSAA(Pairwise Sequence Alignment Algorithm)操作、系統(tǒng)發(fā)生樹算法PTA(Phylogenetic Tree Algorithm)操作、啟發(fā)式多序列比對算法HMSAA(Heuristic Multiple Sequence Alignment Algorithm)操作以及目標(biāo)函數(shù)OF(Objective Function)評價。其中雙序列比對算法操作、系統(tǒng)發(fā)生樹算法操作為可選擇功能，目標(biāo)函數(shù)評價和啟發(fā)式多序列比對算法操作是必選功能，對每個功能的描述僅關(guān)注主要組成部分。動態(tài)規(guī)劃比對(DP)和快速比對(fast)是雙序列比對算法操作的子功能，對于動態(tài)規(guī)劃比對，動態(tài)規(guī)劃模式選擇(DP_mode)是其行為特點， 主要包括2種模式可供選擇：標(biāo)準(zhǔn)動態(tài)規(guī)劃算法(normal)和優(yōu)化內(nèi)存消耗的動態(tài)規(guī)劃算法(space_opti)。距離法(dist)、最大似然法ML(Maximum Likelihood)和最大簡約法MP(Maximum Parsimony)是系統(tǒng)發(fā)生樹算法操作的子功能，對于距離法和最大似然法，遺傳模型選擇(genetic_model)是其行為特點， 這里只顯示了2種常用的遺傳模型，分別是kimura兩參數(shù)模型(kimura)和Judes-Cantor單參數(shù)模型(JC)。對于距離法，它還有一個行為特點 是對聚類算法的選擇(dist_algorithm)， 聚類算法的選擇模式主要有2種：鄰接法NJ(Neighbor-Joining method)和非加權(quán)配對算術(shù)平均法UPGMA(Unweighted Pair-Group Method with Arithmetic means)。啟發(fā)式比對算法操作主要包括2個子功能，漸進(jìn)式比對(prog)在之前的研究中已進(jìn)行詳細(xì)敘述，對于迭代比對(iter)，迭代模式選擇(iter_mode)是其行為特點， 且存在多種模式可供選擇，圖2中只顯示了迭代漸進(jìn)式比對(progIter)和基于隱馬爾可夫模型(hidden Markov)的迭代模式。對于目標(biāo)函數(shù)(OF)評價，目標(biāo)函數(shù)選擇(OF_sel)是其行為特點 ，包括一致性函數(shù)(COFFEE)和比對和函數(shù)(SP) 2種函數(shù)選擇模式，除此之外，目標(biāo)函數(shù)計算參數(shù)設(shè)置(para_set)也是其行為特點， 且需要同時設(shè)置2種參數(shù)：罰分模型(penalty)和替換矩陣(subMatrix) 。MSAA領(lǐng)域的特征模型如圖2所示。

Figure 2 Feature model of MSAA圖2 MSAA特征建模

3.2 領(lǐng)域設(shè)計過程

對多序列比對算法進(jìn)一步分析后，得出3種常見的漸進(jìn)式比對算法步驟，如圖3所示。3種多序列比對算法有共同的起點與終點，均需進(jìn)行雙序列比對以及最后確定最佳漸進(jìn)式比對的操作，不同之處在于根據(jù)系統(tǒng)發(fā)生樹或星比對確定比對順序的算法通常采用SP目標(biāo)函數(shù)，而采用COFFEE目標(biāo)函數(shù)的算法，則一般是通過雙序列比對信息構(gòu)建拓展庫以指導(dǎo)多序列比對。 迭代比對中常用的是MUSCLE算法，其思想是將漸進(jìn)式樹比對算法進(jìn)行迭代，在每一個子步驟中，選擇執(zhí)行速度更快的方法，例如運用k-mer算法[47]來進(jìn)行雙序列比對。進(jìn)一步通過迭代思想提高多序列比對MSA(Multiple Sequence Alignment)的精度，其算法步驟如圖4所示。在此基礎(chǔ)上，可對迭代部分進(jìn)行替換來產(chǎn)生其他新式的多序列比對算法。

Figure 3 Steps of three common progressive alignment algorithms圖3 3種常見漸進(jìn)式比對算法的步驟

Figure 4 Steps of the MUSCLE圖4 MUSCLE算法的步驟

通過上述分析，下一步根據(jù)MSAA領(lǐng)域的特征模型進(jìn)行領(lǐng)域設(shè)計，對特征之間的約束以及依賴關(guān)系進(jìn)行設(shè)計分析，建立算法構(gòu)件的交互模型。本節(jié)僅對MSAA領(lǐng)域中漸進(jìn)與迭代結(jié)合的多序列比對算法進(jìn)行交互設(shè)計，以此做一個簡單的示例。該領(lǐng)域算法的輸入為生物信息序列，包括核酸序列或蛋白質(zhì)序列，在算法執(zhí)行前需要對序列信息進(jìn)行合法性檢查，檢查輸入序列中是否包含非法的堿基字符或氨基酸字符，因此該類型算法的主要構(gòu)件為序列合法性檢查構(gòu)件(seq_check)、多序列比對模式選擇構(gòu)件(msa_mode)、啟發(fā)式多序列比對算法(HMSAA)構(gòu)件、目標(biāo)函數(shù)(OF)構(gòu)件、雙序列比對算法(PSAA)構(gòu)件、系統(tǒng)發(fā)生樹算法(PTA)構(gòu)件和結(jié)果輸出構(gòu)件(result_op)。根據(jù)構(gòu)件間的依賴關(guān)系建立構(gòu)件的交互模型，如圖5所示。

Figure 5 Interaction model of algorithm components圖5 算法構(gòu)件交互模型

圖5中實線所連接的節(jié)點為迭代漸進(jìn)比對中必須含有的基本構(gòu)件，構(gòu)件的執(zhí)行優(yōu)先級隨著箭頭方向逐漸降低。點劃線箭頭表示算法構(gòu)件組裝過程中所需的相關(guān)數(shù)據(jù)或操作，例如啟發(fā)式多序列比對構(gòu)件需要系統(tǒng)發(fā)生樹構(gòu)件的結(jié)果來指導(dǎo)后續(xù)比對。虛線箭頭表示在算法執(zhí)行過程中2個構(gòu)件之間需進(jìn)行交互，例如在選擇算法類型時，多序列比對模式構(gòu)件需調(diào)用OF構(gòu)件、PSAA構(gòu)件、PTA構(gòu)件來進(jìn)行裝配操作。下面對關(guān)鍵構(gòu)件進(jìn)行了簡單的形式化描述，采用自然語言的描述方式以便于理解該領(lǐng)域的算法構(gòu)件。AQ和AR為Radl規(guī)約語言中定義的關(guān)鍵詞，分別用于描述前置斷言和后置斷言。

(1)msa_mode構(gòu)件。

|[inusersettingsoutmsa_mode: ADT]|

AQ: 用戶已選擇算法類型。

AR: 指定算法類型，并完成相應(yīng)組裝操作。

(2) PSAA構(gòu)件[48]。

|[inOF: ADT;a[][]: Array[][];outb[][]: Array [][];score: double]|

AQ: 存在目標(biāo)函數(shù)參數(shù)和需要進(jìn)行比對的序列組。

AR: 序列兩兩比對的結(jié)果。

(3) HMSAA構(gòu)件。

|[inOF: ADT;a[][]: Array[][];align: ADToutb[][]: Array [][]]|

AQ: 存在目標(biāo)函數(shù)參數(shù)、需要進(jìn)行比對的序列組以及比對所需的關(guān)聯(lián)操作，具體由msa_mode指定。

AR: 比對結(jié)束的序列組。

(4) PTA 構(gòu)件。

|[inPSAA: ADT;geneModel: ADToutphy_tree: ADT]|

AQ: 存在雙序列比對產(chǎn)生的得分矩陣，并選擇了相關(guān)遺傳模型。

AR: 用以指導(dǎo)后續(xù)多序列比對操作的系統(tǒng)發(fā)生樹。

4 Apla形式化實現(xiàn)及實驗

本節(jié)根據(jù)MSAA領(lǐng)域的特征模型和算法構(gòu)件交互模型，結(jié)合先前在HMSAA領(lǐng)域中的研究成果，對MSAA領(lǐng)域中的構(gòu)件進(jìn)行基于Apla的形式化實現(xiàn)。運用Apla中敏捷的泛型機制，提高算法的抽象性，在HMSAA領(lǐng)域構(gòu)件的基礎(chǔ)上進(jìn)行符合約束條件的修改及擴展，擴大支持生成的算法領(lǐng)域范圍。最后對生成的漸進(jìn)式序列比對算法進(jìn)行實驗分析。

4.1 Apla實現(xiàn)

本節(jié)只展示迭代漸進(jìn)比對算法的Apla組裝實現(xiàn)，對先前的算法構(gòu)件進(jìn)行相應(yīng)的修改。程序代碼中僅列出了MSAA領(lǐng)域構(gòu)件的定義，以及參數(shù)的具體釋義。

(1)msa_mode構(gòu)件。

該構(gòu)件定義了一系列合法的泛型ADT組合，提高了算法的抽象性。泛型子程序msa根據(jù)用戶在組裝過程中傳入的ADT，生成不同的多序列比對算法。

defineADTmsa_mode(sometypeelem);

proceduremsa(someadtadtset);

……

enddef

(2)HMSAA構(gòu)件。

該構(gòu)件被定義為ADT，主要包括2個泛型子程序，分別是漸進(jìn)式比對Prog和迭代比對Iter，泛型子程序prog根據(jù)不同獲取比對步驟的操作進(jìn)行漸進(jìn)式比對，泛型子程序iter包括迭代子算法IterNode，傳入不同的迭代子算法操作，生成相應(yīng)的多序列比對算法，flag表示迭代是否繼續(xù)。

defineADTHMSAA(sometypeelem);

procedureprog(someactiongetSteps;seqs: array [string];seqsName: array[string]);

procedureiter(someactionIterNode;flag: boolean);

……

enddef

(3)PTA構(gòu)件。

該構(gòu)件定義為ADT，其主要用于進(jìn)行系統(tǒng)發(fā)生樹的計算操作。該ADT在運用距離法生成系統(tǒng)發(fā)生樹時，需先調(diào)用dist_matrix中的泛型子程序DistMatrix，根據(jù)傳入不同類型的雙序列比對操作和遺傳模型來計算序列組的距離矩陣。PTA構(gòu)件中包括泛型子程序TreeByDist，它將selAl作為它的泛型參數(shù)，指定距離法中運用的聚合算法類型。

defineADTdist_matrix(sometypeelem);

procedureDistMatrix(someacationpsa;someactionselGm);

enddef;

defineADTPTA(sometypeelem);

procedureTreeByDist(distMat: elem;someactionselAlgorithm;seqName: array[string];first: Integer;last: Integer;treeName: string;result: boolean);

……

enddef

(4)OF構(gòu)件。

該構(gòu)件被定義為ADT，內(nèi)部存儲了使用仿射空位罰分所需的參數(shù)和替換矩陣，泛型子程序getOF定義了泛型操作參數(shù)comp，目前可運用Sp函數(shù)或COFFEE函數(shù)計算目標(biāo)函數(shù)的值，用以評價多序列比對。

defineADTOF(sometypeelem);

gapOpen:double;

gapExtend:double;

subMatrix:array[array[double]];

proceduresetOFpara(gapOpen: double;gapExtend: double;subMatrix: array[array[double]]);

proceduregetOF(someactioncomp);

……

enddef

(5)result_op構(gòu)件。

該構(gòu)件被定義為ADT，泛型子程序multiAlign_op在多序列比對結(jié)果的基礎(chǔ)上，對結(jié)果進(jìn)行格式化輸出，運用format泛型操作參數(shù)指定輸出的格式化模式，常用的格式化模式有ClustalW格式、Phylip格式和Html格式等。子程序phyloTree_op將系統(tǒng)發(fā)生樹結(jié)果進(jìn)行輸出。

defineADTresult_op(sometypeelem)

proceduremultiAlign_op(pathAlignOutput: String;ADTHMSAA; someactionformat);

procedurephyloTree_op(pathTreeOutput: String;seqName: array[string];ADTPTA);

enddef

根據(jù)構(gòu)件裝配形成迭代漸進(jìn)式比對算法的裝配代碼如下所示。通過PAR平臺的C++程序轉(zhuǎn)換系統(tǒng)，可將Apla裝配算法程序轉(zhuǎn)換為可執(zhí)行的C++程序。

programipmsa;

const/* input sequences*/

var

seqs,seqsName: array[String];

//seqs是待比對的序列組

//seqsName是比對序列對應(yīng)的名稱

seqsNum: Integer

//seqsNum是比對序列的條數(shù)

constpathTreeOutput: String;

constpathAlignOutput: String;

ADTpsa: newPSAA(dp_nw);

ADTdist: newdist_matrix(seqsNum);

ADTpta: newPTA();

ADThmsaa: newHMSAA();

ADTof: newOF(sp);

ADTresult: newresult_op();

of.setOFPara(gapOpen: double;gapExtend:

double;submatrix: array[array[double]]);

proceduredistMat: newdist.DistMatrix(psa,kimura，…);

proceduregenerateTree: newpta.TreeByDist(distMat,UPGMA,…);

procedureprog_align: newhmsaa.prog(tree,…);

procedureiter: newhmsaa.iter(prog_align,…);

ADTmode: newmsa_mode();

proceduremul_align_main(seqs: array[String];

seqsName: array[String];pathTreeOutput: String;

pathAlignOutput: String;ADTmsa_mode;ADTresult_op);//算法組裝代碼

var

res: Boolean;treeFileName: String;

begin

align_mode:mode;

result_type:result;

align_mode.msa(generateTree(distMat(…),…),of(…),iter(prog_align,…));

result_type.phyloTree_op(pathTreeOutput,seqsName,pta);

result_type.multiAlign_op(pathAlignOutput,ClustalW,…);

end;

procedureiter_prog_msa: newmul_align_main(mode,result,…);//主程序

begin

check(seqs);

iter_prog_msa(seqs,seqsName,seqsNum,…);

end;

4.2 實驗

GenBank是由美國國家生物技術(shù)信息中心(NCBI)建立和維護(hù)的世界3大核酸數(shù)據(jù)庫之一，本文從該數(shù)據(jù)庫下載了4條關(guān)于血紅蛋白或β球蛋白的DNA片段作為實驗數(shù)據(jù)，四條序列的長度均在500個堿基以上。通過將組裝形成的漸進(jìn)式比對算法與ClustalO、MUSCLE進(jìn)行實驗比較，驗證了目前已生成的算法具有一定的實用性。截取部分比對結(jié)果如圖6所示，該圖橫線上半部分表示所生成的系統(tǒng)發(fā)生樹結(jié)果，橫線下半部分表示多序列比對結(jié)果。

Figure 6 Sequences alignment results圖6 序列比對結(jié)果

5 結(jié)束語

近年來生物信息學(xué)發(fā)展迅速，但仍有大量問題未完全得到解決，多序列比對問題便是其中之一，由于其問題的NP完全性，研究人員試圖尋求最佳近似解?，F(xiàn)有的研究大多針對特定問題或特定算法，甚少從算法領(lǐng)域?qū)哟伍_展研究，存在著可重用性和開發(fā)效率較低、冗余性過高等問題，使用者往往難以選擇恰當(dāng)?shù)亩嘈蛄斜葘λ惴ā?/p>

本文基于產(chǎn)生式編程思想和FODM的建模方法，考慮MSAA領(lǐng)域中的雙序列比對、啟發(fā)式多序列比對、系統(tǒng)發(fā)生樹和目標(biāo)函數(shù)等特征，通過一系列分析活動及回溯求精，構(gòu)建了MSAA領(lǐng)域特征模型；深入分析特征間的依賴約束關(guān)系，抽取其中的通用特征以及可變特征，形式化設(shè)計了相應(yīng)的算法構(gòu)件及其交互模型，進(jìn)一步使用PAR的Apla語言進(jìn)行了形式化實現(xiàn)，建立了Apla泛型構(gòu)件庫；最后通過PAR平臺的一系列程序轉(zhuǎn)換系統(tǒng)將其快速裝配生成可執(zhí)行的算法。對比之前的研究結(jié)果，本文模型精化擴展了部分構(gòu)件，提高了算法的抽象性與泛型程度，擴大了可組裝算法的范圍。

Apla語言的高抽象性與易于驗證性，確保了構(gòu)件裝配算法的多樣性，提高了算法構(gòu)件庫的可靠性；PAR平臺自動或半自動的算法裝配生成，提高了算法的開發(fā)效率，較好地展示了算法特征之間的關(guān)系，便于研究人員理解和使用算法。本文融合領(lǐng)域工程、產(chǎn)生式編程、形式化方法等理論、方法和技術(shù)在多序列比對算法族上開展的研究實踐，理論上可為生物信息學(xué)中其他領(lǐng)域算法研究提供新的思路。

下一步工作將繼續(xù)完善PAR和算法構(gòu)件庫，增加相應(yīng)的算法構(gòu)件，如隱馬爾可夫模型，快速傅里葉變換等，將該方法學(xué)進(jìn)一步應(yīng)用于其他生物信息學(xué)研究領(lǐng)域中。同時也將積極開發(fā)可視化裝配工具，方便算法構(gòu)件的組裝操作，用戶通過選擇不同的構(gòu)件，即可生成相應(yīng)的序列比對算法。運用XML文件對構(gòu)件間的組成和約束關(guān)系進(jìn)行刻畫，裝配操作只需修改XML文件的內(nèi)容，而不會影響構(gòu)件庫中的組裝代碼。