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

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

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

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

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

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