生物信息學期末考試重點

1、第一講生物信息學（Bioinformatics）是20世紀80年代末隨著人類基因組計劃的啟動而興起的一門新型交叉學科，它體現(xiàn)了生物學、計算機科學、數(shù)學、物理學等學科間的滲透與融合。生物信息學通過對生物學實驗數(shù)據(jù)的獲取、加工、存儲、檢索與分析，達到揭示數(shù)據(jù)所蘊含的生物學意義從而解讀生命活動規(guī)律的目的。生物信息學不僅是一門學科，更是一種重要的研究開發(fā)平臺與工具，是今后進行幾乎所有生命科學研究的推手。生物技術(shù)與生物信息學的區(qū)別及聯(lián)系生物技術(shù)生物信息學英文名稱BiotechnologyBioinformatics最終目的產(chǎn)品研究方法利用生物的特性和功能，設(shè)計構(gòu)建具有預(yù)期功能的新物質(zhì)或品系對生物信息進行

2、采集、處理、存儲、分析和解釋涉及學科基因工程、分子生物學、生物化學、遺傳學、細胞生物學、胚胎學、免疫學等生物學、計算機科學、數(shù)學、物理學等發(fā)展歷程可追溯到 2000 B.C.數(shù)十年生物信息學的發(fā)展歷史 人類基因組計劃（HGP） 人類基因組計劃由美國科學家于1985年提出，1990年啟動。根據(jù)該計劃，在2015年要把人體約4萬個基因的密碼全部揭開，同時繪制出人類基因的譜圖，也就是說，要揭開組成人體4萬個基因的30億個堿基對的秘密。HGP與曼哈頓原子彈計劃和阿波羅計劃并稱為三大科學計劃，被譽為生命科學的登月計劃。(百度百科)隨著基因組計劃的不斷發(fā)展，海量的生物學數(shù)據(jù)必須通過生物信息學的手段進行收集

3、、分析和整理后，才能成為有用的信息和知識。換句話說，人類基因組計劃為生物信息學提供了興盛的契機。上文所說的基因、堿基對、遺傳密碼子等術(shù)語都是生物信息學需要著重研究的地方。第二講 回顧細胞結(jié)構(gòu)細胞是所有生命形式結(jié)構(gòu)和功能的基本單位細胞組成細胞膜 主要由脂類和蛋白質(zhì)組成的環(huán)繞在細胞表面的雙層膜結(jié)構(gòu)細胞質(zhì) 細胞膜與細胞核之間的區(qū)域：包含液體流質(zhì)，夾雜物存儲的營養(yǎng)、分泌物、天然色素和細胞器細胞器 細胞內(nèi)完成特定功能的結(jié)構(gòu)：線粒體、核糖體、高爾基體、溶酶體等細胞核 最大的細胞器DNA的結(jié)構(gòu)堿基 （腺嘌呤A、鳥嘌呤G、胞嘧啶C、胸腺嘧啶G）核苷酸核苷酸是構(gòu)成DNA分子的重要模塊。每個核苷酸分子由一分子稱作

4、脫氧核糖的戊糖（五碳糖）、一分子磷酸和一分子堿基構(gòu)成。每種核苷酸都有一個堿基對，也就是A、T、C、G基因是什么基因是遺傳物質(zhì)的基本單位基因就是核苷酸序列。大部分的基因大約是1000-4000個核苷酸那么長?；蛲ㄟ^控制蛋白質(zhì)的合成，從微觀和宏觀上影響細胞、組織和器官的產(chǎn)生。基因在染色體上。第四講 數(shù)據(jù)結(jié)構(gòu)及其對應(yīng)算法數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)探討的是在計算機中如何有效地存放數(shù)據(jù)，使其可以方便地被處理 二維數(shù)組 鏈表 棧和隊列第五講 序列比較序列比較的根本任務(wù)是：1. 發(fā)現(xiàn)序列之間的相似性2. 辨別序列之間的差異目的：相似序列 相似的結(jié)構(gòu)，相似的功能 判別序列之間的同源性推測序列之間的進化關(guān)系 序列

5、對比定義:序列對比(sequence alignment)是運用某種特定的數(shù)學模型或算法，找出兩個或多個序列之間的最大匹配堿基或殘基數(shù)，比對的結(jié)果反映了算法在多大程度上提供序列之間的相似性關(guān)系及他們的生物學特征。編輯距離.AGCACAC-A. A-CACACTA.-Match（a，a）字符匹配-Delete（a，-） 從第一條序列刪除一個字符，或者在第二條序列相應(yīng)的位置插入空位 -Replace（a，b）以第二條序列中的字符b替換第一條序列中的字符a, a不等于b-Insert（-，b）在第一條序列插入空位符，或者刪除第二條序列中的對應(yīng)字符b編輯距離，又稱Levenshtein距離，是指在對于

6、兩個字符串，由其中一個轉(zhuǎn)換成另一個所需要的最少編輯次數(shù)，該編輯可以是 Replace, Delete,InsertBesting BeatenS1. Replace (s - a )S2. Replace (i - e ) S3. Delete (g - -)S3. Insert(-,g)問題：把一個字符串s1最少經(jīng)過多少步操作變成字符串s2？相關(guān)算法 遞歸函數(shù)調(diào)用自身，需要有邊界函數(shù)n! = n(n-1)(n-2).1;f(n) = f(n-1)+f(n-2) 動態(tài)規(guī)劃 （最長公共字符子序列）將大問題分解為一系列子問題，每個子問題的解保存在數(shù)組中用來求最終解問題描述 字符序列的子序列是指從給

7、定字符序列中隨意地（不一定連續(xù)）去掉若干個字符（可能一個也不去掉）后所形成的字符序列。令給定的字符序列X=“x0，x1，xm-1”，序列Y=“y0，y1，yk-1”是X的子序列，存在X的一個嚴格遞增下標序列，使得對所有的j=0，1，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一個子序列。最長公共字符子序列A=“a0，a1，am-1”；B=“b0，b1，bm-1”；Z=“z0，z1，zk-1”為它們的最長公共子序列，那么關(guān)于A,B,Z應(yīng)該有如下性質(zhì)：1） 如果am-1=bn-1，則zk-1=am-1=bn-1，且“z0，z1，zk-2”是“a0，a1，am-2”和

8、“b0，b1，bn-2”的一個最長公共子序列； 2） 如果am-1!=bn-1，則若zk-1!=am-1，蘊涵“z0，z1，zk-1”是“a0，a1，am-2”和“b0，b1，bn-1”的一個最長公共子序列； 3）如果am-1!=bn-1，則若zk-1!=bn-1，蘊涵“z0，z1，zk-1”是“a0，a1，am-1”和“b0，b1，bn-2”的一個最長公共子序列。 最長公共字符子序列現(xiàn)有兩個序列X=x1,x2,x3，.xi，Y=y1,y2,y3，.，yj，設(shè)一個Ci,j: 保存Xi與Yj的LCS的長度。第六講編輯距離問題算法 if i = 0 且 j = 0，matrix(i, j) = 0

9、 if i = 0 且 j 0，matrix(i, j) = j if i 0 且j = 0，matrix(i, j) = i ifi 1 且j 1 ，matrix(i, j) = min matrix(i-1, j) + 1, matrix(i, j-1) + 1, matrix(i-1, j-1) + f(i, j) ，當?shù)谝粋€字符串的第i個字符不等于第二個字符串的第j個字符時，f(i, j) = 1；否則，f(i, j) = 0。第八講全局序列比對算法Levenshtein 與 LCS 的異同點 Si-1,j-1 + cost(ai,bj) cost = 0 | 1Si,j = minS

10、i-1,j+cost(ai,-) delete (i,-) Si,j-1+cost(-,bj) delete (j,-)算法DemoABBA 01234B 11123B 22112A 32221第九講 生物信息學的計算機、統(tǒng)計學及數(shù)學基礎(chǔ)生物信息學的定義：生物信息學是生物學與計算機科學以及應(yīng)用數(shù)學等學科相互交叉而形成的一門新興學科。因此，計算機技術(shù)將是進行生物信息學研究的重要手段;而數(shù)學知識是研究的重要方法。 目前，一般提到的 生物信息學 是就指這個狹義的概念，更準確地說，應(yīng)該是分子生物信息學（Molecular Bioinformatics）。 2、動態(tài)規(guī)劃方法動態(tài)規(guī)劃（Dynamic Pr

11、ogramming）是一種解決多階段決策過程的最優(yōu)化方法或復(fù)雜空間的優(yōu)化搜索方法動態(tài)規(guī)劃解決問題的基本過程是：將一個問題的全局解分解為局部解，逆序遞推求出局部最優(yōu)解，隨著執(zhí)行過程的推進，“局部”逐漸接近“全局”，最終獲得全局最優(yōu)解 在生物信息學中，使用得最多的是反向傳播神經(jīng)網(wǎng)絡(luò)（Back Propagation Neural Network，簡稱BP網(wǎng)）。專家系統(tǒng)專家系統(tǒng)（Expert System）是一種基于知識的智能系統(tǒng)，它將領(lǐng)域?qū)＜业慕?jīng)驗用一定的知識表示方法表示出來，并放入知識庫中，供推理機使用 知識庫是專家系統(tǒng)的第一重要組成部分，知識庫中的知識通常分為兩類：1. 一類領(lǐng)域的事實性知識或

12、廣泛公用的知識2. 另一類是啟發(fā)性知識，是該領(lǐng)域?qū)＜以陂L期研究和實踐過程中積累起來的經(jīng)驗總結(jié)知識獲取方式大致上可以分為兩種：一種是由知識工程師向領(lǐng)域?qū)＜以儐栍嘘P(guān)知識，經(jīng)過整理編輯后將知識轉(zhuǎn)換成計算機表示形式，送入知識庫另一種是針對大量數(shù)據(jù)進行機器學習，分析、總結(jié)和抽取出有用的新知識，這是更高層次的知識獲取方式。 專家系統(tǒng)的另一個重要部分是推理機，由它來控制和協(xié)調(diào)整個系統(tǒng)，并根椐當前輸入的數(shù)據(jù)和知識，按一定的推理策略，去解決當前的問題，推導出結(jié)論。第十講 數(shù)據(jù)挖掘數(shù)據(jù)挖掘（定義）從技術(shù)層面上：數(shù)據(jù)挖掘就是從大量數(shù)據(jù)中提取有用信息的過程 從商業(yè)層面上：數(shù)據(jù)挖掘就是一種商業(yè)信息處理技術(shù)，通過對大量業(yè)

13、務(wù)數(shù)據(jù)進行抽取、轉(zhuǎn)換、分析和建模處理，從中提取輔助商業(yè)決策的關(guān)鍵性數(shù)據(jù)數(shù)據(jù)挖掘（任務(wù)）分類分析（Classification）通過分析示例數(shù)據(jù)庫中的數(shù)據(jù)，為每個類別做出準確的描述或建立分析模型產(chǎn)生分類規(guī)則，然后用這個模型或規(guī)則對數(shù)據(jù)庫中的其他記錄進行分類。已被廣泛應(yīng)用于用戶行為分析、生物科學等領(lǐng)域。 聚類分析（Clustering）聚類和分類是兩個容易混淆的概念。聚類是一種無指導的觀察式學習，沒有預(yù)先定義的類。而分類問題是有指導的示例式學習，預(yù)先定義類。分類是訓練樣本里包含有分類屬性值，而聚類是要在訓練樣本中發(fā)現(xiàn)這些分類屬性值。第十一講 動態(tài)規(guī)劃矩陣相乘只有當矩陣A的列數(shù)與矩陣B的行數(shù)相等時A

14、B才有意義。一個mn的矩陣a(m,n)左乘一個np的矩陣b(n,p)，會得到一個mp的矩陣c(m,p) 共計算 2 * 3 * 4 = 24次動態(tài)規(guī)劃算法 確定要用動態(tài)規(guī)劃算法之后如何去分析問題 怎么描述問題，要把問題描述為交疊的子問題 交疊子問題的初始條件（邊界條件） 動態(tài)規(guī)劃在形式上往往表現(xiàn)為填矩陣的形式回顧編輯距離 或者 LCS算法，以上三點也都在我們的分析中體現(xiàn)背包問題背包問題簡述問題：如何在不超出背包重量的前提下得到最大價值？思考解決問題的結(jié)構(gòu)，尋找最優(yōu)子結(jié)構(gòu)Item a1,a2,a3W: 5,3,2 P : 9,7,8MaxWeight: 5W: 5,3,2P : 9,7,8Max

15、Weight: 5問題：一共要計算多少種可能性？核心算法cim=maxci-1m,ci-1m-wi+pi第十四講 信息可視化技術(shù)背景計算機圖形學的產(chǎn)生和發(fā)展為可視化的誕生奠定基礎(chǔ)1987年正式將可視化分為：數(shù)據(jù)可視化、信息可視化、科學可視化數(shù)據(jù)可視化將數(shù)據(jù)以圖像的形式呈現(xiàn)出來數(shù)據(jù)可視化主要旨在借助于圖形化手段，清晰有效地傳達與溝通信息。數(shù)據(jù)可視化是關(guān)于數(shù)據(jù)之視覺表現(xiàn)形式的研究；其中，這種數(shù)據(jù)的視覺表現(xiàn)形式被定義為一種以某種概要形式抽提出來的信息，包括相應(yīng)信息單位的各種屬性和變量。 數(shù)據(jù)可視化技術(shù)的基本思想是將數(shù)據(jù)庫中每一個數(shù)據(jù)項作為單個圖元元素表示，大量的數(shù)據(jù)集構(gòu)成數(shù)據(jù)圖像，同時將數(shù)據(jù)的各個屬性值以多維數(shù)據(jù)的形式表示，可以從不同的維度觀察數(shù)據(jù)，從而對數(shù)據(jù)進行更深入的觀察和分析。 基本概念及構(gòu)成元素 數(shù)據(jù)空間：由n維屬性和m個元素組成的數(shù)據(jù)集所構(gòu)成的多維信息空間 數(shù)據(jù)開發(fā)：利用一定的算法和工具對數(shù)據(jù)進行定量的推演和計算 數(shù)據(jù)分析：指對多維數(shù)據(jù)進行切片、塊、旋轉(zhuǎn)等動作剖析數(shù)據(jù)，從而能多角度多側(cè)面觀察數(shù)據(jù) 數(shù)據(jù)可視化：指將大型數(shù)據(jù)集中的數(shù)據(jù)以圖形圖像