計(jì)算機(jī)算法在生物信息學(xué)中的應(yīng)用綜述

劉奇付　李靜靜

摘 要：在人類基因組計(jì)劃的推動(dòng)下，生物信息學(xué)得到了人們的廣泛關(guān)注，并呈現(xiàn)出數(shù)量多、計(jì)算量大等鮮明特征，因此要求在生物信息學(xué)中采用計(jì)算機(jī)算法，以提高生物信息學(xué)處理問題的效率。以生物信息學(xué)中常用的計(jì)算機(jī)算法為切入點(diǎn)，進(jìn)一步從基因表達(dá)數(shù)據(jù)分析、基因組序列信息分析、生物序列差異和相似性分析、遺傳數(shù)據(jù)分析以及蛋白質(zhì)結(jié)構(gòu)與功能預(yù)測5個(gè)方面，論述了計(jì)算機(jī)算法在生物信息學(xué)中的典型應(yīng)用。

關(guān)鍵詞：生物信息學(xué)；基因；計(jì)算機(jī)算法；數(shù)據(jù)分析

DOI：10.11907/rjdk.171382

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2017）009-0209-03

Abstract：In the human genome project， the bioinformatics has been widely concerned by the broad masses of bioinformatics scholars， and has the characteristics of large quantity and large computational complexity. This requires that the computer science algorithm should be used in bioinformatics ， In order to improve the efficiency of bioinformatics processing problems. In this paper， the computer algorithm used in bioinformatics as the starting point， and further from the analysis of gene expression data， genome sequence information， biological sequence differences and similarity， genetic data and predict the structure and function of protein five aspects， discusses the computer algorithm A typical application in bioinformatics for discussion.

Key Words：bioinformatics； gene； computer algorithm； data analysis

0 引言

生物信息學(xué)（Bioinformatics）作為一門新興的交叉學(xué)科，是隨著生命科學(xué)和計(jì)算機(jī)科學(xué)的高速發(fā)展而出現(xiàn)的。它通過充分利用生物學(xué)、信息學(xué)、數(shù)學(xué)、物理學(xué)、統(tǒng)計(jì)學(xué)以及計(jì)算機(jī)網(wǎng)絡(luò)等工具或手段，對大量生物數(shù)據(jù)信息進(jìn)行有效的闡明和分析，使之成為具有相應(yīng)生物意義的生物數(shù)據(jù)信息。其涵蓋了基因組信息的獲取、處理、分配、存儲等多個(gè)方面，通過對生物信息的比較和分析，從而獲取基因編碼以及核酸和蛋白質(zhì)結(jié)構(gòu)功能等信息，是最具活力和發(fā)展前景的學(xué)科之一。然而，生物信息學(xué)在我國由于起步較晚，加之其自身呈現(xiàn)出的數(shù)量多、計(jì)算量大等特征，使生物信息學(xué)面臨著計(jì)算瓶頸?；诖耍P者結(jié)合自己的工作實(shí)踐，對計(jì)算機(jī)算法在生物信息學(xué)中的應(yīng)用進(jìn)行探討，以期為在生物信息學(xué)中進(jìn)行有效的數(shù)據(jù)挖掘提供理論支持。

1 生物信息學(xué)中常用的計(jì)算機(jī)算法

算法作為計(jì)算機(jī)科學(xué)的一個(gè)重要分支，在計(jì)算機(jī)科學(xué)中居于核心地位。在信息時(shí)代，算法作為解決問題的重要工具之一，其通過輸入符合規(guī)范的信息，從而在短時(shí)間內(nèi)快速獲取所需要的輸出，現(xiàn)已在各個(gè)領(lǐng)域得到了廣泛應(yīng)用。在生物信息學(xué)中，計(jì)算機(jī)算法的應(yīng)用也對生物信息學(xué)的發(fā)展起著積極推動(dòng)作用。生物信息學(xué)中常用的計(jì)算機(jī)算法主要包括以下幾種：

（1）分治法。分治法即在解決大的問題實(shí)例時(shí)，通過將該問題實(shí)例分解為具有相同問題的幾個(gè)小的問題實(shí)例，再采用遞歸方法依次對這些小的問題實(shí)例求解，然后將所得的解合并，從而得出大的問題實(shí)例的解。分治法主要應(yīng)用于合并排序、最近對和凸包問題等領(lǐng)域。而在生物信息學(xué)中，可以通過分治法來分析處理序列比對以及序列聯(lián)配等問題。其中，序列比對在生物學(xué)中是最為常見的問題之一，通過PSW-DC算法、生物序列比對算法，在分而治之方法理念的指導(dǎo)下，將Query序列劃分成幾個(gè)片段，再分配給對應(yīng)的處理器，然后并行地按照Smith-Waterman算法和目標(biāo)序列進(jìn)行對比，最終根據(jù)相應(yīng)規(guī)則的擴(kuò)展過程得到最優(yōu)化的序列匹配[1]。

（2）圖算法。圖算法指通過特制的線條算圖求得問題實(shí)例解的一種便捷算法。圖作為一種非線性結(jié)構(gòu)，極具復(fù)雜性。因此，圖算法無論是在工程、人工智能、數(shù)學(xué)領(lǐng)域，還是在生物信息學(xué)、計(jì)算機(jī)科學(xué)領(lǐng)域均得到了廣泛應(yīng)用。其中，在生物信息學(xué)中，運(yùn)用圖算法能夠解決很多生物信息學(xué)問題，例如：DNA測序、蛋白質(zhì)測序等。

（3）貪婪算法。貪婪算法指在一定標(biāo)準(zhǔn)下，通過制定一系列步驟構(gòu)造問題實(shí)例的解，并從眾多解中選取局部最優(yōu)的一個(gè)。選取不具有撤銷性，因而依此選取直至全局達(dá)到最優(yōu)。在生物信息學(xué)中，貪婪算法主要應(yīng)用于解決基因組重排、反序排列等問題[2]。該算法在生物信息學(xué)中的應(yīng)用不僅能夠使問題得到最優(yōu)解，而且具有較高的運(yùn)算速度，是一種有效且可行的計(jì)算機(jī)算法。

（4）動(dòng)態(tài)規(guī)劃算法。動(dòng)態(tài)規(guī)劃算法是指將大的問題實(shí)例分解為若干小的、類似的、交錯(cuò)的子問題實(shí)例，通過從下到上的遞推方式求得最優(yōu)值，并將子問題實(shí)例的解進(jìn)行有效存儲，防止重復(fù)計(jì)算子問題，從而得到問題最優(yōu)解決方案的一種算法策略。將動(dòng)態(tài)規(guī)劃算法運(yùn)用到生物信息學(xué)中，能夠有效地分析并處理數(shù)據(jù)之間的重疊性以及相關(guān)性等特點(diǎn)，因此主要應(yīng)用于DNA序列比較、局部及全局序列聯(lián)配、多重聯(lián)配、基因預(yù)測及填充表達(dá)缺失數(shù)據(jù)等問題中[3]。endprint

2 計(jì)算機(jī)算法在生物信息學(xué)中的典型應(yīng)用

2.1 基因表達(dá)數(shù)據(jù)分析

基因表達(dá)數(shù)據(jù)分析一直是生物信息學(xué)研究的熱點(diǎn)和難點(diǎn)。在當(dāng)今的工作實(shí)踐中，往往采用計(jì)算機(jī)算法中的聚類分析對基因表達(dá)數(shù)據(jù)進(jìn)行分析處理，通過把表達(dá)規(guī)律相近的基因聚成一類，從而找出相互之間有關(guān)聯(lián)的基因，并分析基因功能。計(jì)算機(jī)算法可以通過基因的轉(zhuǎn)錄調(diào)節(jié)網(wǎng)絡(luò)，觀察基因的表達(dá)模式隨環(huán)境變化或在藥物作用下作出的相應(yīng)改變，闡明基因相互間的調(diào)節(jié)作用，并對基因的啟動(dòng)子加以研究，分析具有相同表達(dá)模式的同類啟動(dòng)子的組成特性。計(jì)算機(jī)算法中的聚類分析作為分析基因表達(dá)數(shù)據(jù)的重要方法之一，不僅能夠發(fā)現(xiàn)基因間的線性關(guān)系，而且能夠找出基因間的非線性關(guān)系，因而逐步得到廣大研究者的認(rèn)可[4]。

2.2 基因組序列信息分析

生物信息學(xué)中的基因組序列并不是基因的簡單排列，而是具有特定的組織和信息結(jié)構(gòu)，并經(jīng)過長期演化形成的結(jié)果，是基因充分發(fā)揮其應(yīng)有功能所必需的基礎(chǔ)條件之一。利用計(jì)算機(jī)算法對基因組序列信息進(jìn)行分析，并預(yù)測相關(guān)功能位點(diǎn)是近年來的主要研究方向之一。分析基因組序列信息通常采用從頭算法和比較同源列法兩大類。其中，從頭算法是基于統(tǒng)計(jì)學(xué)的方法，它是指通過識別蛋白質(zhì)編碼基因的性質(zhì)及特征，對外顯子、內(nèi)含子和基因間的區(qū)域進(jìn)行有效區(qū)分；而比較同源列法則是通過將基因信息與數(shù)據(jù)庫中的基因信息進(jìn)行同源比較，從而找出新基因。在新的DNA序列中，一般除基因外，還包含許多與核酸結(jié)構(gòu)特征有關(guān)聯(lián)的其它信息，這些信息對DNA與蛋白質(zhì)或RNA之間的相互作用具有決定性影響，而運(yùn)用計(jì)算機(jī)算法搜索與已知蛋白質(zhì)、表達(dá)序列標(biāo)簽相似的區(qū)域，并對其進(jìn)行編碼，是生物信息學(xué)中分析基因組序列信息最為理想的算法之一。

2.3 生物序列差異與相似性分析

在生物信息學(xué)中，分析生物序列的差異和相似性是最基本且重要的操作之一，通過對生物序列差異和相似性的分析比較，能夠及時(shí)得到生物序列中的結(jié)構(gòu)、功能以及進(jìn)化等方面信息。一般而言，結(jié)構(gòu)、功能和生物序列間呈現(xiàn)出相互制約的關(guān)系，結(jié)構(gòu)由生物序列決定，而功能又由結(jié)構(gòu)決定。在分析生物序列差異和相似性中采用計(jì)算機(jī)算法，能夠快速達(dá)到研究目的。其中，目的之一即通過生物序列之間的相似性，發(fā)現(xiàn)相似的結(jié)構(gòu)及功能。當(dāng)然也有特殊情況，例如：幾乎沒有任何相似之處的生物序列，不僅分子構(gòu)成的空間形狀相同，而且功能也相同；目的之二即通過對比生物序列之間的相似性，對生物序列間的同源性進(jìn)行判斷，并依此推斷生物序列間的進(jìn)化關(guān)系。在分析生物序列的差異和相似性的過程中，常用的計(jì)算機(jī)算法主要為Needleman-Wunsch動(dòng)態(tài)規(guī)劃算法、Smith-Waterman算法以及支持向量機(jī)算法等。

2.4 遺傳數(shù)據(jù)分析

在生物信息學(xué)研究中，由于基因結(jié)構(gòu)、組序列信息以及生物序列的復(fù)雜性，要求在對遺傳數(shù)據(jù)信息的分析過程中運(yùn)用計(jì)算機(jī)算法。具體而言，可以借用一些可視化工具，將基因以圖、樹、鏈和方體等形式表現(xiàn)出來，從而提高相關(guān)工作人員對基因信息以及基因模式的理解。而知識發(fā)現(xiàn)作為發(fā)現(xiàn)遺傳數(shù)據(jù)最有力的可視化工具之一，能夠?qū)z傳數(shù)據(jù)進(jìn)行充分挖掘，對轉(zhuǎn)錄調(diào)控基因組水平也能起到積極影響。

2.5 蛋白質(zhì)結(jié)構(gòu)與功能預(yù)測

蛋白質(zhì)的生物功能是由蛋白質(zhì)結(jié)構(gòu)決定的，因此在生物信息學(xué)中對蛋白質(zhì)進(jìn)行研究時(shí)，應(yīng)當(dāng)首先了解蛋白質(zhì)結(jié)構(gòu)。隨著現(xiàn)代科技的進(jìn)步，預(yù)測蛋白質(zhì)結(jié)構(gòu)與功能的方法和手段均有了很大進(jìn)步，但在具體操作過程中依然遠(yuǎn)遠(yuǎn)滿足不了實(shí)際需要，這從一定程度上為計(jì)算機(jī)算法的推廣應(yīng)用提供了契機(jī)。將計(jì)算機(jī)算法運(yùn)用于蛋白質(zhì)結(jié)構(gòu)與功能預(yù)測中，不僅對研究蛋白質(zhì)結(jié)構(gòu)與功能間的相互關(guān)系起著至關(guān)重要的作用，而且對蛋白質(zhì)工程以及蛋白質(zhì)設(shè)計(jì)的進(jìn)展能起到積極促進(jìn)作用。通常而言，預(yù)測蛋白質(zhì)結(jié)構(gòu)主要包括對蛋白質(zhì)二級結(jié)構(gòu)以及空間結(jié)構(gòu)進(jìn)行預(yù)測。其中，二級結(jié)構(gòu)預(yù)測屬于模式識別問題，通過運(yùn)用計(jì)算機(jī)算法能夠有效判斷氨基酸殘基形狀，而在空間結(jié)構(gòu)預(yù)測時(shí)采用計(jì)算機(jī)算法，能夠以蛋白質(zhì)序列為出發(fā)點(diǎn)，判斷亞細(xì)胞定位、糖基化位點(diǎn)、信號肽剪切位點(diǎn)等與蛋白質(zhì)功能有關(guān)的特征。

3 研究展望

隨著生物信息學(xué)的發(fā)展，我國專家學(xué)者對生物信息學(xué)的重視程度不斷提高，而計(jì)算機(jī)算法的推廣應(yīng)用也在一定程度上為生物信息學(xué)的發(fā)展提供了新的契機(jī)。但從生物信息學(xué)的總體發(fā)展情況來看，仍和國際水平有很大差距，需要在未來研究中特別注意如下兩方面問題：

（1）專業(yè)人才培養(yǎng)。生物信息學(xué)作為一門新興學(xué)科，要求相關(guān)從業(yè)人員既要具備扎實(shí)的生物學(xué)知識，又要具有較高水平的計(jì)算機(jī)學(xué)科技能，但縱觀我國生物信息學(xué)的從業(yè)人員現(xiàn)狀，存在著嚴(yán)重的人才斷層及人才匱乏現(xiàn)象，從而對計(jì)算機(jī)算法在生物信息學(xué)中的應(yīng)用產(chǎn)生了一定制約。因此，要求在后期的研究過程中，注重專業(yè)人才的培養(yǎng)，有效解決人才匱乏的現(xiàn)狀，為計(jì)算機(jī)算法在生物信息學(xué)中的應(yīng)用提供強(qiáng)大的人才支持。

（2）計(jì)算機(jī)算法應(yīng)用范圍拓展。隨著人類基因組計(jì)劃的啟動(dòng)以及計(jì)算機(jī)科學(xué)水平的提高，計(jì)算機(jī)算法在生物信息學(xué)中的應(yīng)用已取得了初步進(jìn)展，在分析基因表達(dá)數(shù)據(jù)、基因組序列信息、生物序列差異和相似性、遺傳數(shù)據(jù)，以及預(yù)測蛋白質(zhì)結(jié)構(gòu)與功能等方面發(fā)揮了重大作用。但生物信息學(xué)包含的內(nèi)容極其豐富，因此要求在后期的研究過程中，應(yīng)當(dāng)有計(jì)劃地?cái)U(kuò)大計(jì)算機(jī)算法在生物信息學(xué)中的應(yīng)用范圍，使計(jì)算機(jī)算法的價(jià)值得到最大限度的發(fā)揮，為生物信息學(xué)研究的有效開展提供強(qiáng)有力的技術(shù)支持。

4 結(jié)語

生物信息學(xué)作為一門生物學(xué)與計(jì)算機(jī)科學(xué)交叉融合的新興學(xué)科，其核心是生物學(xué)，基本工具則是計(jì)算機(jī)科學(xué)。因此，要求生物信息學(xué)相關(guān)研究人員在工作實(shí)踐中，加強(qiáng)各學(xué)科之間的溝通、合作，充分把握計(jì)算機(jī)算法在生物信息學(xué)中的應(yīng)用，從而解決生物信息學(xué)中信息數(shù)量多、計(jì)算量大等問題，推動(dòng)生物信息學(xué)的進(jìn)一步發(fā)展。

參考文獻(xiàn)：

[1] 于嘯，孟繁疆.數(shù)據(jù)挖掘技術(shù)在生物信息學(xué)中的應(yīng)用[J].農(nóng)機(jī)化研究，2009（3）：186-188.

[2] 趙磊，劉利軍，黃青松.計(jì)算機(jī)算法在生物信息學(xué)中的應(yīng)用[J].化學(xué)與生物工程，2009，26（9）：79-81.

[3] 黃元南，王建新，陳建二.數(shù)據(jù)挖掘技術(shù)在生物信息學(xué)中的應(yīng)用探索[J].電腦知識與技術(shù)，2006（9）：1-11.

[4] 莊麗艷，董紅斌.進(jìn)化計(jì)算在生物信息學(xué)中的應(yīng)用[J].哈爾濱師范大學(xué)自然科學(xué)學(xué)報(bào)，2007，23（1）：60-63.

（責(zé)任編輯：黃 ?。〆ndprint