生物序列比對(duì)的并行計(jì)算以及啟發(fā)式算法.pdf

1、生物信息學(xué)以計(jì)算機(jī)、網(wǎng)絡(luò)為工具，用數(shù)學(xué)等科學(xué)理論、方法和技術(shù)研究生物大分子，主要包括脫氧核糖核酸(DNA)和蛋白質(zhì)(Protein)的序列、結(jié)構(gòu)和功能。生物序列的比對(duì)，是生物信息學(xué)中最基本、最重要的操作，在序列分析、基因識(shí)別、蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)、生物進(jìn)化樹(shù)的構(gòu)建等領(lǐng)域中有著廣泛的應(yīng)用。通過(guò)序列比對(duì)可以發(fā)現(xiàn)生物序列中的功能、結(jié)構(gòu)以及進(jìn)化信息。 在本文中，我們提出了可重構(gòu)光總線并行計(jì)算模型LARPBS模型上的一個(gè)快速可擴(kuò)放的雙序列比對(duì)并

2、行算法，以及用蟻群算法求解多序列比對(duì)問(wèn)題的三種不同方法，并給出了該方面工作的進(jìn)一步研究思路。 生物序列的信息量很大，對(duì)其進(jìn)行比對(duì)操作需要花費(fèi)大量的計(jì)算時(shí)間，所以，序列比對(duì)的并行計(jì)算已經(jīng)成為研究的一個(gè)熱點(diǎn)問(wèn)題。我們利用可重構(gòu)的光總線并行計(jì)算模型LARPBS，設(shè)計(jì)了一個(gè)快速可擴(kuò)放的雙序列比對(duì)并行算法，對(duì)于長(zhǎng)度為m、n的兩個(gè)序列，該算法使用p個(gè)處理機(jī)可以在O(mn/p)時(shí)間完成序列的比對(duì)計(jì)算，這里，p滿足1≤p≤max{m,n}。該算

3、法允許通過(guò)對(duì)p的選取來(lái)調(diào)節(jié)處理機(jī)的個(gè)數(shù)和時(shí)間復(fù)雜度，使得算法不僅在計(jì)算時(shí)間上達(dá)到最優(yōu)，而且具有很好的可擴(kuò)放性。 由于生物序列較長(zhǎng)，求解序列比對(duì)特別是多重序列比對(duì)的計(jì)算復(fù)雜度較高?？梢宰C明，即使對(duì)于最簡(jiǎn)單的計(jì)分函數(shù)，尋找最優(yōu)的多重序列比對(duì)也是一個(gè)NP-完全問(wèn)題。在實(shí)際計(jì)算中不太可能用精確的算法求得多重序列的準(zhǔn)確比對(duì)，而只能用啟發(fā)式的算法在合理的時(shí)間內(nèi)求得近似解。本文研究了對(duì)生物序列如何用啟發(fā)式的算法，在綜合考慮解的正確性以及計(jì)算速

4、度兩方面因素的前提下，求得質(zhì)量較高的多序列比對(duì)。 我們?cè)O(shè)計(jì)了多重序列比對(duì)的蟻群求解算法Ant-Align，利用人工螞蟻逐個(gè)選擇各個(gè)序列中的字符進(jìn)行配對(duì)。在算法中，螞蟻根據(jù)信息素、字符匹配得分以及位置偏差等信息決定選擇各序列中的字符的概率，通過(guò)信息素的更新與調(diào)節(jié)相結(jié)合的策略，以及參數(shù)的動(dòng)態(tài)自適應(yīng)調(diào)節(jié)方法，有效的解決了局部收斂的問(wèn)題，加強(qiáng)了算法尋求全局最優(yōu)解的能力。 針對(duì)Ant-Align算法在比對(duì)較長(zhǎng)序列時(shí)正確性下降的問(wèn)題

5、，我們?cè)O(shè)計(jì)了基于分治策略的多序列比對(duì)蟻群求解算法Divide-Ant-MSA，首先將長(zhǎng)序列分段成為短序列，對(duì)于分段后的序列再用Ant-Align算法分別進(jìn)行求解，然后將各段的比對(duì)結(jié)果進(jìn)行拼接。與Ant-Align相比，Divide-Ant-MSA不但收斂速度加快，而且解的質(zhì)量也得到進(jìn)一步改善。 在所有多重序列比對(duì)算法中，漸進(jìn)比對(duì)方法應(yīng)用最為廣泛。但是，漸進(jìn)方法最大的缺點(diǎn)是在早期階段形成的錯(cuò)誤不能在后期的計(jì)算中糾正過(guò)來(lái)。針對(duì)這個(gè)問(wèn)