張旭初，石海鶴

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

1 引言

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

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

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

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

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

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

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

2 相關(guān)方法

2.1 領(lǐng)域工程

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

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

2.2 PAR

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

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

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

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

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

2.3 產(chǎn)生式編程

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

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

3 MSAA建模

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

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

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

3.2 領(lǐng)域設(shè)計(jì)過(guò)程

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

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

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

通過(guò)上述分析，下一步根據(jù)MSAA領(lǐng)域的特征模型進(jìn)行領(lǐng)域設(shè)計(jì)，對(duì)特征之間的約束以及依賴關(guān)系進(jìn)行設(shè)計(jì)分析，建立算法構(gòu)件的交互模型。本節(jié)僅對(duì)MSAA領(lǐng)域中漸進(jìn)與迭代結(jié)合的多序列比對(duì)算法進(jìn)行交互設(shè)計(jì)，以此做一個(gè)簡(jiǎn)單的示例。該領(lǐng)域算法的輸入為生物信息序列，包括核酸序列或蛋白質(zhì)序列，在算法執(zhí)行前需要對(duì)序列信息進(jìn)行合法性檢查，檢查輸入序列中是否包含非法的堿基字符或氨基酸字符，因此該類型算法的主要構(gòu)件為序列合法性檢查構(gòu)件(seq_check)、多序列比對(duì)模式選擇構(gòu)件(msa_mode)、啟發(fā)式多序列比對(duì)算法(HMSAA)構(gòu)件、目標(biāo)函數(shù)(OF)構(gòu)件、雙序列比對(duì)算法(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中實(shí)線所連接的節(jié)點(diǎn)為迭代漸進(jìn)比對(duì)中必須含有的基本構(gòu)件，構(gòu)件的執(zhí)行優(yōu)先級(jí)隨著箭頭方向逐漸降低。點(diǎn)劃線箭頭表示算法構(gòu)件組裝過(guò)程中所需的相關(guān)數(shù)據(jù)或操作，例如啟發(fā)式多序列比對(duì)構(gòu)件需要系統(tǒng)發(fā)生樹構(gòu)件的結(jié)果來(lái)指導(dǎo)后續(xù)比對(duì)。虛線箭頭表示在算法執(zhí)行過(guò)程中2個(gè)構(gòu)件之間需進(jìn)行交互，例如在選擇算法類型時(shí)，多序列比對(duì)模式構(gòu)件需調(diào)用OF構(gòu)件、PSAA構(gòu)件、PTA構(gòu)件來(lái)進(jìn)行裝配操作。下面對(duì)關(guān)鍵構(gòu)件進(jìn)行了簡(jiǎn)單的形式化描述，采用自然語(yǔ)言的描述方式以便于理解該領(lǐng)域的算法構(gòu)件。AQ和AR為Radl規(guī)約語(yǔ)言中定義的關(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)行比對(duì)的序列組。

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

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

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

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

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

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

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

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

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

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

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

4.1 Apla實(shí)現(xiàn)

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

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

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

defineADTmsa_mode(sometypeelem);

proceduremsa(someadtadtset);

……

enddef

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

該構(gòu)件被定義為ADT，主要包括2個(gè)泛型子程序，分別是漸進(jìn)式比對(duì)Prog和迭代比對(duì)Iter，泛型子程序prog根據(jù)不同獲取比對(duì)步驟的操作進(jìn)行漸進(jìn)式比對(duì)，泛型子程序iter包括迭代子算法IterNode，傳入不同的迭代子算法操作，生成相應(yīng)的多序列比對(duì)算法，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ā)生樹的計(jì)算操作。該ADT在運(yùn)用距離法生成系統(tǒng)發(fā)生樹時(shí)，需先調(diào)用dist_matrix中的泛型子程序DistMatrix，根據(jù)傳入不同類型的雙序列比對(duì)操作和遺傳模型來(lái)計(jì)算序列組的距離矩陣。PTA構(gòu)件中包括泛型子程序TreeByDist，它將selAl作為它的泛型參數(shù)，指定距離法中運(yùn)用的聚合算法類型。

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)部存儲(chǔ)了使用仿射空位罰分所需的參數(shù)和替換矩陣，泛型子程序getOF定義了泛型操作參數(shù)comp，目前可運(yùn)用Sp函數(shù)或COFFEE函數(shù)計(jì)算目標(biāo)函數(shù)的值，用以評(píng)價(jià)多序列比對(duì)。

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在多序列比對(duì)結(jié)果的基礎(chǔ)上，對(duì)結(jié)果進(jìn)行格式化輸出，運(yù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)式比對(duì)算法的裝配代碼如下所示。通過(guò)PAR平臺(tái)的C++程序轉(zhuǎn)換系統(tǒng)，可將Apla裝配算法程序轉(zhuǎn)換為可執(zhí)行的C++程序。

programipmsa;

const/* input sequences*/

var

seqs,seqsName: array[String];

//seqs是待比對(duì)的序列組

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

seqsNum: Integer

//seqsNum是比對(duì)序列的條數(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 實(shí)驗(yàn)

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

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

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

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

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

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

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